Justin Rogers : Terrarium, Algorithms

Game Development: Book resources for users interested in more in-depth world generation discussion.

Justin Rogers — Wed, 13 Oct 2004 09:57:00 GMT

I think every book kind of covers world generation in an off-handed manner. There are very few books actually focused on the process of world generation alone. By world generation, I don't just mean the creation of terrain, and I'm instead talking about the population of the final world space with objects that the user can interact with. Terrain is sometimes part of the process (Tribes), but only comprises a portion of world generation.

Normally this manifests in games where space is of the primary concern. The layout of space is fixed (aka empty and unimportant) while the units that define a location in space are important, the actual space isn't really all that important. World generation comes into play with the dynamic and/or static creation of planets, trade routes, goods and services, random enemy encounters, and the rest of the automatically generated content that changes every time you might play the game.

We are also focused on automatic generation here and not static generation. Games like Halo, Fable, and the other big guys, don't leave room for error. They have someone hand-design each of the levels. At times they use automatic procedures to get a hint at what a level is going to look like, but they most often drastically modify this hint into the final product.

The game Elite was capable of generating enough data dynamically to consume the memory of today's machines, but was able to run in a much smaller working set (32K ;-). These guys really used world creation algorithms to generate something from nothing, when they really had nothing to start from but the most minimalistic code. That is all that would fit on the tape drives and even then you wanted your game to be up and running without waiting hours to be loaded into memory.

The first resource for this type of examination is a really poor example and I don't recommend it for all but the most complete game programming book collectors. Infinite Game Universe: Mathematical Techniques (Advances in Computer Graphics and Game Development) starts out slow, reads slow, ends slow, and doesn't provide nearly the information that you'd think it should. The latest reviews on Amazon are ultra poor. At $35 discounted price it is a buy only if you are interested in several historic techniques and not necessarily the latest techniques for automatic world creation. Also note that there may not be any latest and greatest techniques for world generation, and instead most groups use either a pure math or brute force approach. Both are possible on today's machines.

Sadly enough I got to right here, swearing I had at least two more resources on my shelf. You know what? That isn't the cast. That is the only resource fully dedicated to more than a single aspect of world building. Since that is the case, I'll go ahead and plug a great terrain generation book Real-Time 3D Terrain Engines Using C++ and DirectX 9 (Game Development Series). This is definitely a meaty book. All of the code is in C++, but easily translated into C#. In fact if enough people pull my leg I'll drop a source zip somewhere of nearly the entire book translated over into C#. I'm not sure of the legality of such practices, so I'll actually format an appropriate email to Greg and the publisher before I go and do something that might get me in trouble.

Ah ha, I knew I'd find another resource, but again, mainly terrain based (which is probably why it took me so long to find)... It was also in an AI book, AI Game Programming Wisdom 2, making it that much more difficult to just pull off of a shelf. One article (7.4) details the process involved in creating the random maps in Empire Earth. There is actually some good world building knowledge there, even though you are just creating a 2D map... Further, article 7.6 details the process of creating walls. Now, as done during part of a strategy you might not consider this world generation, but if done before-hand you would. I'm inclined to say this is definitely world-generation even if it is a run-time modification.

That is what I have for you. In terms of managed resources, we released the Terrarium world building code at some point, but I can't seem to find where we did that exactly. Most of the information is for mapping a world, specifically a height field, back to a 2 dimensional display. We originally did Isometric tiles, but the latest version run using larger square tiles. .Netterpillar appears to have some world generation code and I'll gladly provide a link to any discussion of that particular code if David tosses it online and maybe shows off a few enhancements? I think that would be extremely awesome.

Terrarium: How do we punish creatures that take too much time?

Justin Rogers — Mon, 29 Mar 2004 08:02:00 GMT

Okay, so Darren Neimke thinks this deserves a blog entry and I think he is probably correct. The method for punishing creatures that take up too much time really isn't understood and the methods are actually somewhat complicated, so they deserve to be examined. I talked about the Terrarium game loop in an earlier discussion that you can view here with specific comments about punishing creatures time-wise, without explaining how, “Terrarium: A focus on game loops and scheduling”.

The first thing we do is time an average creature. We assume that an average creature will do specific amounts of specific things. Right now those things include adding/removing items from collection, processing collections in loops, and making mathematical decisions. We do this using three methods:

