• Create Account

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

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

3 replies to this topic

### #1SillyCow  Members

1327
Like
0Likes
Like

Posted 05 September 2012 - 09:41 AM

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 browser game: Vitrage - A game of stained glass

My android games : Enemies of the Crown &  Killer Bees

### #2Wizuriel  Members

150
Like
0Likes
Like

Posted 05 September 2012 - 12:25 PM

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?

Edited by Wizuriel, 05 September 2012 - 12:28 PM.

3522
Like
3Likes
Like

Posted 05 September 2012 - 12:29 PM

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-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
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!"

### #4jefferytitan  Members

2508
Like
1Likes
Like

Posted 05 September 2012 - 03:32 PM

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.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.