The game I'm building, from a game mechanics point of view is somewhat similar to a streamlined version of Hearts of Iron, so, paths need to be generated across irregular regions with varying movement costs in-built (i.e. terrain type) as well as dynamic ones (weather patterns, disruptions in the logistics chain, enemy avoidance etc. ).
The way I have things set up is that, during map load, an adjacency matrix is populated, with weights assigned based on level settings. Currently, no dynamically-changing weights are being applied but I do intend to implement this further along in development, so, I should probably take this into consideration somehow as well.
My problem right now is determining what algorithm would work best for me. In essence, I pretty much have a weighted, non-directional graph represented by an adjacency matrix whose size is fixed at level load.
I was thinking on using Dijkstra's Algorithm but I'm not entirely sure that I will end up with reasonable path solutions (a less than optimal path solution would really stand out in the eyes of a player when issuing move commands).
I was also thinking on using A* but I couldn't come up with a reasonably working heuristic function that would work in my case. I was also adviced against using it in this particular case.
Also, memory efficiency is not really a big issue, I can tolerate some overhead here, however speed is important.
If there's any recommendations you can give me, that would be awesome.