Now I am able to find a path between two rooms. This is done via the gdx-ai A* algorithm. Adding pathfinding support was really easy. I used the IndexedAStarPathFinder implementation from gdx-ai. Thanks to this, I only had to implement some little interfaces.
IndexedAStarPathFinder
First of all the IndexedAStarPathFinder needs an IndexedGraph. This graph consists of several IndexedNodes. Nodes are connected via Connections. The pathfinder will use the graph to find a path between any two nodes, if such a path exists. The pathfinder also needs a Heuristic. The purpose of the heuristic function is to return an estimate of the distance between two nodes. This is useful, because the pathfinder will check the nodes with a small estimated cost first.
IndexedNode
The graph will consist of several nodes. In my case each node will be a Room object. So I let the Room class implement the IndexedNode interface.
public interface IndexedNode<N extends IndexedNode<N>> {
public int getIndex ();
public Array<Connection<N>> getConnections ();
}
The index is easy, whenever I add a new room to the world, it will get the next free number, resulting in a consecutive order. getConnections must return an Array of Connections. To do so, my Connector class must implement the Connection interface.
public interface Connection<N> {
public float getCost ();
public N getFromNode ();
public N getToNode ();
}
The only thing missing in the Connector class is the getCost function. For simplicity I use the size of the room as the cost.
IndexedGraph
Now I have Connections and Nodes, the next missing piece is the Graph itself.
There exists a default implementation for IndexedGraphs, called DefaultIndexedGraph. This graph consists of an Array of nodes and will work perfectly, but there is a small thing that bothered me:
public Array<Connection<N>> getConnections (N fromNode) {
return nodes.get(fromNode.getIndex()).getConnections();
}
So what's the problem? Well, nodes is an Array and getIndex will return the index of that node inside the nodes array. So the whole function call will just return the fromNode we already have! Basically we could just write this:
public Array<Connection<N>> getConnections (N fromNode) {
return fromNode.getConnections();
}
In my case, I already have a GameWorld which has an array of rooms, so I let it implement the IndexedGraph interface and that's really easy:
public class GameWorld implements IndexedGraph<Room> {
// ...
@Override
public int getNodeCount() {
return rooms.size;
}
@Override
public Array<Connection<Room>> getConnections(Room fromNode) {
return fromNode.getConnections();
}
}
Heuristic
The last missing piece of the puzzle is the heuristic function. To make it really simple, I only implemented a heuristic using euclidean distance.
public class EuclideanHeuristic implements Heuristic<Room> {
public static final EuclideanHeuristic instance = new EuclideanHeuristic();
private EuclideanHeuristic() {}
@Override
public float estimate(Room node, Room endNode) {
return endNode.getCenter().sub(node.getCenter()).len();
}
}
The heuristic itself doesn't contain any attributes, because of that it wouldn't make much sense to have different instances of it, so I added a static singleton instance.
And that's all, now I have a working pathfinding algorithm. Thanks gdx-ai!