After implementing this I can return to random map generation and implement things like optimal stair placement, or locked doors with user reachable keys, or strategically located loot or gangs of NPCs, etc...
This implementation will also prove useful later in development when implementing the player character and NPCs.
So far I have created a small console application to test different approaches to this algorithm, and also for optimization before integration into Frost and Flame.
I am not using the same map format as Frost and Flame during testing, I created a very light map format for testing. Although I am using a similar pointer based approach as found in the code for procedural map generating. I am also taking my own approach to this algorithm's implementation, I wont be creating separate lists of tiles, nor will I be using any specific memory for the tiles in order to determine paths between them.
I plan on having the map store a few extra variables for path-finding and reusing them each time a path needs to be found. This will also cut down on memory allocation / de-allocation for each path finding call.
With regards to performance Vs Memory, this approach should perform well with a possibly slightly larger memory usage than traditional approaches to the implementation of this algorithm.
I have since completed the final algorithm, and have thus started integration into Frost and Flame.
At this point the path is not yet returned, only calcu