Java A* Algorithm: going to a specific tile that moves you to another tile

Question

I have my AI to where it only looks at the 3 tiles in front of it for pathfinding which depends on the direction. However during pathfinding it may check a tile that is a action tile.

An action tile is one that moves you to another tile (changes your position).

The player ships can only go in 3 directions (Forward, Left, Right): the left and right turns move the ship diagonally on the grid.

Basic movement example:

Start:

• Ship position: (4,3)
• Face: North
• Move placed: Forward

End result:

• Ship position: (4,4)
• Face: North

---

Action movement example: (Action tile at location 4,4)

Start:

• Ship position: (4,3)
• Face: North
• Move placed: Forward

End result:

• Ship position: (4,5) // as shown moves player an extra space
• Face: North

---

The method to find the next position based on the action tile is given as context.getMap().getNextActionTilePositionForTile(position, tile);: tile - type of action tile; position - current position

How would I make my algorithm account for the action tiles that change position when calculating a path?

Pathfinding Class:

public class AStarSearch {
    
    private ServerContext context;
    private List<AStarNode> openList;
    private List<AStarNode> closedList;
    
    public AStarSearch(ServerContext context) {
        this.context = context;
    }

    private Comparator<AStarNode> nodeSorter = new Comparator<AStarNode>() {

        @Override
        public int compare(AStarNode n0, AStarNode n1) {
            if(n1.fCost < n0.fCost) return 1;
            if(n1.fCost > n0.fCost) return -1;
            return 0;
        }
        
    };

    public List<AStarNode> findPath(VesselFace startFace, Position start, Position goal){
        openList = new ArrayList<AStarNode>();
        closedList = new ArrayList<AStarNode>();
        List<AStarNode> neighbors = new ArrayList<AStarNode>();
        AStarNode current = new AStarNode(start, startFace, null, 0, start.distance(goal));
        openList.add(current);
        while(openList.size() > 0) {
            Collections.sort(openList, nodeSorter);
            current = openList.get(0);
            if(current.position.equals(goal)) {
                List<AStarNode> path = new ArrayList<AStarNode>();
                while(current.parent != null) {
                    path.add(current);
                    current = current.parent;
                }
                openList.clear();
                closedList.clear();
                return path;
            }
            openList.remove(current);
            closedList.add(current);
            
            int x = current.position.getX();
            int y = current.position.getY();
            switch (current.face) {
                case NORTH:
                    neighbors.add(new AStarNode(new Position(x-1, y+1), VesselFace.WEST,current,0,0));
                    neighbors.add(new AStarNode(new Position(x, y+1), VesselFace.NORTH,current,0,0));
                    neighbors.add(new AStarNode(new Position(x+1, y+1), VesselFace.EAST,current,0,0));
                    break;
                case EAST:
                    neighbors.add(new AStarNode(new Position(x+1, y+1), VesselFace.NORTH,current,0,0));
                    neighbors.add(new AStarNode(new Position(x+1, y), VesselFace.EAST,current,0,0));
                    neighbors.add(new AStarNode(new Position(x+1, y-1), VesselFace.SOUTH,current,0,0));
                    break;
                case SOUTH:
                    neighbors.add(new AStarNode(new Position(x-1, y-1), VesselFace.WEST,current,0,0));
                    neighbors.add(new AStarNode(new Position(x, y-1), VesselFace.SOUTH,current,0,0));
                    neighbors.add(new AStarNode(new Position(x+1, y-1), VesselFace.EAST,current,0,0));
                    break;
                case WEST:
                    neighbors.add(new AStarNode(new Position(x-1, y+1), VesselFace.NORTH,current,0,0));
                    neighbors.add(new AStarNode(new Position(x-1, y), VesselFace.WEST,current,0,0));
                    neighbors.add(new AStarNode(new Position(x-1, y-1), VesselFace.SOUTH,current,0,0));
                    break;
            }
            for(AStarNode neighborNode : neighbors) {
                int at = context.getMap().getTile(neighborNode.position.getX(), neighborNode.position.getY());
                if(at > 2){ // special action tiles
                    //TODO - allow ship to navigate through action tiles by looking ahead
//                  neighborNode.position = context.getMap().getNextActionTilePositionForTile(neighborNode.position, at);
                }
                if(at == 1 || at == 2) continue; // ignore rocks
                double gCost = current.gCost + current.position.distance(neighborNode.position);
                double hCost = neighborNode.position.distance(goal);
                AStarNode node = new AStarNode(neighborNode.position, neighborNode.face, current, gCost, hCost);
                if(positionInList(closedList, neighborNode.position) && gCost >= node.gCost) continue;
                if(!positionInList(openList, neighborNode.position) || gCost < node.gCost) openList.add(node);
            }
        }
        closedList.clear();
        return null;
    }
    
    private boolean positionInList(List<AStarNode> list, Position position) {
        for(AStarNode n : list) {
            if(n.position.equals(position)) return true;
        }
        return false;
    }

}

Node class:

public class AStarNode {

    public Position position;
    public VesselFace face;
    public AStarNode parent;
    public double fCost, gCost, hCost;
    
