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.