InitAI - Simulates initializing data storage for AI components. Here we basically create all of the collection storage and create a sample organism state that defines our creature for later comparison.
DistanceChecks - Assume the creature will do a certain number of distance checks. Currently we time 50 complex distance checks. If you optimize your distance checks you could easily quadruple this number. We end up making a bunch of calls to rand to create the random locations, and then compute a solid square root using the Math.Sqrt function. (You can use an approximation to speed things up here).
StoreInformation - StoreInformation stores a bunch of random creatures and plants into varying arrays depending on whether or not they are friend or foe. This again lets us do a series of additional distance checks to determine the closest creature.

We do this a few times to warm-up the GC and get the methods JIT'ed. Then we clear the timing information and run these tests 100 times so we can get the average. Depending on the timing returned, creatures will on average get about 2 ms to operate their tick based on the timings that we do. There is a kind of minimum timing that creatures will get and a theoretical maximum, that causes an assertion that only happens if you break in the debugger during this method (or you have a horked run-time since you work at MS and you just compiled yourself a bug in your code ;-).

We use the base-time to determine how many creatures your computer should run as well, since we want to fit all of the creatures within about 300 milliseconds or 3/5ths of a game tick. That is why some machines have smaller world sizes than others. The maximum timings for creatures dictate this size, even if creatures only use half the time, we still don't allow more to operate since if the creatures did use the time it would elongate the game tick and cause choppy speed artifacts.

Now for the fun stuff. When the creature gets run, we time them to make sure they don't go over their maximum time allowance. We do this unobtrusively, so that we don't break creatures that are only going over by a little bit. We never interrupt the creature unless they go really over the time limit. In fact, the deadlock detection routine allows for up to a couple of seconds before the creature actually gets blacklisted using the deadlock routine. Blacklisting is really bad, since we zero out the creature's assembly and it no longer loads or allows that creature to participate.

Under normal operation, creatures actually do return though, and we check the amount of time they spent processing against the allowed quantum. Depending on the state of things, we add points to a special overage variable or subtract them off if they didn't use all of their time. Overage is a number between 0 and some positive amount, and we never let you have a negative overage amount that allows you to essentially process longer in the future because you didn't use your time earlier.

At the beginning of the following ticks, if your overage ever exceeds _maxOverage (something like a couple times the quantum), then we process your tick without you. Basically, the creature class processes it's portion of the tick, but you don't get called. You can check if you get skipped at any time by checking the TurnsSkipped property on your creature. Unfortunately overage is stored within the game engine itself, so you can't really check if you are operating too long until you've been skipped at least once and been notified using the TurnsSkipped property.

Note you have to check this property every time you run your code because it does get reset if callbacks into your code are made. This is to ensure that it only holds value when you need to know how many ticks have elapsed since the last time you got to process a turn. This can be important since various actions may have completed and you'll never get the event handler callbacks for them (they were processed while you were taking a processing nap for being naughty ;-)

A large number of developers have expressed concern that they don't know how much time they have left or how much overage they used. Our response is that the Terrarium is not about maximizing the amount of time you have available to you, and it isn't about managing your overage allowing you to think longer than you should some ticks and then buy your overage back down on other ticks. It is simply about writing simple and effective algorithms to solve the problem space provided to your buy the Terrarium environment and other creature authors. Note, the rules for stopping the processing of a creature would have to be quite a bit more strict if we did give out the overage information. There are a number of gameplay attacks and tick elongation issues that developers could introduce and then completely work around the detection logic. That would be extremely bad.

To wrap up:

Your creature is granted a time quanta within the Terrarium based on tuning metrics of the average creature developed very early in the Terrarium process. This tuning logic has worked for a long time now and is an effective method for load balancing the number of creatures per machine and the amount of time they should get to run.
Creatures that hang can cause deadlocks. These creatures are removed from the system (the entire species, not just the instance), and never allowed to run on the machine again (assuming Ecosystem mode).
Creatures that go over their time by small amounts here and there are never affected. These creatures end up buying back their overage by going under the allowed quanta on some ticks. This is how the average creature functions in the Terrarium.
Creatures that go over consistently eventually have their ticks skipped. These creatures can determine that they are being bad by checking the TicksSkipped propery in their code to determine if they have been skipped during the previous tick(s). This can be used to custom tune depth in path finding algorithms, shrink problem spaces, or provide better maximums for collections that are being processed.
Giving programmatic access to overage variables means possible attacks against the scheduling logic that would allow for UI/gameplay issues to arise. To combat these attacks the Terrarium would need to employ extremely strict rules on how creatures are run, and the liberal allowance of overage currently allowed that works so well would have to be revoked and replaced by a system that didn't allow nearly as much overage. The threading system would also have to be replaced with a much stricter system that would, in many cases, break into user code while it was running and short-circuit user code execution paths. This would place a great deal of stress on the user to write code that would recover from such a situation, along with numerous gameplay issues since the creature wouldn't complete it's tick.

