Legacy Projects: Real-time Strategy

Yesterday I decided to post some vids of old projects that I've not posted about or which I never posted videos of. Today I'm dumping a few vids of RTS projects I've tinkered with.

They all use my RTS framework 'Warsmith', which I've been working on for many years. My old project Zyrtuul was where the framework originated. There are 4 prototype games that use the framework. My main focus has always been the framework itself, with the game prototypes being just a side effect.

Implementing Path-Finding in Zyrtuul

In this post I discuss my implementation of path-finding in the real-time strategy game I'm currently building (the working title for the game is Zyrtuul, though I might end up changing that).

A commonly used path-finding algorithm in game development is the A* algorithm (pronounced 'A star') which is an extension of the older well-known graph traversal algorithm called Dijkstra's Algorithm. I coded up a C++ implementation of various path-finding algorithms back in 2005 (as part of one of the demonstration applications that accompanied my CompSci master's degree), so I chose to re-use my old implementation of A* rather than re-inventing the wheel.

I started off coding the game as well as the game engine in C++ because, at the time, my main interest was in developing the underlying technology. But as it progressed I started wanting to focus on the actual game rather than the technology. Coding the engine and game simultaneously was simply taking too long (and I wasn't really learning anything new, having done so much engine work over the years already). So I decided to switch to the Unity engine for the game.

Unity doesn't support C++, instead you write scripts in C# or Javascript (edit: apparently Boo and their own language called UnityScript are also supported). I am therefore now coding in C# (simply because I have more experience using C# than the others).

Converting the code from C++ to C# was initially pretty straight-forward until I realized that C# does not provide a priority queue (a fundamental component of the path-finding algorithm) as part of its library. With my initial C++ implementation I was using the STL priority queue, but I now realized that I would have to find an implementation online or else write my own.

A priority queue is a data structure that keeps its elements sorted based on some user-specified criterion, in our case based on the path node cost / distance when conducting a path-finding query. In short, a priority queue is the most efficient way of performing path queries because of the fact that it automatically keeps itself sorted when you add or remove items.

It seems that the Microsoft C# team decided that a priority queue was too niche to be included in the .NET foundation library, so I was out of luck. Fortunately others had encountered this problem as well and so I was able to find a priority queue C# implementation online that, with some minor modification, suited my needs. Once the priority queue was done the rest of the graph traversal / path-finding code came together nicely. So I ended up getting a task that would ordinarily take a significant amount of time and effort done in about a day due to code re-use.

Path-finding solved the macro-navigation problem (navigation on a large scale), but micro-navigation was still a problem due to the fact that the pathing grid has limited resolution and also due to the fact that the grid is not static -- moving entities can invalidate previously valid routes. A vehicle could easily determine that to get from one side of the map to the other it needed to move around a lake or large obstacle that was blocking its way, but it still had issues on a smaller scale. For example, if vehicle A was told to find a path to some point and then vehicle B was instructed to move to a location that blocks this path, vehicle A would eventually encounter vehicle B and need to determine how to deal with it.

For this game I could get away with very simple collision detection and collision response based on bounding spheres and having vehicles 'pushed away' from one another when they are colliding. This partially solved the problem of vehicles coming into contact with one another (they would simply push one another out of the way), but was far from perfect as it could lead to 'jostling'. Also, it just made them look downright impolite. If two vehicles were headed directly toward one another, they would simply push head to head with neither able to get past. Alternatively, if you told many vehicles to move to a single location they would all mass together, jostling and pushing one another in an attempt to settle at that location.

One attempted solution was a "frustration factor"... when a vehicle was too close to another vehicle it had a frustration factor value that represented how 'frustrated' the vehicle was, with the idea being that it would eventually decide to simply find a new path to its destination it it became annoyed enough. This was simply a floating point value that increased over time when the vehicle was too close to another vehicle, and decreased over time when it wasn't. If a vehicle's frustration factor rose beyond a certain threshold it would request a new route to its current destination. Unfortunately I spent far too much time trying to get this to give the desired results and I found it to be too unpredictable. Eventually I decided that the moment a vehicle encounters another vehicle, one of the two vehicles must immediately find a new path. I arbitrarily decided that in the case of path blocking conditions the unit that was created first gets to keep its current path and the more recently created unit has to find a new path.

Quite a few other rules are also in place to handle various conditions and edge cases, but I think I've already written too much and so won't go discuss these here. The navigation behaviour of the individual units is fairly solid at this point, but not quite perfect (it's close though, better than some commercial RTS games I've seen). However, it will suffice for now -- I can hone it further later on, when polishing the game up.

Truck Simulation Using Durban Driving World

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.