next »

[toipot]

I've been trying to implement some kind of formation controls in my game today, where issuing a move order to a group of units will lead them to nicely form up without bumping into each other too much and coming to a standstill. As an example, I'm trying to avoid solutions for the move orders that look like this:

Bad move orders

This is the first time i've played around with this kind of problem, but I've managed to come to (I think) an ok solution using the Gale-Shapley Algorithm to match up ships to optimal target locations. The optimum solution is found using the difference between the ship's distance from the ship Center of Mass and the target location's distance from the target center of mass. Pseudocode wise:

Code:

Vector shipCoM = (0,0);
for each selected unit
{
    shipCoM+=unit.Position;
}

shipCoM /= numberofships;

Vector targetCoM = (0,0);
for each available target location
{
    targetCoM+=targetPosition;
}

targetCoM /= numberofships;

 Then the match quality between any given ship and a target location is given by (smaller the better)

Code:

 Vector difference = (unit.Position - unitCoM) - (targetPosition - targetCoM);
 float quality = dotprod(difference,difference);

Using Gale-Shapley with this I get move orders that look a little nicer, with less path crossings than with just using distance to target as a fitness function (see bad move orders  ).

Better move orders

But what i'm really trying to do is minimise the number of path crossings, and there are still plenty of those using this method. Does anyone know of a neater way of accomplishing this?

Ideally I'd like the units to move in formation enroute to the destination also, but lets go one problem at a time  

[Fallsburg]

Ideally I'd like the units to move in formation enroute to the destination also, but lets go one problem at a time 

I think if you solved this, that your problem would be solved.  If an order is given for a formation to move, do just that move the formation.  Units should know that they are in a formation and their relative position to the centroid of the formation, and try to keep that formation throughout the move.  Of course, if they hit a choke point smaller than their formation then all bets are off, but that's going to be true for any algorithm.

[rivon]

Kinda like that. Set the target point as target for the whole formation. The target of every soldier would then be calculated as formation target+soldier's position in the formation. If there was an obstacle everyone would try to get as close as possible to his own target. Once close enough, he would stop. Then, if you target some place in the open, everyone would move to their exact place in the formation again.

[toipot]

Ok, I see what you mean but i'm not sure if it entirely solves the problem. I may just be overcomplicating the situation though! 

The units are actually only loosely bound to the formation for the duration of the move (in fact, at the moment the units aren't individually aware that they're in a formation, but that can be fixed). So it's possible to just give them 'position numbers' in the formation, but the problem is the same; figuring out which position number should be assigned to which unit so as they don't all run into each other when they take up their place in the formation.

The target of every soldier would then be calculated as formation target+soldier's position in the formation.

This is pretty much what I do now, except this is done when the move order is made, then the units all individually proceed to their targets.
I've found that without some sort of sorting algorithm to match units to targets though, they all end up crashing together in a confused mess  . Those 'bad move orders' show what kind of moves they try to take.

[toipot]

My algorithm just returned this solution for movement positions for example,

This is a pretty efficient solution in terms of overall distance moved, but there is a good chance that ships a and b are going to bump into each other on the way and end up knocking other objects around.

By eye I can see that my ideal solution would be more like
a ->1
b ->2
c ->3

etc. I dont know if there is a nice method for finding these kind of solutions  

[rivon]

Well, my solution would work for formations which are always rotated the same. For example a ring where everyone is always standing at a specific angle to the center of the ring and at a specific distance.
However, if your formations get rotated differently, then it's understandable that there will be overlaps in the paths.

I think I have a solution to that though. It seems that the rotation of the formation gets calculated as the angle of the vector pointing from the average position of all the units to the target, right? Then I think the solution is quite simple really. If the difference between the current angle and the target angle is bigger than 90 degrees, then just reverse the "indices" of the units. So a unit at the right end of the "arrow" would get assigned the leftmost position in the formation (which would in fact now be the one on the right, after the more than 90deg rotation). If the difference between the current angle and the target angle is smaller than 90deg, then do nothing. Everyone keeps their position in the formation and just moves to the different target position.

[_Tommo_]

I'd create a "Formation" object which pathfinds to the goal, then I'd ask very nicely to each Unit inside it to try and stick to relative points in the formation as it moves, again using pathfinding.
It could work

[Klaim]

I'd create a "Formation" object which pathfinds to the goal, then I'd ask very nicely to each Unit inside it to try and stick to relative points in the formation as it moves, again using pathfinding.
It could work

Would do the same, actually I thought it was a problem solved long time ago.
More advanced ways to do this include a grid system that make sure every entity are always placed relatively to the others and their original distance, which make them look like thay are a grid moving.

[toipot]

I think I have a solution to that though. It seems that the rotation of the formation gets calculated as the angle of the vector pointing from the average position of all the units to the target, right?

Unfortunately not It looks that way from the pictures, but that's just the default. By holding right click and pointing in a direction you can alter the orientation (think total war orientation).

For example, an arrow pointing back in the direction of motion

I'd create a "Formation" object which pathfinds to the goal, then I'd ask very nicely to each Unit inside it to try and stick to relative points in the formation as it moves, again using pathfinding.
It could work

