The core libraries are now done (or so I thought), so I'm slowly refactoring the game libraries, one component at a time. But because nothing escapes my refactoring extravaganza, I discovered another victim in the core libraries, ready to be refactored mercilessly: the grid/graph pathfinding. So, my original idea is to make the pathfinders objects that keep some state and run one iteration at a time, as I envisioned that I might interrupt an A* calculation halfway through. Well, thinking about it, that's nonsense, so ... refactor away.

Now the pathfinding routine is just a function with 3 arguments:

  • A config struct which, as the name implies, provides configuration/setup for the search execution: start point, goals, heuristics, search space etc.
  • A state struct which maintains the algorithm state: fscore/gscore maps, the priority queue, etc.
  • An output struct which stores the output from the search, such as the path, path costs (optional), visited nodes (optional), etc.

To aid debugging, I've added a conditionally compiled part that records state and output at every search iteration. After this semantic separation in these structures, recording the state is now a breeze! I just keep a vector of states/outputs per iteration to see their "history" and how they evolve.

So, with the nicely modularized grid pathfinder function and the newly refactored rendering system, we can implement an application that visualizes pathfinding (inspired by Amit's super awesome A* page, among others). I've made an application that uses ImGui and my widgets (the tilegrid one to be precise), so that I can dynamically modify weights on the map, as well as start and goals, heuristics, 4 or 8 connectivity, etc. Additionally, several visualization options are provided as overlays: visited cells, gscore, fscore, the calculated path, start/end points, etc, all as layers: gscore, fscore and weights exist for all cells, so they are rendered using a dense tile renderer, while start, goals, visited cells are rendered using a sparse tile renderer. The tilegrid widget uses a group renderer, tha renders all the layers specified. Way too much text and way too little action, here's a video capture of the visualizer:

 

Next thing to do is make sure the graph pathfinder works well, and then continue the refactoring quest, which is totally worth it.