Justin Rogers : Terrarium, Games4 .NET

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.

Gaming: Generating random world content and some consistency algorithms...

Justin Rogers — Wed, 13 Oct 2004 04:59:00 GMT

Generating random world content is one of those tasks that gets written off as a trivial matter. It isn't hard to throw some stuff around a virtual space and call it good. However, after trivializing the world content generation during your first game, you'll never make the same mistake twice. You should set aside quite a bit of time to think about your algorithms, employ consistency checks early on, and future proof your algorithms against later enhancements. Exactly how much time you should set aside is a project planning consideration based on how complex your world content is going to be.

Planning Units
The first thing you should do is plan to set aside some time to work with your world units. Depending on the world space you are working in you might be required to take into consideration several dimensions of space. Another feature is whether or not the game-world is broken into consistently sized chunks (aka a grid) or whether it is a free-positioning coordinate system (using floating point numbers to define location). The size of various object should also be considered since allowing multi-square items in a grid system or arbitrarily shaped objects in a free-positioning system drastically changes the next few steps of the process.

Basic Consistency Checks
Consistency checks help keep a given random world playable and even more importantly, believable. They are heavily linked to your units and how your world space is broken down. In fact, most of the values in your game related to world content generation will probably be aggregate values built from more basic variables. Because computations are involved you have to make sure each aggregate value is consistent across the board and consistent with how you expect your game to be played. The means the first type of consistency check is a playability check:

// Terrarium Pseudo Example Code
int EnergySpentStandingStill = 20;
int EnergySpentDuringMinimalMove = 18;

if ( EnergySpentStandingStill >= EnergySpentDuringMinimalMove ) {
// Playability hack since moving uses less energy than standing still
}

Playability checks are most often the result of a broken aggregate chain. Normally, we'd derive our value for movement energy directly from the value for energy spent while standing still. If we do that, and as long as someone doesn't change the constant multiplier to some value less than or equal to one, then we should be safe. But safe should never be taken for granted, and the consistency check should always be there. When tweaking game rules to improve playability, you'll often make mistakes that would create inconsistencies that would be found with playability checks.

Bounding and range checks can be even more important. I've actually played commercial games before where I was required to perform some task that would never be possible. For instance, a mini-game might required that you achieve a score, but not provide enough elements to achieve that score. Another problem are hunt and search games where a required element is inaccessible. Three colored keys and a set of matching doors will quickly show you that the placement of the keys is important to opening the doors in the proper sequence. If the blue door is first and the only accessible key is the yellow key, then you might have a problem.