I was trying to avoid adding an overarching formation class due to how temporary these formations are, and try and do everything with move orders (potentially waypointed) and a bunch of flocking behaviours.

At any given stage of the movement, some units could be lured off, killed, move to a different group, or jump out of the level, and as soon as the formation gets in range of an enemy, it'll break up in order to try and encircle the enemy units. So I was trying to avoid being too strict with positioning and just give out move orders to targets optimised such that we can minimise logjams.

Maybe i'm just being too fussy, stricter positioning would probably look better in motion too  Although I'll still need some sort of algorithm to assign positions in the formation class to each ship.

[_Tommo_]

...

Maybe i'm just being too fussy, stricter positioning would probably look better in motion too   Although I'll still need some sort of algorithm to assign positions in the formation class to each ship.

It wouldn't be really "strict": the Formation goes merrily along its way, while Units try to keep their place in it.
A Formation doesn't even know which Units it contains, it's more like a placeholder for unified pathfinding

ie. when you select some units and then right-click:
-you create a Formation (with the required shape) and use that to pathfind to the destination
-notify each Unit about the new Formation and their relative position to it; it's as simple as

Code:

//inside Formation
for( each selected Unit )
   unit->onFormationInitiated( this, formationPosition - unit.position )

-start the Formation movement

then, any Unit that has a pointer to a Formation (read: is assigned to a Formation) computes its new relative position using the Formation matrix and pathfinds to that, ie:

Code:

if( mFormation )
   target = mFormation->getLocalPosition( mFormationOffset );

If it gets attacked, killed, misplaced or whatever, it's up to it - it sets the Formation pointer to NULL and it's free to do whatever it wants.
The Formation and the other Units wouldn't even know.
Which is very stupid too - you could use the Formation object to broadcast a "help" signal to the other entities

EDIT: I've noticed that the 2nd pass actually has the same problem you solved at the beginning
So well, you have to assign the formation-relative points using the algorithm from the OP

[Pishtaco]

Just thinking about the algorithm for finding the straight-line paths, I realize that you would prefer to have a neat algorithm, but have you considered the non-neat, brutal ones?

For example, let's suppose that the formation you're moving into is always more-or-less in a line (rather than, say, a rectangular block). For simplicity we can always assume that the vector from the centre of the ships to the centre of the targets is horizontal. You could just order the ships and targets by their vertical positions, and then match each ship to the corresponding target.

