HackerRank: Pacman A*

HackerRank: Pacman A*

In the previous game, you performed UCS on the PacMan grid. In this game we use AStar algorithm to reduce the nodes expanded using search using a simple yet efficient heuristic.

AStar on graphs uses the following function

cost = d(s,c) + h(c)

where s is the source node, c is the node currently expanded and h(c) is the estimation of the cost to reach from c to the destination ( food ).

In this game, we use manhattan heuristic as an estimate. Given two nodes (r,c) and (r1,c1). The manhattan heuristic is the manhattan distance between the two nodes and is given by

|r1 - r | + |c1 - c|

https://codepair.hackerrank.com/paper/QG1xc8Pg?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9
private Node UCS() {
Queue<Node> queue = new PriorityQueue<Node>(X * Y, new Comparator<Node>() {
@Override
public int compare(Node node1, Node node2) {
return node1.distance() + cost(node1) - (node2.distance() + cost(node2));
}
});

boolean[][] explored = new boolean[X][Y];

queue.add(new Node(pacman));

while (!queue.isEmpty()) {
Node node = queue.poll();

int x = node.position()[0];
int y = node.position()[1];

if (explored[x][y]) {
continue;
}
explored[x][y] = true;

if (node.isFood()) {
return node;
}

if (isValidMove(x - 1, y) && !explored[x - 1][y]) {
queue.add(new Node(new int[] {x - 1, y}, node));
}
if (isValidMove(x, y - 1) && !explored[x][y - 1]) {
queue.add(new Node(new int[] {x, y - 1}, node));
}
if (isValidMove(x, y + 1) && !explored[x][y + 1]) {
queue.add(new Node(new int[] {x, y + 1}, node));
}
if (isValidMove(x + 1, y) && !explored[x + 1][y]) {
queue.add(new Node(new int[] {x + 1, y}, node));
}
}
return null;
}
private boolean isValidMove(int x, int y) {
return x >= 0 && y >= 0 && x < X && y < Y && board[x][y] != WALL;
}

private int cost(Node node) {
return (node.position()[0] > food[0] ? node.position()[0] - food[0] : food[0] - node.position()[0]) +
(node.position()[1] > food[1] ? node.position()[1] - food[1] : food[1] - node.position()[1]);
}
private Node(int[] position, Node parent) {
this.position = position;
this.parent = parent;
this.distance = parent.distance() + 1;
}