A* algorithm: need help fixing path that come in contact with obstacle

Question

I am using A* as a pathfinding technique for my AI; it works fine until it gets close to an obstacle (in my case rocks). Right now it just continues the loop if it finds a neighbor thats a rock. It should not actually do this. It should check it.

Allowed Moves: FORWARD,LEFT,RIGHT (LEFT & RIGHT at diagonals) turns are basically two phases: FORWARD, turn face then FORWARD (counts as one move with no additional cost)

The AI should know to turn left or right on the rock in the direction of the goal while also taking other rocks into account.

The line that checks for rocks is: if(at == 1 || at == 2) continue;

I guess you could use the neighborlist to check the sides of the ship.

However it shouldn't always check it. Only when it comes in contact with a rock

Scenario 1: (ship should turn left (one move) once then continue on path)

Scenario 2: (ship should either turn left or right twice (two moves) to unblock itself)

Scenario 3: (ship should turn left or right depending on which path is shorter: doing two lefts will hit rock twice but distance is shorter than if it went right by 1 tile)

In each of these scenarios the face of the ship is the only thing that changes; unless its a forward move into the rock then there is no change. If right/left were used in any other situation (regular tiles) it would change position also.

public class AStarSearch {
    
    private ServerContext context;
    private List<AStarNode> openList;
    private List<AStarNode> closedList;
    
    private double ORTHOGONAL_COST = 1.0;
    private double DIAGONAL_COST = ORTHOGONAL_COST * Math.sqrt(2.0);
    
    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(Player bot, Position goal){
        openList = new ArrayList<AStarNode>();
        closedList = new ArrayList<AStarNode>();
        List<AStarNode> neighbors = new ArrayList<AStarNode>();
        AStarNode current = new AStarNode(bot, bot.getFace(), MoveType.NONE, null, 0, bot.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();
                Collections.reverse(path);
                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, y), VesselFace.NORTH, MoveType.NONE,current,0,0));
                    neighbors.add(new AStarNode(new Position(x, y+1), VesselFace.NORTH, MoveType.FORWARD,current,0,0));
                    neighbors.add(new AStarNode(new Position(x-1, y+1), VesselFace.WEST, MoveType.LEFT,current,0,0));
                    neighbors.add(new AStarNode(new Position(x+1, y+1), VesselFace.EAST, MoveType.RIGHT,current,0,0));
                    break;
                case EAST:
                    neighbors.add(new AStarNode(new Position(x, y), VesselFace.EAST, MoveType.NONE,current,0,0));
                    neighbors.add(new AStarNode(new Position(x+1, y), VesselFace.EAST, MoveType.FORWARD,current,0,0));
                    neighbors.add(new AStarNode(new Position(x+1, y+1), VesselFace.NORTH, MoveType.LEFT,current,0,0));
                    neighbors.add(new AStarNode(new Position(x+1, y-1), VesselFace.SOUTH, MoveType.RIGHT,current,0,0));
                    break;
                case SOUTH:
                    neighbors.add(new AStarNode(new Position(x, y), VesselFace.SOUTH, MoveType.NONE,current,0,0));
                    neighbors.add(new AStarNode(new Position(x, y-1), VesselFace.SOUTH, MoveType.FORWARD,current,0,0));
                    neighbors.add(new AStarNode(new Position(x-1, y-1), VesselFace.WEST, MoveType.RIGHT,current,0,0));
                    neighbors.add(new AStarNode(new Position(x+1, y-1), VesselFace.EAST, MoveType.LEFT,current,0,0));
                    break;
                case WEST:
                    neighbors.add(new AStarNode(new Position(x, y), VesselFace.WEST, MoveType.NONE,current,0,0));
                    neighbors.add(new AStarNode(new Position(x-1, y), VesselFace.WEST, MoveType.FORWARD,current,0,0));
                    neighbors.add(new AStarNode(new Position(x-1, y+1), VesselFace.NORTH, MoveType.RIGHT,current,0,0));
                    neighbors.add(new AStarNode(new Position(x-1, y-1), VesselFace.SOUTH, MoveType.LEFT,current,0,0));
                    break;
            }
            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());
                if(at == 1 || at == 2) continue; // this is the line where it checks if tile is rock or not

                double gCost = current.gCost + costToReach;
                double hCost = heuristicDistance(neighborNode.position,goal);
                AStarNode node = new AStarNode(neighborNode.position, neighborNode.face,neighborNode.move, 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 double getActionCost(Position node, int currentTile) {
        if(currentTile > 3 && currentTile < 11) {
            return 0.2;
        }else {
            return 1;   
        }
    }

    private double heuristicDistance(Position current, Position goal) {
        int xDifference = Math.abs(goal.getX() - current.getX());
        int yDifference = Math.abs(goal.getY() - current.getY());

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

        return orthogonal * ORTHOGONAL_COST + diagonal * DIAGONAL_COST;
    }
    
    private boolean positionInList(List<AStarNode> list, Position position) {
        for(AStarNode n : list) {
            if(n.position.equals(position)) return true;
        }
        return false;
    }

}

