Advertisement

Help collision avoidance method

Started by July 01, 2009 11:27 AM
4 comments, last by Antonym 15 years, 4 months ago
I am trying to implement a collision avoidance method though it's giving me some trouble. I have a ship that can only move the way it's facing. I test it against objects by using the dot product with both's offset and velocity vector(1 moving towards, 0 parallel, -1 moving away). Though I also need to know how close their trajectories are so as to know how much the ship needs to turn away and what way to turn. This second part is the one that has been giving me problems :S. Any ideas/help is appreciated. Thanks.
Have you looked into simple steering methods instead?

Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-founder and 10 year advisor of the GDC AI Summit
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!"

Advertisement
Thanks, I think I found the steering behavior I needed.

'Unaligned collision avoidance behavior tries to keep characters which are moving in arbitrary directions from running into each other. Consider your own experience of walking across a plaza or lobby full of other walking people: avoiding collisions involves predicting potential collisions and altering your direction and speed to prevent them. If all nearby characters are aligned, a less complicated strategy can be used, see separation below.

To implement this as a steering behavior, our character considers each of the other characters and determines (based on current velocities) when and where the two will make their nearest approach. A potential for collision exists if the nearest approach is in the future, and if the distance between the characters at nearest approach is small enough (indicated by circles in Figure 12). The nearest of these potential collisions, if any, is determined. The character then steers to avoid the site of the predicted collision. It will steer laterally to turn away from the potential collision. It will also accelerate forward or decelerate backwards to get to the indicate site before or after the predicted collision. In Figure 12 the character approaching from the right decides to slow down and turn to the left, while the other character will speed up and turn to the left.'

Though the implementation, how do I find their nearest approach? Also, about handling the potential collision. How do I know if I should accelerate/deccelerate, turn left or right?

Thanks.
I'm by no means a master of AI or anything, but does your AI have a destination? Some checkpoint or somewhere it needs to be? If so you could just turn towards that point (over shooting the direction if need be, you can realign later). If its going straight at its destination and going to collide, then pick a random direction (or base your direction off the other objects in the area).
Don't if that helps but give it a try.

~Kasigori~
~Kasigori~ Scientia Potentia Est.
Quote: Original post by Antonym
Though the implementation, how do I find their nearest approach? Also, about handling the potential collision. How do I know if I should accelerate/deccelerate, turn left or right?


If you have a steerForSeek function taking a point in parameter, that should take care of the accelerate/deccelerate and turning. What you need to find is a point where your ship wants to go to avoid the potential collision. For example :

Ship A is at (0,0) and is going to (10,10)
Ship B is at (10,5) and is going to (0,5)

There should be a collision at (5,5). Ship A sees this and figures out it should be going to (5,0) to avoid the ship. A potential collision has a higher factor than destination when calculating the steerForSeek point, so ship A decides to head toward (6,1). Ship B does a similar processing and ends up with (4,9) as its destination. They both end up steering right and avoid each other.
Developer for Novus Dawn : a [s]Flash[/s] Unity Isometric Tactical RPG - Forums - Facebook - DevLog
This is a modified version of the functions found in the OpenSteer library for unaligned collision avoidance. I am trying to use it to get the point/vector I need to get away from threats. I am not sure what I am doing wrong though.

void ShipEnemy::avoid(const float minTimeToCollision,						std::vector<Object*> others){    float steer = 0;    Object* threat = NULL;    // Time (in seconds) until the most immediate collision threat found    // so far.  Initial value is a threshold: don't look more than this    // many frames into the future.    float minTime = minTimeToCollision;    // for each of the other vehicles, determine which (if any)    // pose the most immediate threat of collision.	for (std::vector<Object*>::iterator i = others.begin(); i != others.end(); i++){        Object* other = *i;        if (other != this && other->mBody){	            // avoid when future positions are this close (or less)			float collisionDangerThreshold = GetRadius() * 2;            // predicted time until nearest approach of "this" and "other"            float time = predictNearestApproachTime (other);            // If the time is in the future, sooner than any other            // threatened collision...            if ((time >= 0) && (time < minTime)){                if (computeNearestApproachPositions (other, time)                    < collisionDangerThreshold){                    minTime = time;                    threat = other;                }            }        }    }	b2Vec2 side = GetDirection3();	side.Normalize();	side = b2Vec2(side.y,-side.x);    // if a potential collision was found, compute steering to avoid    if (threat != NULL){		b2Vec2 direction = GetDirection3();		b2Vec2 otherDirection = threat->GetDirection3();        // parallel: +1, perpendicular: 0, anti-parallel: -1        float parallelness = b2Dot(direction, otherDirection);        float angle = 0.707f;        if (parallelness < -angle){            // anti-parallel "head on" paths:            // steer away from future threat position            b2Vec2 offset = hisPositionAtNearestApproach - GetPosition();            float sideDot = b2Dot(offset,side);			steer = (sideDot > 0) ? -1.0f : 1.0f;        }        else{            if (parallelness > angle){                // parallel paths: steer away from threat                b2Vec2 offset = threat->GetPosition() - GetPosition();				float sideDot = b2Dot(offset,side);				steer = (sideDot > 0) ? -1.0f : 1.0f;            }            else{                // perpendicular paths: steer behind threat                // (only the slower of the two does this)                if (threat->GetSpeed() <= GetSpeed()){                    float sideDot = b2Dot(side, otherDirection);					steer = (sideDot > 0) ? -1.0f : 1.0f;                }            }        }    }	b2Vec2 result = side;	result *= steer;	if(steer != 0)		targetPoint = result + GetPosition() + GetDirection3();}float ShipEnemy::predictNearestApproachTime (Object *other){    b2Vec2 myVelocity = GetVelocity();    b2Vec2 otherVelocity = other->GetVelocity();    b2Vec2 relVelocity = otherVelocity - myVelocity;    float relSpeed = relVelocity.Length();    // for parallel paths, the vehicles will always be at the same distance,    // so return 0 (aka "now") since "there is no time like the present"    if (relSpeed == 0)		return 0;    // Now consider the path of the other vehicle in this relative    // space, a line defined by the relative position and velocity.    // The distance from the origin (our vehicle) to that line is    // the nearest approach.    // Take the unit tangent along the other vehicle's path    b2Vec2 relTangent = relVelocity;	relTangent.x /= relSpeed;	relTangent.y /= relSpeed;    // find distance from its path to origin (compute offset from    // other to us, find length of projection onto path)    b2Vec2 relPosition = GetPosition() - other->GetPosition();    float projection = b2Dot(relTangent,relPosition);	float time = projection / relSpeed;    return time;}float ShipEnemy::computeNearestApproachPositions (Object *other,                                 float time){	b2Vec2 position = GetPosition();	b2Vec2 direction = GetDirection3();	float speed = GetSpeed();	b2Vec2 otherPosition = other->GetPosition();	b2Vec2 otherDirection = other->GetDirection3();	float otherSpeed = other->GetSpeed();	b2Vec2 myTravel = direction;	myTravel *= speed * time;	b2Vec2 otherTravel = otherDirection;	otherTravel *= otherSpeed * time;	b2Vec2 myFinal = position + myTravel;    b2Vec2 otherFinal = otherPosition + otherTravel;    ourPositionAtNearestApproach = myFinal;    hisPositionAtNearestApproach = otherFinal;	float distance = (myFinal - otherFinal).Length();    return distance;}


[Edited by - Antonym on July 3, 2009 4:39:52 PM]

This topic is closed to new replies.

Advertisement