Tell me more ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 6 down vote favorite

How to represent the following situation best - agent (@) needs to get to the goal($). The path is blocked by a moat(~~~). A rake (or some other device, like waterwalking boots) is available that will make it possible to cross the obstacle. 

.....~~~...   . ground
...=.~~~...   = rake
.....~~~.$.   ~ water
.@...~~~...   @ agent
.....~~~...   $ goal

How to properly pathfind from @ to $ provided there is no immediately available path? Should my path have not only cost but also prerequisites?

UPD: The problem is the goal is not accessible and rake is just one of many possible objects on the map. Question then is "how to make the agent understand that it needs the rake?"

share|improve this question
I think you should clarify your use case because that would affect the approach one takes to solving this problem. For example, if the use case is to calculate paths for enemies then you should probably first see if the goal can be reached currently, if not have the enemies get the rake (ie. the rake IS the goal) and then pathfind to the first goal again. – jhocking May 16 '12 at 13:39

2 Answers

up vote 4 down vote accepted

I'm thinking about a stack of goals, pathfinding will have to be annotated:

  • Start with a goal get $
  • Try find path to $ - path exists with waterwalking capability required.
  • Push goal get waterwalking.
  • Goal stack is now get waterwalking, get $
  • Somehow find that rake gives waterwalking, let's rename it to boat.
  • Path to rake. Top goal reached, pop it from stack, goal is get $.
  • Path to $ - now we have capability and can reach goal.
share|improve this answer
1  
+1 I did something similar with my game, and wrote a little post about it a while back under Unit Tasks – Byte56 May 16 '12 at 13:24
@byte66 doesn't handle special case when there is a path without using rake but, using the rake results in shorter path – Gajoo May 16 '12 at 13:35
@Gajet you're right. Guess will need a different approach for that. – zzandy May 16 '12 at 13:56
It's just a matter of adding additional cost. When you encounter water, add the cost of getting the water-walking item to the path. A* will skip the water-walking until it becomes the cheapest path. – Byte56 May 16 '12 at 16:45
up vote 3 down vote

The whole path finding stuff is just a search for shortest path over a graph. to solve your problem the only change you need to apply is to add some extra edges (representing the path boat can take), and do a simple path find algorithm. it doesn't matter whether you use BFS, Dijkstra or A*, just implement a normal path finding algorithm with some extra edges. for more information about path finding in a graph check wiki page

share|improve this answer
+1 Make your rake a one-way link to the water, with water-to-ground beeing one-way links as well. – Laurent Couvidou May 16 '12 at 12:43
I don't have clear understanding how to bind together geometrical search and feature search. How to go from no path from @ to $ to goto rake, bring it to water, place it, goto $. – zzandy May 16 '12 at 13:03
@zzandy while path finding, for each tile you go to nearest tiles if possible. you just need to add a condition that if the current node is a rake, you can directly add a node from other side of the river to open list. – Gajoo May 16 '12 at 13:06
But what if you can carry the device? I thought that's what he meant (and hence my answer.) – kaoD May 16 '12 at 13:06
Yes, I mean the device can (and must) be caried. @kaoD, your answer does not include the step when an agent gets the idea it needs the rake. – zzandy May 16 '12 at 13:14
show 7 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.