How do i find if an object is before or after a waypoint?

Question

Im working on a racing game for a school project. Using Visual studio 10 pro, and Irrlicht. Sorry for bad grammar >.>, and its my first question so not sure if its done right.

How i want it to work is that i make waypoints at different points on the track, and then i run my waypoint check to see if a car is past its next waypoint (the next it "needs" to go past), if yes then it updates the next waypoint, else nothing.

The way i hope this will work is, i make a vector from n to n+1, then find the vector that is perpendicular to the first vector at n. Then i see if the object is in front or behind that vector. I found a Gamedev.net forumpost that helped me make this function:

void Engine::checkWaypoint(Vehicle* vehicle)
{
  btVector3 vector = waypoints[vehicle->nextWaypoint];
  // n
  btVector3 nextVector = waypoints[vehicle->nextWaypoint + 1];
  // n+1
  vector = nextVector - vector;
  // First vector
  btVector3 pos = btVector3(vehicle->position.X,vehicle->position.Y,vehicle->position.Z);

  float product = vector.dot(pos - waypoints[vehicle->nextWaypoint]);
  // positiv = before, negative = behind

  if(product < 0)
    vehicle->nextWaypoint += 1;
}

Current bugs with this is:

1. Updates the nextwaypoint more then ones without going past a new point.

2. When it gets to the end and resets, it stops triggering on the first waypoints.

So my questions:

Is this an good way to do this?

Did i do it right?

Answer 1

Found out that my original code was working, problem was with the waypoints.

Made the waypoints easy to see and all of them were too close to each other, so the kode was repeating itself a lot of times at the same spots.

So made the distance between waypoints longer, and made them into an track, and everything started working like i wanted it too.

Answer 2

Your code measures how far along the vector from the current way-point to the next, the player is. However if the vectors for two consecutive segments are (for example) at right-angles, the algorithm could skip multiple way-points at a time. (i.e. if you draw the line across the next way-point, it might extend right down the middle of the road, which means the player could be going back and forward across it, while driving towards that way-point).

Some kind of bounding volume might work, either the distance to the waypoint (check that it's less than maybe 2x the width of the road), or the distance to the vector you've calculated between points.

(or you might get away with just adding more waypoints)

As to why it doesn't work when you lap, it seems you just add one to the waypoints to find the next one. You need to do that calculation modulo the total:

next_waypoint = (vehicle->nextWaypoint + 1) % num_waypoints;

Answer 3

Usually, in a race game you have to be at the checkpoint for it to be validated : you just check that the car is close enough from the checkpoint. So, I think the following pseudo-code would be valid:

if( car is_near current_checkpoint )
    current_checkpoint = current_checkpoint->next_checkpoint;

is_near: return distance(car, current_checkpoint) < some value

The for distance test, you can either use a simple circle shape (as shown in the pseudo-code), or you can test whether the car hits the bounding box of the checkpoint (or a box that is place inside the checkpoint), it depends on how your checkpoints are made.

Or else, you can have a curve made by all the lines from checkpoints to their followers, and then find the closest line on where it is on it, from which you can find the next checkpoint. Example:

                        o--o
                       /    \
    o-----------------o      \
   /                          \  <-- your track: S = start
  /                            o                 E = end
 /        o---o        X      /                  o = checkpoint
S        /     \       .     /                   X = car
        /       o------.----o
       /                  ^
   E--o                   |
                closest road from the car

Inconvenient: results may vary depending of the curvature of the roads. I advise you to use the first method I described.