shortest path algo unweighted graph

Question

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 . Now I want to develop a algo for the demons to follow the pacman . I am not sure which algorithm should I go for .

So my input to the function will be foo( current position, pacman position,grid, path)

var maze = [            [0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0],
                        [0,1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,0],
                        [0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0],
                        [0,1,0,1,0,1,1,1,1,0,0,1,1,1,1,0,1,0,1,0],
                        [0,1,0,1,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0],
                        [0,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,0],
                        [0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0],
                        [0,1,1,1,1,1,0,0,0,1,1,0,0,0,1,1,1,1,1,0],
                        [0,1,0,0,0,1,1,0,0,1,1,0,0,1,1,0,0,0,1,0],
                        [0,1,0,0,0,0,1,0,0,1,1,0,0,1,0,0,0,0,1,0],
                        [1,1,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,1,1],
                        [0,1,0,0,0,1,1,0,0,0,0,0,0,1,1,0,0,0,1,0],
                        [0,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,0],
                        [0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0],
                        [0,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,0],
                        [0,1,0,1,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0],
                        [0,1,0,1,0,1,1,1,1,0,0,1,1,1,1,0,1,0,1,0],
                        [0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0],
                        [0,1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,0],
                        [0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0]];

possible duplicate of [Depth first search - 2D Game map](http://stackoverflow.com/questions/9547295/depth-first-search-2d-game-map) — Saeed Amiri, Oct 19 '13 at 15:51

score 3 · Answer 1 · edited May 23 '17 at 11:57

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.

@sameerkarjatkar No, you can use the implicit graph structure and build it on the fly. All you need for it is a method `next(v)` that returns all vertices that can be reached from `v` with one step. — amit, Oct 19 '13 at 07:47

score 0 · Answer 2 · answered Oct 19 '13 at 07:29

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.

score 0 · Answer 3 · answered Oct 19 '13 at 19:56

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.

shortest path algo unweighted graph

3 Answers3

Linked