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.

I was also adviced against using it in this particular case.

Well, I can't seem to be able do devise a proper set of rules for the heuristic function to work, because, due to the irregular nature of the regions comprising the map, there really isn't any intuitive way of coming out with a decent aproximation for the path.

Which brings me back to Dijkstra which, like you said, works because there is no heuristic function to implement. However, this also means that it'll yield less optimal results as far as paths are concerned. Or, in any case, results that might seem jarring to the player.

Well, I can't seem to be able do devise a proper set of rules for the heuristic function to work, because, due to the irregular nature of the regions comprising the map, there really isn't any intuitive way of coming out with a decent aproximation for the path.

Which brings me back to Dijkstra which, like you said, works because there is no heuristic function to implement. However, this also means that it'll yield less optimal results as far as paths are concerned. Or, in any case, results that might seem jarring to the player.

Dijkstra's Algorithm generates optimal paths. The only difference between Dijkstra's and A* is that A* generates an optimal path faster (given a good heuristic).

I've never played HoI, but in a game like Europa Universalis (or Risk, as per your example) just has things set up as a simple graph, and probably does A*. In this case, a simple heuristic can be distance. Even with things like water and weather conditions, a distance-based heuristic should still look "good". Even if you wanted a perfect path, again, the only difference between good heuristics is that one generates a perfect path faster.

EDIT: I should clarify... when I say "distance", I mean as the crow flies. You could calculate actual path distances too if you like, but a trivial absolute distance metric may well be "good enough", depending on your efficiency needs. Heck, if your application can afford more processing time (since I assume your game is going to be fairly slow paced), why not use Dijkstra's?

Well, I can't seem to be able do devise a proper set of rules for the heuristic function to work, because, due to the irregular nature of the regions comprising the map, there really isn't any intuitive way of coming out with a decent aproximation for the path.

Which brings me back to Dijkstra which, like you said, works because there is no heuristic function to implement. However, this also means that it'll yield less optimal results as far as paths are concerned. Or, in any case, results that might seem jarring to the player.

EDIT: I should clarify... when I say "distance", I mean as the crow flies. You could calculate actual path distances too if you like, but a trivial absolute distance metric may well be "good enough", depending on your efficiency needs. Heck, if your application can afford more processing time (since I assume your game is going to be fairly slow paced), why not use Dijkstra's?

Of course! I don't know where my mind was that I totally ignored this. Fun fact is that I actually do need a distance measurement system anyway. *facepalm* My head seems to be in the clouds. Thanks Seraph!

My problem's solved now on a theoretical level anyway. But, just as a random addition, the previous heuristic function I tried to implement involved splitting the movement into two cases: regional movement (confined to one country) or international movement. Based on these, a distance aproximation would have been generated by using cardinal points (i.e. East is the closest to NE while SW is the furthest from NE). That just complicated things alot and gave me nightmares trying to debug it.

It also has another limit: region granularity. The more regions you have that share the same cardinal point association, the less reliable the heuristic function becomes.

Your solution however, apart from being the obvious one is also the simplest xD

Couple questions regarding the environment your pathing algorithm will operate in:

1.) What order of magnitude number of vertices and edges will this algorithm have to operate on? 10, 100, 1000, 10000, etc?

2.) How quickly will your pathing algorithm have to perform in? IE is this a Real Time Strategy game with a fully navigable map, or is it turn based with a 'region' map ala Risk?

The answers to these questions will provide the necessary specs for the algorithm you need to use. If your algorithm is going to be working on a relatively small number of vertices and/or it's a turn based game, your performance requirements are relatively low and Dijkstra's should work just fine.