Search Algorithm for Pacman

Question

I need to find the path with the lower cost in a graph represented by a matrix. I researched a bit on the Dijkstra's algorithm but I need a vector with the sequence of nodes in the shortest path, not the distance itself. The game is being made ​​for Assembly, but if anyone knows an implementation in C at least it's gonna help a lot. I will use it to calculate the route of ghosts, matching heuristic algorithms to create the Very Hard Mode of the game. I also tried something with A*, but the implementations I found used struct, which are not applicable to the situation. Thanks a lot since now. ^^

Answer 1

This problem is the basis for the edx AI course. I've managed to google a breadth first search code written in C here. From what I can remember breadth first search is guarenteed to find the shortest path if it exists. I don't think it would be too hard to add a heuristic algorithm in there either, there should be notes on the edx link that would help with that.