Pathfinding: detecting when a group of units has reached the target.

Started by
2 comments, last by jefferytitan 11 years, 7 months ago
When issuing a goto command to a group of units, I just issue the same go-to-tile command to all of them.
Once the first unit has reached the target tile, it effectively blocks it by standing on it.
The rest of the units in the group remain in an endless pathfinding loop, wasting precious CPU cycles to get closer to a point they cannot reach.
Another problem is that they make a very long pathfinding calculation because other units ,which are standing next to the target, are blocking them (they just go deeper and deeper Into a* until they exceed the iteration limit. This results in a paradox were units standing closer to the target make heavier calculations to reach the target then when they were further away. ( when they were standing the further away their comrades were not yet there to block them)
So what I am looking for is a good stop condition which tells the unit it should stop trying to improve it's position.

My Oculus Rift Game: RaiderV

My Android VR games: Time-Rider& Dozer Driver

My browser game: Vitrage - A game of stained glass

My android games : Enemies of the Crown & Killer Bees

Advertisement
Can you check if the friendly unit blocking your path is on your goal square? If so report back that you reached you're goal?

Edit: or can you make friendly units push other friendly units out of the way?
I think it isn't as much the stop condition that is at fault as a couple of your premises on how to move. If you are pathing around people who are likely to not be there by the time you get there, that is a waste. Let them path through a square that is occupied but don't let them MOVE into a square that is occupied (and repathing at that point, if necessary). Also, don't have all of them go to the specific point. After all, you are not really wanting them to go to that specific point, you want them near that point. Therefore, the stop condition should simply be if they are in the area of that point. Based on the number of units in the group and the typical distance you want them to stand from each other when stopped, come up with a formula to convert the number of units into a radius. Your stop point per unit is now "inside n units from the assigned point".

Of course, that means that first arrivers take the near side and late arrivers have to go around. Therefore, you can move the "real" stop point to a distance just slightly beyond the click point, aligned with the vector between the center of mass of the group and the actual click point. That is, when you click on a spot, drop a line between the center of mass and that point. Take that direction and push the "actual" center point out beyond the click point in that same line... perhaps 1/2 the radius calculation that you did earlier. That way, people will tend to collect near the actual click point as they arrive inside that circle.

I'm just making this shit up as I go, but you can see that there are options to be had in "solving" the problem.

Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-founder and 10 year advisor of the GDC AI Summit
Author of the book, Behavioral Mathematics for Game AI
Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

Alternately you may want to use formations. Give them each a target that matches their position in the formation, centred around the target. And if they have been within radius x of their target for time t and the target has a friendly on it.. stop pathing.

This topic is closed to new replies.

Advertisement