Or you could take your current algorithm, and find all pairs of ships who might collide. Then randomly choose such a pair, and swap the ships over (as long as this doesn't make some overall metric much worse). Do this twenty times. I imagine that most of the time you will get a decent matching at the end.

[toipot]

It wouldn't be really "strict": the Formation goes merrily along its way, while Units try to keep their place in it.
A Formation doesn't even know which Units it contains, it's more like a placeholder for unified pathfinding

It's probably a pretty good idea, although I think you'd definitely have to have the formation keeping track of how many members it has, in order to free it once it's empty. I'll give this a go, but as you say it doesn't really solve the problem of how to move the units into formation in the first place.

For example, let's suppose that the formation you're moving into is always more-or-less in a line (rather than, say, a rectangular block). For simplicity we can always assume that the vector from the centre of the ships to the centre of the targets is horizontal. You could just order the ships and targets by their vertical positions, and then match each ship to the corresponding target.

This isn't a bad idea, but I can't guarantee that the formation can be nicely rotated into a line so that sorting would work, for example, this is perfectly possible:

In fact here my algorithm seems to give a pretty good solution (even with the line crossings!  ). The ships in front move over to the far side of the formation, leaving the further behind ships to take up their places without too much bumping. This is a bit of a fluke though, I can find plenty of angles where my algorithm results in plenty of collisions :D. With the vertical sort, ships a and b would almost certainly be bumping into each other.

Or you could take your current algorithm, and find all pairs of ships who might collide. Then randomly choose such a pair, and swap the ships over (as long as this doesn't make some overall metric much worse). Do this twenty times. I imagine that most of the time you will get a decent matching at the end.

I'm starting to think this is probably the way forward, and i'm not exactly short of cpu so a couple of swaps is probably no problem.
Coupled with the formation suggestion, I think I can probably get things running a bit smoother. Thanks!

[kurtkz]

Would it not be possible to stagger the movement of the units over time? Maybe try to sort the units along the longest axis and move them to the furthest target along that axis? That's probably simplifying your original problem but perhaps it's an avenue worth exploring?

Or is it absolutely essential to move the units together?

[JobLeonard]

How about trying to minimise the difference in vector angles for the different units? In other words: they all try to move in roughly the same direction. Then crossing paths are less likely, as that means bigger angles. Maybe combined with a shortest path for a minimal total cost.

Anyway, I think you're kind of missing the point of using formations from a tactical point of view: letting tougher units form a barrier for weaker units, or (when using a V formation) enveloping other units/formations. So it's very important formations are followed during movement. That doesn't sound temporary at all, so maybe a Formation object isn't so bad. You could even have the formation automatically rearrange itself if a unit leaves the group (due to death, or the player selecting and giving it a different move command) - remove those units from the formation object and re-arrange. Actually, I recall some games doing this, and doing it hopelessly wrong because everytime a unit was removed all units got a new spot at random instead of just moving a little bit to fill the gap.

Also, just because two lines cross doesn't mean the units have to cross - they can reach that point at different times. Pretty obvious, but it might be worth mentioning - if you go with the persistent Formation angle, you could account for when a unit is expected to be where and compare that to the other positions.

[toipot]

Would it not be possible to stagger the movement of the units over time? Maybe try to sort the units along the longest axis and move them to the furthest target along that axis? That's probably simplifying your original problem but perhaps it's an avenue worth exploring?

It's certainly possible, but I'd be worried that formation manoeuvres would just take forever as many of the units wait for traffic. It's worth keeping in mind though, especially as I do need to implement some sort of traffic avoidance.

How about trying to minimise the difference in vector angles for the different units? In other words: they all try to move in roughly the same direction. Then crossing paths are less likely, as that means bigger angles. Maybe combined with a shortest path for a minimal total cost.

Nice idea, try and favour parallel lines. I'll try this along with the brute force method (swapping pairings).

Anyway, I think you're kind of missing the point of using formations from a tactical point of view: letting tougher units form a barrier for weaker units, or (when using a V formation) enveloping other units/formations. So it's very important formations are followed during movement. That doesn't sound temporary at all, so maybe a Formation object isn't so bad.

Well, i'm trying to avoid combat just being between fixed formations. At the moment, when a formation gets in range of an enemy, the formation breaks into individuals to try and simulate some kind of semi-realistic dogfighting. The player is only supposed to be able to control the units up to a point (hopefully to make it feel more like giving orders to real, intelligent soldiers). So i'm mainly playing with formations in order to 'line up' your units before engaging the enemy. I don't know if it's gonna work all that well yet, but we'll see! 

You could even have the formation automatically rearrange itself if a unit leaves the group (due to death, or the player selecting and giving it a different move command) - remove those units from the formation object and re-arrange. Actually, I recall some games doing this, and doing it hopelessly wrong because everytime a unit was removed all units got a new spot at random instead of just moving a little bit to fill the gap.

Yes, exactly I'm hoping that some variation on the algorithm above should handle that quite well.

[BorisTheBrave]

I think you are making life hard by trying to decide it all upfront. As I understand it, most RTSs set goals for individual troops, then as they move, they apply flocking algorithms to avoid walking into each other in the short term.

If you did that, and periodically re-applied your matching algorithm, then it would effectively fix the case where the existing matches don't make sense because they cross each other, because in the process of routing around each other, they will naturally change what the optimal matching is to be consistent with their local decisions.

[JobLeonard]

I believe there's also a least-energy-path method that helps troops avoid places they should (by marking other units and places they can fire on as high-energy cost tiles). Although that might apply more to harvesters

[toipot]

I think you are making life hard by trying to decide it all upfront. As I understand it, most RTSs set goals for individual troops, then as they move, they apply flocking algorithms to avoid walking into each other in the short term.

If you did that, and periodically re-applied your matching algorithm, then it would effectively fix the case where the existing matches don't make sense because they cross each other, because in the process of routing around each other, they will naturally change what the optimal matching is to be consistent with their local decisions.

I tried this, and the units moved to the target position no problem, but the difficulty was in making them move to the target position in formation as the flocking made them jostle about, and when free move at max speed to the target ignoring their relative place in the formation.

So to try and get nice formation movement, I tried to take as the formation target position the current formation centre of mass, but perturbed towards the final target destination by some amount proportional to the max velocity of the units. Like in this image:

Which made the units move in a reasonably realistic manner, moving in formation, and also meant that I can change the orientation of the formation as it moves, such that the formation orients itself along the direction of motion until it gets close to the target, where it rotates to the orientation requested by the player. So this all worked quite nicely actually.


Unfortunately though, this kind of formation movement seems to make life much more difficult for the player in my prototype. The hard part seems to be in deciding upon what level to handle formation movements. My game involves controlling a couple of loosely defined squads of units, so the natural choice of formation level was the squad. In other words, each squad has a formation to try and keep to, meaning that I could have formations of many squads that looked like this (squad number given above the units):

Which looks nice, but makes traffic/collision avoidance much harder. Before the player could control each unit pretty much independently (as I mentioned before, the old formations were very loose) so if a unit got stuck, they could quickly repoint it while the rest of the formation moved happily along it's way. Having formation movement based on CoM though completely screws up the movement if units get stuck in traffic, so I'd need to implement a whole extra layer of traffic avoidance or something to throw units out of the formation if they get too far away.

So in short, I think im gonna give up on nice formation movement (which requires a stricter Formation class) and just use the suggestion of a very loose formation class using flocking to govern movement on the way to the target. Otherwise, as interesting as the problem is, I'm gonna end up adding crazy levels of complexity into something was was meant to be a small part of a short project  

[Gregg Williams]

Are there any RTS games with nice formations?

I'm not that experienced in the genre, mostly having stopped playing it after several years straight of Starcraft, but I don't recall Starcraft or games before it really having much in the way of formations.

[Klaim]

Look at Supreme Commander.