    public AStarNode(Position position, VesselFace face, AStarNode parent, double gCost, double hCost) {
        this.position = position;
        this.face = face;
        this.parent = parent;
        this.gCost = gCost;
        this.hCost = hCost;
        this.fCost = this.gCost + this.hCost;
    }
  
}  
```

Answer 1

Your approach here:

for(AStarNode neighborNode : neighbors) {
    int at = context.getMap().getTile(neighborNode.position.getX(), neighborNode.position.getY());
    if(at > 2) { // special action tiles
        neighborNode.position = context.getMap().getNextActionTilePositionForTile(neighborNode.position, at);
    }

    // ...

...looks to me like the correct way to start, if action tiles only ever change the position of the ship, never its facing direction, and never care about the facing direction going in.

You could expand this to a function that takes a whole node and returns a whole node, returning the input unchanged for non-action tiles. That would let you also create actions that change the facing direction of the ship, or that have different outcomes depending on the direction you enter the tile.

The next item to check is your cost function. Should the bonus movement provided by the action tile be something you pay as part of the cost of the path? That's what your current code does:

double gCost = current.gCost + current.position.distance(neighborNode.position);

Here, if the action tile helps us out by rocketing us forward 10 extra spaces, it counts the same as if we had to take 10 steps to get there - because we're doing this after updating the neighbour position. So the pathfinder won't try to use this as a shortcut - it doesn't see it as saving anything.

If you want these action tiles to count as "free" movement or at least discounted, you can do something like this...

for(AStarNode neighborNode : neighbors) {
    // Compute the cost to get *to* the action tile.
    double costToReach = current.position.distance(neighborNode.position);

    int at = context.getMap().getTile(neighborNode.position.getX(), neighborNode.position.getY());

    // Get our early-out as early as we can.
    if(at == 1 || at == 2) continue; // ignore rocks
    if(at > 2){ // special action tiles
        neighborNode.position = context.getMap().getNextActionTilePositionForTile(neighborNode.position, at);

        // If your actions have a cost / pathfinding disincentive, add it here.
        costToReach += context.getMap().getCostOfActionTile(neighbourNode.position, at);
    }

    // Add the cost to reach and action cost here.        
    double gCost = current.gCost + costToReach;

    // ...                

Finally, we need to update your heuristic hCost computation. To be an "admissible" heuristic for A*, our function needs to never overestimate the cost to reach the goal from a particular node.

For instance, if you pay a cost of 1 for orthogonal moves and a cost of \$\sqrt 2\$ for diagonals, your heuristic function could look something like this:

const double ORTHOGONAL_COST = 1.0;
const double DIAGONAL_COST = ORTHOGONAL_COST * Mathf.Sqrt(2.0);

double HeuristicDistance(AStarNode current, AStarNode goal) {
    int xDifference = Math.Abs(goal.position.x - current.position.x);
    int yDifference = Math.Abs(goal.position.y - current.position.y);

    int diagonal = Math.Min(xDifference, yDifference);
    int orthogonal = xDifference + yDifference - 2 * diagonal;

    return orthogonal * ORTHOGONAL_COST + diagonal * DIAGONAL_COST;
}

(This is a slightly tighter estimate than Euclidean distance because it accounts that your ship can only travel at angles of 0°, 45°, 90°..., so it can't take a direct 30° path to a goal - it has to zig somewhere. It also avoids an expensive square root as a bonus 🙂)

But if some tiles move you an extra space for free, then this could be an over-estimate!

Let's say we have to cross a distance of 8 tiles North, but fortunately enough, every second tile is an action that moves us another space North for free. That means we can complete the journey in 4 steps, half of what the heuristic estimates. That makes the heuristic inadmissible: using this heuristic could lead us to find paths more expensive than the cheapest one available.

For a simple action like this (and assuming you can't chain action tiles if one bonus move drops you onto another tile with a bonus move, and that a move in an orthogonal direction never gives you a bonus move diagonally), there's an easy fix: divide the heuristic estimate by two. That estimates that every tile you hit will take you double the distance - so it never over-estimates the cost of a path, no matter how many of these bonus move tiles are between here and there.

It does under-estimate the cost of many paths through areas of plain tiles, but that's not so bad. You can under-estimate the cost and still find the correct least-cost path, it just might take a little more searching because the algorithm is more optimistic about exploring detours (they might lead us to speedy action tile shortcuts!). It also under-estimates all such paths equally, so this doesn't introduce harmful biases that might lead the search astray.

The more complicated your action tile effects become, the more complicated your heuristic might get. But you can always simplify it, accepting a looser estimate (more searching) in favour of simpler computation (faster to process each node you search).

You can bound by the most extreme cases: if you have one action tile that transports you 10 units, divide your heuristic by 10. If you have wormhole tiles that teleport you across the map, assume the closest wormhole goes straight to the wormhole closest to your goal. See that linked answer for more discussion about picking heuristics.

Since you haven't told us the full set of what action tiles are allowed to do (and their costs), that's about all we can tell you for now. If you need help designing a heuristic for a particular set of actions, try posting a new question detailing the full movement and action tile design.