AStarNode:

public class AStarNode {

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

There will be no additional cost of running into a rock as long as its a shorter route. Also, if a ship tries to turn left or right from its current position; but there is a rock at that tile it will move up one tile and changes its direction.

The overall question/goal: How do I fix my current code to account for these situations; please provide an implementation or instructions.

Answer 1

I'll show you how I'd tackle this in C#, since it's the language I'm most familiar with and I'm less likely to make silly syntax errors. 😉 Java syntax is very similar, so you should be able to translate the strategy to your code smoothly enough.

I'd start by defining some data types to manipulate ship positions and headings. Nothing too exciting here.

public enum Direction {
    North,
    East,
    South,
    West
}    

public static Direction TurnRight(Direction direction) {
    return (Direction)(((int)direction + 1) & 3);
}

public static Direction TurnLeft(Direction direction) {
    return (Direction)(((int)direction + 3) & 3);
}

public static Vector2Int ToOffset(Direction direction) {
    switch(direction) {
        case Direction.North: return Vector2Int.up;
        case Direction.East: return Vector2Int.right;
        case Direction.South: return Vector2Int.down;
        case Direction.West: return Vector2Int.left;            
    }
    throw new System.ArgumentException($"Invalid direction {direction}");
}

public struct ShipTransform {
    public readonly Vector2Int position;
    public readonly Direction heading;

    public ShipTransform(Vector2Int position, Direction heading) {
        this.position = position;
        this.heading = heading;
    }
}

Then I'd set up the map functions to compute what happens for special effect tiles...

public class Map {

    // I'll elide the map storage - you can use whatever format you like there.

    public bool IsBlocked(Vector2Int position, Direction travelDirection) {
        // TODO: Return true if there is a ship here that's not moving out of the way.            

        switch(GetTileTypeAt(position)) {
            case TileType.Rock: return true;
            case TileType.WhirlpoolNE: return travelDirection == Direction.West;
            case TileType.WhirlpoolSE: return travelDirection == Direction.North;
            case TileType.WhirlpoolSW: return travelDirection == Direction.East;
            case TileType.WhirlpoolNW: return travelDirection == Direction.South;
            default: return false;
        }
    }
    
    public bool ProcessTileEffect(ShipTransform transform, out ShipTransform result) {
        
        var tileType = GetTileTypeAt(transform.position);
        switch (tileType) {
            case TileType.WindNorth:    result = ProcessWind(transform, Direction.North);
                                        return true;
            case TileType.WindEast:     result = ProcessWind(transform, Direction.East);
                                        return true;
            case TileType.WindSouth:    result = ProcessWind(transform, Direction.South);
                                        return true;
            case TileType.WindWest:     result = ProcessWind(transform, Direction.West);
                                        return true;
            case TileType.WhirlpoolNE:  result = ProcessWhirlpool(transform, transform.position - Vector2Int.one);
                                        return true;
            case TileType.WhirlpoolNW:  result = ProcessWhirlpool(transform, transform.position + Vector2Int.down);
                                        return true;
            case TileType.WhirlpoolSE:  result = ProcessWhirlpool(transform, transform.position + Vector2Int.left);
                                        return true;
            case TileType.WhirlpoolSW:  result = ProcessWhirlpool(transform, transform.position);
                                        return true;
            default:                    result = transform;
                                        return false;
        }
    }

