A Better A* Interface

I have made my own A* framework around 2012. I still use the same code until now. It has been improved a lot of times already but one thing that didn’t change much is the interface. What I mean by ‘interface’ here is the collection of public classes, methods, and interfaces to access the framework. In this post, I’m showing how I did it. First, I’ll show you the method that executes the A* search:

public void ResolvePath(AStarPath<T> path, NodeHandle<T> start, NodeHandle<T> goal, HeuristicCostCalculator<T> calculator, Reachability<T> reachability = null) {
    ...
}

I’m no longer showing the code on how A* works. There are better resources about that else where. What I’m focusing here is the interface and why I did it that way.

First thing you’ll notice is I’m using a generic type variable. This is important because each game or problem domain has its own way of representing their positions be it tiles or waypoints. It also implies that the algorithm should work for any type of position.

Let’s discuss the parameters:

AStarPath<T> path – This is simply a custom class that contains the sequence of T items. It also stores whether the path is reachable or not. The method stores the A* search result in this object. It was done this way to prevent instantiating this class whenever an A* search is needed. The client code is required to maintain an instance of this class. The caller would then also use this class to traverse the path.

NodeHandle<T> start – The start node (self explanatory). NodeHandle has methods related to adding neighbors or connected nodes. Underneath, it is implemented as a graph node.

NodeHandle<T> goal – The goal node (self explanatory).

HeuristicCostCalculator<T> calculator – This is the cost calculator to use during algorithm execution. Will explain the details later. I provided this interface because different problem domains have different implementations of such calculation.

Reachability<T> reachability – Reachability is an interface that tells whether or not a tile is reachable or not. Will explain the details later. I provided such interface because there are instances where reachability differs in case to case basis. Reachability is optional because it may not be needed at all times. Most use cases for A* is really just shortest path.

HeuristicCostCalculator

HeuristicCostCalculator is implemented as an interface. It looks like this:

public interface HeuristicCostCalculator<T> {
    // Computes the heuristic cost from the specified starting position and the goal.
    float ComputeCost(T start, T goal);
}

Basically, it just computes the heuristic cost given two arbitrary positions. As you know, the heuristic cost is important to the algorithm. Without it, it’s no longer A*.

Reachability

Reachability is also implemented as an interface:

public interface Reachability<T> {
    // A reachability check on a single position
    // This is used to check if a goal is reachable at all
    // If not, the search ends abruptly
    // This is to avoid useless search when the position can't be reached at all
    bool IsReachable(T position);

    // Returns whether or not the specified movement of these two nodes is reachable. 
    bool IsReachable(T from, T to);
}

There are two methods. The first one with only one position parameter is used as a quick check to see if the position is reachable at all. For example, in a tile based game, if the tile has a blocker and thus unreachable, A* can be dropped. Or in another case, a tile is free but all its neighbors are blocked. If the position is not reachable, A* search may no longer be needed.

The second one with two parameters is used while the algorithm is being executed. The parameters are not necessarily the starting and goal nodes. The parameters passed here are nodes that are considered during the A* search. There are times where reachability changes for a certain pair of nodes.

For example, in our game Academia, when a tile is blocked, an agent can’t move diagonally along the tile’s diagonal neighbors like moving from bottom neighbor to right neighbor. The agent has to go through the right neighbor of the bottom tile first then move up to the right neighbor of the newly blocked tile. The bottom neighbor and the right neighbor are reachable by their graph node setup (we allow diagonal movement). By using the reachability interface, we can override this rule and mark the pair as unreachable because of the presence of such blocked tile.

Reachability
Moving from chair to water fountain is not allowed because of the wall. Agent has to go from chair to trash can then to water fountain.

Different games may also have game rules that override the graph node setup. A simple example I can think of is say land tile that is connected to a water tile. Only amphibian units can pass from land to water but not land only units. The Reachability interface can be used to express these rules.

Usage

This is how our A* class is then used:

// Say Tile is our "position" class
AStar<Tile> astar = new AStar();

// Prepare node handles
foreach(Tile tile in tileMap) {
    tile.NodeHandle = astar.Add(tile);
}

// Prepare neighbors
foreach(Tile tile in tileMap) {
    foreach(Tile neighbor in tile.Neighbors) {
        // TileLink here stores the weight for moving from the tile to the neighbor
        tile.NodeHandle.AddPath(neighbor.Handle, new TileLink(tile, neighbor));
    }
}

// To use A* search
AStarPath<Tile> path = new AStarPath<Tile>();
Tile start = ResolveStartTile(); // Let's just say this is how we resolve the starting tile
Tile goal = ResolveGoalTile();

// Say MyHeuristicCalculator and MyReachability are implemented as singletons
astart.ResolvePath(path, start.NodeHandle, goal.NodeHandle, MyHeuristicCalculator.Instance, MyReachability.Instance);

// Use the path of reachable or do something else if not
if(path.Reachable) {
    foreach(Tile tile in path) {
        MoveToTile(tile); // It's not really like this in an actual game but you get the idea
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s