Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I am making a 2d soccer game, all players move in 8 directions, so I need to convert AI steering behavior(like arrive and pursuit) into 8 directions.
Here are three example situations:
enter image description here
Player(now is at point A) set target To point B, we could not directly move in direction(B - A), player need to first move to point C in horizontal or vertical, then move in 45 degree to reach target point. Consider in my game there is no steering behavior accumulation, which means, at any time , only have one function to affect player movement(arrive or pursuit), so I first make convert code in arrive function, because pursuit actually call arrive either.
Here is pseudo-code:

void RSAIController::Init()
{
   ...
    m_vDirectionArray[0] = CCPoint(1.f, 0.f);
    m_vDirectionArray[1] = CCPoint(0.7071f, 0.7071f);
    m_vDirectionArray[2] = CCPoint(0.f, 1.f);
    m_vDirectionArray[3] = CCPoint(-0.7071f, 0.7071f);
    m_vDirectionArray[4] = CCPoint(-1.f, 0.f);
    m_vDirectionArray[5] = CCPoint(-0.7071f, -0.7071f);
    m_vDirectionArray[6] = CCPoint(0.f, -1.f);
    m_vDirectionArray[7] = CCPoint(0.7071f, -0.7071f);
}
//called in arrive method, then use m_vMoveDirection as speed direction
void RSAIController::ConvertTo8Directional()
{
    int idx = -1;
    float maxValue = -MaxFloat;
    CCPoint direction = m_vTarget - m_pPlayer->Pos();
    //do this because in cocos2d normalize zero vector will return (1, 0)
    //which is not the expected result,so I avoid it manually
    if(!VIsZero(direction))
        direction = direction.normalize();

    for(int i = 0; i < 8; ++i)
    {
        float dotValue = m_vDirectionArray[i].dot(direction);
        if(dotValue > maxValue)
        {
            maxValue = dotValue;
            idx = i;
        }
    }
    m_vMoveDirection = m_vDirectionArray[idx];
}

Then I am thinking 8-directional AI movement is pretty common in old nes game, like "Nintendo World Cup". Does anyone used to meet this problem or have any articles related to this?

UPDATE: I have update the code in @Json advice, but still got the errors I met before.
1.Actually player will change direction in 22.5 degree not 45 degree. I need player move on the diagonals when the degree is just reach 45.
2.When player move on the diagonals, the player will keep shaking. For example, in situation 1, when player start to move from C to B in first frame, player decide to move in perfect 45 degree, but player can not reach precise point C because "distance from A to C" has small error to "player speed(constant) * move time from A to C" , this will cause next frame player probably run in horizontal direction, again and again..
Do I need to check when the last frame that arrive at C, then just make player at the precise point C manually to avoid this error, or there has any other trick to fix this?

share|improve this question

2 Answers 2

up vote 1 down vote accepted

Angles are almost always a poor way to handle such situations. You already have vectors, which are perfect representations of directions. Just take the eight unit directions (normalized <1,0>, <1,1>, <0,1>, <-1,1> etc.), form the dot product with your desired direction, and then take the vector with the largest value. This assumes your characters move the same speed in every direction. If they move faster on the diagonals, just don't normalize the directions.

Basically, this procedure works by making your character move in the direction which most quickly minimizes the distance to the goal.

Be sure to have your character only do things if they aren't already at their destination! This code won't work as intended:

 if(!direction.IsZero())  
        direction.normalize();  
 float radians = direction.getAngleToXAxis();  

If the direction is zero, then getAngleToXAxis doesn't make any sense, and should throw an exception. If the direction is the zero vector, you are at your destination, and the rest of the logic can be skipped. Don't just blindly avoid normalizing a zero vector. A zero vector going into a normalization usually has some special interpretation, which in this case is "you have arrived at your destination."

EDIT: So the original problem is a little more complicated. Basically you are going to need to add a little bit of state to your character. I'm going to describe the simplest way I can think of, but it is a little hack-y because what you want is non-optimal pathfinding behavior.

State: last direction player moved in (E,N,W,NE, etc.), corresponding to one of the eight directions, or NONE if they weren't moving last frame. To decide which way to go:

  1. If at destination: stop, set direction to NONE (you might use a boolean flag for this, NONE is conceptual).

  2. If last time you moved N,S,E, or W, find the closest just out of those four (so use the dot-product trick, but only with <0,1>, <1,0>, <-1,0>, and <0,-1>). If it matches what you did last time, then keep doing that. Otherwise, go to 4.

  3. Similarly, if last time you did NE, SE, NW, or SW, find the closest from those, and keep doing it if it is still good. Otherwise go to 4.

  4. Pick the best direction, as above. Set the last frame direction to this direction, and return it.

