• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
BogdanV

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

6 posts in this topic

 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.

 

 

0

Share this post


Link to post
Share on other sites

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?
2

Share this post


Link to post
Share on other sites

 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.

0

Share this post


Link to post
Share on other sites

 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
0

Share this post


Link to post
Share on other sites

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.
0

Share this post


Link to post
Share on other sites


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

0

Share this post


Link to post
Share on other sites

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.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0