Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length

 
Advanced search

1027464 Posts in 41218 Topics- by 32831 Members - Latest Member: paolo

July 28, 2014, 04:21:49 AM
TIGSource ForumsDeveloperTechnical (Moderators: Glaiel-Gamer, ThemsAllTook)RTS formation movement
Pages: [1] 2
Print
Author Topic: RTS formation movement  (Read 1942 times)
toipot
Level 0
**


View Profile
« on: January 14, 2013, 12:14:11 PM »

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  Grin).

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  Grin
« Last Edit: January 14, 2013, 12:24:08 PM by toipot » Logged
Fallsburg
Level 10
*****


Fear the CircleCat


View Profile
« Reply #1 on: January 14, 2013, 12:40:36 PM »

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

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.
Logged
rivon
Level 10
*****



View Profile
« Reply #2 on: January 14, 2013, 12:52:59 PM »

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.
Logged
toipot
Level 0
**


View Profile
« Reply #3 on: January 14, 2013, 01:16:26 PM »

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!  Grin

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.

Quote
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  Grin. Those 'bad move orders' show what kind of moves they try to take.
Logged
toipot
Level 0
**


View Profile
« Reply #4 on: January 14, 2013, 01:30:16 PM »

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  WTF
Logged
rivon
Level 10
*****



View Profile
« Reply #5 on: January 14, 2013, 02:40:59 PM »

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.
Logged
_Tommo_
Level 8
***


frn frn frn


View Profile WWW
« Reply #6 on: January 14, 2013, 04:05:33 PM »

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 Smiley
Logged

Klaim
Level 10
*****



View Profile WWW
« Reply #7 on: January 14, 2013, 04:15:30 PM »

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 Smiley

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.
Logged

http://www.klaimsden.net | Game : NetRush | Digital Story-Telling Technologies : Art Of Sequence
toipot
Level 0
**


View Profile
« Reply #8 on: January 14, 2013, 04:35:17 PM »

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 Smiley 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 Smiley

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  Smiley Although I'll still need some sort of algorithm to assign positions in the formation class to each ship.
Logged
_Tommo_
Level 8
***


frn frn frn


View Profile WWW
« Reply #9 on: January 14, 2013, 05:03:49 PM »

...

Maybe i'm just being too fussy, stricter positioning would probably look better in motion too  Smiley 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 Smiley

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 Smiley

EDIT: I've noticed that the 2nd pass actually has the same problem you solved at the beginning Tongue
So well, you have to assign the formation-relative points using the algorithm from the OP Smiley
« Last Edit: January 14, 2013, 05:11:13 PM by _Tommo_ » Logged

Pishtaco
Level 10
*****



View Profile WWW
« Reply #10 on: January 15, 2013, 02:59:03 AM »

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.
Logged

toipot
Level 0
**


View Profile
« Reply #11 on: January 15, 2013, 10:14:01 AM »

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 Smiley

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!  Grin). 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!
Logged
kurtkz
Level 0
***

kurtkz
View Profile WWW Email
« Reply #12 on: January 15, 2013, 11:54:02 AM »

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?
Logged

JobLeonard
Level 9
****



View Profile
« Reply #13 on: January 15, 2013, 12:04:59 PM »

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.
Logged
toipot
Level 0
**


View Profile
« Reply #14 on: January 15, 2013, 02:11:39 PM »

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!  Grin

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 Smiley I'm hoping that some variation on the algorithm above should handle that quite well.
Logged
Pages: [1] 2
Print
Jump to:  

Theme orange-lt created by panic