3
\$\begingroup\$

So I've got some units which should move to a specific position which is given by the player. Currently the units can move there by finding a path with the A* algorithm (to be more precise: A* Pathfinding Library for Unity)

I was wondering what the best way to move the units is? When the player has selected e.g. 20 units, some of them are near each other, some of them are far away from the others, what is the best way to navigate them to a single position defined by the user. Obviously they cannot just all have the same target since they would never reach it when the first unit moved to it. Thus what do I have to do? Do I have to assign different targets to each unit or do I calculate the target position relative to the position they were to each other before?

\$\endgroup\$
1
\$\begingroup\$

When you have a group selection and you issue a movement order for that group by clicking, the natural expectation of the player is that the destination point will be the new "center" of the group once they arrive.

One possible approach to this problem is to compute the centroid of the group when the movement order is issued, and then construct a path from that centroid to the clicked location. You can also compute the offsets from the centroid to each unit in the group at the start of the movement order, and store this in some kind of transient "formation" data structure. When units get within a certain distance of the target point -- a good value for this distance could be the radius of the circle that encloses the full unit group(*) -- have them move to the final destination, which you can compute by applying their stored formation offset to the clicked target position.

Of course, it does mean your units will try to clump up into a single tight ball while moving. You can solve this by enforcing proximity constraints, or by use the formation deltas to move the entire group "in formation." Doing either of those raises another question: you computed an A* path from one point to the other, but you aren't moving everybody exactly along that path, so how do you deal with obstacles in the way?

The solution is to employ a simpler form of local pathfinding to move units around local obstructions. Edge-walking (where you simply move a unit around the border of an obstacle until it gets back on the path or strays too far from it) can be useful because it doesn't have nearly the computational cost of A* and it will produce acceptable results for very small search spaces, which is what you're using it for.

This is good, because the main benefit of this overall approach is not doing N A* searches for N units; since A* is computationally expensive, you want to minimize its use. This approach allows you to scale up the number of units in a selection group without negatively impacting search performance (at least not linearly impacting it).

A key thing to keep in mind for pathfinding in RTS games is that a divide-and-conquer approach is going to provide huge wins, especially given the size of RTS maps and the number of pathfinding agents generally involved. Any way you can seize upon to reduce pathfinding complexity or put it into increasing granularity hierarchies will help improve the overall performance of the system.

(*) You may also want to handle "outlier" units (for example, you have five guys close together and one guy really, really far away from the others -- all selected) by adjusting their formation delta to some maximum distance from the centroid. This means the outlier will move in closer to be with his friends by the time the move ends.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.