Pathfinding / Deciding on direction

Question

Hi everyone, i'm making a simple iPhone game using cocos2d-iphone. I have an array of fiends, the "fiendSet" which has to navigate around a field full of obstacles. I spent the last three nights trying to get my A* pathfinding to work. I found the actual A* implementation here on stackoverflow and it works brilliantly. However, once i try to move my fiends around i run into trouble.

Each of my fiends has a CGPoint called motionTarget which contains the x and y values for where the fiend has to go. If only set the positions x and y to absolute values once a second, it works, like so:

-(void) updateFiendPositions:(ccTime)dt {
    for (MSWFiend *currFiend in fiendSet) {
         currFiend.position = ccp(currFiend.motionTarget.x,currFiend.motionTarget.y);
    }
}

However, this doesn't look very nice, the fiends just "jump" 20px each second instead of animating nicely. I only implemented this as a placeholder method to verify the pathfinding. Now i want smooth animation. This is what i did:

-(void) updatePositions:(ccTime) dt {
    for (MSWFiend *currFiend in fiendSet) {
        if (currFiend.motionTarget.x != -1 && currFiend.motionTarget.y != -1) {
            float x,y;      

            if ((int)floor(currFiend.position.x) < (int)floor(currFiend.motionTarget.x)) {
                x = currFiend.position.x+(currFiend.speed*dt);
            }
            if ((int)floor(currFiend.position.x) > (int)floor(currFiend.motionTarget.x)) {
                x = currFiend.position.x-(currFiend.speed*dt);
            }
            if (abs((int)floor(currFiend.position.x)-(int)floor(currFiend.motionTarget.x)) < 2) {
                x = currFiend.motionTarget.x;
            }

            if ((int)floor(currFiend.position.y) < (int)floor(currFiend.motionTarget.y)) {
                y = currFiend.position.y+(currFiend.speed*dt);
            }
            if ((int)floor(currFiend.position.y) > (int)floor(currFiend.motionTarget.y)) {
                y = currFiend.position.y-(currFiend.speed*dt);
            }
            if (abs((int)floor(currFiend.position.y)-(int)floor(currFiend.motionTarget.y)) < 2) {
                y = currFiend.motionTarget.y;
            }

            currFiend.position = ccp(x,y);
        }
    }
}

This works great for fiends moving in one direction. As soon as a fiend is supposed to go around a bend, trouble starts. Instead of for example first going up, then right, then down; my fiends will combine the up/right motion into one, they are "cutting corners". I only want my fiends to move either north/south OR east/west for each position update, not both. In other words, i don't want to animate changes to x and y simultaneously. I hope this explanation is clear enough..

I'm pretty sure i have a logic error somewhere.. i just havn't been able to figure it out for the last three sleepless nights after work.. Help!

Answer 1

You have to keep track of each node in the path to the target. That way you only animate the motion to the next node. Also you can use a CCMoveTo action instead on doing the animation yourself.

Answer 2

@Aleph thanks for your suggestion. I found that it was the code which determines when to assign a new motionTarget, that was faulty, not the code i posted to begin with. When you mentioned keeping track of each nodes position, i thought of my motionTarget determination code and found the error after 2-3 hours. I ended up doing it like this:

-(void) updatePositions:(ccTime) dt {
for (MSWFiend *currFiend in fiendSet) {
    int fiendGX,fiendGY,targetGX,targetGY,dGX,dGY;
    float x,y,snappedX,snappedY;
    BOOL snappedIntoPosition = FALSE;

    fiendGX = (int)round(100.0f*(currFiend.position.x/20));
    fiendGY = (int)round(100.0f*(currFiend.position.y/20));
    targetGX = (int)round(100.0f*(currFiend.motionTarget.x/20));
    targetGY = (int)round(100.0f*(currFiend.motionTarget.y/20));

    snappedX = currFiend.position.x;
    snappedY = currFiend.position.y;

    dGX = abs(fiendGX-targetGX);
    dGY = abs(fiendGY-targetGY);

    float snappingThreshold; //1 = snap when 0.1 from motionTarget.
    snappingThreshold = currFiend.speed/10;

    if (dGX < snappingThreshold && dGY < snappingThreshold) {
        snappingThreshold = currFiend.motionTarget.x;
        snappingThreshold = currFiend.motionTarget.y;
        int newPathStep;
        newPathStep = currFiend.pathStep + 1;
        currFiend.pathStep = newPathStep;
    }

    int gX,gY; 
    gX = [[currFiend.path objectAtIndex:currFiend.pathStep] nodeX];
    gY = (tileMap.mapSize.height-[[currFiend.path objectAtIndex:currFiend.pathStep] nodeY])-1;

    currFiend.motionTarget = ccp(gX*20,gY*20);          //Assign motion target to the next A* node. This is later used by the position updater.

    if (currFiend.motionTarget.x != -1 && currFiend.motionTarget.y != -1) {
        x = currFiend.motionTarget.x;
        y = currFiend.motionTarget.y;

        if ((int)floor(currFiend.position.x) < (int)floor(currFiend.motionTarget.x)) {
            //Move right
            x = snappedX+(currFiend.speed*dt);
            if (x > currFiend.motionTarget.x) {
                x = currFiend.motionTarget.x;
            }
            y = snappedY;
        }
        if ((int)floor(currFiend.position.x) > (int)floor(currFiend.motionTarget.x)) {
            //Move left
            x = snappedX-(currFiend.speed*dt);
            if (x < currFiend.motionTarget.x) {
                x = currFiend.motionTarget.x;
            }
            y = snappedY;
        }

        if ((int)floor(currFiend.position.y) < (int)floor(currFiend.motionTarget.y)) {
            //Move up
            y = snappedY+(currFiend.speed*dt);
            if (y > currFiend.motionTarget.y) {
                y = currFiend.motionTarget.y;
            }
            x = snappedX;
        }
        if ((int)floor(currFiend.position.y) > (int)floor(currFiend.motionTarget.y)) {
            //Move down
            y = snappedY-(currFiend.speed*dt);
            if (y < currFiend.motionTarget.y) {
                y = currFiend.motionTarget.y;
            }
            x = snappedX;
        }
    }
    currFiend.position = ccp(x,y);
}
}