A * Pathfinding - Java, Slick2D library

Here's a simple example of how A-star pathfinding works in Slick2D. In a real game, you will probably have a more realistic implementation of an interface TileBasedMap

that actually looks for accessibility in whatever map structure your game uses. You can also refund various costs, for example, on a card.

import org.newdawn.slick.util.pathfinding.AStarPathFinder;
import org.newdawn.slick.util.pathfinding.Mover;
import org.newdawn.slick.util.pathfinding.Path;
import org.newdawn.slick.util.pathfinding.PathFindingContext;
import org.newdawn.slick.util.pathfinding.TileBasedMap;


public class AStarTest {

    private static final int MAX_PATH_LENGTH = 100;

    private static final int START_X = 1;
    private static final int START_Y = 1;

    private static final int GOAL_X = 1;
    private static final int GOAL_Y = 6;

    public static void main(String[] args) {

        SimpleMap map = new SimpleMap();

        AStarPathFinder pathFinder = new AStarPathFinder(map, MAX_PATH_LENGTH, false);
        Path path = pathFinder.findPath(null, START_X, START_Y, GOAL_X, GOAL_Y);

        int length = path.getLength();
        System.out.println("Found path of length: " + length + ".");

        for(int i = 0; i < length; i++) {
            System.out.println("Move to: " + path.getX(i) + "," + path.getY(i) + ".");
        }

    }

}

class SimpleMap implements TileBasedMap {
    private static final int WIDTH = 10;
    private static final int HEIGHT = 10;

    private static final int[][] MAP = {
        {1,1,1,1,1,1,1,1,1,1},
        {1,0,0,0,0,0,1,1,1,1},
        {1,0,1,1,1,0,1,1,1,1},
        {1,0,1,1,1,0,0,0,1,1},
        {1,0,0,0,1,1,1,0,1,1},
        {1,1,1,0,1,1,1,0,0,0},
        {1,0,1,0,0,0,0,0,1,0},
        {1,0,1,1,1,1,1,1,1,0},
        {1,0,0,0,0,0,0,0,0,0},
        {1,1,1,1,1,1,1,1,1,0}
    };

    @Override
    public boolean blocked(PathFindingContext ctx, int x, int y) {
        return MAP[y][x] != 0;
    }

    @Override
    public float getCost(PathFindingContext ctx, int x, int y) {
        return 1.0f;
    }

    @Override
    public int getHeightInTiles() {
        return HEIGHT;
    }

    @Override
    public int getWidthInTiles() {
        return WIDTH;
    }

    @Override
    public void pathFinderVisited(int x, int y) {}

}

      

        
        
        
      

    

In your game, you can also make your character class lookup path an implemented interface Mover

so that you can pass this as a user data object instead of null

in the call findPath

. This will make this object available from methods blocked

and cost

through ctx.getMover()

. So you might have some engines that ignore some, otherwise block, obstacles, etc. (Imagine a flying character or an amphibious vehicle that can move in water or higher, otherwise blocking walls.) Hopefully this gives the basic idea.

EDIT Now I noticed that you specifically indicated that you are using a class TiledMap

. This class does not implement an interface TileBasedMap

and cannot be directly used with Slick2D's A-Star implementation. (The default tiled map does not have any kind of blocking concept, which is key when doing pathfinding.) So you will have to implement this yourself using your own criteria for when the tiles are blocked or not and how much it should cost to cross them ...

EDIT 2

There are several ways to define the concept of tile interlocking. Below are some relative direct ways:

Separate blocking layer

In the Tiled map format, you can specify multiple layers. You can allocate one layer just for your blocking tiles, and then implement TileBasedMap

according to something like this:

class LayerBasedMap implements TileBasedMap {

    private TiledMap map;
    private int blockingLayerId;

    public LayerBasedMap(TiledMap map, int blockingLayerId) {
        this.map = map;
        this.blockingLayerId = blockingLayerId;
    }

    @Override
    public boolean blocked(PathFindingContext ctx, int x, int y) {
        return map.getTileId(x, y, blockingLayerId) != 0;
    }

    @Override
    public float getCost(PathFindingContext ctx, int x, int y) {
        return 1.0f;
    }

    @Override
    public int getHeightInTiles() {
        return map.getHeight();
    }

    @Override
    public int getWidthInTiles() {
        return map.getWidth();
    }

    @Override
    public void pathFinderVisited(int arg0, int arg1) {}

}

      

        
        
        
      

    

Locking based on tile properties

In the Tiled map format, each tile type can have optional custom properties. You can easily add a property blocking

to the tiles that need to be blocked and then test this in your implementation TileBasedMap

. For example:

class PropertyBasedMap implements TileBasedMap {

    private TiledMap map;
    private String blockingPropertyName;

    public PropertyBasedMap(TiledMap map, String blockingPropertyName) {
        this.map = map;
        this.blockingPropertyName = blockingPropertyName;
    }

    @Override
    public boolean blocked(PathFindingContext ctx, int x, int y) {
        // NOTE: Using getTileProperty like this is slow. You should instead cache the results. 
        // For example, set up a HashSet<Integer> that contains all of the blocking tile ids. 
        return map.getTileProperty(map.getTileId(x, y, 0), blockingPropertyName, "false").equals("true");
    }

    @Override
    public float getCost(PathFindingContext ctx, int x, int y) {
        return 1.0f;
    }

    @Override
    public int getHeightInTiles() {
        return map.getHeight();
    }

    @Override
    public int getWidthInTiles() {
        return map.getWidth();
    }

    @Override
    public void pathFinderVisited(int arg0, int arg1) {}

}

      

        
        
        
      

    

Other options

There are many other options. For example, instead of having a set level identifier as a blocking, you can set properties on the layer itself, which can indicate whether it is a blocking layer or not.

In addition, blocking and non-blocking tiles are included in all of the above examples. Of course, you can have both blocking and non-blocking objects on the map. You may also have other players or NPCs etc. that are blocking. All this will need to be processed in some way. This, however, has to start.