Friday, August 31, 2012

Combining Twisted and Django

Franco Nero as the twisted gunslinger Django

Newcomers to Evennia sometimes misunderstand it as being a "Django mud codebase somehow using Twisted". The correct description is rather that Evennia is a "Twisted-based mud server using Django". Allow me to elaborate.

A mud/mux/moo/mu* is per definition a multi-user online game system. All these users need to co-exist on the server. If one player does something, other players shouldn't have to (noticeably) wait for that something to end before they can do anything. Furthermore it's important for the database schema to be easy to handle and upgrade. Finally, in a modern game, internet presence and web browser access is becoming a must. We combine two frameworks to achieve this.

Two frameworks combined

Twisted is a asynchronous Python framework. "Asynchronous" in this context means, very simplified, that Twisted chops up code execution into as small bits as the code lets it. It then flips through these snippets rapidly, executing each in turn. The result is the illusion of everything happening at the same time. The asynchronous operation is the basis for the framework, but it also helps that twisted makes it easy to support (and create) a massive range of different network protocols.

Django implements a very nice abstract Python API for accessing a variety of SQL-like databases. It makes it very convenient to maintain the database schema (not to mention that django-South gives us easy database migrations). The fact that Django is really a web framework also makes it easy to offer various web features. There is for example an "admin site" that comes with Django. It allows to modify the database graphically (in Evennia's case the admin site is not quite as polished as we would like yet, but it's coming).

Here are some highlights of our architecture:

  • Portal - This is a stand-alone Twisted process talking to the outside world. It implements a range of communication protocols, such as telnet (traditional in MUD-world), ssh, ssl, a comet webclient and others. It is an auto-connecting client to Server (below).
  • Server - This is the main MUD server. This twisted server handles everything related to the MUD world. It accesses and updates the database through Django models. It makes the world tick. Since all Players connect to the Server through the Portal's AMP connection, it means Server can be restarted without any players getting kicked off the game (they will re-sync from Portal as soon as Server is back up again).
  • Webserver - Evennia optionally starts its own Twisted webserver. This serves the game's website (using the same database as the game for showing game statistics, for example). The website is of course a full Django project, with all the possibilities that entails. The Django admin site allows for modifying the database via a graphical interface. 
  • Webclient - There is a stand-alone MUD web client existing in a page on the default website. This uses Twisted to implement a long-polling ("comet") connection to a javascript client. As far as Evennia's concerned, this is just another outgoing protocol served by the Portal.
  • Other protocols - Since it's easy to add new connectivity, Evennia also offers a bunch of other connectivity options, such as relaying in-game channels to IRC and IMC2 as well as RSS feeds and some other goodies. 

On the joining of the two

An important thing to note about Twisted's asynchronous model is that there is no magic at work here: Each little snippet of code Twisted loops over is blocking. It's just hopefully not blocking long enough for you to notice. So if you were to put sleep(10) in one of those snippets, then congratulations, you just froze the entire server for ten seconds.

Profiling becomes very important here. Evennia's main launcher takes command arguments to run either of its processes under Python's cProfile module. It also offers the ability to connect any number of dummy Players doing all sorts of automated random actions on the server. Such profile data is invaluable to know what is a bottleneck and what is not.

I never found Twisted asynchronous paradigms much harder to understand than other code. But there are sure ways to write stupid blocking code that will come back and bite you. For example, much of  Evennia's workload is spent in the Server, most notably in its command handler. This is not so strange; the command handler takes care of parsing and executing all input coming from Players, often modifying the game world in various ways (see my previous post for more info about the command handler).
The command handler used to be a monolithic, single method. This meant that Twisted had to let it run its full course before letting anyone else do their turn. Using Twisted's inlineCallbacks instead allowed for yielding at many, many places in this method, giving Twisted ample possibilities to split execution. The effect on multi-user performance was quite impressive. Far from all code can  be rewritten like this though.

Another important bottleneck on asynchronous operations is database operations. Django, as opposed to Twisted, is not an asynchronous framework. Accessing the database is a blocking operation and can be potentially expensive. It was never extremely bad in testing, to be honest. But for large database operations (e.g. many Players) database access was a noticeable effect.

