The State of Things

The World Project was started in January 2007. There's been plenty of time to get moving on things, even though the end goals were not known at the time. Despite this, I was working throughout this time, and I definitely gave more attention to work throughout the process. Basically, the World got worked on whenever I had the spare time, energy, and willpower. I haven't obsessed over it like I have previous projects, but the further it gets along, the clearer the resulting vision becomes, and the greater the drive to reach it. As always it feels like the last 10%, but anyone in software knows: The first 90% of a project takes the first 90% of the time, the last 10% takes the other 90% of the time.

So here's what I wrote:

• State Machines: Separates machine structure, machine layout (visual), and machine execution. Machines can be edited using a visual layout method. States and Transitions execute behaviors. Transitions utilize a TriggerListener, which invoked the transition via an event. Decision points can be created, and evaluators on transitions that exit from them. Sub-machines are somewhat supported, but I ended up doing these a different way within the World, so I scrapped the original methodology. Idealy we'd have nested machines, but until I need it, I won't write it. Writing the visual editor, generic methodology for creating behaviors/transitions/evaluators, and allowing extensibility, all took some time.
• Scheduler: The main game thread executes within a scheduler, from which any task may be invoked at any time. It's single threaded (simpler), but does the job. Priorities have been in the task system from day 1, but never used. I'll get there when I need it (noticing something, I bet, but don't mistake it for laziness).
  
• Socket wrapper: Wrapped a socket based communication system for ease of use. UDP or TCP. It's designed to take a set of possible objects and optimize for transmitting the limited set. Originally it used the C# BinaryFormatter. Once I built a better data protocol the transmission size shrunk by a factor of 20 or so. In any case, it makes data send and receive very easy. It also fires an event (for the receives) for each individual type of data received. Since the data types are known ahead of time it's easy. I like being clever with C# and generics.
• Network Scheduler: A second thread, similar to the scheduler, that handles incoming and outgoing (well, someday) traffic scheduling. Because of this and the scheduler, an idle zone sits at 0% CPU usage. It might not seem like a big deal, but it means that the code is structured well enough to know when it is idle and not waste resources. Coming from the typical client-side game process of update->draw->repeat ad nauseum, this is quite the change.
• Directory server: A simple client/server protocol that supports looking up the location of a zone server. It's really pretty easy given the above. Not even used yet, but I wanted to get right into it.
• Generic GameDatabase system: This was probably implemented much more complicatedly than necessary, but I had some incorrect ideas about the layering of this system. This is a gnarly bit of code that represents the storage and transmission mechanism of the game system data. This includes the mechanics, formulae, attributes, etc, even though this layer doesn't know what the data even is. Probably more complicated than necessary. It also supports client/server updates of the gamedata, but my hunch (2 years later) is that it was a waste of time. Oh well. It's neat code anyway.
  
• Lua scripting for embedded language: Lua can be bound into behaviors, transitions, and evaluators of state machines. The higher up system can also use lua to evaluate Effects and Actions. This was pretty much cake.
• GameSystem implementation of the GameDatabase: Specific types to implement the World project. I also wrote a system for editing the data, using some wacky Windows Forms code. It's mostly PropertyGrid based, so it's a bit... raw..., but functional if you happen to be the writer. There's some pretty crazy behind the scenes stuff in there though. For example, if you assign a State Invoke to a behavior, and that state (in the database) has parameters, it will automatically setup the parameter list for you, with the provided defaults. It's amazing how much a pain UI can be.
• Zone implementation of the GameSystem: Yet another nested layer! This is the sort of main execution code. It takes the GameSystem and implements an instance of it: A Zone and its constituent Entities. There's a lot of stuff here that I'll leave for later.
• Zone Client/Server Protocol: Uses the network stuff to keep a set of clients up to date and allow them to play in the server. The relevant data is all in client-space now, even though we don't have much of a client to view it.
  
• Custom modules: Zones can establish a plugin module to provide additional types of behaviors, triggers, evaluators, effects, and actions. It also provides a set of options to the server UI which happen to have become extremely useful.

Code wise that's relatively where we stand. Of course there's more detail than that implemented. It's not a small codebase, but I wouldn't call it massive. There are 2 major points I want to touch on, since they're at the core of the design. First is the event-driven nature of the system. Second is to address the 'but I haven't done that yet' part, since I think it's one of the strengths of my development method, despite sounding like laziness. The second I'll delay for another post entirely, the first I think I'll write now.

Event driven systems have a lot of benefits, and a lot of problems. First let me define that as I see it. Event driven systems work off of knowing when things happen, and reacting, rather than poking through the system to see if something needs to happen. It's reactive rather than proactive. Why do things this way?

Well, consider the cost of poking through the system analyzing potential occurances. What if nothing needs to happen? You just wasted time! You also forced the entire zone to cycle through memory! That's more time! You also might have missed something happening if the cycle takes too long! That's inaccurate! If the expected zone size involves crazy-large numbers of entities, you just can't afford to run naively.

Now consider the cost of figuring out when things will happen. First, you have to somehow know how to know when things'll happen. This varies dramatically from thing-to-thing. Right there you know this will be harder than the alternative. Each case is different. Let's consider a set of possibilities:

1. X seconds pass: This is easy! Just tell the scheduler to fire in X seconds. Yay!
2. An Entities is moving north: Wait, when do we care? Well, the entity needs to move! Continuously! When do we move it? Every millisecond? Every second? Well, I guess in some games you could get away with infrequent moves, but not many. Chess maybe. And the first? Well, then you're basically being proactive again, you're forcing anything that moves to be updated even when it doesn't really care. So instead, represent motion as a start point and a vector at a specific time. Then the location is a function rather than a constant. Physics complicates things, but as long the equations are solvable you can do this. Now, this limits the game, of course. No crazy space physics, nothing hyper-non-linear. But most games don't need those things, and if you did, you wouldn't write an event-driven server.
   
3. Two entities collide in the world: Typically collision is done after everything moves, then analyzing if things intersected. Well, we aren't explicitly moving. So how to do this? Well, we can intersect two lines, right? Just extrapolate the entity's location into the future and figure out the next thing it collides with. Use some aggressive space-time culling to remove unnecessary tests. And then, any time anything changes motion, you get to recalculate. All sorts of fun! This is the hairiest part of the system. If motion becomes very dense, this system may not work out as written! But we'll see. The key will be culling unneeded tests. You don't care about something that will collide with you in 3 hours and 12 seconds. You can just recalculate in 10 seconds, and ignore anything that is 'probably' more than 10 seconds away. Put a speed clamp on things and you can limit the space sampling needed pretty easily. It was tricky but this system works. Two objects moving at each other, if they care about collisions at all, will be woken up when they touch. And in between that time? 0 resources spent on collisions between them. Heck, if they were the only thing there the CPU would go idle.
   
4. Do something when someone else acts: Well, we can just hook an event on 'someone else' and then do 'something' when needed. This means we have a LOT of events throughout the zone and entities. keep in mind that state machines pretty much work off these events as well. This task is 100% natural for a state machine transition and behavior.

Since I want to be running very large, sparse zones, I decided to invest the necessary time to make the event driven system work. It's hard to know when things will happen, but the rewards have been pretty sweet. I can run zones with 100 or so entities fighting each other, using about 1% of my CPU. If I actually want to watch it, I use about 15%, due to the bad drawing algorithms I use right now. (There's some irony there, huh..)

So that's the code and what it can do. Ah, but remember 'It Must Be a Game'? Where's the game! Gra! We got started on that fairly recently, and it's not just me anymore, and I think we've done some pretty neat things in the last couple months. Next-next time.