Taking a closer look at the power provided in stack based finite-state machines.

Justin Rogers — Thu, 25 Mar 2004 02:52:00 GMT

Abstract:
I've blogged before on the various types of finite-state machines you could possibly use in the Terrarium, but I didn't really go into any depth on how you might take advantage of them. So I'm going to take this opportunity to talk about stack based finite-state machines, how your engine can quickly and easily interact with them, and propose an extension that allows for nested finite-state machines.

Requirements for a stack based FSM:
Well, the largest requirement is a stack where you can store state information. You can either have the engine store this stack for you, or allow the FSM to store the stack. I'm going to assume that the FSM is going to hold onto the stack for now, but we'll have to add some new rules later for nested state machines to operate properly. Since this is the .NET world I am going to take full advantage of delegates to implement our state machine. Each state will consist of a method callback and an optional data pointer to store extra data. We'll use an object for this, but you could strongly type these if you wanted to.

We'll encapsulate all of this data into an abstract base class that we'll expect each FSM to inherit from. This allows us to create a strong contract with the engine, so it won't be left wondering what to do once the FSM is added to it's queue. Our base class will provide access to the stack, provide a default idle implementation, and in the future could perform other important operations.

using System;
using System.Collections;

public delegate void StackFSMStateCallback(object extraData);
public class StackFSMState {
    public StackFSMStateCallback callback = null;
    public object extraData = null;

    public StackFSMState(StackFSMStateCallback callback, object extraData) {
        this.callback = callback;
        this.extraData = extraData;
    }
}

public abstract class StackFSM {
    private Stack stateStack = new Stack();

    public StackFSMState GetNextState() {
        if ( stateStack.Count > 0 ) {
            return (StackFSMState) stateStack.Pop();
        } else {
            return new StackFSMState(new StackFSMStateCallback(this.Idle), null);
        }
    }

    protected void SetNextState(StackFSMState state) {
        stateStack.Push(state);
    }

    public virtual void Idle(object extraData) {
        SetNextState(new StackFSMState(new StackFSMStateCallback(this.Idle), null));
    }
}

Creating our first FSM based on the stack:
Creating a new FSM based on the stack implementation is pretty easy. We just need to override the Idle state method and provide our own implementation. What would happen if we just wanted to randomly pop a new state onto the stack to execute 10% of the time. This would actually be pretty easy. BasicFSM does just that. We are adding Console.WriteLine calls so we can understand which states are actually executing. If we are in Idle we'll print that we are in that state, else we'll print we are in the Basic state. Notice that I'm calling base.Idle whenever I'm not doing any processing. This isn't required, but since base.Idle simply pops a new Idle state onto the stack, I might as well use it. I could just as easily pop the state onto the stack myself, or simply not pop anything at all, since the GetNextState method makes sure we always return a valid state event.

public class BasicFSM : StackFSM {
    Random rand = new Random();

    public override void Idle(object extraData) {
        Console.WriteLine("Running an Idle state");

        if ( rand.Next(0, 10) == 5 ) {
            SetNextState(new StackFSMState(new StackFSMStateCallback(this.BasicState), null));
        } else {
            base.Idle(extraData);
        }
    }

    public virtual void BasicState(object extraData) {
        Console.WriteLine("Running a basic state");
    }
}

To demonstrate the rest of the code, let's change BasicFSM.Idle so that we randomly select which method we use to pop state back onto the stack. We'll call this one UnsureFSM since we might run into this situation if a developer was unsure as to what they needed to do. Or a tester might throw this code in to try and whack our state machine implementation.

public class UnsureFSM : StackFSM {
    Random rand = new Random();

    public override void Idle(object extraData) {
        Console.WriteLine("Running an Idle state");

        if ( rand.Next(0, 10) == 5 ) {
            SetNextState(new StackFSMState(new StackFSMStateCallback(this.BasicState), null));
        } else {
            switch(rand.Next(0, 3)) {
                case 0:
                    base.Idle(extraData);
                    break;
                case 1:
                    break;
                case 2:
                    SetNextState(new StackFSMState(new StackFSMStateCallback(this.Idle), null));
                    break;
            }
        }
    }

    public virtual void BasicState(object extraData) {
        Console.WriteLine("Running a basic state");
    }
}

Implementing a basic engine:
If you take all of the code up to now, you'll get a basic FSM implementation, but no engine to run it. Since I want you to be able to test the process I am going to add a basic engine that calls into our FSM based on whatever the current state might be. This'll be a basic queue for now where we add each of our FSM implementations, but you'll probably want a full on game scheduler running this at a later time. I'll definitely be talking about game schedulers in the future so stay tuned.