I have read of some people using Twisted's deferToThread to do database writes. The idea sounds reasonable - just offload the operation to another thread and go on your merry way. It did not help us at all though - rather it made things slower. I don't know if this is some sort of overhead (or error) in my test implementation - or an effect of Python just not being ideal with using threading for concurrency (due to the GIL). Either way, certain databases like SQlite3 doesn't support multiple threads very well anyway, and we prefer to keep giving plenty of options with that. So no deferToThread for database writes. I also did a little testing with parallel processes but found that even slower, at least once the number of writes started to pile up (we will offer easy process-pool offloading for other reasons though).

As many have found out before us, caching is king here. There is not so much to do about writes, but at least in our case the database is more often read than written to. Caching data and accessing the cache instead of accessing a field is doing much for performance, sometimes a lot. Database access is always going to cost, but it does not dominate the profile. We are now at a point where one of the most expensive single operations a Player (even a Builder) performs during an entire gaming session is the hashing of their password during login. I'd say that's good enough for our use case anyway.

Django + MUD?

It's interesting that whereas Twisted is a pretty natural fit for a Python MUD (I have learned that Twisted was in fact first intended for mudding, long ago), many tend to be intrigued and/or surprised about our use of Django. In the end these are only behind-the-scenes details though. The actual game designer using Evennia don't really see any of this. They don't really need to know neither Django nor Twisted to code their own dream MUD. It's possible the combination fits less for some projects than for others. But at least in our case it has just helped us to offer more features faster and with less headaches. 

Thursday, August 16, 2012

Taking command

Commands are the bread and butter of any game. Commands are the instructions coming in from the player telling the game (or their avatar in the game) to do stuff. This post will outline the reasoning leading up to Evennia's somewhat (I think) non-standard way of handling commands.

In the case of MUDs and other text games commands usually come in the form of entered text. But clicking on a graphical button or using a joystick is also at some level issuing a command - one way or another the Player instructs the game in a way it understands. In this post I will stick to text commands though. So open door with red key is a potential command.

Evennia, being a MUD design system, needs to offer a stable and extensive way to handle new and old commands.  More than that, we need to allow developers pretty big freedom with developing their own command syntax if they so please (our default is not for everyone). A small hard-coded command set is not an option.

Identifying the command

First step is identifying the command coming in. When looking at open door with red key it's probably open that is the unique command. The other words are "options" to the command, stuff the open command supposedly knows what to do with. If you know already at this stage exactly how the command syntax looks, you could hard-code the parsing already here. In Evennia's case that's not possible though - we aim to let people define their command syntax as freely as possible. Our identifier actually requires no more than that the uniquely identifying command word (or words) appear first on the input line. It is hard to picture a command syntax where this isn't true ... but if so people may freely plug in their own identifyer routine.

So the identifyer digs out the open command and sends it its options ... but what kind of code object is open?


 The way to define the command

A common variant I've seen in various Python codebases is to implement commands as functions. A function maps intuitively to a command - it can take arguments and it does stuff in return. It is probably more than enough for some types of games.