// A sample bounds check based on a grid
int gridSize = 10; int gridArea = gridSize*gridSize;
int apples = 10; int pears = 80; int oranges = 50;
if ( (apples+pears+oranges) > gridArea ) { // We can't even place our elements }

// A sample accessibility check
bool accessible = false;
if ( Accessible(BlueKey) ) {
    Unlock(BlueDoor);
    if ( Accessible(YellowKey) ) {
        Unlock(YellowDoor);
        if ( Accessible(RedKey) ) {
            accessible = true;
        }
    }
}
if ( !accessible ) { // We have a problem! }

Accessibility is almost a section of it's own, but it is a form of spatial boundary check with respect to a given world-state. I'll leave it up there. The primary set of checks are just to make sure numbers are consistent. If you have to get 50 points to win, make sure 50 points are possible. If the player needs to create 50 points in 3 minutes, but it takes 6 minutes to get enough pieces, then that falls under a boundary check and should be caught.

Density Checks
There are checks that are dependent on more than just counts and derived aggregate values. For instance, you may be required to place 50 pieces, and so you do. If you are using a grid system, you can easily find that 50 pieces should fit in a 10x10 grid. What happens when some of the pieces are different grid sizes. Perhaps some take up 2 squares, 3 squares, or even 4 squares. Now you have a density check. You have to add the size or area of each element and check that against the available space.

We had some very important density checks to solve in the Terrarium. For instance, we needed enough room to store up to 250 creatures and plants. On the same note, we couldn't fix the world size because then systems with 60 creatures and plants would be too spread out and they'd run out of energy finding other plants and animals to eat.

Density checks may also help ensure believability in the game. If you find an apple across the screen from an apple tree, you might get confused. You might need to check that all apples are within a certain distance of the tree. Stack these distance checks with some boundary checks to ensure each tree has a range of apples surrounding it and you've created a full on consistency check for one of your game elements.

Density works in reverse as well. You may need to prove a minimum density in order to make elements well dispersed. Take Squirrel .NET and the addition of trees to the game world. A squirrel can only carry a specific number of nuts at a time, and they need to stop by trees in order to store them. If all of the trees are in the same spot in the game world, then making a choice about which tree to go to isn't a big deal or make a big difference to solving the puzzle of collecting the nuts. Ensuring that the trees are evenly spread is really important. A great consistency check is to logically shrink the grid, and ensure that trees don't exist in the same grid space.

// Squirrel .NET Game World Enhancement
int gridSize = 10;
int halfSize = gridSize / 2;

bool[,] used = new bool[halfSize, halfSize];
for(int i = 0; i < trees.Length; i++) {
    if ( used[trees.X/2, trees.Y/2] ) { // Inconsistent }
    used[trees.X/2, trees.Y/2] = true;
}

// Reversing the consistency check into a generation algorithm
int gridSize = 10;
int halfSize = gridSize / 2;

bool[,] used = new bool[halfSize, halfSize];
Tree[] trees = new Tree[10]; // Place 10 trees
for(int i = 0; i < trees.Length; i++) {
    trees[i] = new Tree([1..10], [1..10]); // Pseudo range generator
    while(used[trees[i].X/2, trees[i].Y/2) {
        // Pre-Consumed, loop
        trees[i] = new Tree([1..10], [1..10]);
    }
}

The nice thing about consistency checks and generation algorithms, is that they are heavily reusable in many different circumstances. In the abstract the objects you place are just objects, and they take on more specific roles once you label them and apply graphics. A layout scheme for 15 different elements in a 2 dimensional grid is easily reduced to an algorithm that might work for laying out two different types of elements in a completely different program. If you come up with anything impressive, feel free to toss it up in the comments!

Implementing AI wars where code is the primary asset. (focus on Terrarium)

Justin Rogers — Tue, 28 Sep 2004 11:44:00 GMT

The one thing I've taken away from the .NET Terrarium in terms of AI development is that players value their code over everything else. Protecting code from being viewed by other users is extremely difficult and hard to implement. After all, the focus of a distributed AI game is to pass the intelligence all over the place, to multiple machines, so it can operate across a large number of machines and potentially become the dominant system. If the code leaves your machine, it becomes possible that other users are going to steal your code, plain and simple. You can try trusting some other environments, perhaps a central server that hosts your code, but even then your code exists somewhere that you aren't in charge of basic protection.

Code as an Asset:
The development of new AI in the Terrarium was driven by the decompilation and examination of existing code. To show you how pervasive code dissassembly was, we introduced an Animal Farm, or location where users could share code. Even with this central repository of code, we constantly saw users working in ILDasm and ILAsm to produce verbatim copies of existing AI. The existing code as considered an asset by not only the developer, but also by the rest of the players. Controlling that asset meant possibly controlling the Terrarium's game world. Code is such an asset that users will go to any length to get their hands on it.

What is the best way to protect your assets? Well, don't create a situation where your assets fall into the hands of other users. Why do you think ASP .NET is so popular and Windows Forms is still riding coat tails? People can protect their code assets when it comes to server side coding, but find it much harder to protect code on the client. This is a common problem. So if you want code protection, you need to host your assembly either at a central server level or from your own machine. If you follow these guidelines then users will be more likely to participate and generate professional level AI while still protecting their investment in programming the code.

Execution Time as an Asset:
We've identified three places to run the AI. You can operate at the local client level, at the server level, or at a distributed client level. Identifying execution time as an asset, load balancing across the greater distributed network of all clients is going to yield the best results in terms of execution time. The resources are apparently limitless as long as you can maintain a large user base. In reality, users aren't always connected. The only 100% up-time resource is going to be your server. You can run AI on the server, but then you run the risk of not having enough execution time to schedule the AI as the game becomes more and more popular. You can offload this risk by allowing users to host their own personal servers and implementing relatively simple queueing routines.

The most limited location to run the AI is on the local client. Each user that produces AI hosts a networkable interface through which their AI can operate. This is the most resource consumptive option because it entails replicating a large amount of game state down to the local client and the propagation of AI commands back up to wherever the game is being hosted. Your AI is bound by the amount of processor time you want to give it. Further, you can only host a single instance of your AI at a time (potentially more in a more robust hosting environment).

Up-Time as an Asset:
Looking at our three models again, the natural next step is examining up-time. If you are programming an AI it is truly an investment of time and effort, but should it also be an investment of your own computer time? In the distributed model it up-time becomes a non-issue as long as the server is available to server AI assemblies down to distributed clients that do all of the processing. The server model is fairly identical in that your AI is playable as long as the server is up and people are selecting it as an opponent. The problem with local client interfaces is that your AI is only around as long as you are. You have to maintain an interface for people to connect through.

Can we solve the up-time problem for local only hosting? Yes, if we trust someone else to host our code for us. This is a sticky point, but we can share a hosting location with a number of friends, family, colleagues where we each host an AI off of the same box. This box might be a web server or similar online resource, and once the AI is loaded, it now acts as an AI interface in addition to it's other roles. A third option is the pay for play option where you AI is hosted by the game originator for a small maintenance fee proportional to keeping their server up and running with your AI on it.

Penalties:
This is really important and something a lot of people don't think about. How many different ways can code hose a machine? Plenty right? You can get stuck in an infinite loop and never return, you can run a machine out of memory, you can screw up a static initializer, you write finalizers in your code to hang the GC. Who should be penalized for bad code? If you allow AI to run on the server or distributed clients then everyone is going to pay the price for bad code. Forcing code to run at the local client level means only the original AI developer is going to pay the penalty for bad code.

Can you get around all of those issues in server or distributed hosting? Sure, but I offer the following advice. Fixing the hosting problems comes in the form of adding constraints. These constraints are based on usage scenarios and known patterns of attack. They leverage existing code protection features as much as possible. In the end, you have a system capable of doing nearly all of the things the original system could do, minus a select few things that are considered unsafe. From the other end of the spectrum, you can explicitly enable features one by one. This direction is safer, but much more limited. It is akin to a custom scripting language because you have full control over what the underlying code is capable of. .NET doesn't currently offer good facilities to make this a possibility. You can't explicitly enable access to only certain classes, and disable all other access. You can't hook into the memory management functionality and suppress creation of objects once the component has reached it's limits. They may be available as Whidbey roles around in the form of hosting protections, but that will be a code-path much more difficult to code than the average .NET programmer will be able to handle.

At the end of the day the penalties should probably be placed right back on the AI developer. In a real game, AI developers are just as responsible for bugs as the rest of the development team. In fact, if there is a bug in the AI, it often takes down the entire game. In a developer game the model is switched because the AI now becomes an unknown and the AI developer may not bear the brunt of poorly written code. In fact, there are issues with developer code in the Terrarium that only manifest after the code has traversed several machines and is widely available when an odd code-path is run through.

I'm leaning more and more towards a local client hosting model for developer based AI games for a number of reasons. I think I've mentioned the potential network models that allow AI and Networked players to operate almost transparently by taking advantage of a network protocol. Now stack the asset protection on top of that along with the ability to remove advanced code hosting features and you have yourself a definite winner.

Terrarium: Did we do the right thing with the creature event model?

Justin Rogers — Sun, 05 Sep 2004 00:51:00 GMT

History
Why did we use the eventing model? Well, because it made sense that creatures only needed to spend processing time on things they were curious about. It seemed like it might make things easier because a basic creature could hook only one event while a more complex creature could hook many events. It was also a great demonstration of how you would build pluggable apps within the .NET Framework. However, at some point we broke the model a bit and added some virtual methods for serialization and deserialization of creature data.

At no point did we consider revisiting the model and changing it out for another model that might be more appropriate. The backwards compatibility mindset was always in place and we didn't want people to have to recode their creatures entirely as versions changed. It also became rather difficult to change the pattern away from the 10 or so events and large eventing infrastructure that was in place. With that in mind we kept the pattern.

Pattern
Our pattern was to simulate the concept of discrete inputs. Certain things may or may not happen in a given round, and other things may not happen for the entire life-time of the creature. No reason to check for these conditions every tick of the game loop. We created several separate events that comprised certain worldy actions such as attacking, defending, eating, etc... We also needed the creatures to be notified even if nothing of importance happened. This ensures the creature gets some time to process irregardless of the state of the world. These are the Load and Idle events. The Load happens before all other events are called, while the Idle happens after all other events are called. Load allows you to set things up and prepare for action, Idle lets you operate after world notifications have been propagated. Easy enough right?

Complexity
We definitely made some mistakes. First, there are a lot of events. Many creature authors are curious about which events they need and the order the events happen in. We have some documentation, but that doesn't help when you are first picking up the Terrarium for the first time. You want things to be as plain and simple as possible. Another level of complexity is added in that many developers wind up doing work in each event that may or may not overwrite work done in other events. You could blame this on the person writing the code, I rather blame it on the model and blame myself for allowing it.

Additionally there is the problem of storing information about discrete events having happened. The author could store the information, but we already store it within the base class. This isn't immediately obvious. I mean why would we store the information for you and give you an event that gives you the same information? It makes more sense for you to be notified that it is your turn to process and then allow you to investigate the state of the world.

What about time-slicing? Since we time-slice you, each event we call is taking a bit more of your time. Additionally it is harder to load balance your time across ten events than it would be across a single event. You have to store the amount of time spent in each of your events in order to get an accurate measure of how much time you used and how much you have left to process. For path-finding algorithms you may want to make the most effective use of your time by knowing about how much time you have left, even if the measure is somehow relative.

No Guarantees
We don't guarantee that your events will fire. In fact, we can skip you if you are taking too long, and the only way you know is by examining a special property that tells you for how long you were skipped. Any in process events continue processing, so while you aren't being notified, your move may complete or you may get teleported. If you are relying on the eventing model to keep your private state in check you are in for a rude awakening.

Single Cast Events
Having single-cast events isn't very useful in our model as you can tell from some of the downsides. In fact, in trying to demonstrate a plug-in model, we desperately failed. Normally, plug-ins will hook up to some global events that exist on the game engine and not exhibit a bunch of local events that are only consumed by the plug-in.

Fixing the Model
The model is quite easy to fix. Simply don't use events. There is no reason to use events in our model, rather with a base-class already in place we simply supply a single callback method, virtual of course, for the creature to implement all logic. This drastically reduces the complexity of the code required to implement the creature into a single entry point program. While you might think that authors couldn't code creatures that were nearly as functional as before, they actually have more time to operate now and have a less complex model to program against. As I'm making these changes to the source it simplifies other portions of the engine and helps refine the layout of the interfaces between the creature base, the engine, and the UI.

Working With What You Have
You have some options already as a creature developer. By writing a simple base class that manages all of the events for you and stores local information in a very minimalistic format, you can write your derived creatures to use the new local information from within a single method that is fired by the Idle event. At one point we had a work-item open to ship this class within OrganismBase itself. The idea would have been to have the Animal class for anyone interested in programming the old model, but also a new SingleCallAnimal supporting the new, simpler syntax.

My thoughts on the future of Terrarium as a learning game.

Justin Rogers — Sat, 17 Jul 2004 06:49:00 GMT

I'm completely third party with respect to the Terrarium. Yes I still help with the evangelism and coding of the application itself, but on a very limited role as the product goes towards maturity and new product ideas develop for future versions. That said, there are many things I can't talk about in regards to the application because I know about future features that I'm under NDA for, but there are equally many things on a conceptual level that I can talk about. That brings me to the Terrarium as a learning game. When I first started working on the Terrarium the concepts for the game were simple.

Thoroughly test the .NET Framework from top to bottom in what I would call the ONLY enterprise sample. We tested the server, client, client/server interoperation, platform invocation, every level of security, and so many features it would make your head spin. Now it seems like not that much, but when we released, the .NET Terrarium was the most stressful application anyone had ever developed. In saying that, we still found issues as late as V1.1 that were only being exercised by the Terrarium and no other application in existence (unless they were quiet about it).
Get a shitload of people running the application. That meant making a pretty screen saver that people could run and would want to run. Unfortunately technical requirements were that it run on a laptop with 2.5 megs of video memory. Come on, we got pretty damn cool for such small memory requirements. We never did whack the aquarium that shipped with the XP Plus! Pack, but we sure did get a lot of people running anyway.
Educate users on the process of programming .NET applications and get them writing small samples in a friendly environment. The basic creature was only 15 or so lines of easily explained code, while the upper limits of coding the AI are still being established today. That is a pretty nicely designed learning infrastructure.

As far as I'm concerned those were the main goals and we accomplished all of them. We had a huge university outreach program that kind of fizzled out, but at least one group of students got a very interesting experience with the application. The technical outreach at various conferences was unparalleled with hundreds and hundreds of users playing and submitting creatures at each conference the Terrarium was used as a lab exercise program.

Now, that said, the Terrarium focuses on great features of the .NET Framework, but is is a partial game. It doesn't meet the requirements I have for a game engine, and for good reason, we simply didn't have the time or resources to make something of that magnitude when our primary goals were something entirely different (see goals 1 through 3 none of which cover making a demonstrable game engine). Moving forward some very big decisions have to be made. Based on some recent postings by Mitch, it appears he has ideas of going a mech warrior route. In my mind, I'm more focused on enabling the learning experience of getting up to speed on AI and .NET programming in general. You can start to see where the two sides of the equation diverge with different end goals being established. This isn't a bad thing and I'll describe why.

First and foremost the Terrarium is going to be a community project very soon. That means releasing some very nice community enhancements. From my standpoint this means releasing source code that I've had under my belt for almost two years now waiting for the source release to happen so I could push some changes that were never approved in the official release. It also means that the community goals can be easily resolved with some simple code-fixes. Users tend to say quite a few things but they boil down to the following items:

The rules are inconsistent, don't work very well, or what boils down to not enough rules.
Users have a hard time getting the Terrarium up and running for the first time.
There is no publicly available mechanism for real competition.

For the first, there is some nice code available that allows a server module to change the basic engine settings dynamically. This can be used to simulate weather and a number of other unique conditions. The next step is increasing the variety of creatures without increasing the complexity, again, the code is ready to go for this feature as well. The second feature relies on things like TerrariumProxy or TerrariumIM in order to work properly. Both of these features will allow users to play without worrying about the NAT problems that are traditionally encountered by so many of the users.

For the third feature the TerrariumClusterServer will be made available. This last one I haven't talked about at all, but it basically allows a single machine to simulate any number of Terrariums and allows competitions to be run using a pluggable ranking system. Now, rather than using multiple trusted machines for a competition, we can have a single server located on the Internet capable of running competitions and determining the best users. After all, with the source release the public EcoSystem will be able to be taken advantage of quite easily and the threshold for overcoming an established population is very huge. The new feature set will rely on simulating trials between creatures and collecting statistics about the winner over a period of time. All creatures are inserted on an equal basis and pitted against one another. To avoid any cross-idea issues I will say that this feature set is based around spawning 10 or more concurrent Terrarium engines on the same box, hijacking the network, reporting and peer registration layers, and finally running all engines concurrently. There are no rule changes or other concepts that might create an intellectual property issue.

That means, what do I think of Boris as mentioned on Mitch's blog? Well, I think it is a very niche market. I think the community needs to reach out to those players that haven't joined up yet. I know the nerds, geeks, dweebs, dorks, and other misfits have already tried the game and love it, and these same people would dig the mechs, but I think the direction the game needs to head is a more general adoption. For me that means concentrating on things that interest children, teenagers, college students, and technical individuals. I think bringing the female gaming markets and child gaming markets into the fray is important. What kinds of features am I looking for?

Everyone can play and be somewhat successful. That means even without a large amount of programming experience you should be able to make an effective creature. This feature works based on a creature designer that creates a creature with fairly decent survival statistics. I guess as the developer of this type of feature I'll have to keep up with all the rest of the programmers so that automatically generated creatures are only slightly worse than the best creatures in the environment.
Everyone is interested in watching the game play out. Mechs aren't the coolest thing ever. They are pretty cool, I'll admit, but the classics of bugs and animals are much cooler. Children are especially interested in bugs and animals, as is the female gaming crowd (moreso animals than bugs at this stage). Guys that watch mechs, also watch vicious animal attacks, so I don't think any of the action will be missing here ;-)
Code protection is a must and individuals that want to be competitive at the code level are able to safely release their creatures and battle them without worrying about having their code ripped off. I want to foster some of the best programmers to play the game and if intellectual property is at stake these best of the best simply won't play.
Provide a challenge for good programmers. The base designed creatures will be good enough to provide a challenge, but so will the variety of coding a creature. Every niche of the scale will provide areas where people can play. The imbalance of the current game towards small, quickly reproducing creatures is nothing short of atrocious.
Keep it on the P2P layer, get rid of the server, and call it a day. I think the ability to play the game cheaply is a must and running a Terrarium server can be a large expense. Focusing on this particular layer will be a must for any real adoption level. After all, the Terrarium server breaks down at 2500 users or so, we can theoretically hold 10000, and that is only if an admin is tweaking things every few days. Going beyond 10000 or even supporting 10000 currently requires a large operating budget.

This is by no means a complaint about how the current Terrarium is being run. I get insights into the direction of the game and I love where it is going as an application, but I can certainly disagree on design issues and other such nonsense. At this stage that is all I'm doing is disagreeing at some design level, and it may turn out that the insights I'm basing my opinion on are changed at a later date. Most of the above comes from my long term attachment to a project that I've been extremely close to, and I'm still extremely protective of.

Terrarium and the upcoming source release. Looking forward to the latest server changes?

Justin Rogers — Tue, 27 Apr 2004 01:48:00 GMT

Users of the Terrarium client application are going to love the latest changes. Lots of extra eye candy (go check out Mitch Walker's blog for some screenies), a bunch of code fixes, AND the full source code. However, I think the server guys are getting left behind. What have we added to the server for people to look forward to?

A VS .NET Project is now present for building the web application. Unfortunately this means we moved all of the code to code-behind files and it is a bit harder to look at. I never could understand why someone would use code-behind for web services.
We got rid of the OWC dependency! Yay! This was a big win. We actually pushed out a small version of the server internally that used a custom charting component, so the OWC dependency was removed, but that never got released externally. With the latest release, there aren't any dependencies on external components any more, so you don't have to worry about finding an old copy of Office.
Some small UI clean-ups have gone into the application. In general, it is still a bare-bones server, so don't expect much. Most of the feature set was placed into making the installation easy and seamless.
Seamless install process. Well, almost seamless. There is no such thing as a seamless install process because there are too many stupid little dependencies to check for. The latest install process should let you exit the installer and immediately start using the server. Just in case the installer isn't good enough, we've included a server setup helper application that blasts the server into place. All of the old dependency files are now embedded as resources as well, so no accidentally deleting required files. Gotta love that.

I've been holding off the release of the Terrarium Server : Community Edition until after the MS source release. The TS:CE will have lots of additional enhancements that will improve the server experience even more. Namely a fully refactored database, enhanced reporting and statistics roll-ups, and several new service methods for enhanced client features that I'll also detail once the source release hits the web. I hate having so many dependencies on the public release of the source, but that is the way the cookie crumbles.

[Terrarium] How do we pass creature assemblies around?

Justin Rogers — Fri, 23 Apr 2004 23:56:00 GMT

This is the primary feature of the .NET Terrarium. The ability to safely and easily pass around creature assemblies and run them on end user machines. There are several considerations for this process including security, transport, loading, and storage. I've already talked about the Terrarium Model and security over in the Plug-In Framework (Foreward): Defining the end goal, so I'll be talking about the later three now.

Transport
Transport can be very easy (WebRequest), or fairly difficult (Socket). Today, you can easily use web services or web requests to grab information off of a central server, and the Terrarium does this all the time. We have several services that go out and grab extinct creature assemblies off of the web server. This is probably the easiest way to get a creature assembly.

The P2P methods are a bit more difficult. We actually created a miniature web server HttpWebListener (thanks to Lance Olson) and use that for P2P interaction. So are we really using Socket? Yeah, but not the way you would think. Each client still issues basic WebRequests for data from each peer, but we host those little miniature HTTP servers in order to intercept the commands. This is actually pretty cool and I'm sure everyone will enjoy having the source code at their fingertips for this little gem pretty soon.

Since HTTP is a stateless protocol I can tell you now that we have to implement a message based system whenever we communicate with other peers. All of the messages originate on one side of the pipe (the client) and will change depending on the response from the listener. This is a fairly easy process, made quite complicated by requring multiple connections, one for each message, but overall it isn't that bad. Sample messages would be, do you have assembly A? Here is assembly A, did you get it okay? Here is a new creature, are you receiving it okay?

Storage
Now that we have the assemblies getting tossed around we have to store them somewhere. We can't store them in the same place as our executable. We can't store them in Program Files and still act under “Run as Normal User”. We can't really store them anywhere, except for the users local settings. Ah, we found a spot. Since we have to store assemblies off in some remote directory, how do we go about loading creature assemblies when they are requested?

That is where our assembly caching logic comes in. The basic process starts inside of the game logic. You see the game logic knows about the assembly caching logic, and so rather than calling an Assembly.Load on a creature's full name, we simply call into your assembly cache and pull out an assembly. This works great. However, there are still times when an Assembly.Load might get called outside of our code (deserialization) and we need to be aware of that so we can return the assembly when probing fails. For that we hook AssemblyResolve, verify that the assembly being requested isn't one of our own, and finally look things up in the assembly cache.

There is one hang-up here. We never make use of private paths, so the run-time doesn't control the probing, we do. We get a lot more storage potential out of this, including monitoring how many assemblies are currently loaded, how many are in the assembly cache, and finally the ability to run clean-up logic if we want to. We also don't automatically download the assemblies if they aren't already in the assembly cache. We could make a web request and search for the assembly on the server, however, we rely on other game logic to ensure the assembly is there.

To note some additional security we've layered on our cache. Each time the Terrarium starts, the cache directory is dynamically changed to some random directory name. No brute force, I know where your assemblies are hidden, attacks. This prevents users from storing things in assemblies and then taking advantage of them later through email, URLs on their website, or any number of other hacker routes.

Loading
This is the most complex aspect of assembly use that we have. Not only do we have many layers of code access security protection, but we grep the assembly IL for bad constructs, load the assembly in multiple ways to prevent context caching of assemblies, and a few other goodies. I've detailed the code access security items and IL grepping within Plug-In goals document, so you can see the real deal there. I'll talk a bit about loading assemblies for the first time and the process they go through.

Loading an assembly for the first time is a pretty big deal. We obviously run the IL grep over the assmebly before we do anything, but once that process happens, we have a number of other checks that have to be run. Namely, we have to get a bunch of assembly attributes off of the type, make sure the image isn't bad, etc... Simply enumerating the IL won't give us this full verification that everything is kosher, and we don't want to lock the file on disk. So we use the byte[] overloads of the Load method. The method supports loading of just the assembly, or what most people don't know, debug symbols as well. Took some time to get all of this code written correctly to allow all of that precious debug information to make it to it's final location in the assembly cache.

Once the assembly is verified, we check it against the Species service to make sure it is unique, add it to the list of creatures, and store it's assembly remotely. If this is a new creature for sure, we save the assembly into the assembly cache (copying symbols if necessary), and load the assembly again. This time for real, since this will be the assembly codebase that we use for creating creatures.

The entire process is fairly quick. Later as the application shuts down and restarts, we'll be responsible for loading creature assemblies over and over again. They'll always come out of the assembly cache from there on out. Some hang-ups do occur. If the original assembly (before copy) was located in the probing path, a call to Assembly.Load by the serialization code might load the wrong assembly. We prevented this by some ingenious serialization, but I'll talk about that later. You also have to make sure all of your code loads from the assembly cache as well, and doesn't call Load, else that probing issue will catch you sooner or later.

Joel's Lightweight Code Gen spells SUWEET for small scripting languages in games.

Justin Rogers — Sat, 10 Apr 2004 18:46:00 GMT

Reading Joel's blog and having lunch with him are two different things. You never really see all of the possibilities of a technology until you see the twinkle in someone's eye and realize that the technology might be slightly more powerful than you originally realized. Today I want to cover function based scripting languages and how these can easily be implemented using the LCG inside of any existing MUD or MMOG system.

The syntax for small scripting languages is not similar to what you see with C# and VB .NET. Small scripting languages are generally functional and not necessarily centered around the creation of objects. In the game world, a developer might create new functions in order to perform specific actions. Each of these functions is then attached to a game world object and fired as part of an invocation list as needed. Code is not used to define everything in the game world. Invocation lists might be stored in a data file with a list of object id's, and their attached function id's. Object's might not even be hard objects, they might just be scalar data or structs. The data something contains, might also not readily identify it's object type, but instead the functions it handles. Let's take a sample case.

> You see a mossy rock in front of you.

Mossy rock? Why is it mossy? Why is it called a rock? You might think someone created a mossy rock object (MossyRockObject : MUDObject) somewhere and compiled it into the game. This is probably not the case. More likely is that they attached the GetName function and that function is diving into the database or some other data file to get the name of the object. Is mossy even part of the game? Or is that something else? Maybe the GetName method is calling a GetAge function or the game engine is calling a GetAge function. In this case the possibilities of getting a name could chain together a large number of similar functions that all return pieces of the objects name.

// Note all functions are assumed to turn return an Object data type and the
// engine is capable of handling the rest. I'm making this very JScript like.
function GetName(ObjectID) {
var name = DatabaseName(ObjectID);
return name;
}

Now, I'd actually have to attach that function after I made it. Each function could be in it's own file. I could store them in XML. I could pre-parse them into some byte-code type structure that I could quickly convert to IL later. Lots of options. So we add a command to our MUD or MMOG that allows us to attach a function to an object. Remember that mossy rock? Well, in our case we simply told the game system to create a new MUDStaticObject. This object is derived from MUDObject and has properties that make it act as a static object within the game world (aka a rock isn't a mobile). Once we create the object, we have an ID. The UpgradeObject {id} {function name} is now capable of attaching a new function. The system is loose. The new function is now something that can be called by name, or it can be added to any of the objects invocation lists. An invocation list is important, because we want the game engine to be able to generically support something like name's, but not necessarily only through the GetName function (note we could have allowed many instances of the GetName function, one per object, but I'm choosing invocation lists instead ;-).

An invocation list for our object looks something like, invocationListNames = { functionIdGetName }. Note there is only a single ID when grabbing a name. We might not even call this a list but instead an invocation bind point so that we have the ability to limit the number of functions for this particular feature to just one. If we wanted to upgrade our name from say “rock” in the database to “mossy rock”, we just swap out the methods.

function GetExtendedName(ObjectID) {
    object = GetObjectByID(ObjectID);
    name = object.GetName(ObjectID);
    age = object.GetAge(ObjectID);
    prefix = “shiny “;

    switch(age) {
        .... // Change prefix
    }
    return prefix + name;
}

That was easy. Dynamic methods make the above possible. My MUD can take textual input through a world builder, create this new method, and then at run-time, when I compile the method I can convert my script to the appropriate IL to make things happen. In the case above, I'd still have to use UpgradeObject to attach GetExtendedName and then add it to the invocation bind point for grabbing somethings description. That isn't a big move. Then we use some global functions GetObjectByID to surface a structure capable letting us call methods that we think might exist on our object. We could have just called GetName, but what if that function didn't exist on the object? With the object. syntax we are adding some checks in there to make sure that method has been attached. If not you can exit out of the script or do whatever else is necessary.

I'm getting pumped guys. This is the kind of interface I've been waiting on for a long time. It is the type of interface that will allow Terrarium to become more functional and provide an easier to replicate sand-box. It will certainly create an easier to create plug-in framework environment. Whidbey is Whidbey though, and that means some time before you get to produce production level apps on this stuff. I'm going to try and go back and fulfill a promise I made months ago to actually complete my plug-in framework documentation that would allow you to create strong plug-in environments today.

References:
[1] A fun lunch with a couple of Rotor fans
[2] hello, world... LCG (Lightweight Code Gen) style!
[3] Late-bound invocation notes - CallVirt, Delegates, DynamicMethod, InvokeMember.

Note that I didn't actually cover 3. However, this article provides an EXTREMELY fast solution to some common scripting problems. I'll try and blog about why later when I get more time.

Terrarium: Processing events, controlling your creature, and common pitfalls.

Justin Rogers — Wed, 31 Mar 2004 06:42:00 GMT

Figuring out which events you are going to need for your creature to process can be very difficult within the Terrarium, especially for new users overwhelmed by the idea of having to optionally handle up to 10 events. Some creature authors don't even hook an event and wonder why their creature is never called. Here are the events, in order that they are called, along with their purpose and how often they are called.

Event	Times Called	Order	Description
Load	1	1	This event is called at the beginning of your turn. It is always called unless you have been skipped, in which case none of your events are called. This event is best used to set up your processing state in order to prepare for the remainder of the events. Many people erroneously use this event in order to do other processing that later gets overwritten by processing inside of the remaining events.
MoveCompleted	0-1	2	If your move completed because you reached your destination, or you were blocked, then this event is fired. This event is best processed by storing the event args locally on your creature and processing movement in the Idle event along with the rest of the events. I highly recommend aggregating all data from events 2 through 9 so they can be processed by event 10 in one fell swoop. Note this event may or may not fire immediately following a movement action in your previous tick. This is a multi-round action and so the event can take multiple rounes before it fires.
AttackCompleted	0-1	3	Your previous attack action has completed. This will happen if you previously attacked. Attacking is a one round event, and so this event will fire on the tick immediately following an attack. You can check how much damage you were able to do, and if the target was killed, or was able to escape without any damage being done.
EatCompleted	0-1	4	Your previous eat action has completed. This will tell you if your eat action was successful. This is a one round even and will fire immediately following an eat action in your previous tick.
Teleported	0-1	5	If you get teleported, either locally or remotely, this will notify you of that event immediately following your insertion back into the processing queue. Note the only evidence of your teleport is that you were sent back to the local terrarium, or your were teleported remotely. This event may be fired after your creature was taken out of the queue for multiple rounds. The results of the LocalTeleport property will greatly change how you process this event.
ReproduceCompleted	0-1	6	This event tells you that your baby has been born. It gives you no information. However, this event, under normal circumstances, should fire IncubationTicks after you start your reproduction. This is normally 10 ticks, but under various circumstances can take much longer.
Born	0-1	7	This is a brand new creature, and you were just born. The sole purpose of this event is to pass you a byte[] representing your Dna from the parent creature. This event should probably be processed in-line inside of the event, since it is only called once and it is used to set up your initial state information for your creature.
DefendCompleted	0-1	8	If you tried to defend in the previous round then this event will fire. There is no notification of a success or failure on this action. Damage is computed within a random range based on your attributes, and so depending on the layout of the random numbers, you'll either take more or less damage.
Attacked	0+	9	This event will fire once for every creature that attacks you in the previous round. You can use this event to get the Attacker, so that you can defend against them in the future. This is important, since if you don't get the attacker here, you might not see the attacker later in a Scan due to camouflage. On the following round, you will only be able to defend against a single creature, so choose carefully.
Idle	1	10	This is the final event called in the sequence. Like Load it is guaranteed to be called, so long as you aren't being skipped. I highly recommend that the results of all previous actions be stored and saved to be processed in this event. Users always run into concurrency problems when logic from various events overwrites the logical decisions of other events, and it is so much easier to process your creature in a linear and deterministic manner. I almost think that a special inherited Animal class could be developed that allowed for just this model.

I make some assertions in the descriptions of events that people might not like, but I will stick by them. I think that the conditional events 2-9 should always be used (with the exception of Born), to set state locally on the creature. Once the state is set, it should later be processed in Idle. A large number of creatures developed do the exact opposite of this. They instead put all of their logic in the Load event, and then later process all of the optional events. This leads me to a list of common pit-falls to watch out for.

Make sure to hook at least one event. Some creatures forget to hook them (first time authors mainly), and then wonder whey they aren't getting called for processing.
Make sure to process the TurnsSkipped property. Your creature may be going over the time limit and you may never know. Process the TurnsSkipped property so you can realize this. Once your creature is tuned, you should process this anyway to make sure you aren't waiting on events that will NEVER fire. Some creatures issue a move command and then wait for the MoveCompleted event. This even can be skipped over during a skipping turn and your creature would never get notified.
Don't do extraneous processing in optional events, that you are later going to overwrite in the Idle event. Lots of authors wonder why the actions being set in their MoveCompleted event or Attacked event later get overwritten. It is because they aren't taking into account the code running in their Idle event. This is also a huge perf sink, since often creatures will run the same logic twice, from two locations in your code.
Don't use the Load event for your main processing code. If you do, you are going to lose all of the extra information from the optional events that could help you short-circuit code or better process your turn. Also setting actions in the Load event can cause them to later be overwritten by code in your optional handlers.
You have to hook the Teleported event. Most authors don't bother because they don't think it is important. Instead they rebuild their world state every single tick doing the same scans over and over again, not reusing information. The extra processing time used scanning could be going into more complex processing algorithms.

That is all for now. Enjoy!

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.