# Java Game: A* Algorithm (searching only cells in front of character)

Game Type: grid tile map that is turned based

Directions allowed: Left, Forward, Right (to reverse directions you must either use two lefts or two rights) - both left and right moves diagonal but change the face of the ship depending on original face)

Slots: Depending on ship size there are a certain number of slots for that particular ship for user to enter to allow the ship to move that many spots per turn (ie. 3 slots == 3 moves per turn)

Example:

Start Position: 2,2

Start face: North

Move Placed: Left

End Result: Position: 1,3 ; Face: West

Problem: algorithm uses all 8 tiles for path finding; but should only look for the tiles that are in front (depends on ship face)

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

}


Pathfinding calculation:

    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(Position start, Position goal){
List<AStarNode> openList = new ArrayList<AStarNode>();
List<AStarNode> closedList = new ArrayList<AStarNode>();
AStarNode current = new AStarNode(start, null, 0, start.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();
return path;
}
openList.remove(current);
for(int i = 0; i < 9; i++) {
if (i == 4)continue;
int x = current.position.getX();
int y = current.position.getY();
int xi = (i % 3) - 1;
int yi = (i / 3) - 1;
int at = context.getMap().getTile(x + xi, y + yi);
if(at == 1 || at == 2) continue; // ignore rocks
Position a = new Position(x + xi, y + yi);
double gCost = current.gCost + current.position.distance(a);
double hCost = a.distance(goal);
AStarNode node = new AStarNode(a, current, gCost, hCost);
if(positionInList(closedList, a) && gCost >= node.gCost) continue;
if(!positionInList(openList, a) || 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;
}


Implementation:

@Override
public void calculateRoute() {
Position destination = new Position(3,3); // replace with cluster
if(this.equals(destination)) {
return;
}based
path = context.getPlayerManager().findPath(this, destination);
VesselFace face = getFace();
if(path != null) {
if(path.size() > 0) {
int numberOfMoves = getVessel().has3Moves() ? 3 : 4;
Position currentPosition = this.copy();
for(int slot = 0; slot <= numberOfMoves; slot++) { //moves to enter
int positionIndex = (path.size() - 1) - (slot); //subtract slot to allow multiple moves
if(positionIndex < 0 || path.size() < slot) { // make sure it doesn't count too far
return;
}
Position pos = path.get(positionIndex).position;
Position left = MoveType.LEFT.getFinalPosition(currentPosition, face);
Position right = MoveType.RIGHT.getFinalPosition(currentPosition, face);
Position forward = MoveType.FORWARD.getFinalPosition(currentPosition, face);
if(left.equals(pos)) {
currentPosition.add(left.getX() - getX(), left.getY() - getY());
getMoves().setMove(slot, MoveType.LEFT);
switch(face) {
case NORTH:
face = VesselFace.WEST;
break;
case SOUTH:
face = VesselFace.EAST;
break;
case WEST:
face = VesselFace.SOUTH;
break;
case EAST:
face = VesselFace.NORTH;
break;
}
}else if(right.equals(pos)) {
currentPosition.add(right.getX() - getX(), right.getY() - getY());
getMoves().setMove(slot, MoveType.RIGHT);
switch(face) {
case NORTH:
face = VesselFace.EAST;
break;
case SOUTH:
face = VesselFace.WEST;
break;
case WEST:
face = VesselFace.NORTH;
break;
case EAST:
face = VesselFace.SOUTH;
break;
}
}else if(forward.equals(pos)){
currentPosition.add(forward.getX() - getX(), forward.getY() - getY());
getMoves().setMove(slot, MoveType.FORWARD);
switch(face) {
case NORTH:
face = VesselFace.NORTH;
break;
case SOUTH:
face = VesselFace.SOUTH;
break;
case WEST:
face = VesselFace.WEST;
break;
case EAST:
face = VesselFace.EAST;
break;
}
}
}
}
}
}


I use the switch statement and currentPosition.add() method so that when you place 3 moves for that particular turn; it knows where it should end up. Probably not best practice.

Statement that adds a move to the particular slot

getMoves().setMove(slot, MoveType.FORWARD);


Tiles that should be checked every turn based on ship face: • It sounds like you know what needs to change about your implementation. Where did you run into difficulty applying this change that we can help you overcome? – DMGregory Jan 7 at 21:22
• @DMGregory Is there a way I can just check the cells in front when it changes nodes; and not all 8? – dre Jan 7 at 21:29
• You'd replace your for(int i = 0; i < 9; i++) loop with one that iterates only over the 3 cells of interest. You could use the notion of a neighbourhood for this. Note that the nodes of your pathfinding search are now not just positions, but position+direction pairs. Just because you explored the node (1, 2, North) and put it in the closed set does not mean you can skip the (1, 2, South) - there might be a shorter path to the goal through this node southward than the one you found northward, so you need to treat them as distinct entities. – DMGregory Jan 7 at 21:36
• @DMGregory Could you provide a brief example of neighborhood for this type of search? Where it just looks for the 3 cells directly in front of it? – dre Jan 7 at 21:42
• You drew the four neighbourhoods you need yourself. Click the link I shared to see how you can take those offsets you've chosen and store them in a collection for ease of iteration. – DMGregory Jan 7 at 21:45

This is only a partial attempt, giving more details for the comment I made.

A* searches over a graph of nodes that contain the "state" of the ship. In most tutorials (including mine, sorry) the state is only the position. But in your case I think the state is both the position and the facing direction. You need to know the facing direction to calculate the three positions in front of it. And then after the move, you'll have both a position and a new facing direction.

Node currently has a position; change it to have both position and facing. Here's a rough version of the for(int i = 0; i < 9; i++) loop to find the neighbors. Instead of going through 9 neighbors, each of the 4 directions will have exactly 3 neighbors. (Yes, there are 12, not 8! because it depends on which direction you were facing before) int x = current.position.getX();
int y = current.position.getY();
List<Node> neighbors = new ArrayList<Node>();
switch (current.facing) {
case NORTH:
neighbors.add(new Node(new Position(x-1, y-1), WEST, …));
neighbors.add(new Node(new Position(x, y-1), NORTH, …));
neighbors.add(new Node(new Position(x+1, y-1), EAST, …));
break;
case EAST:
neighbors.add(new Node(new Position(x+1, y-1), NORTH, …));
neighbors.add(new Node(new Position(x+1, y), EAST, …));
neighbors.add(new Node(new Position(x+1, y+1), SOUTH, …));
break;
case SOUTH:
neighbors.add(new Node(new Position(x-1, y+1), WEST, …));
neighbors.add(new Node(new Position(x, y+1), SOUTH, …));
neighbors.add(new Node(new Position(x+1, y+1), EAST, …));
break;
case WEST:
neighbors.add(new Node(new Position(x-1, y-1), NORTH, …));
neighbors.add(new Node(new Position(x-1, y), WEST, …));
neighbors.add(new Node(new Position(x-1, y+1), SOUTH, …));
break;
}

/* for each of the nodes in the neighbors list, use the same

• Also does my for(int i = 0; i < 9; i++) stay the same and this goes in it? – dre Jan 8 at 20:37
• The parent is always the node you came from, which is called current in your code. The gCost is always the parent's gCost plus the cost of moving one more step, which depends on your game, but it looks like the code you posted uses the distance between the new node and the old node. The hCost is the heuristic, and you can reuse your existing heuristic that doesn't take into account the facing direction. – amitp Jan 9 at 20:30