Evennia chooses to let the command be defined as a class instead. There are a few reasons. Most predominantly, classes can inherit and require less boiler plate (there are a few more reasons that has to do with storing the results of a command between calls, but that's not as commonly useful). Each Evennia command class has two primary methods:
  • parse() - this is responsible for parsing and splitting up the options part of the command into easy-to use chunks. In the case of open door with red key, it could be as simple as splitting the options into a list of strings. But this may potentially be more complex. A mux-like command, for exampe, takes /switches to control its functionality. They also have a recurring syntax using the '=' character to set properties. These components could maybe be parsed into a list switches and two parameters lhs and rhs holding the left- and right hand side of the equation sign. 
  • func() - this takes the chunks of pre-parsed input and actually does stuff with it. 
One of of the good things with executing class instances is that neither of these methods need to have any arguments or returns. They just store the data on their object (self.switches) and the next method can just access them as it pleases. Same is true when the command system instantiates the command. It will set a few useful properties on the command for the programmer to make use of in their code (self.caller always references the one executing the command, for example). This shortcut may sound like a minor thing, but for developers using Evennia to create countless custom commands for their game, it's really very nice to not have to have all the input/output boilerplate to remember. 

... And of course, class objects support inheritance. In Evennia's default command set the parse() function is  only implemented once, all handling all possible permutations of the syntax. Other commands just inherit from it and only needs to implement func(). Some advanced build commands just use a parent with an overloaded and slightly expanded parse().

 Commands in States

So we have individual commands. Just as important is how we now group and access them. The most common way to do this (also used in an older version of Evennia) is to use a simple global list. Whenever a player enters a command, the identifier looks the command up in the list. Every player has access to this list (admin commands check permissions before running). It seems this is what is used in a large amount of code bases and thus obviously works well for many types of games. Where it starts to crack is when it comes to game states.
  • A first example is an in-game menu. Selecting a menu item means an instruction from the player - i.e. a command. A menu could have numbered options but it might also have named options that vary from menu node to menu node. Each of these are a command name that must be identified by the parser. Should you make all those possible commands globally available to your players at all times? Or do you hide them somehow until the player actually is in a menu? Or do you bypass the command system entirely and write new code only for handling menus...?
  • Second example: Picture this scenario: You are walking down a dark hallway, torch in hand. Suddenly your light goes out and you are thrown into darkness. You cannot see anything now, not even to look in your own backpack. How would you handle this in code? Trivially you can put if statements in your look and inventory commands. They check for the "dark" flag. Fair enough. Next you knock your head and goes 'dizzy'. Suddenly your "navigation" skill is gone and your movement commands may randomly be turned around. Dizziness combined with darkness means your inventory command now returns a strange confused mess. Next you get into a fight ... the number of if statements starts piling up.  
  • Last example: In the hypothetical FishingMUD,. you have lots of detailed skills for fishing. But different types of fishing rods makes different types of throws (commands) available. Also, they all work differently if you are on a shore as compared to being on a boat. Again, lots of if statements. It's all possible to do, but the problem is maintenance; your command body keep growing to handle edge cases. Especially in a MUD, where new features tend to be added gradually over the course of years, this gives lots of possibilities for regressions.
All of these are examples of situation-dependent (or object-dependent) commands. Let's jointly call them state-dependent commands. You could picture handling the in-game menu by somehow dynamically changing the global list of commands available. But then the global bit becomes problematic - not all players are in the same menu at the same time. So you'll then have to start to track who has which list of commands available to them. And what happens when a state ends? How do you get back to the previous state - a state which may itself be different from the "default" state (like clearing your dizzy state while still being in darkness)? This means you have to track the previous few states and ...

A few iterations of such thinking lead to what Evennia now uses: a non-global command set system. A command set (cmdset) is a structure that looks pretty much like a mathematical set. It can contain any number of (unique) command objects, and a particular command can occur in any number of command sets.
  • A cmdset stored on an object makes all commands in that cmdset available to the object. So all player characters in the game has a "default cmdset" stored on them with all the common commands like look, get and so on.
  • Optionally, an object can make its cmdset available to other objects in the same location instead. This allows for commands only applicable with a given object or location, such as wind up grandfather clock. Or the various commands of different types of fishing rods. 
  • Cmdsets can be non-destructively combined and merged like mathematical sets, using operations like "Union", "Intersect" and a few other cmdset-special operations. Each cmdset can have priorities and exceptions to the various operations applied to them. Removing a set from the mix will dynamically rebuild the remaining sets into a new mixed set.
The last point is the most interesting aspect of cmdsets. The ability to merge cmdsets allows you to develop your game states in isolation. You then just merge them in dynamically whenever the game state changes. So to implement the dark example above, you would define two types of "look" (the dark version probably being a child of the normal version). Normally you use your "default cmdset" containing the normal look. But once you end up in a dark room the system (or more likely the room) "merges" the dark cmdset with the default one on the player, replacing same-named commands with new ones. The dark cmdset contains the commands that are different (or new) to the dark condition - such as the look command and the changed inventory command.  Becoming dazed just means yet another merger - merging the dazed set on top of the other two. Since all merges are non-destructive, you can later remove either of the sets to rebuild a new "combined" set only involving the remaining ones in any combination. 

Similarly, the menu becomes very simple to create in isolation (in Evennia it's actually an optional contrib). All it needs to do is define the required menu-commands in its own cmdset. Whenever someone triggers the menu, that cmdset is loaded onto the player. All relevant commands are then made available. Once the menu is exited, the menu-cmdset is simply removed and the player automatically returns to whichever state he or she was in before.

Final words

The combination of commands-as-classes and command sets has proved to very flexible. It's not as easy to conceptualize as is the simple functions in a list, but so far it seems people are not having too much trouble. I also think it makes it pretty easy to both create and, importantly, expand a game with interesting new forms of gameplay without drastically rewriting old systems.