# Q：寻路算法在实现网格

Reading about Dijkstra's algorithm for pathfinding, I see that every example applicable to a "grid based" game is related to the case in which you have a "cell" that is passable or not passable. I better examplain with an image:

I need to implement an algorithm for pathfinding from A to B (returning a list of Cells to "follow") for the case II. As you can see from the image, in this model there aren't cells which are "unpassable", but every cell has stored 4 informations that determines if, while inside a cell, you can go up, down, left, right.

Searching on the net I found a lot of implementations of Dijkstra's algorithm for Case I.

1. Is it possible to implement it for case II?
3. Should I use another algorithm for that case (The grid will be 32x14)?

1. Is it possible to implement it for case II?
3. Should I use another algorithm for that case (The grid will be 32x14)?

Yes, it is possible. Transform your cells into a graph by modelling cells as nodes, and only connect two cells with an edge, if no wall separates them.

However, Dijkstra is not the best algorithm to use, for such an easy example. If all edges in the graph have a distance of one, you can simply use a BFS search to find the quickest path.

Additionally, the fact that the path is a grid may mean that you could even find faster algorithms to solve the problem. However, this only makes sense if your grid is really big. For your 32x14 grid, I highly doubt that a sophisticated algorithm will be faster than BFS.

algorithm  path-finding