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

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));

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) {
current = current.parent;
}
openList.clear();
closedList.clear();
Collections.reverse(path);
return path;
}
openList.remove(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.

• Do I understand correctly that if the tile in front of the boat is a rock, turning left or right should turn in-place, rather than moving into the diagonally adjacent tile as normal? And a forward move should result in no change? Are there any additional costs to these moves (like taking damage because of scraping the rock)? What happens if the tile in front of the ship is open, but the diagonal tile I'm trying to move into is a rock? (This should all be documented in your question - asking questions that are vague about what you want often attracts answers that don't do what you want) – DMGregory Jan 14 at 23:04
• @DMGregory Yes you are correct; its a turn in place for LEFT & RIGHT moves. No additional cost. If tile is open in front; then it should take the tile avoiding the rock. – dre Jan 14 at 23:08
• I'm not asking what it should do, I'm asking what is the outcome of trying to perform a Left move when the forward-left neighbour is a rock, but the other tiles are empty. Also, do any of these rules also apply if the tile is occupied by another ship, or does something else happen in those cases? – DMGregory Jan 14 at 23:10
• Not sure what you mean by outcome; when I think outcome I think of result of what its going to do. Rules will apply to other ships as well; but I only need to know about the rocks as ships that sit just act like rocks anyway. – dre Jan 14 at 23:12
• Imagine this is a player ship, not an AI. The player foolishly inputs a command to turn left, even though there is a rock there. What happens to their ship? Does it turn in place, move forward instead of turning, or something else? – DMGregory Jan 14 at 23:14

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 ShipTransform(Vector2Int position, Direction heading) {
this.position = position;
}
}


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;
}

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

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

}
}


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 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(
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();

// First, we'll try moving in our current heading.
var forward = here.MoveForward();

// If we're facing a barrier, we can only turn in-place.
} else {
// Otherwise, we can move forward into the tile in front of us.

// And we can turn into the tiles left or right of it...
// If that tile is blocked, we just turn our facing direction.
} else {
// Otherwise, we move into the tile diagonal to our original.
}

// Repeat for a right turn.
} else {
}
}

// 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".

• Nice. That’s explained really well. On a side note; since the FindMoves() method just gives you possible positions from the current position; how would you personally chain this to make a path for AI to follow? Let’s say you have n moves per turn; how would you do this n times for path? Or is that a separate question to ask? – dre Jan 16 at 1:23
• If you're using A* like your question asks (which you should not, if you're following the method we discussed for days in chat, which does not use A*) then you insert this method to do the neighbour enumeration in your A* loop as long as your Open Set is non-empty. Once you reach your move budget, this will return an empty list of neighbours, so you stop adding new nodes to the Open Set, allowing you to whittle it down until it is empty. – DMGregory Jan 16 at 1:29
• Okay that makes sense; you say ‘should not’ what other option would be better used? The DFS algorithm I set up? – dre Jan 16 at 3:24
• The approach we discussed in chat. – DMGregory Jan 16 at 3:34