• 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
yadango

Minimal Path Problem

15 posts in this topic

I'm trying to implement a minimal/shortest path type problem. Normally, you'd think Dijkstra or some other algorithm would work, but this is a special type of graph where the weights aren't fixed. For example, if the problem was like this, it would be easy (just use Dijkstra):

[img]http://i73.photobucket.com/albums/i206/yadango/graph1.jpg[/img]

However, the problem I have is like the following.

[img]http://i73.photobucket.com/albums/i206/yadango/graph2.jpg[/img]

Think of it like this... because A -> D is downhill and D -> E is uphill, the weight for D -> E is 1.
Because B -> D is flat and D -> E is uphill, the weight for D -> E is a little larger, 5.
Because C -> D is uphill and D -> E is uphill, consecutive uphill are a doozy for the enemy and so he has a weight of 9.

In other words, any weight along the path doesn't just depend on where you were previously, but where you were before that too. It can even extend farther back several levels like going uphill 3 times in a row is a real doozy and you must pay an extra penalty for that too.

I've thought of a bunch of stuff, but backtracking requires a lot of memory especially when the graph gets large and so far the only solution I've come up with is to just test all possible paths (since enemies are usually close to the player the graph doesn't get too large but for even small graphs testing all possible paths takes too much time).

Has anyone seen a problem like this before? Is there an algorithm for it? Algorithms like Dijkstra, Viterbi, etc. don't work because they assume only one weight per edge.

Thanks!
0

Share this post


Link to post
Share on other sites
An issue I see is, that you add new criteria to an optmization problem. Doing this is always dangerous, because you could create a NP-hard problem faster than you think. So, maybe your problem is already NP-hard, in this case you will have a really hard time to find a fast solution [img]http://public.gamedev.net//public/style_emoticons/default/tongue.png[/img] Edited by Ashaman73
0

Share this post


Link to post
Share on other sites
If all you're doing is modeling terrain elevation costs in a path, I don't see why you need such complicated conditional edge weights. You could easily account for elevation cost in a graph by simply defining a baseline cost between two nodes at the same elevation. If the elevation differs, simply add or subtract from that base cost to simulate increased or decreased difficulty of that transition (be sure to never go negative, or else Dijkstra or A* is no longer correct!).

Modeling the problem in this manner allows you to use local information at each step to build up a more global solution without having to inspect the actual decisions made to determine future values. Your path cost here means the sum total of the "ease of travel" and if you minimize this cost, your path will be the one that is easiest to follow.
1

Share this post


Link to post
Share on other sites
[quote name='alvaro' timestamp='1348731175' post='4984257']
You can split node "D" into "D from A", "D from B" and "D from C", because those seem to actually be different states. Then Dijkstra will work again.
[/quote]
Was my first thought too, but then you need to split E and after that, the following nodes ...
This is the killer argument:
[quote name='yadango' timestamp='1348728643' post='4984250']
In other words, any weight along the path doesn't just depend on where you were previously, but where you were before that too. It can even extend farther back several levels like going uphill 3 times in a row is a real doozy and you must pay an extra penalty for that too.
[/quote] Edited by Ashaman73
1

Share this post


Link to post
Share on other sites
Exactly guys! You guys are all right on it... it would either require a massive expansion of nodes or probably a metaheuristic to solve! I'm just silly lol. Ever had that thought where you say ok I'm going to add a little twist to an existing problem to see if I can get better results only to find out that what you're trying to do is silly or impossible :-)? I'm surprised I couldn't find anything on google about this type of problem... "Graph" "shortest path" "multiple weights" "conditional weights" etc... turned up nothing! Edited by yadango
0

Share this post


Link to post
Share on other sites
If the path history can affect the weight in arbitrary ways, I think you'll have to use something like backtracing, and you are in NP territory. If you can summarize the feature of the path history into a few possibly values (say, number of preceding uphills), then unfold the nodes as being different if you arrive there with different values of that feature.

I don't think there is anything else to this problem. Edited by alvaro
1

Share this post


Link to post
Share on other sites
Thanks alvaro,

Thanks to you guys I think I found a journal article on the topic: "Finding the Shortest Path in Dynamic Network using Labeling Algorithm." The thing I was looking for was a shortest path algorithm with "nondeterministic weights." The problem is actually quite common (happens with traffic as weights change with time) and has a ton of research published on it. I thought the problem I mentioned might be intractable too but it turns out it is not [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img]. It says that as long as the weights are known ahead of time (not random as with traffic and can be listed or represented using a function), the problem is not intractable. [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img] Though, yeah, having to backtrack to find out what the possible weights are is going to slow down an already slow polynomial time algorithm he he he.

Thanks! Edited by yadango
0

Share this post


Link to post
Share on other sites
I'm struggling to follow your reasoning as to why you have to look backwards to determine the cost of the path going forwards. If your weights are done correctly, getting to node D includes the cost of getting to any of the previous nodes that made up the path. Unless your movement along the terrain can cause a landslide that affects the path ahead I don't follow your line of thinking.

Are your weights taking into account the full cost of traversing the node, such as slope, softness of terrain etc or are they just taking into account the distance?
1

Share this post


Link to post
Share on other sites
Another possibility is to add an additional dimension, exhaustion, for each node. Say exhaustion can have values 0, 1 or 2. Any uphill path goes up a level of exhaustion (capped at 2). Any downhill path goes down a level of exhaustion (capped at 0). Any flat path... not sure. Stay the same? Or maybe have values 0,1,2,3,4,5 and up = +2, down = -2, flat = -1?

In any case, depending upon the exhaustion level you could modify the outgoing costs, e.g. triple if very exhausted. This would not be an NP-hard problem, just a problem with an x times bigger search space.
0

Share this post


Link to post
Share on other sites
Theoretically, you can prune the graph so that D does not exist anymore and your paths are now A-E, B-E, C-E with their associated costs. The trick is identifying these situations and restructuring the graph on the fly. This example is also potentially overly-simplistic and this solution would get brittle quickly.
0

Share this post


Link to post
Share on other sites
[quote name='jefferytitan' timestamp='1348802773' post='4984579']
Another possibility is to add an additional dimension, exhaustion, for each node. Say exhaustion can have values 0, 1 or 2. Any uphill path goes up a level of exhaustion (capped at 2). Any downhill path goes down a level of exhaustion (capped at 0). Any flat path... not sure. Stay the same? Or maybe have values 0,1,2,3,4,5 and up = +2, down = -2, flat = -1?

In any case, depending upon the exhaustion level you could modify the outgoing costs, e.g. triple if very exhausted. This would not be an NP-hard problem, just a problem with an x times bigger search space.
[/quote]

How is that another possibility? That's exactly what I suggested...
0

Share this post


Link to post
Share on other sites
[quote name='alvaro' timestamp='1348827703' post='4984676']
How is that another possibility? That's exactly what I suggested...
[/quote]

The way I read your suggestion was exponentially branching based on the full search history. My suggestion is that the exact path is likely not to matter, only how tired you are at a given node. This means you can have different costs from node D to E for each of a fixed number of tiredness values without the need to stretch it into NP territory. Rather like an earlier thread about pathfinding for vehicles with momentum.

I looked back at the posts one more time, I see where you mention a similar scheme. I'm not sure whether I read your post before you edited it, or perhaps I dismissed the post the moment it mentioned NP.
0

Share this post


Link to post
Share on other sites
[quote name='jefferytitan' timestamp='1348831213' post='4984683']
I looked back at the posts one more time, I see where you mention a similar scheme. I'm not sure whether I read your post before you edited it, or perhaps I dismissed the post the moment it mentioned NP.
[/quote]

Yeah, I guess I shouldn't have said two separate things in one paragraph. Plus, you probably expressed the idea better.

Anyway, that's probably the way to go.
0

Share this post


Link to post
Share on other sites
[quote name='Postie' timestamp='1348799916' post='4984568']
I'm struggling to follow your reasoning as to why you have to look backwards to determine the cost of the path going forwards. If your weights are done correctly, getting to node D includes the cost of getting to any of the previous nodes that made up the path. Unless your movement along the terrain can cause a landslide that affects the path ahead I don't follow your line of thinking.
[/quote]

Correct. Yeah, if say using squared RMS (square of euclidean distance), you really pay for doing large uphills in the first place, so even something simple like that should take care of things like the one large hill + one small hill is worse than two medium size hills of the same distance problem. I was just trying to extend the problem in a different way to see where I could go with it he he he.

So in general, after reading the research on these types of problems, I've accepted that you should never break Bellman's Principle unless you absolutely have to. It's fun stuff though... there are some really interesting problems that break Bellman's Principle (mainly time-based things like traffic and music performance). Edited by yadango
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