Are there any good heuristics about picking the 'best' A* path where the complete path doesn't exist? I was thinking that the shortest overall path + heuristic distance that ends up adjacent to an enemy unit might work, but is there a better heuristic? The only other one I can think of would be to calculate the shortest path without any obstructions, but wouldn't that often come to the same path? In this context, the most likely reason for a block would be enemy units in the way, so a reasonable initial path would be to advance towards the objective and take ground as quickly as possible. Thanks, Ralph

I believe the node with the best final cost in the closed list after the search fails can still be used to generate a path to the best place it was able to get to.

In an old RTS game we did:

1) try to find path
2) if no path exists, ignore certain types of blocking entities (walls, buildings) and repath

the #2 step gets you what we called an "approach path". The units will basically path around terrain but otherwise beeline to the destination.

If you mean "user clicks on non-pathable area" the typical solution is to make the cursor change state to the "you can't go here" cursor and just not respond to clicks. Otherwise you can find the closest valid point towards the unit from the invalid destination and path there instead.

-me

If the path is blocked by an enemy that can be destroyed then the pathing is fairly simple. You simply have a tiered system of objects. First try to path with everything in the way, next remove objects that are friendly and can be persuaded to move. Next remove objects that are neutral and can be destroyed or opened. Finally remove objects that are unfriendly and can be "persuaded" to move in other ways. If the path can still not be made, path to the closest reachable location.

(EDIT: this is exactly what Palidine said so nevermind.)

Quote:

Original post by Palidine In an old RTS game we did: 1) try to find path 2) if no path exists, ignore certain types of blocking entities (walls, buildings) and repath the #2 step gets you what we called an "approach path". The units will basically path around terrain but otherwise beeline to the destination. -me

That's what I meant by no obstructions, sorry I wasn't clearer. I was thinking that the other method I described might be faster to calculate for the normal case.

Sorry, I forgot to set the context. This is for a hex-based wargame (Operational Art of War III) so there are very few cases where the terrain would be fully blocked, it's almost always going to be enemy activity blocking it, and I was thinking that I could shave some cycles by cheating instead of doing the full requery to the pathfinding engine for the fully blocked case.

Units shouldn't ever block path finding. If they do, you're going to end up with horrendous pathfinding problems. If you want to, unit/unit avoidance should be handled by a seperate dynamic avoidance routine; 99% of RTS games completely ignore this all together.

In a typical RTS there is zero collision between moving entities. 99% of the time the user will interpret interpenetration as occlusion and their mind will tell them that entity A is behind entity B instead of inside it.

Gameplay-wise users get infinitely more pissed off with dynamic avoidance than with units just running through each other. Dynamic avoidance means slow unit response time (you need to shuffle stuff out of the way, delay moves, etc). Interpenetration can look bad sometimes but makes the gameplay smooth and reactive which is what RTS games are all about.

Something that works is a half-breed approach: idle units will move out of the way of pathing units, but pathing units will not avoid idle units. So basically, that which the user intends to move moves fast and direct; that to which the user is not paying attention gets out of the way.

-me

Quote:

Original post by Palidine Units shouldn't ever block path finding. If they do, you're going to end up with horrendous pathfinding problems. If you want to, unit/unit avoidance should be handled by a seperate dynamic avoidance routine; 99% of RTS games completely ignore this all together.

I agree, but I'm not doing an RTS game, I'm working on an old-fashioned Hex-based (and turn-based, sorry) wargame (Operational Art of War III.) Pathfinding, and AI in general for me has different problems than you find in a typical RTS does.

I've got several references that talk about how to program yet another RTS, but I don't see many references for this type of game, and the problems I'm running into are a lot different.

I took over programming about a year ago on what is a mature game, and I'm working on improving the gameplay, interface, and on updating the AI to be the best it can be. Speed is important, it's playing on a 300x300 grid with up to 2000 units on a side, but I'm more interested in providing a challenging and fun experience.

Thanks for your input,
Ralph

You could make the movement cost through enemy units larger than a clear hex, so the path would be found. The cost could vary based on the stregth of the units in the hex, so the best path would be through the most weakly defended areas. I'll have to remember this for my war game code!

Quote:

Original post by ID Merlin You could make the movement cost through enemy units larger than a clear hex, so the path would be found. The cost could vary based on the stregth of the units in the hex, so the best path would be through the most weakly defended areas. I'll have to remember this for my war game code!

hrm... yeah. You might be able to get something with an Influence map (basically another grid of your game, each unit applies an influence curve over a certain radius that is additive with the curve of other units, if you have just 2 sides you apply one side as positive and the other as negative). You could then path along contours of the influence map.

It really depends on what you want the behavior of the "best" path to be. Do you want an approach path? Do you want an approach path to a certain point after which you want an alternate route, etc.

From the player's perspective you probably just want to completely invalidate unreachable cells so the player is constrained to valid cells. For the AI, this is a higher level problem.

At what level is this solution meant to work? With the player's units, the AI's units, or both? I guess, just define the problem a little more specifically: is this an RTS, a turn based game, etc. At the end of the day the player's units should go _exactly_ where the player expects them to go.

-me

Quote:

Original post by Palidine Quote: Original post by ID Merlin You could make the movement cost through enemy units larger than a clear hex, so the path would be found. The cost could vary based on the stregth of the units in the hex, so the best path would be through the most weakly defended areas. I'll have to remember this for my war game code!

I'm not sure that would work for me, but I'll think about it. The problem is that I'd have to drive up the maximum path cost to where it would have to explore a lot more of the map.

Quote:

hrm... yeah. You might be able to get something with an Influence map (basically another grid of your game, each unit applies an influence curve over a certain radius that is additive with the curve of other units, if you have just 2 sides you apply one side as positive and the other as negative). You could then path along contours of the influence map. It really depends on what you want the behavior of the "best" path to be. Do you want an approach path? Do you want an approach path to a certain point after which you want an alternate route, etc.

It's turn-based. The player's solution is simple, the AI is harder. I definitely plan to use influence maps for the high-level AI to identify choke points, etc. That's a ways off though. I hadn't thought about using them for the lower level AI. Your question about what 'best' is got me thinking. I'm not sure what 'best' is. I probably just want an approach path right now. Later on, I'll add in the coherent strategy for picking my battles.<g>

Right now, most of the AI acts either unit by unit, or formation by formation. Making the strategic AI that will coordinate the battles and optimize strategy is going to be the hardest part.

Thanks,
Ralph