Posts Tagged ‘concurrency’

Tower Defense as a Thread Model

Thursday, June 11th, 2009

I keep having the strangest reoccurring dream. In my dream, I’m playing a turret defense game. 1 However, it is no ordinary tower game. It’s actually a thread process model. In the dream, each turret type represents a thread synchronization mechanism, generally some sort of atomic primitive. The units marching along the paths represent the threads that require synchronization. Most are worker threads calculating a result set, but some may be polling threads reading device updates or doing other jobs. The range circle of each tower and the position of the unit along the path represent states when it is appropriate for the thread to be accessed, either quiescent states or work states where the thread has completed some useful task and has a result ready to be read. If the unit\thread moves out of the turret\synchronization range circle, the thread result is lost or held and operation on the next work cycle begins. Shooting a unit\thread with a turret is a read\synchronization operation and gathers the result.

Yeah, I know, clearly I’ve had threads on the mind a little too much lately. 🙂 I’ve been working on a major refactor of the engine at work and thread synchronization problems are tricky.

Usually when I have dreams like this I wake up in the morning and have a good laugh wondering what the heck I was thinking. This time, however, I think there may be something to it. Now, I’m not suggesting a design built literally on the model exactly as it is in the dream but I think there are elements that could be useful.

The part that is intriguing about the turret defense thread model is that you can guarantee completion (all units hit) without guaranteeing really very much at all about either the turrets or the units. The units are not synchronized with each other; in fact, in many tower games faster units can overtake slower ones. A unit does not guarantee a minimum speed–it may even be allowed to stop entirely on occasion–although it does guarantee a maximum speed. The turrets are not synchronized with each other, nor do they communicate any information to each. A turret does not guarantee a specific number of units hit, only that it will hit units at a specific rate. A turret also does not guarantee what order it will fire at units in. A unit likewise guarantees nothing about when or by whom it will be hit except that it can be hit when it is within a valid range.

Yet, with a sufficient number of correctly placed turrets all the units will be hit with none escaping. More importantly, most of the time you can have far fewer turrets than units and still complete successfully. The number of turrets required is a simple function of the maximum speed of the turret, the maximum speed of the unit, and the number of times the turret must hit the unit for completion. Placement is trickier, but with a thread model you could surely replicate that with signals.

Fascinating, isn’t it?

I’m not sure yet where to go with all this, but it seems like there’s a useful idea to be gleaned. It’s not that different that a traditional worker pool, but the lack of communication seems important. I’m sure there’s something useful that can be done with this.


1. For anyone who cares, the specific game seems to be Crystal Defenders, but with some elements of Bloons Tower Defense 3.