public class FSMEngine {
    private static void Main(string[] args) {
        Queue fsmQueue = new Queue();
        fsmQueue.Enqueue(new BasicFSM());
        fsmQueue.Enqueue(new UnsureFSM());

        while(true) {
            StackFSM fsm = (StackFSM) fsmQueue.Dequeue();
            StackFSMState state = fsm.GetNextState();
            state.Callback(state.ExtraData);
            fsmQueue.Enqueue(fsm);

            Thread.Sleep(500);
        }
    }
}

Compile all this code into an executable and run it. You should get some pretty interesting results and you'll be able to play with the concepts involved.

Exercising the stack:
So far we aren't exercising the stack. What would it take to really exercise a stack based FSM? Well, states that push multiple states onto the stack of course. We basically need to break out of the push a new state on, pop it off next turn, rinse, repeat. The one thing that is really good at defining multiple states is a movement algorithm. These types of algorithms generally define multiple waypoints to be tackled along your path to the destination. We can also exercise the code-path where we push a state back onto the stack because it isn't complete yet.

So the MovementFSM starts in the Idle event and decides that 50 percent of the time it'll pick a target. If no target it selected it pops on a new idle state, however, if we grab a target to move towards, then we have to extrapolate the points along the path that we'll be moving towards. The ExtrapolateWayPoints handles this task for us by computing a random number of intermediate points and then popping these onto the stack. We compute the points from closest to farthest away, and then push the on the stack in reverse order so the closest point is at the top of the stack.

Once the movement points are on the stack, we fall out and see what happens. Each point is moved towards in the Move state method. We are now using the extraData to store the point we are moving towards, so we can print this out and see exactly where the FSM is moving. At some point (10 percent of the time), we don't actually reach our destination waypoint, so we pop the waypoint back onto the stack. This is an important refinement since it shows how easy it is to continue on our previous state with the same data. If we didn't reach out location because it is unreachable, then we could even pop on additional waypoints to refine the path.

One of the most powerful features of the stack based FSM is made apparent in the Move state method. When the current state is complete, no work has to be done in order to transition to the next state. Nothing new has to be done. You can do new things, but you don't have to. Removing this transition logic from certain algorithms makes them much easier to implement. Here is the code:

public class MovementFSM : StackFSM {
    Random rand = new Random();

    public override void Idle(object extraData) {
        Console.WriteLine("Running in Idle State: " + name);

        Point target = PickTarget();
        if ( target != Point.Empty ) {
            ExtrapolateWayPoints(target);
        } else {
            base.Idle(extraData);
        }
    }

    public virtual void Move(object extraData) {
        if ( extraData != null ) {
            Point wayPoint = (Point) extraData;
            Console.WriteLine("Moving towards " + wayPoint.ToString());

            if ( rand.Next(0, 10) == 1 ) {
                // Move not completed
                SetNextState(new StackFSMState(new StackFSMStateCallback(this.Move), extraData));
            } else {
                // We are done, assume the next state is on the stack.
                // Bonus! No transition required!
            }
        }
    }

    private void ExtrapolateWayPoints(Point target) {
        Point[] wayPoints = new Point[rand.Next(1, 20)];
        Point start = new Point(rand.Next(0, 100), rand.Next(0, 100));

        int distanceX = target.X - start.X;
        int distanceY = target.Y - start.Y;

        for(int i = 0; i < wayPoints.Length - 1; i++) {
            wayPoints[i] = new Point(
                distanceX / wayPoints.Length * i + start.X,
                distanceY / wayPoints.Length * i + start.Y
            );
        }
        wayPoints[wayPoints.Length-1] = target;

        // Pop the way-points on in reverse order so the closest is on the top
        // of the stack.
        for(int i = wayPoints.Length - 1; i > -1; i--) {
            SetNextState(new StackFSMState(new StackFSMStateCallback(this.Move), wayPoints[i]));
        }
    }

    private Point PickTarget() {
        if ( rand.Next(0, 2) == 1 ) {
            return new Point(rand.Next(0, 100), rand.Next(0, 100));
        }

        return Point.Empty;
    }
}

Additional Features:
After a good deal of thought, I'm going to save the nested FSM implementation for an additional article. There are many ways to implement nested FSMs with respect to where their stack state is stored and I'd like to thoroughly explain these. I might also talk about stack control methods in the future and add that to the StackFSM implementation. I think some worthy things to note would be stack compression (always a big subject), using fixed sized stacks, replacing stacks entirely and using your own strongly typed implementations, as well as some methods for better taking advantage of the extraData object.

