Travelogue

StateThread library is a user level threading library which implements a cooperative threading model. Since its cooperative there is no need for mutexes etc and each thread is very light weight with a small stack allowing you to create thousands of such threads at any time.

In the game I decided I will model each state machine as a separate state thread and every timestep just let each thread run to update its state. The only problem though is that the main thread needs to schedule each thread in sequence as each thread needs to yield control for any other thread to run. As a result i implemented a 2 state run method for each thread ( runnable/wait Queue).

Each child thread will be in one of these states, if its in runnable , the main thread will schedule it for running. Once a thread completes its iteration it will move to a WaitQueue state. Once each of the runnable threads are done running the main thread broadcasts a condition variable to indicate movement of all waitQueue threads back to runnable status, where they again block on a condition variable waiting for the main thread to yield control to them.

Implementing this took a bit of time mainly due to me using a 3 state system earlier with the thread explicitly signalling to the main thread but for some reason the main thread was never getting the signal and both the threads would block indefinetly. Now the main thread signals a runnable thread and yields control by calling st_usleep(0) immediately after the signal. This works beautifully. Now I am able to create a few hundred entities without much perceivable slow down in frame rates. I am still doing a healthy 125 fps or more on my really old nvidia GF4 Ti4200.

What I feel about this system is that it allows me great flexibility in designing game AI. Imagine a typical situation of giving orders to an unit.

Now with each unit I can now assign a Priority Queue which works like a command queue. All commands to the Unit are queued to it and when the thread gets a chance to run it runs through the commands as fast as possible. Now since its a priority Queue we can handle like User commands higher than AI instructions or vice versa or even assign individual events higher priority. Like if it gets a user command as well as a DIE instruction because the AI computed that this unit is dead due to an attack, then probably we should probably ignore the user command as it may change the state of the unit to a situation where it doesn't die making the AI command completly invalid cause if dont' ignore the AI command the user will see the bullet miss the unit but the unit still dies!

But if all these events are processed in the same frame probably it won't matter. Further this also allows units to be grouped very easily. When a bunch of units are grouped we can just create another thread which manages all the grouped entities. The individual AI threads for the units will just look if the unit is currently grouped and can disable certain local decision making and give priority to the group decision making.

When the unit is then given a new instruction we can detach it from the group and send it out on its own and at the end of the assignment rejoin the unit to the group. This allows a myriad possibilities in better group AI.

Imagine forming a group out of different kind of units like siege weapons, infantry, mechanized infantry and tanks. Now the group AI can acquire targets and send individual units against different kinds of targets. These units will run individually for some time and at the end of the assignment rejoin the group AI thread as available. Group threads themselves can be group controlled by our Master AI thread. This kind of a model I feel will lead to a significantly stronger AI than what most computer games have today. The challenge though in game AI is not the modelling but also the decision making that needs to happen in very short time intervals. I am not sure if I will be able to achieve it but its a good starting point!.

I probably will also release the code as a simulation framework allowing people to design their own simulations by just coding the Unit AI/Group AI and watch their simulation unfold.