Jump to content
  • Advertisement
Sign in to follow this  
captain_crunch

Extending AStar with vehicles and terrain costs

This topic is 3750 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello! I am creating a game where agents move across a tiled map with different terrain (costs). There are various types of vehicles available scattered about the map. Some vehicles have off-road capabilites while some are much faster on roads. When the agent must go to a specific destination B, it must decide which option is better (shortest travel time): 1. Going by foot to B 2. Moving by foot to vehicle V1 some distance off and driving to B 3. This is a more advanced requirement, but it would be cool if the agent could take a fast car to a depot somewhere and enter a rover vehicle for a drive into the mountains. 4. This requirement is also in the advanced department, but sometimes the agent needs a vehicle with high load capacity so it should pick the truck over the motorbike. In other situations the reverse would be the case. Since it is a game, it is not necessary to pick the optimum solution every time, it is better to trade off with performance... Currently, I have some heuristic functions (outside AStar!) that try to answer the questions by estimating a travel time for each vehicle on the map, but they disregard the terrain, since I want to avoid having to calculate a path for every vehicle on the map. So the functions cannot pick the off-roader over the road vehicle when going into the countryside. Is it feasible to extend AStar with these kinds of features, or should they be kept separate from the AStar algorithm? Suggestions are welcome...

Share this post


Link to post
Share on other sites
Advertisement
That isn't really an extension to A*; it's pretty much what A* does. You just need to think of it slightly differently; don't think of it as an algorithm for pathfinding on a map, but an algorithm for pathfinding within a problem space. Then, instead of the only state changes (edges) available being 'move north', 'move east', and so on, in some nodes you have 'enter vehicle' and 'leave vehicle', which alter the subsequent cost of 'move north' etc.

You may conceivably want to look at my LPC astar implementation for an example of a version that, while it's used for map pathfinding, is designed to be fully general for application to more abstract problems like this one.

Share this post


Link to post
Share on other sites
OK, I had a look at your code but I am still trying to wrap my head around this.

I want AStar to return the path that is slightly longer to get to the vehicle that will drive to the destination faster. To do this, I would need to change the heuristic function h that rates the potential nodes to pick next. Otherwise, AStar will always go straight to the destination, because the nodes nearer the destination will score higher.

What should h look like then?

Share this post


Link to post
Share on other sites
Really, I'd say you want to perform the A* search across potential states, not potential locations. This means that being in Location X in Vehicle A is a different node in the search to being in Location X in Vehicle B. The node traversal costs and distance heuristic will be different depending on which vehicle you're in. Then everything else should Just Work™.

If it helps, imagine the choice of vehicles (including being on foot) as a 3rd dimension overlaid on the existing 2D map. Only locations where there is a vehicle present allow you to move in that 3rd dimension.

Share this post


Link to post
Share on other sites
That's a good way to think about it.

But I still doubt that AStar is able to find a path that goes out of its way to find a vehicle first, without modifying h.
Otherwise the algorithm will just seek straight to the destination, disregarding the extra dimensions.

In my mind, h would need to incorporate both the current distance to the destination (which is standard) as well as the current distance to all vehicles on the map plus an estimate of driving time to the destination in that vehicle.

Share this post


Link to post
Share on other sites
A* doesn't go "straight to the destination"; plain old best-first search does that, and its failure to optimally solve problems like yours is why A* exists.

Your h does need to take into account the cost of the entire path to the current node; if it doesn't, presumably meaning that all it's working with is the estimated cost to goal node, then it will behave like BFS and generally fail on this problem. If cost to current node is taken into account, then A* will explore a 'fan' of problem space directed toward the goal, and will find your vehicles without any need for them to be written into h. (Given that the vehicles are in the graph as we've been discussing.)

Share this post


Link to post
Share on other sites
Since you're trying to minimize travel time your heuristic and cost functions should be in terms of time, not distance.

An admissible heuristic will always result in A* (or related algorithms) finding the optimal path. A heuristic is admissible if and only if it always underestimates the total cost to reach the goal.

If the heuristic is not admissible, then the paths it finds will still always be at least as close to optimal as the amount that the heuristic overestimated a path length.

Share this post


Link to post
Share on other sites
In agreement with all of the other posts.

However, if processing is an issue, and you're absolutely keen on avoiding computational complexity, you may want to consider a higher level of abstraction for heuristics BEFORE you do your final A* algorithm.

This heuristic might be (for example) making a best guess of how far away the quickest vehicle is based on the average intervening terrain, and so on.

This pulls your in-game A.I. away from purely deliberative agency to more of a BDI model using rough heuristics to make best guesses

I say this because you specifically cite a need to avoid computational complexity, and the point that you don't need to absolutely always take the most efficient path.

If you're looking for REALISTIC SEEMING behaviours, you actually want folks to make poorer decisions sometimes, and more generic BDI agents are good for this.

Share this post


Link to post
Share on other sites
Quote:
Original post by corsarius
However, if processing is an issue, and you're absolutely keen on avoiding computational complexity, you may want to consider a higher level of abstraction for heuristics BEFORE you do your final A* algorithm.

This heuristic might be (for example) making a best guess of how far away the quickest vehicle is based on the average intervening terrain, and so on.



This is actually what I have right now, a routine that picks vehicles and destinations and then asks A* for the simple paths between points. It works fairly well.

Except for estimating the intervening terrain. Consider the case of a road winding in rough terrain - this would seem pretty hard to estimate. That's what brought me to thinking that integrating with A* would be a better way to go.

I want to thank everyone for their contributions, I made some tests and will now go away and see if I can make it work.

Share this post


Link to post
Share on other sites
One thing you might consider is adding in a multiplier when figuring your heuristic.

Standard rate of movement = 1.0 * weight

Movement in a car is .6 * weight

Movement in a truck is .75 * weight

Movement n a motorcycle is .35 * weight

So when finding your path, you would use distance = modifiedSpeed * weight.

So in an example where you are going 5 nodes, then can get in a car, then go 5 more nodes, or else go 7 nodes on foot, or else go 3 nodes, then 10 nodes in a motorcycle, assuming all the nodes have the weight of 1.

on foot 7
in car 5+(5*.6) = 8
in motorcycle = 3 + (10*.35) = 6.5

The motorcycle would win, so the NPC would run to the motorcycle and then drive to the goal.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!