Justin Rogers

Terrarium: A path-finding dream/nightmare...

Path-finding in the Terrarium is a classic David versus Goliath problem.  While the groundwork for enabling path-finding experimentation in 2D was always there, some of the implementation details tended to make it hard for people to try out new ideas.  What are some of the great features in the Terrarium with regards to path-finding?

1. A basic 2D movement system using basic waypoints to start movement and a movement completed callback system.
2. Static terrain elements in the form of plants.
3. Dynamic terrain elements in the form of other creatures.
4. The callback system implements a blocked routine so you can find out if your movement completed 100% or you got blocked along the way.

I think we got these parts right.  Movement in the Terrarium is as easy as a MoveTo(Point).  Your creature will make a straight line path for that point.  If you run into something you can try to move around it or provide whatever algorithm you'd like.  This means algorithms can be completely reactive without any form of prediction (reactive by responding to blocking events, rather than predictive in trying to plot the optimum path up front).

We also got some things wrong in the path-finding implementation.  These are things that either made it difficult to implement precise path-finding or left developers confused.

1. We used a grid cell system that encompassed an 8x8 pixel area.  Each creature took up a grid area that was used to compute blocking.
2. The line drawing algorithm used internally made it hard to diagonally navigate by blocked cells.  Even after publishing the algorithm, some authors had trouble with navigating terrain and randomly getting blocked even though they felt they shouldn't.
3. We never provided any helper algorithms for path-finding.  This was just a lack of time on our part.
4. Our Vector implementation had a poor Sqrt implementation.  We used an approximation that was as much as 10% off at times.  Yuck, that isn't very accurate at all.

Even with all of the issues with the path-finding system, we had thousands upon thousands of creature authors (We love you guys!).  Every author had a slightly different approach to path-finding I'm sure, but I can identify several classes of implementation.  I'd like to do this, because it shows how Terrarium was an excellent environment for spec'ing out new and interesting ideas.

1. A*.  Go figure right?  Of course the most popular robotics path-finding algorithm would be implemented at some point.  I think most of the creatures wound up using something like A* to do the path-finding.
2. Divide and Conquer (for lack of a better name).  This is your classic recursive refinement algorithm.  Plot waypoints which recursively define a more refined path when a blocking agent is in the way.  I used this most often, because it was fast, I could spread the refinement over multiple game ticks, and I never had to worry about using too much processor time.
3. Reactive path-finding.  This was the simplest algorithm we ever saw.  Basically, move blindly to a point.  If you get blocked then try to move in reverse vectors for some period of time to try and get around the blocking agent.  Eric Zinda, the brain behind the original Terrarium, was the first author that used this approach and it worked quite well for most developers during the initial release of the Terrarium.
4. Gravity path-finding.  I loved talking about and implementing this approach.  Basically, every agent in the system defines some degree or aura of repulsion.  This resulted in very organic path-finding with creatures taking arc'ed curves around blocking agents to try and get back on track.  Gravity was defined by the threat a given blocking agent defined, so that you might be repulsed very early by carnivores if you were a herbivore, or you might even be drawn to a plant.  A better name for this might be Magnetic path-finding or even influence mapping (this is the technical name for it), but the original note describing this algorithm used gravity, so I'll stick with that to honor the original idea.
5. Influence Mapping.  I think this deserves it's own section as well.  All of the above algorithms can be enhanced using influence mapping.  At some point you have to decide where to move and influence mapping can help make that decision, as well as influencing how you get there.  For A* there is a concept of a cost for each cell you move through and by influence mapping an area you can provide better costing for cells based on whether or not there is a threat or benefit in a given area.  (I want to move to X, but if I can eat plants along the way, then that is cool too, even if I have to move a bit further).

Moving forward I think the Terrarium source code will enable AI developers to better define arenas for testing various forms of path-finding.  Changing the grid cell algorithm out for a radius algorithm would be the first order of business and would allow for much more organic movement rather than the square movement of the current Terrarium.  Using a more solid vector class and other helper libraries will enable much more rapid prototyping of higher level algorithms.  Being able to modify the environment and provide more types of simulation (weight mapping the terrain using height values) will enable more complex terrain to navigate making more specialized path-finding algorithms better suited to navigating a Terrarium than the generic algorithms currently used (currently time is a big issue and the most basic algorithms tend to be the most highly used.  With some small changes to the code-base more specialized and time consuming algorithms may become more important and better suited than the simple/generic methods of today).