Here is a demo of this technique (click to set a new destination):
http://jsfiddle.net/9cLy3/embedded/result/
This is an example of hysteresis.

share|improve this answer
    
I have updated the code, actually within your advice, I still has same problems I met before(I do not say it clearly yesterday, sorry) 1.player change direction in 22.5 degree not 45. 2.player keep shaking when moving on the diagonals –  Captain Jan 28 at 15:43
    
Thanks, I follow your sample and now AI move as I want:) –  Captain Jan 29 at 16:52
        if (degrees < 45 && degrees > -45)          direction = vector(1.0, 0.0);  
        else if (degrees == 45.f)                   direction = vector(1.0, 1.0);  
        else if (degrees > 45 && degrees < 135)     direction = vector(0.0, 1.0);  
        else if (degrees == 135.f)                  direction = vector(-1.0, 1.0);  
        else if (degrees > 135 || degrees < -135)   direction = vector(-1.0, 0.0);  
        else if (degrees == -135.f )                direction = vector(-1.0, -1.0);                                                                          
        else if (degrees > -135 && degrees < -45)   direction = vector(0.0, -1.0);  
        else if (degrees == -45.f)                  direction = vector(1.0, -1.0);  

This logic seems to be a little off, for example you are only assigning vector(1.0,1.0) if the angle is exactly equal to 45.0f when really it should represent a range of one eighth of a circle.

I would use the following to convert any given angle in radians to 8-way movement:

float factor =  (2.0f * pi) / 8.0f;  // or 360.0f/8.0f if using degrees
float newAngle = round(oldAngle / factor) * factor;

Once you have newAngle perform a mathematically correct conversion to a vector without any need for further manipulation. This example assumes newAngle is in the correct units for the trigonometric functions:

direction = vector(sin(newAngle), cos(newAngle));

Note: this last line will produce a unit vector (i.e. of length one), you may need to handle thing a bit differently if you want the diagonals to be of length sqrt(2) like the code you posted with your question.

Edit: I can see two approaches to address the issue of switching directions on each frame and approximating 16-direction movement.

BlackList: If each time a player changes direction we disable or blacklist the direction they were taking before that turn, this would rule out that issue, and instead result an a high degree of over steering. This might be acceptable if the target was stationary but is unlikely to look natural if the target moves into the direction we have blocked, and players would learn to take advantage of this.

//
int currentDirection = -999;     // the direction taken last frame
int previousDirection = -999;    // the direction taken before the last turn
//

float factor =  (2.0f * pi) / 8.0f;  // or 360.0f/8.0f if using degrees
float idealDirection = oldAngle / factor;
int newDirection = round(idealDirection);
if (newDirection != currentDirection) {
    if (newDirection == previousDirection) {  
        if (idealDirection > newDirection) {
            newDirection++;
        }
        else {
            newDirection--;
        }
    if (newDirection != currentDirection) {
        previousDirection = currentDirection;
        currentDirection = newDirection;
    }
}
float newAngle = newDirection * factor;

Bias: If we set a bias towards heading in the current direction and only switch direction when a new direction is much more desirable we should have a more natural result. This will have an about of back and forth between headings abut the bias can be tuned to reach the desired result.

//
int currentDirection = -999;     // the direction taken last frame
float bias =  2.0;               // how much better should the new direction be
//

float factor =  (2.0f * pi) / 8.0f;  // or 360.0f/8.0f if using degrees
float idealDirection = oldAngle / factor;
int newDirection = round(idealDirection);
if (newDirection != currentDirection) {
    float distanceFromCurrent = abs(currentDirection - idealDirection);
    float distanceFromNew = abs(newDirection - idealDirection);
    if (distanceFromCurrent > (distanceFromNew * bias)) {
        currentDirection = newDirection;   // switch to new direction
    }
    else {
      newDirection = currentDirection;     // stick to the established heading
   }
}
float newAngle = newDirection * factor;
share|improve this answer
    
I have rewrite the error description, sorry for unclear words I wrote yesterday.. –  Captain Jan 28 at 15:45
1  
I read your methods, I think it also works, but Jason's dot product way seem to be more clean in my understanding~~Thanks anyway! –  Captain Jan 29 at 16:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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