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

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?

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.

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.

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.

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.

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.

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.