A* Pathfinding - Java, Slick2D Library

Question

So I use Slick2D and I am making a game. It has a TiledMap and entities (as any other game) and I want a way to use A*. I don't really know how to use it because I can't find an explanation.

Just for those who don't use Slick, it already has AStarPathFinding and TiledMap classes which I use.

Answer 1

Here is a simple example of how the A-star path finding in Slick2D works. In a real game you would probably have a more realistic implementation of the TileBasedMap interface which actually looks up the accessibility in whatever map structure your game uses. You may also return different costs based on for example your map terrain.

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 may also wish to make your path finding character class implement the Mover interface so that you can pass that as a user data object instead of null to the findPath call. This will make that object available from the blocked and cost methods through ctx.getMover(). That way you can have some movers that ignore some, otherwise blocking, obstacles etc. (Imagine a flying character or an amphibious vehicle that can move in water or above otherwise blocking walls.) I hope this gives a basic idea.

EDIT I now noticed that you mentioned specifically that you are using the TiledMap class. This class does not implement the TileBasedMap interface and cannot be directly used with the A-star implementation in Slick2D. (A Tiled map does not by default have any concept of blocking which is key when performing path finding.) Thus, you will have to implement this yourself, using your own criteria for when a tile is blocking or not and how much it should cost to traverse them.

EDIT 2

There are several ways that you could define the concept of a tile being blocking. A couple of relative straight forward ways are covered below:

Separate blocking layer

In the Tiled map format you can specify multiple layers. You could dedicate one layer for your blocking tiles only and then implement the 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) {}

}

Tile property based blocking

In the Tiled map format each tile type may optionally have user defined properties. You could easily add a blocking property to the tiles which are supposed to be blocking and then check for that in your TileBasedMap implementation. 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 layer id as blocking you could set properties for the layer itself that can indicate if it is a blocking layer or not.

Additionally, all of the above examples just take blocking vs. non-blocking tiles into consideration. Of course you may have blocking and non-blocking objects on the map as well. You could also have other players or NPCs etc. that are blocking. All of this would need to be handled somehow. This should however get you started.