    ShipTransform ProcessWhirlpool(ShipTransform transform, Vector2Int whirlpoolCorner) {
        Vector2Int position = 2 * whirlpoolCorner + Vector2Int.one - transform.position;
        return new ShipTransform(position, TurnRight(transform.heading));
    }        

    ShipTransform ProcessWind(ShipTransform transform, Direction windDirection) {
        var position = transform.position + ToOffset(windDirection);

        if (IsBlocked(position, windDirection))
            return transform;

        return new ShipTransform(position, transform.heading);
    }
}

Then I'd make a data structure to represent an A* node - with a few convenience methods to make it easier to compute neighbouring nodes I want frequently:

public struct MoveState {
    public readonly ShipTransform transform;
    public readonly int gCost;
    public float hCost;

    public MoveState(ShipTransform transform, int cost) {
        this.transform = transform;
        gCost = cost;
        hCost = 0;  // Our parent will fill this in later.
    }

    public MoveState SpendMove() {
        return new MoveState(transform, gCost+1);
    }

    public MoveState MoveForward() {
        return new MoveState(
            new ShipTransform(transform.position + ToOffset(transform.heading), transform.heading),
            gCost);
    }

    public MoveState Turn(Direction direction) {
        return new MoveState(
            new ShipTransform(transform.position, direction), 
            gCost);
    }
}

Now we can make a method that enumerates the moves we can make from a given position:

public static void FindMoves(MoveState start, List<MoveState> outcomes, Map map, int moveBudget) {        
    outcomes.Clear();

    // If we have no moves left, return with an empty list.
    if (start.gCost >= moveBudget)
        return;

    // Add "wait" move (or move that cannot be completed).
    var here = start.SpendMove();
    outcomes.Add(here);

    // First, we'll try moving in our current heading.
    var forward = here.MoveForward();
            
    if (map.IsBlocked(forward.transform.position, forward.transform.heading)) {
        // If we're facing a barrier, we can only turn in-place.
        outcomes.Add(here.Turn(TurnLeft(here.transform.heading)));
        outcomes.Add(here.Turn(TurnRight(here.transform.heading)));
    } else {
        // Otherwise, we can move forward into the tile in front of us.
        outcomes.Add(forward);

        // And we can turn into the tiles left or right of it...
        var turned = forward.Turn(TurnLeft(here.transform.heading));
        var advanced = turned.MoveForward();            
        if (map.IsBlocked(advanced.transform.position, advanced.transform.heading)) {                
            // If that tile is blocked, we just turn our facing direction.
            outcomes.Add(turned);
        } else {
            // Otherwise, we move into the tile diagonal to our original.
            outcomes.Add(advanced);
        }

        // Repeat for a right turn.
        turned = forward.Turn(TurnRight(here.transform.heading));
        advanced = turned.MoveForward();
        if (map.IsBlocked(advanced.transform.position, advanced.transform.heading)) {
            outcomes.Add(advanced);
        } else {
            outcomes.Add(turned);
        }
    }

    // After we've moved, then the map takes a turn and can move us.
    for (int i = 0; i < outcomes.Count; i++) {
        // If we're on a tile that moves us, replace the outcome with that move.
        if (map.ProcessTileEffect(outcomes[i].transform, out ShipTransform result)) {
            outcomes[i] = new MoveState(result, outcomes[i].moveBudget);
        }
    }

    // Done!
}

Note that nowhere in here does the algorithm consider what the AI "should" do per se. It only exhaustively enumerates the set of things that could happen.

Also notice here that the gCost only ever increments by 1 - because every move exhausts exactly one movement action slot, whether it's orthogonal or diagonal or a "wait".