The project I'm currently working on is a truck driving training simulation. My role is to developed the world in such a way that AI vehicles follow the rules of the road, and so that we can evaluate the driver performance via a fairly extensive collection of scoring tests that penalize the driver for failing to adhere to the rules of the road. We are attempting to implement tests for each of the rules specified in the K53. The world that is being built is to be used as a generic driving world for future projects of this nature, but is based on Durban city.
The artificial intelligence engine is an extension of the system that we developed for a military project called CJOps a few years ago. That particular project was based in a rural environment, whereas this simulation is based in the bustling CBD of an urban environment. Significant additions were thus required in order to meet the criteria for this project.
AI vehicles and pedestrians are semi-autonomous. Their navigation behaviour requires that routes and paths be laid down in our in-house editor. These include such information as traffic flow direction, speed limits, spawn points and the placement of world features such as stop streets, yield, traffic circles, traffic light and intersections. Additional information such as traffic density and the specific types of vehicles that appear in different parts of the world is also specified in our editor and read in by the sim.
The computer-controlled vehicles and pedestrians choose their own objectives and destinations, follow routes as necessary, perform collision avoidance behaviour and react to one another in realistic manner. Pedestrians will move out of the way of oncoming traffic and will wait until it is safe to cross streets. One of the modifications that was previously required was to limit the extent to which pedestrians avoided vehicles -- they were too effective at this and we were concerned that this would provide negative training as the driver of the sim could drive fairly recklessly without hitting pedestrians. Ironically, we had to dumb them down to rectify this.
Collision avoidance behaviour is implemented using predictive collision zones and vector math. By predictive collision zones I mean a collection of collision boxes owned by each AI vehicle that extend outward ahead of the vehicle by a distance determined by the current speed of the vehicle. These turn to follow the path of the vehicle rather than stretching directly ahead. As such, they basically tell you where the vehicle will be N seconds from now. When these intersect those of another vehicle, we can determine whether a collision is going to occur in future and have the vehicles behave as appropriately (for example, slowing down, yielding or stopping).
Much information can also be gleaned using vector math (using dot product and cross product operations on various vectors such as forward vectors, right vectors and the vectors from one entity to another). For example, if we assume that vehicles drive on the left side of the road (as is the case in South Africa), then whenever a pedestrian crosses the road, vehicles will approach from the right hand side. By acquiring a list of all nearby vehicles and checking the dot product of the pedestrian's right vector and the forward vector of each vehicle, taking the movement speed and distance of the vehicle into consideration, we can determine whether the vehicle is approaching the pedestrian and likely to hit it. In this instance (assuming both vectors are normalised), if the dot product of the pedestrian's right vector and the vehicle's forward vector is close to -1 (to determine 'close to' some threshold is necessary) then the vehicle is approaching from the pedestrian's right hand side. This kind of logic is, for example, used by pedestrians to know whether it is safe to cross a road.
Of course, in order to ensure the AI engine performs well, world partitioning is required. Rather than using an octree or a quadtree we chose to use a dynamic grid-based system. Since the world is very large, the dynamic grid is re-calcuted periodically based on the main vehicle's position. This grid allows us, for example, to filter out large numbers of vehicles when acquiring lists of nearby vehicles.
In order for the logic governing the behaviour of computer-controlled entities and the logic for evaluating the drivers performance to work as intended, the world must be built to certain specifications, both from the artists side (in the way the terrain geometry is modelled and the naming convention of materials) and from within the editor (much of the behaviour is determined by the placement of various zone types).
Painted lines on the road such as dotted lines, solid lines, parking lines, the lines at stop streets and yield and so on all use specific material names. Separate materials are also mapped to each lane. Ray-casting downwards allows us to check terrain height at each wheel, as well as the material at that point. This allows us to determine when vehicles change lanes, cross solid white lines etc. The same data used by the AI vehicles is also available to the main vehicle for scoring checks.