PathFinding algorithm within this implementation of a grid

1
votes

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 the algorithm with Case II

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?
  2. If yes, can you please give me an advice?
  3. Should I use another algorithm for that case (The grid will be 32x14)?
1
algorithmpath-finding
As for "should I use Dijkstra" - if the grid is relatively small or you really need best solution then yes. If the grid is large and good enough solution is acceptable, I'd recommend A*. - Ondrej Svejdar

1 Answers

3
votes

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.