Alrighty! This page will be a work in progress. One of the first things that I will be writing a tutorial on will be a waypoint system. I used this waypoint system in an open city game that I helped develop. I remember when I started writing my first waypoint system I looked everywhere for some information on how to write it and couldn't find squat! So I want to help some people out and offer at least a little something to start off on. :) One suggestion to anyone programming a project is to use something like CVS to keep everyone up to date. Using that system allowed us to move ahead faster, stay more focused, and saved us a LOT of integration time. Please let me know if there is anything that is not explained thoroughly enough, or have any questions about this system.

The waypoint system that I designed up has two parts to is: the first part is the actual waypoint itself and then the manager that manages all of the waypoints. The waypoint itself contains all of the information that each of the cars would possibly need to access. I did not necessarily program in all of the features yet, but the information is there for future implementation. Take note: this system is not fully optimized. I optimized the best I could for the amount of time that I was allowed to work on this but as with all programming, there is about 200 ways to do it and this one might not be the best one! :) But it should give you a good start. Also take note that the traffic lights and manager are integrated in with the waypoint system somewhat and that I am using one row of waypoints down the middle of the road and having them "project" a waypoint for a car to chase. We also made a math library and other classes that were used extensively throughout the game... so for this reason a copy and paste wont work too well :( Sorry!

CAR AI

The car consists of its physics (dynamics), AI, bounding sphere for collision, and other information that we needed for our game. These are the variables that I have in my CarAI class.

// The cars around us. Use this to detect a possible collision
CCarAI *m_surroundingCars[MAX_CAR_POINTERS];

// Our destination waypoints. Where are we going next?
CWayPoint *m_nextWaypoints[MAX_NEXT_WAYPOINTS];

// How many waypoints we are using. # of ones we are connected to. Most would usually be 4 and that would be at // a 4-way intersection: 3 waypoints for other lanes and 1 for the waypoint before us.
GLint m_iNumDestinationWaypoints;

// Current position
ngVector3D m_currentPosition;

// Last valid point
ngVector3D m_lastValidPosition;

// Which way are we going? I used two axis, like X and Z. Used so waypoint will be able to correctly project the //destination waypoint.
GLuint m_uiDrivingDirection;

// Length of car. How many cars can fit in one road length?
GLfloat m_fLengthOfCar;

// Target Speed. I add a fudge-factor to make it look more realistic. Based on speed limit.
GLfloat m_fTargetSpeed;

// Can we move? Use this for multiple things: too many cars in intersection, crash ahead, collision about to happen, // etc.
bool m_bAllowedToMove;

// Are we the player?
bool m_bIsPlayer;

// Our last valid waypoint. Can use for debugging
CWayPoint *m_pLastValidWaypoint;

// What mode we are in. Driving mode and turning mode are ones mainly used.
GLint m_iCurrentMode;
GLint m_iLastMode;

// Our current turning mode
GLint m_iCurrentTurnMode;

// What lane are we in?
GLint m_iCurrentLane;

// Our dynamics
ngVehicleDynamics *m_pThisCarsDynamics;

// The manager
CWaypointManager *m_waypointManager;

// Our turning vector
ngVector3D m_turnVector;

// The matrix used to set up turn points
ngMatrix4X4 m_posRotateBy, m_negRotateBy;

The logic for the car is as follows:

1. The vehicle queries the next waypoint to see if it is an intersection.

2. If the waypoint is an intersection (this is any turn in the road from one road to another) the vehicle sees if it is allowed to go by querying the light to see if it is green. If the waypoint isn't an intersection then the car continues to move towards the waypoint.

3. If the light is green then the car continues to the waypoint. Once it hits the waypoint the vehicle calculates if it will be going straight by dotting the AT (forward vector) of the car and the vector of the current waypoint and destination waypoint. If its within tolerance then we are going straight, if its not, then we cross the AT and that same vector to determine right or left. If we are turning then we calculate the waypoints that it needs to in order to achieve a proper curve by finding a corner of the road (which corner is determined by which way we are turning) and rotating that point around that the number of times we wish to turn. The higher the number of points, the more precise the turning will look and the more computationally expensive the calculation will be. Essentially, we are getting the center of a circle and creating the points along the outside of the circle using the circles radius.

When the vehicle is adding the new waypoints to the car's known waypoints I am pushing them to the front of that list. This insures that the waypoint we want to go to next is the waypoint that will start us turning.

If the light is yellow or red then the car checks to see if its distance from the waypoint is greater or less than the WAYPOINT_TOLERENCE. (This is the enum that we use to say, "If I am plus or minus this amount, I am at the waypoint.") We want to stop just short of triggering the switching of waypoints. This way our vehicle will keep querying the light. If you hit the waypoint, then it would be deleted from the list and we would never stop.

4. Once we reach a waypoint, we delete that one off of the queue, and add one more random one to the end of the list. We also check to see what the speed limit for our next waypoint is and determine our targetSpeed. To make the vehicles look a little more realistic I come up with a random number between 1 and 6 and then randomly add or subtract it from the speed limit of the next waypoint.

WAYPOINTS

As said before, the waypoints contain all of the information that the vehicle could possibly need. Listed below is the information that I had my waypoint class contained.

// Type of waypoints
enum WayPointTypes { WP_NONE = 0, WP_ROAD, WP_ONE_WAY, WP_INTERSECTION, WP_STOP_SIGN,
WP_TRAFFIC_LIGHT, WP_NUM_POINT_TYPES,};

// Types of roads
enum RoadTypes { WP_DIRT = 1, WP_STREET, WP_HIGHWAY, };

//////////////////////////////-- Class --/////////////////////////////
//
//-- NAME: CWayPoint
//
//-- PURPOSE: Create a waypoint
//
//////////////////////////////////////////////////////////////////////
class CWayPoint
{
private:

// Our node number
GLint m_iNodeNumber;

// Number of lanes on the road
GLint m_iNumberOfLanes;

// Width of lane
GLint m_iWidthOfLane;

// Width of median
GLfloat m_fMedianWidth;

// TEMP VARIABLE: X or Z axis alignment
// 1 if oriented an the X axis
GLint m_iXOrientation;

// Length of road segment
GLfloat m_fRoadSegmentLength;

// Speed limit
GLuint m_uiSpeedLimit;

// Type of road
GLuint m_uiTypeOfRoad;

// What type of waypoint are we?
GLuint m_uiTypeOfWayPoint;

// Are we an intersection?
bool m_bIntersection;

// If we are an intersection, whats the traffic light thats there?
CTrafficLight *m_pTrafficLight;

// Waypoints we point to
CWayPoint *m_rgConnectedWaypoints[MAX_WAYPOINT_POINTERS];

// Number of waypoints used (connected)
GLint m_iNumWaypointsUsed;

public:
CWayPoint();
virtual ~CWayPoint();

// Use this for setting up a cars during initialization of the game
GLint m_iCar;
bool m_bCarCanStartHere;

// Our world coordinates
ngVector3D m_worldCoordinates;

Now, these waypoints are placed in the world and connected to each other according to which one you lead to. I used a waypoint manager that kept track of the loading, unloading, and connecting the pointers of each of them to one another. The node number is a unique ID that each waypoint has and is part of what I used to store them in the hash table. One good thing about using this method is that upon saving of the waypoints, you have a database of the waypoints. This allowed for easy integration with the game since it can be a different file for each level, thus freeing up memory. It also made it easy to update each levels waypoints since all you had to do is update the CVS server with one file and the other members of the group didn't have to worry about a recompile if it was updated. The former CarAI would access these waypoints with the accesser functions to receive the information it needed.

When a car requested its destination from the waypoint, the waypoint would first see what axis it was on and then take the lane width, divide it in half, and add that to its position. In our world, I kept all of the waypoints in a two dimensional grid (X and Z). This way, if the vehicle was traveling on a road that was running in the X direction, it would add the lane width divided by two to the Z axis. I determined which lane to add it to by checking the next waypoint and doing a simple and fast subtract to determine which lane (for any road over 1 lane). Look below to see how I laid out the waypoints on the map. The yellow points are the waypoints and the red one is the traffic light. The traffic light will be explained in depth later.

The downside to using this method is that each waypoint had to be hand placed and connected by hand. This was accomplished in a world editor that one of the other people in our group, Mark Robbins, had built. This was time consuming and ended up requiring him to build an undo into it! :) heh I learned too save often to make sure that if I did make a mistake connecting two of the wrong waypoints together I could quickly go back to my last state.