I got the nydus canal algorithm working in Crescendo!

What the heck is a nydus canal, you ask? Well, no time to explain it all, but it is a Zerg building in the massively popular RTS game, Starcraft. It works like a teleporter, such that units that go in through one nydus canal come out the other.

When the units come out the other side, the game code has to figure out non-overlapping places to put the units, so they don’t end up on top of each other. My game has crazy trees dropping acorns and squirrels, so I needed to come up with a similar algorithm for figuring out what spaces to test for to see if they are unoccupied around a given unit (the tree).

I had trouble figuring out the geometry, but today I asked my friend Philip, who helped me greatly with the Abound screensaver physics, and he had a good idea. Here is the result:

The center circle is the Tree that is dropping acorns. The first ring of circles circumscribing the center circle (the green ones) is the first places I will try to place the acorn. If all those spots are already occupied by other game units, I expand the search out to the next ring of circles and try those spaces, etc.

This is the way programming works for me: Things like this algorithm that don’t seem like they would be hard to do actually end up taking several hours. In this case, I worked on figuring this out for about four hours. The final code is only about 25 lines long.