Terrarium: Enumerating collections with an outlook on how to speed up the process.

Justin Rogers — Tue, 23 Mar 2004 01:20:00 GMT

Okay, so I was going through some old source code, that I won't claim since I probably didn't write it based on the fact the as statement wasn't used (as soon as I found out about the as statement I made sure to take advantage of its usage whenever possible) and I found the following code. Note this is pretty old code, but I'll use it anyway.

OrganismState organismState = newWorldState.GetOrganismState(organismID);

if (organismState != null && organismState.GetType() == typeof(PlantState))
{
    PlantState plantState = (PlantState) organismState;
    int availableLight = CurrentVector.State.GetAvailableLight(plantState);
    plantState.GiveEnergy(availableLight);
}

Okay, now this is a prime example of some code that should have used the as statement. So what is happening in the above code? Well, we are doing a null check, then we are doing a GetType() call, and check that versus a target type. After all this we perform a cast and finally start to work on the target. How could this code be simplified?

PlantState plantState = newWorldState.GetOrganismState(organismID) as PlantState;

if ( plantState != null )
{
int availableLight = CurrentVector.State.GetAvailableLight(plantState);
plantState.GiveEnergy(availableLight);
}

That simplifies things quite a bit and is a little faster. Unfortunately we have little pieces of the original all over the place in the code, so updating things becomes a hassle (assume that the original way was the only way to do it for some reason) whenever we change the way we perform certain operations (aka iterating over a collection of various objects where we only want specific ones based on a type). Here things like pre-sorting can greatly enhance the locality of the type checking operation, and at the same time allow you to quickly change the way sorting happens if your code changes a bit. It also allows you to prevent the type checking for the same item multiple times. This can be pretty powerful. Let's examine the collections we might use in order to simplify our design.

// We know there are Animals and Plants, both of which are derived from Organism
// so we are going to role all this data up early for use in all of our
// methods.

int animals = 0;
int plants = 0;

// Pre-count
for(int i = 0; i < State.Organisms.Length; i++)
{
    if ( State.Organisms[i] is PlantState )
    {
        plants++;
    }
    else if ( State.Organisms[i] is AnimalState )
    {
        animals++;
    }
}

OrganismState[] oStates = new OrganismState[State.Organisms.Length];
PlantState[] pStates = new PlantState[plants];
AnimalState[] aStates = new AnimalState[animals];

for(int i = 0, j = 0, k = 0; i < State.Organisms.Length; i++)
{
    oStates[i] = (OrganismState) State.Organisms[i];
    if ( State.Organisms[i] is PlantState )
    {
        pStates[j++] = (PlantState) State.Organisms[i];
    }
    else if ( State.Organisms[i] is AnimalState )
    {
        aStates[k++] = (AnimalState) State.Organisms[i];
    }
}

I want to place a note here about something. Notice, I'm using casting instead of the as keyword. You see, the difference is that I'm already pre-checking the value using the is keyword. I don't want to incur the wrath of extra work (as does some extra work checking the type before casting) twice in this case. This demonstrates that depending on your casting process and where you need various pieces of information in order to make your casting decisions, you'll need to change which casting methods you use.

Now our original method changes a bit and becomes highly simplified. Rather than doing the casting and iterating over an array where up to half of the elements might not even match the correct type, we've already done the work of pre-sorting, so we can index into our plant state array directly.

for(int i = 0; i < pStates.Length; i++)
{
int availableLight = CurrentVector.State.GetAvailableLight(pStates[i]);
pStates[i].GiveEnergy(availableLight);
}

A final optimization has been pointed out several times in other blogs. There is no reason to incur the wrath of a local variable such as availableLight if we don't need it. It is possible to instead change the method GetAvailableLight to simply apply the lighting values directly to the plant state in question. I mean, why would we, when it simplifies the design process (taking away some flexibility). The final method might look something like:

for(int i = 0; i < pStates.Length; i++)
{
CurrentVector.State.GiveEnergyByLight(pStates[i]);
}

Only use this final optimization where it makes sense. Perhaps do some tuning and see if it actually buys you anything.

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

Justin Rogers — Fri, 05 Mar 2004 03:52:00 GMT

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?

A basic 2D movement system using basic waypoints to start movement and a movement completed callback system.
Static terrain elements in the form of plants.
Dynamic terrain elements in the form of other creatures.
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.

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.
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.
We never provided any helper algorithms for path-finding. This was just a lack of time on our part.
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.

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.
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.
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.
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.
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).