Shortest Path Algo Unweighted Graph

Just to enhance my java script skills i am trying to develop a pacman game in js. have a grid of 20 by 20 . This grid has 0's and 1's which indicate if there is a wall or a path .

Solution 1:

For unweighted graph you have a several options for finding a shortest path:

• BFS - simplest solution - the BFS is complete and optimal - it will find the shortest path if such exist.
• Bi-Directional BFS - basically the same, but do BFS from both sides, and end when two BFS meet. It significantly decreases the number of vertices discovered. I explained more about how to do it and why it's good in this thread.
• Heuristical A* Algorithm - it is an informed algorithm, and thus usually faster then the others, but is harder to program. Use an admissible heuristic function with it, like the manhattan distances.

Personally - I think I'd use BFS in this case - but start from pacman, until you discover all "targets" (demon locations) - it will give you the shortest path from each demon to pacman.
Note that if you have just a few demons and a big board, doing A* several times (once per demon) might be a better solution.

One should probably benchmark it to see which is actually better.

Solution 2:

If you need to find the shortest path from a source to all vertices, perform a Breadth first search from the source and keep storing the parent of each vertex in a separate array.Following the parent nodes will give you the path from each vertex to its parent.

Solution 3:

I think Depth-first search also works here. Compared with Breadth-first search, there's no need to store all the leaf nodes when you use DFS. But it is not able to find a solution at times. The input here is not that complex, so I think DFS is good enough.

Also, the A* search algorithm is the best choice, cause it's faster than uninformed search and always complete and optimal. It guarantees the solution is optimal. For a complicated situation, to create a efficient heuristic function really costs. Here, you can use Manhattan distance or Euclidean distance.