Posts Tagged ‘c++’

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.

Quote of the Day

Thursday, April 24th, 2008

“I have always wished for my computer to be as easy to use as my telephone; my wish has come true because I can no longer figure out how to use my telephone.”

Bjarne Stroustrup

One Dozen Easy C++ Programming Tips

Wednesday, December 12th, 2007
  1. Consistency breeds ease of use. Even if your buttons do some weird thing, as long as they all do the same weird thing users will eventually figure it out. Make the buttons each behave differently, however, and the user is lost forever.
  2. Sort data the way it is most likely to be used. The logical sort order for a date is chronological, not alphabetical.
  3. When in doubt, the default option should be the least destructive \ most undoable choice.
  4. If you have to write an explanation of your code, never assume that the reader has read the same papers you have, unless you told them what else to read–and where to find it–first.
  5. Wrong code comments are worse than no code comments.
  6. “Copy and paste” errors happen to everyone. Be on the look out for them.
  7. If a bug disappears in debug mode, 90% of the time it will be one of two things: 1) you are overflowing memory or 2) you have a thread race condition. At least two thirds of the time, it will be a memory overflow. It is extremely unlikely it is problem with the compiler.
  8. Releasing your program compiled in “debug mode” is not an acceptable “fix”. The bug only looks like its gone… it’s still there, and can come back to bite you at any time. Don’t do it, no matter how tempting it might seem.
  9. If the program crashes on exit, you probably freed something you didn’t properly allocate, or that isn’t allocated anymore.
  10. Leaking memory is bad. Freeing pointers or objects that don’t belong to you is worse. If an object you expect to be free is still hanging around, don’t force it, find out why… “fixing” bugs by patching the symptoms and not the cause makes the code much harder to repair in the long run.
  11. If you have an intermittent bug, and your “fix” made it go away and you don’t know why, the bug is almost certainly still there. If you can’t explain it, you didn’t fix it.
  12. Good documentation is more important than more features. Write it down, even if it’s just a simple “readme.txt” file… the next person who has to work with your stuff will appreciate it!

More tips? Ideas you would recommend? Post a comment!

A Million Objects

Sunday, December 9th, 2007

From a Zen Kōan:

Gyosan asked Isan, “If a million objects come to you, what should you do?” Isan answered, “A green object is not yellow. A long object is not short. Each object manages its own fate. Why should I interfere with them?” Gyosan bowed in homage.

It’s good advice for programming multi-core, too.