ITC330 Life, Chaos & Virtual Worlds

This subject was run for the first half of 2002. It was 'supposed' to explore the ideas of chaos, complexity, and other indigestable concepts that are used in fields such as Artificial Intelligence, genetics, A-Life, simulations and models of emergent phenomena, etc; and how they could be applied to games, for example in creating an intelligent monster, or a life-like reality. For the most part it was well over our heads and sometimes seemed non-applicable to games per se (the dangers of adopting a subject owned and run by another campus), but it did have one perk, in having a third assignment specific to us games students instead of a final examination. Although admittedly, said assignment was a pretty hefty thing.

For the assignment, we had to develop a complexity scenario that could be used in a computer game. For those who don't know - I suspect that would mean everyone who didn't do this subject (and a few who did! :-p ) - in layman's terms, a complex system is a closed system in which there are many different elements that interact to produce some sort of emergent phenomena. The elements themselves may be very simple, and likewise the rules of interactions between them; but the behaviour of the system and what happens to each element, for any given initial conditions, cannot be easily predicted. A trait of complex systems is that they are very sensitive to the initial (starting) conditions of the system - so even with the same elements and rules, if even one of those elements starts off in a slightly different position, you could get an entirely different result from the system. You can't guess how the system will behave simply by considering each individual element and the rules governing them, because at any particular moment in time each element is potentially interacting with all the other elements simultaneously: you have to look at the system as a whole.
A well-known example of a complex system model is the 'Flocking of Boids' model by Craig Reynolds (see it and many others on his website, http://www.red3d.com/cwr/). This is a model of flocking behaviour, like you might see with groups of birds, hence the name. It has a group of elements ('boids') that fly around in space, and that follow simple rules for sticking together in a group - each boid tries to stay within a certain distance of all the other nearby boids, while also endeavouring to align its heading with the average heading of the rest of the group. Sounds simple, right? The result is far from simple, however; if you just watch the model, you will see groups of boids collecting into flocks and splitting up again, with flocks spontaneously changing direction; it's impossible to predict what any particular boid, and the flock as a whole, will do next.

'TankCoherency' model

Ok, so we have this thing called a complex system, and this assignment that asks us to produce a working computer program model of a complexity scenario that could be used in a computer game... but what? Coming up with ideas for this assignment was a task in itself, especially since we were expected to do something original and innovative with it. Suggestions and starting points included programming a pathfinding agent, or creating an a-life, or writing a fractal landscape generator - but whatever I did, I knew that I'd prefer to create something that appeared to have an intelligence on the screen, and that you could interact with. Eventually I hit upon the idea of doing a pathfinding agent that incorporates coherency and interacts (to a limited extent) with other agents around it.

The premise was simple. In a lot of Real-Time Strategy (RTS) games that I have watched or played, such as Total Annihilation and StarCraft, I have frequently seen that groups of units that the player wishes to move together from one location to another, tend to lose formation and arrive in a disorganised mass as they navigate through the terrain. Now, obviously in some cases you wouldn't want your units to hold a particular formation, just that they get to where you direct them. However, I have seen many instances when units massed for an attack and sent across the battlefield become scattered or jumbled up, and end up arriving piecemeal in an uncoordinated fashion.

The problem becomes most apparent when the units in question all have different statistics and attributes, such as speed, which is common in many RTS games. For example, you might have two different types of tank - a heavy, slow tank that can dish out and soak up a lot of firepower; and a fast, light tank that can't take much punishment, but is useful in a scouting and supporting role. If you amass a group of these two types of tank and send them to attack an enemy installation, invariably the fast ones will scoot off and leave the slow ones behind. Your fast, lightly armoured tanks arrive at the base without the backup of the heavier tanks and get blown to pieces, which leaves your heavier tanks unsupported for when they do eventually arrive. To avoid this, the player has keep reining in the fast vehicles so that they don't leave the slow ones behind, while trying to keep the mass rolling inexorably forward. Again, this may be a desirable attribute of the game in which the challenge is to keep a small but varied force together so that they can fight effectively - but in a different type of RTS, one in which you mass-produce vast numbers of units and throw them at the enemy, such micromanagement is a burden on the player and can detract from the gameplay.

It seemed to me that these problems come about when each unit acts as an individual on the battlefield, and performs its own independent pathfinding and decision processes with no reference to any other vehicles around it. So, why not have the units communicate with one another, with the ability to be formed into a formation that keeps them together as an organised group, and then be able to direct the group of units as a whole? Such a formation of units could negotiate obstacles in whichever way suits them all best, and form up again on the other side. And it would take a lot of the work out of launching an effective attack against an enemy base - instead of having to manage the units individually to get the best performance from the group, the player would be able to manage groups of units simply and effectively.

Yes, such quasi-intelligent units would save the player from an enormous amount of micromanagement while playing the game... but I hadn't really seen such a thing in many RTS games to date. StarCraft, and the WarCraft series before it, were fantastic games. However, try to select a group of units and send them to a destination on the battlefield, and they'll typically fall into a line pattern, each following the same route and with the faster units jockeying for position with the slower ones; hardly an effective fighting formation under many circumstances. Total Annihilation had a smart approach to the pathfinding for groups of units - if you select a group of units and direct them to a destination, each unit will aim at a different destination that is slightly offset from where you clicked, based on their current position relative to the other units in the group. The upshot is that, generally, no two units will be trying to reach the exact same destination, thus avoiding the situation where all the units are fighting with one another to park on the same piece of turf. However, the units still acted totally independent of one another while in transit, which still leads to the fast-deserting-the-slow and 'traffic jam' situations. HomeWorld is another example of an RTS, however it is different from those previously mentioned since it actually incorporates formation-setting for units. Of course, HomeWorld is different from other RTS's in other ways too, not least of which is the fact that it is a game of directing spaceship fleets in 3D space, rather than directing tanks, ships or aircraft, so it's clever facilities for setting up formations are quite integral to playing the game.

For my project, I decided to focus on implementing a coherency-based pathfinding system for a set of ground units. These units can form into any of three different formations, and can be directed through their 3D world, navigating around obstacles, while trying to maintain their formation.

Click for full-screen image

My model is based on a handful of 'vehicles' in a 3D environment populated with 'obstacles'. In this case the vehicles are tanks, that draw on inspiration from Total Annihilation in terms of their statistics (and to a degree their appearance). The obstacles appear as octagonal, light grey structures or varying sizes. Each vehicle performs its own directional/pathfinding/collision avoidance methods in order to navigate around the environment toward a destination point without running blindly into the obstacles. In addition, groups of vehicles can be assigned into formations, in which case each vehicle will be navigating around the environment while trying to stay within coherency of the formation it has been assigned to. The workings of the model itself - specifically the pathfinding/collision avoidance behaviours of the vehicles - is based off the pathfinding work of Craig Reynolds, as mentioned above.

Program manual

Once the program has started, you will be presented with a line of seven vehicles (four green tanks and three brown) arrayed to the right side of the screen. In the top left is a row of bitmapped icons representing each vehicle, and underneath each vehicle is a box that is used to display information on what formation that vehicle is part of (if any), and whether it is the leader of the formation. In the top right is a set of icons for each formation, while in the middle centre is a small quick-reference list of keyboard commands. Text messages and notifications will be printed out at the bottom left of the screen. See the above image.

Because part of the cause and challenge of the phenomenom I have described above is due to units having different properties, the two different types of tank have different attributes. The green tanks are considerably slower in terms of speed, turn rate etc than the brown ones; however, in a game application, they would also be more powerful. All the vehicles use the same pathfinding methods, etc.

The simplest way to run the program is to press 'A', which will run an automatic demonstration of wha the model does for the user to observe its behaviour. This will populate the model world with a number of different-sized obstacles (created randomly), and then run a loop where it randomly picks a few vehicles, assigns a randomly selected formation to them, and sends them on a circular drive around the environment. Once they have returned to their start point, the current formation is disbanded, and a new randomly selected formation assigned to some more randomly selected vehicles. If you don't like the look of generated environment, or (heaven forbid) something goes wrong like a vehicle becomes hopelessly stuck against an obstacle, you can just press 'A' again to reset the demonstration and start over.

If you want to start the program over again from the beginning, press the 'N' key. This will erase all vehicles and obstacles and reset everything back to how it was at program startup. You can also use 'N' to stop an automatic demonstration and return control to the user.

Although the automatic demo gives a reasonable showing of what it does, I wrote the program along the lines of an RTS game, which the user would interact with. As such, the program uses a left-click mouse interface based on what has become pretty much the de facto standard for RTS games in addition to keyboard controls.

To begin with, all the vehicles are selected. Selected vehicles are highlighted with a green box drawn around them, and a green outline will also be drawn on its icon in the top left corner of the screen. To select a single vehicle, simply left-click on the vehicle itself, or on its icon in the top left corner. If successful, you'll hear a 'ch-clunk' sound indicating the vehicle has been selected - it will now have a green box around it and on its bitmapped icon, and any other selected vehicles will be deselected. To select multiple vehicles, hold down the Shift key while clicking - this will select/deselect the vehicle without changing the selection status of any other vehicles. To deselect all vehicles, right-click anywhere on the screen.

Once a vehicle is selected, you can give it orders. Left-clicking in an empty area of the screen will set the vehicle's destination coordinates to that point - you should hear an 'engine rev' sound, and it will begin to drive over there. Once a selected vehicle is moving, you can cancel the move order and stop it immediately by pressing 'S'.

When a vehicle is told to move somewhere in the environment, it receives a destination vector coordinate. It compares this to its current position and heading, and if necessary, turns to face the destination and accelerates to reach it. When it gets close enough, it decelerates to a stop. This much was inspired by both the vehicle movement in Total Annihilation, and the steering pathfinding behaviours demonstrations by Craig Reynolds. As a graphical indication to the user, selected vehicles draw an orange line from their position to their destination.

The vehicles also use a collision avoidance system for navigating the obstacles in the environment, based on one of the steering behaviours demonstrated by Craig Reynolds. If a vehicle is selected, this system will be visible as a set of three lines out the front of the vehicle, that vary their length with the vehicle's speed - one long one pointing along the vehicle's heading, and two shorter ones pointing out the front at an angle to either side of the long line. These lines represent the points to the front of the vehicle that it tests to determine if there is an obstacle in front, and what to do about it. It first checks the two short-range points to either side, and a third short-range point directly in front; the long-range point is only checked if no obstacle was found at close range. If any of these points are found to fall within an obstacle's bounding sphere, the vehicle adjusts it's heading in an attempt to avoid running straight into it. The vehicles are preventing from travelling straight through one another, and through obstacles, by a bounding-sphere collision detection system, that simply takes each vehicle/obstacle position and draws a circle around it - anything that penetrates into this sphere is moved back quick smart.

When you have one or more vehicles selected, you can assign a formation to them. There are three different formations demonstrated in this model: line-astern, which has all the vehicles following one another in a line; line-abreast, which has the vehicles lining up alongside one another; and an arrow formation, which lines the vehicles up in a V shape with a leader at the point. Each formation is assigned a leader vehicle - this is the one commanded by the user (or automatic demo), and the rest will follow it. Any other vehicles assigned to a formation will no longer take orders from the user, but instead takes as its destination vector a point offset to the side and/or behind of the vehicle in front, depending on the formation.

You assign a formation by pressing either '1', '2', or '3' on the keyboard (for each of line astern, line abreast, or arrow formations, respectively), or left-clicking on the relevant icon in the top right corner. Then, left-click on the vehicle you want to assign as the leader (it doesn't have to be one of the originally selected vehicles), or right-click to cancel. Note you can assign a formation to as many or as few vehicles as you want. Once a formation has been assigned, this information will be displayed in the boxes under the vehicles' icons in the top left of the screen. Only the leader of a formation can be directed to a destination - the rest are locked to following the vehicle in front.

When a formation is created, there'll probably be a bit of jostling between the vehicles as they attempt to settle into position. This should settle down after a few seconds, but the more vehicles in the formation, the longer it will take. You can have more than one formation at any one time, so long as they aren't the same type. Also note that a vehicle that is part of one formation cannot be assigned to another without first disbanding the formation it is part of. To disband a formation, select one or more of the vehicles of that formation and press 'D' or click the 'disband' button in the top right of the screen.

Once a formation has been created, the lead vehicle can be given a destination vector, and it will lead the rest of the vehicles there. If the vehicles encounter an obstacle, they will fall back on their individual collision avoidance methods, and may sometimes temporarily break formation to follow a different route around the obstacle, before joining back up on the other side. They will try to remain in coherency as much as possible, but if one falls too far behind (as can happen with a fast vehicle leading a group of slow ones), it will signal the leader to stop to allow it to catch up.

You can experiment with different formations, and compare the way the vehicles behave when directed somewhere while in formation, as opposed to directing a group without assigning them to a formation. Of the three formations inplemented, line-astern is undoubtably the easiest and most flexible formation: it negotiates the environment quite well, with the line of tanks easily snaking around obstacles, and is the quickest and most trouble-free to form up and navigate through the environment. Line-abreast and, to an extent, the arrow formation are much more unwieldly, as the vehicles have some problems with trying to hold station to the side of another vehicle - especially when that vehicle starts pivoting to aim at it's destination, which naturally changes the destination vector offset to its side! The arrow works (and looks) a bit better, but it still has some problems. To help alleviate these problems somewhat, the vehicles are set to follow a 'boids'-style flocking behaviour of adjusting their heading to that of the leader vehicle, whenever they are in position in the formation. Once the formation is moving forward, there's not much problem, but the chaos that ensues when one vehicle in a line-abreast formation pivots more than a little way could well be more frustrating to the player of an RTS than micromanaging units ever was! As it stands, these formations could be a good option for attacking (so long as you only moved straight ahead), but poor for simply navigating around, in comparison to the line-astern formation, and would need some smarter algorithms behind them. For these reasons, the automatic demonstration is limited to picking no more than five vehicles for either line-abreast or arrow formations.

Now for environment controls. When the program starts, there are no obstacles in the environment, so the vehicles will have nothing to navigate around. There are two methods for creating obstacles - with the random generator, and user-defined. The first method is to press the 'R' key on the keyboard - this will generate an obstacle with a random position and a random size.

The second method is to press the 'O' key. The message line in the bottom right will indicate that you are now creating a new obstacle, and any selected vehicles will have their selection boxes dulled to indicate that interactions with them have been temporarily disabled. Left-click where you want your obstacle - the program will now show a green wireframe of an obstacle centred on that spot, that grows or shrinks as you move the mouse. When the wireframe is the size you want it, left-click one last time - the solid object will appear there, and the program will resume running as it left off. You can make obstacles any size you want (up to a preset maximum), but you should avoid making them too small or they may confuse the vehicles. You can have a maximum of ten obstacles in the environment.

You can manipulate your view of the 3D environment and vehicles with the arrow keys. Left and right arrow keys rotate the view in that direction, and up and down adjusts the elevation of the viewpoint. You can only interact with the model from the default viewpoint, however; simply click the mouse or press the spacebar to reset the viewpoint to its original position.

Finally, to exit the program, press the Escape key.

Known bugs & SNAFU's

Just as I was preparing the Release version of the program for assignment submission, it broke my heart to discover a bizarre bug that triggers the automatic demonstration when you assign a group of vehicles to an arrow formation. About all I could determine was that it seemed to be tied to that formation's ID number of 3 - but I have no idea why it triggers the demo mode, nor how to fix it.
I didn't want to lose the arrow formation, as it was my favourite one, so in the end I decided to shift the problem elsewhere, by swapping the arrow formation's ID number with the line abreast formation's number. This means that if you are working with the program outside of demo mode and assign a line abreast formation, it will trigger the automatic demonstration (oh well, never liked that formation anyway). So, if you want a line abreast formation, all you can do is watch the demonstration and see it what it does. However, the arrow formation will work.

I know that there also seems to be a problem with assigning a line-astern formation, disbanding it, and then trying to re-assign it, but that can be overcome by hitting the 'N' key to reset the program back to the start. I'm quite sure that there are other bugs I've not yet found. Ah, the joys of programming...