hello everyone,
i'm really confused with flocking algorithm it works right but when i combine it with arrive behaviour it don't look really good! specially in case of direction, units rotates all the time and they don't have balance (forces are not balanced) i changed parameters for 1 hour now but i couldn't get ideal result , i was just wondering how everyone manage group movement and forces between them ! for these specific goals
*units shouldn't overlap(not very precise)
*units should stop when they rich their target ( some times there is already something in target position , and they should solve their problem on their own!
thanks
Group Behaviour (movement) in RTS
You are likely to have multiple problems:
- Wrong, or just unstable, turning computations;
- Badly combined behaviours, none of which is executed properly;
- Almost certainly, overshooting due to lack of deceleration close to the target locations.
Post code in order to look at the issues first hand: details are very important.
- Wrong, or just unstable, turning computations;
- Badly combined behaviours, none of which is executed properly;
- Almost certainly, overshooting due to lack of deceleration close to the target locations.
Post code in order to look at the issues first hand: details are very important.
Author
thanks for your answer here is flocking algorithm that i used and parameter
m_sepw = 1240;
m_alignw = 100;
m_cohesionw = 20;
m_arrivew = 200;
they were all 200 at first place but i changed them for more stability ....
the Whole logic is from ai by example book,
This is Calculation Force function
hgeVector cforce;
cforce =SeparationPlus(GameWorld::GetInstance()->Objects) * m_sepw;
if (!AccumulateForce(force, cforce)) return force;
cforce =AlignmentPlus(GameWorld::GetInstance()->Objects) * m_alignw;
if (!AccumulateForce(force, cforce)) return force;
cforce =CohesionPlus(GameWorld::GetInstance()->Objects) * m_cohesionw;
if (!AccumulateForce(force, cforce)) return force;
cforce = Arrive(m_target, m_Dec) * m_arrivew;
if (!AccumulateForce(force, cforce)) return force;
return force;
//----------------------------------------------------------------------------//
hgeVector Vehicle::SeparationPlus(const std::vector<Vehicle*> &neighbors)
{
Vector SteeringForce;
bool change =false;
//iterate through the neighbors and sum up all the position vectors
for (Vehicle* pV = GameWorld::GetInstance()->CellSpace()->begin();
!GameWorld::GetInstance()->CellSpace()->end();
pV = GameWorld::GetInstance()->CellSpace()->next())
{
//make sure this agent isn't included in the calculations and that
//the agent being examined is close enough
if(pV != this)//&&pV->arrive ==false)
{
change = true;
hgeVector ToAgent =position - pV->position;
//scale the force inversely proportional to the agents distance
//from its neighbor.
double len = ToAgent.Length();
ToAgent.Normalize();
SteeringForce +=( (ToAgent)/len);
}
}
return SteeringForce;
}
//------------------------------------------------------------------------//
hgeVector Vehicle::CohesionPlus(const std::vector<Vehicle*> &neighbors)
{
//first find the center of mass of all the agents
hgeVector CenterOfMass, SteeringForce;
int NeighborCount = 0;
//iterate through the neighbors and sum up all the position vectors
for (Vehicle* pV = GameWorld::GetInstance()->CellSpace()->begin();
!GameWorld::GetInstance()->CellSpace()->end();
pV = GameWorld::GetInstance()->CellSpace()->next())
{
//make sure *this* agent isn't included in the calculations and that
//the agent being examined is close enough
if(pV != this)
{
CenterOfMass += pV->position;
++NeighborCount;
}
}
if (NeighborCount > 0)
{
//the center of mass is the average of the sum of positions
CenterOfMass = CenterOfMass/(double)NeighborCount;
//now seek towards that position
SteeringForce = Seek(CenterOfMass);
}
//the magnitude of cohesion is usually much larger than separation or
//allignment so it usually helps to normalize it.
SteeringForce.Normalize();
return (SteeringForce);
}
//--------------------------------------------------------------------------//
hgeVector Vehicle::AlignmentPlus(const std::vector<Vehicle*> &neighbors)
{
//This will record the average heading of the neighbors
hgeVector AverageHeading;
//This count the number of vehicles in the neighborhood
double NeighborCount = 0.0;
//iterate through the neighbors and sum up all the position vectors
for (Vehicle* pV = GameWorld::GetInstance()->CellSpace()->begin();
!GameWorld::GetInstance()->CellSpace()->end();
pV = GameWorld::GetInstance()->CellSpace()->next())
{
//make sure *this* agent isn't included in the calculations and that
//the agent being examined is close enough
if(pV != this)
{
AverageHeading += pV->heading;
++NeighborCount;
}
}
//if the neighborhood contained one or more vehicles, average their
//heading vectors.
if (NeighborCount > 0.0)
{
AverageHeading = AverageHeading/NeighborCount;
AverageHeading -= heading;
}
return AverageHeading;
}
//----------------------------------------------------------------------//
hgeVector Vehicle::Arrive(hgeVector TargetPos,
Deceleration deceleration)
{
hgeVector ToTarget = TargetPos -position;
//calculate the distance to the target position
double dist = ToTarget.Length();
if (dist > 0)
{
if(arrive)
arrive = false;
//because Deceleration is enumerated as an int, this value is required
//to provide fine tweaking of the deceleration.
const double DecelerationTweaker = 0.3;
//calculate the speed required to reach the target given the desired
//deceleration
double speed = dist / ((double)deceleration * DecelerationTweaker);
//make sure the velocity does not exceed the max
speed = min(speed, maxSpeed);
//from here proceed just like Seek except we don't need to normalize
//the ToTarget vector because we have already gone to the trouble
//of calculating its length: dist.
hgeVector DesiredVelocity = ToTarget * speed / dist;
hgeVector res =DesiredVelocity -velocity ;
return res;
}
return hgeVector(0,0);
}
m_sepw = 1240;
m_alignw = 100;
m_cohesionw = 20;
m_arrivew = 200;
they were all 200 at first place but i changed them for more stability ....
the Whole logic is from ai by example book,
This is Calculation Force function
hgeVector cforce;
cforce =SeparationPlus(GameWorld::GetInstance()->Objects) * m_sepw;
if (!AccumulateForce(force, cforce)) return force;
cforce =AlignmentPlus(GameWorld::GetInstance()->Objects) * m_alignw;
if (!AccumulateForce(force, cforce)) return force;
cforce =CohesionPlus(GameWorld::GetInstance()->Objects) * m_cohesionw;
if (!AccumulateForce(force, cforce)) return force;
cforce = Arrive(m_target, m_Dec) * m_arrivew;
if (!AccumulateForce(force, cforce)) return force;
return force;
//----------------------------------------------------------------------------//
hgeVector Vehicle::SeparationPlus(const std::vector<Vehicle*> &neighbors)
{
Vector SteeringForce;
bool change =false;
//iterate through the neighbors and sum up all the position vectors
for (Vehicle* pV = GameWorld::GetInstance()->CellSpace()->begin();
!GameWorld::GetInstance()->CellSpace()->end();
pV = GameWorld::GetInstance()->CellSpace()->next())
{
//make sure this agent isn't included in the calculations and that
//the agent being examined is close enough
if(pV != this)//&&pV->arrive ==false)
{
change = true;
hgeVector ToAgent =position - pV->position;
//scale the force inversely proportional to the agents distance
//from its neighbor.
double len = ToAgent.Length();
ToAgent.Normalize();
SteeringForce +=( (ToAgent)/len);
}
}
return SteeringForce;
}
//------------------------------------------------------------------------//
hgeVector Vehicle::CohesionPlus(const std::vector<Vehicle*> &neighbors)
{
//first find the center of mass of all the agents
hgeVector CenterOfMass, SteeringForce;
int NeighborCount = 0;
//iterate through the neighbors and sum up all the position vectors
for (Vehicle* pV = GameWorld::GetInstance()->CellSpace()->begin();
!GameWorld::GetInstance()->CellSpace()->end();
pV = GameWorld::GetInstance()->CellSpace()->next())
{
//make sure *this* agent isn't included in the calculations and that
//the agent being examined is close enough
if(pV != this)
{
CenterOfMass += pV->position;
++NeighborCount;
}
}
if (NeighborCount > 0)
{
//the center of mass is the average of the sum of positions
CenterOfMass = CenterOfMass/(double)NeighborCount;
//now seek towards that position
SteeringForce = Seek(CenterOfMass);
}
//the magnitude of cohesion is usually much larger than separation or
//allignment so it usually helps to normalize it.
SteeringForce.Normalize();
return (SteeringForce);
}
//--------------------------------------------------------------------------//
hgeVector Vehicle::AlignmentPlus(const std::vector<Vehicle*> &neighbors)
{
//This will record the average heading of the neighbors
hgeVector AverageHeading;
//This count the number of vehicles in the neighborhood
double NeighborCount = 0.0;
//iterate through the neighbors and sum up all the position vectors
for (Vehicle* pV = GameWorld::GetInstance()->CellSpace()->begin();
!GameWorld::GetInstance()->CellSpace()->end();
pV = GameWorld::GetInstance()->CellSpace()->next())
{
//make sure *this* agent isn't included in the calculations and that
//the agent being examined is close enough
if(pV != this)
{
AverageHeading += pV->heading;
++NeighborCount;
}
}
//if the neighborhood contained one or more vehicles, average their
//heading vectors.
if (NeighborCount > 0.0)
{
AverageHeading = AverageHeading/NeighborCount;
AverageHeading -= heading;
}
return AverageHeading;
}
//----------------------------------------------------------------------//
hgeVector Vehicle::Arrive(hgeVector TargetPos,
Deceleration deceleration)
{
hgeVector ToTarget = TargetPos -position;
//calculate the distance to the target position
double dist = ToTarget.Length();
if (dist > 0)
{
if(arrive)
arrive = false;
//because Deceleration is enumerated as an int, this value is required
//to provide fine tweaking of the deceleration.
const double DecelerationTweaker = 0.3;
//calculate the speed required to reach the target given the desired
//deceleration
double speed = dist / ((double)deceleration * DecelerationTweaker);
//make sure the velocity does not exceed the max
speed = min(speed, maxSpeed);
//from here proceed just like Seek except we don't need to normalize
//the ToTarget vector because we have already gone to the trouble
//of calculating its length: dist.
hgeVector DesiredVelocity = ToTarget * speed / dist;
hgeVector res =DesiredVelocity -velocity ;
return res;
}
return hgeVector(0,0);
}
Obvious issues in your code (which is supposed to be properly quoted in code tags, by the way):
- Where is AccumulateForce()? It clearly governs how the behaviours are combined. For example, Arrive() might never get called when needed.
-Where is Seek(), the fundamental building block? Don't you think you should choosing only one point to Seek(), rather than averaging contradictory forces?
- AlignmentPlus returns a heading, not a force. You should turn the vehicle, not apply a force in that direction.
- Or better yet, match the average velocity of buddies, not their heading.
- Forces aren't normalized properly (some are, some aren't), making your weights rather meaningless. Not that you are treating them as weights anyway.
- I don't know what CellSpace() means, but you should treat as neighbours of your agent all entities within a suitable distance, not all entities in the same "cell" or all entities in the whole level. These neighbours should be computed once, not repeatedly for each behaviour.
- I don't see any turning, only forces. Is turning actually important?
What are your agents supposed to do, in concrete game-world terms?
Flocking is only a means to an end, maybe they should follow a leader in a single file (infantry in a forest) or in a fixed formation (ducks flying).
Likewise, deceleration near a target can take different forms: actually stopping suddenly with practically instant deceleration or with an inelastic collision, slowing down without stopping to better track a slow-moving target, staying close to the target with enough damping to ensure stability but no need to actually stop, and so on.
- Where is AccumulateForce()? It clearly governs how the behaviours are combined. For example, Arrive() might never get called when needed.
-Where is Seek(), the fundamental building block? Don't you think you should choosing only one point to Seek(), rather than averaging contradictory forces?
- AlignmentPlus returns a heading, not a force. You should turn the vehicle, not apply a force in that direction.
- Or better yet, match the average velocity of buddies, not their heading.
- Forces aren't normalized properly (some are, some aren't), making your weights rather meaningless. Not that you are treating them as weights anyway.
- I don't know what CellSpace() means, but you should treat as neighbours of your agent all entities within a suitable distance, not all entities in the same "cell" or all entities in the whole level. These neighbours should be computed once, not repeatedly for each behaviour.
- I don't see any turning, only forces. Is turning actually important?
What are your agents supposed to do, in concrete game-world terms?
Flocking is only a means to an end, maybe they should follow a leader in a single file (infantry in a forest) or in a fixed formation (ducks flying).
Likewise, deceleration near a target can take different forms: actually stopping suddenly with practically instant deceleration or with an inelastic collision, slowing down without stopping to better track a slow-moving target, staying close to the target with enough damping to ensure stability but no need to actually stop, and so on.
Author
Hello Again,
is this even possible to stabilize such system in the situation when units are stopped ?( with arrive behaviour) because it seems reasonable that we always have some forces in different directions
seperation and arrive are always opposite and because seperation depends on length it will change time after time , arrive push units to get its target and seperatin do opposite if there is more than one unit around it...
i find some smoothing solution for that but even with that i still have some changes in direction sometimes .
i need a movement simulation like strategy games. i don't know if its the right way to do that.
whats your advice about the whole situation?
Thanks
is this even possible to stabilize such system in the situation when units are stopped ?( with arrive behaviour) because it seems reasonable that we always have some forces in different directions
seperation and arrive are always opposite and because seperation depends on length it will change time after time , arrive push units to get its target and seperatin do opposite if there is more than one unit around it...
i find some smoothing solution for that but even with that i still have some changes in direction sometimes .
i need a movement simulation like strategy games. i don't know if its the right way to do that.
whats your advice about the whole situation?
Thanks
As I said in my previous post, knowing what you really want your agents to do and what the mysterious AccumulateForce() function does to your forces would be really useful.
Other problems with your code and analysis:
- You don't seem to limit forces, which should be constrained by the capabilities of your agents for obvious reasons of realism and game balance.
- You don't seem to limit speed: agents should refuse to accelerate beyond what's appropriate, actively slow down if in unusual circumstances they are already moving too fast, and possibly suffer from drag forces (which, balanced with the agent's limited locomotive forces, create a hard speed limit).
- Separation should not allow crowds to push agents away from where they are meant to stay: agents that have some way to go should be repelled away from stationary ones that have already arrived, but not vice versa.
Other problems with your code and analysis:
- You don't seem to limit forces, which should be constrained by the capabilities of your agents for obvious reasons of realism and game balance.
- You don't seem to limit speed: agents should refuse to accelerate beyond what's appropriate, actively slow down if in unusual circumstances they are already moving too fast, and possibly suffer from drag forces (which, balanced with the agent's limited locomotive forces, create a hard speed limit).
- Separation should not allow crowds to push agents away from where they are meant to stay: agents that have some way to go should be repelled away from stationary ones that have already arrived, but not vice versa.
Author
ah , i totally forgot to mention about AccumulateForce
This function first determines how much of the maximum available steering force is remaining, and then one of the following happens:
If there is a surplus remaining, the new force is added to the running total.
If there is no surplus remaining, the method returns false. When this happens, Calculate returns the current value of SteeringForce immediately and without considering any further active behaviors.
If there is still some steering force available, but the magnitude remaining is less than the magnitude of the new force, the new force is truncated to the remaining magnitude before it is added.
and there is maxspeed and maxforce .
and the problem arise when units want to arrive same position if you test a rts game and select some units and move them to some position inside their bounding box they will all go to there position but they will found their proper positions ,
but in this case when im trying to do that units will found some balance between themselves but they rotate all the time because of velocity changes , i did use some smoothing solution that made that much better but they still have the same behavioure( rotate time after time)
and about your third statement , it seems reasonable i'll check that but i guess i checked that already , i don't remember ! there is thousands of way i tested!
This function first determines how much of the maximum available steering force is remaining, and then one of the following happens:
If there is a surplus remaining, the new force is added to the running total.
If there is no surplus remaining, the method returns false. When this happens, Calculate returns the current value of SteeringForce immediately and without considering any further active behaviors.
If there is still some steering force available, but the magnitude remaining is less than the magnitude of the new force, the new force is truncated to the remaining magnitude before it is added.
and there is maxspeed and maxforce .
and the problem arise when units want to arrive same position if you test a rts game and select some units and move them to some position inside their bounding box they will all go to there position but they will found their proper positions ,
but in this case when im trying to do that units will found some balance between themselves but they rotate all the time because of velocity changes , i did use some smoothing solution that made that much better but they still have the same behavioure( rotate time after time)
and about your third statement , it seems reasonable i'll check that but i guess i checked that already , i don't remember ! there is thousands of way i tested!
Author
i tried it , it didn't work in case when you have a group of agents selected and you give them a target somewhere and they are too close to each other , then when they get near target they will never get there exactly and that solution will not work at all because they are pushing each other and none of them will ever arrive .( it is always some tiny displacement so distance to target never reach zero.)
Is There any alternative to this method for rts games?!
efficient and works well when there is large amount of units on screen,and its 2d for now.
[Edited by - asvsfs on October 20, 2010 2:41:09 PM]
Is There any alternative to this method for rts games?!
efficient and works well when there is large amount of units on screen,and its 2d for now.
[Edited by - asvsfs on October 20, 2010 2:41:09 PM]
Quote:Original post by asvsfs
i tried it , it didn't work in case when you have a group of agents selected and you give them a target somewhere and they are too close to each other , then when they get near target they will never get there exactly and that solution will not work at all because they are pushing each other and none of them will ever arrive .( it is always some tiny displacement so distance to target never reach zero.)
Units are expected to never reach their target exactly: other units should avoid pushing units that are closer to the shared target than they are, with an implicit priority system.
For example, units could temporarily set their Seek() target to the closest intersection between the ray from their position through the next waypoint, and the circles of radius equal to the desired separation distance constructed around their colleagues sharing the same target: they would slow down, or even go backwards, in order to not bump into better placed units.
This can be improved in several ways:
- Instead of simple braking, computing a shortest path that treats colleagues as obstacles; faster agents would be able to walk around slower ones.
- Units could have an explicit priority value, giving them a total ordering, and ignore the separation disc around lower priority units that are in the way; this would solve cases in which units get stuck in narrow passages.
Another option, if you want to use forces, would be scaling the separation forces according to the distance from the target: 0 for an unit on the target, full beyond a certain distance to the target (on the order of 1 second of movement), and linearly interpolated in between.
Your use of AccumulateForce() seems completely wrong because it privileges forces that are accumulated first and forces that happen to have a large magnitude: as I suspected, Arrive() often isn't called when needed.
I would combine Arrive() with movement towards the target (i.e. computing the force that would bring the agent on the target and make it stop there as early as possible), ditch cohesion and alignment behaviours (useless for this application), and take care of separation in a way that allows the leading unit to reach the target as if alone, without being pushed (as I explained above).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
