Jump to content

  • Log In with Google      Sign In   
  • Create Account

We need your feedback on a survey! Each completed response supports our community and gives you a chance to win a $25 Amazon gift card!


Determining most suitable pathfindind algorithm for a Risk-like game?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
6 replies to this topic

#1 BogdanV   Members   -  Reputation: 131

Like
0Likes
Like

Posted 24 April 2014 - 09:39 PM

 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.

 

 



Sponsor:

#2 frob   Moderators   -  Reputation: 22833

Like
2Likes
Like

Posted 24 April 2014 - 09:55 PM

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

Advice needs context. Sometimes advice is good for a specific instance, sometimes it does not apply to a specific case.

A* is a good algorithm. It is well studied, and used in a huge number of games. You say you like Dijkstra's Algorithm, you should know that it is the same as A* with a zero heuristic. With a good heuristic you can still get optimal results but examine fewer connections, so A* can be faster.

What is it about your game that makes you think A* is a bad choice? What would you intend to use instead?

Check out my book, Game Development with Unity, aimed at beginners who want to build fun games fast.

Also check out my personal website at bryanwagstaff.com, where I write about assorted stuff.


#3 BogdanV   Members   -  Reputation: 131

Like
0Likes
Like

Posted 24 April 2014 - 11:07 PM

 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.



#4 SeraphLance   Members   -  Reputation: 1457

Like
0Likes
Like

Posted 24 April 2014 - 11:46 PM

 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?


Edited by SeraphLance, 24 April 2014 - 11:51 PM.


#5 frob   Moderators   -  Reputation: 22833

Like
0Likes
Like

Posted 25 April 2014 - 12:02 AM

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.


You said you were advised against using one of the most popular pathfinding algorithms, but still haven't given a real reason why, other than in the abstract "it might not be perfect".

You right it might be less than optimal, it might seem jarring. So what, it might have lots of problems. It might even work nicely. Have you actually tried it? You can find hundreds of implementations of the algorithm in Google, just pick your favorite from various tutorial sites or even the Boost library (although I hate that their implementation uses an exception to exit) and try it out.

These are the most widely used algorithms for the problem, I haven't seen anything yet that says it is the wrong one for your solution.

Check out my book, Game Development with Unity, aimed at beginners who want to build fun games fast.

Also check out my personal website at bryanwagstaff.com, where I write about assorted stuff.


#6 BogdanV   Members   -  Reputation: 131

Like
0Likes
Like

Posted 25 April 2014 - 12:27 AM


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



#7 jHaskell   Members   -  Reputation: 1109

Like
0Likes
Like

Posted 25 April 2014 - 06:25 AM

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.






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS