3.3 Architecture

3.3.1 C + Guile

Technically, Liquid War 6 is a collection of C functions which are exported to Guile. The main binary embeds a Guile interpreter, which will run a Guile script. This script calls the exported C functions, and glues them together.

It should be possible to implement the game without using Guile at all, using C code to make the various modules communicate together. This might seem an easier way to go, not involving several languages. However, using this script level is a good way to achieve several important goals:

• it’s possible, at any time, to query the game about its internal state, dump objects, take actions. That’s what the console is about. It’s a bit like having an embedded debugger, it’s really a very convenient tool to develop, make experiments and track problems.
• many hacks can be done without recompiling anything at all. Simply edit a few files with an editor, and your patch is running. Once the binary base is set up, hacking scripts on top of it is (almost) a piece of cake.
• forcing the program to use scripts to transfer informations from a module to another is a good way to avoid “spaghetti” code, when modules cross-use each other in an uncontrollable way. Of course in some cases, modules communicate directly, especially when performance is important. But for many tasks, it’s just very comfortable and safe to have module A send orders to module B through a high-level script API.

Having Guile to implement high-level stuff also decreases, to some extent, the need for object-oriented features of C++. The big picture is : low level code that require speed, optimized data processing, is written in C. Code which is more high level and requires abstraction is written in scheme.

3.3.2 Threading and SMP

Liquid War 6 makes a heavy usage of threads. Early versions of the game did not have this feature but starting with 0.0.7beta, one can really consider the game is heavily threaded.

There’s basically:

• a thread to handle the main control flow. This thread runs scheme code which Guile. It’s not the most CPU-greedy thread, but when it’s stalled, there’s no more interaction between the user and the program.
• a thread to handle the display. Depending on rendering options, this thread can consume lots of CPU cycle. On a single processor/core system, it can be interesting to lower rendering options in order to gain speed on other aspects of the game. On a quad-core system, it’s probably useless, just play with all bells and whistles activated.
• two threads to run the core algorithm. One maintains the so-called reference state, the other being dedicated to the draft sate. In a local game there’s no draft state so only one of those two threads is used. There’s even a technical optimization which can be turned on and can theorically use even more threads and be efficient on very big maps but well, it’s rather untested and still has to prove its real efficiency.
• a thread to handle map loading. This one is not active all the time, it’s just here to keep a preemptive interface while loading complex maps.
• network code can also fire threads, especially when connecting on remote systems.

So globally, if you have an SMP system, the game will be happy with it. It will also run on a single processor, as the program uses POSIX pthreads it’s capable to run on any computer which has pthreads implemented for it.

But, and this is a strong limitation, without pthreads, the game won’t run. At all. Or at least, not unless it’s almost completely rewritten.

3.3.3 Internal libraries

The C code is splitted into several internal libraries. This allow independant testing of various game modules.

The main module, the most important one, is libker, (stands for “kernel”). This is were the core algorithm is. To some extent, the rest of the code is just about how to provide this module with the right data and environment. Logically, if you profle the game, you should find out that a great part of the CPU time is spent here. Code here is about spreading gradients, moving fighters and cursors.

The libmap module is here to handle maps, it contains the code to manipulate maps in memory. But it does not know how to load them from disk. This is the responsability of another module, libldr, which is linked against libraries such as libpng or libjpeg and does the job of transforming those standard formats into a usable in-memory structure. The libgen module also works the same way, creating pseudo-random maps. There’s still a another moduled involved in map handling, it’s libtsk, whose job is to load a level in the background. It has a 2-steps asynchronous loading system which allows the game to load maps while the user interface is still responsive, and give a preview of the map as soon as possible, when loading continues in the background, building optimizing structures which are usefull when playing but not mandatory just to show the map.

At the other end of the algorithm-chain, the libpil module will “pilot” things. It’s this module which will translate text readable orders (typically adapted for network usage) into function calls. It has event lists, keeps them in the right order, and will also permanently maintain three different states of the game. A backup state which can be used any time to go back in time and get the game in a stable 100% sure state. A reference state which is correct but ever changing. Basically backup plus all the orders received between backup and reference gives reference. And finally a draft state which is as up to date as possible but might be wrong. This is typically interesting in network game, where we want to show something moving, something fast, even if there’s lag on the network and other computers fail to send information in time. In this case we display draft while still keeping reference and updating it when we finally receive valid informations. Backup would be used to send bootstrap information when people are joining a new game, or to check up if things are going right.

A special libbot module is here to handle bot algorithms. A bot is just a simple move function which takes a game state as an input, and returns an x,y position, just the way a mouse handler would. How complex a bot is “under the hood” depends on the type of bot. Current bots are really basic. Additionnally, libsim will run dummy fight simulations to find out wether some team has a real advantage on another one, speaking of team profiles depending on colors.

The libgfx module handles all the graphics stuff. It is itself splitted in several sub-modules, that is, it does not do anything but load a module such as mod-gl1 which will actually contain the implementation. In an object-oriented language, it would be an abstract class, an inteface. The implementation does not need to be thread-safe. It’s better if it is, for theorically it could be possible to fire Liquid War 6 with two display backends running at the same time on the same game instance, but this code has yet to be written, and it’s a rare dual headed configuration which probably has no real-life usage. If only one graphics backend is activated at a time, the rest of the implementation garantees there will never be two concurrent calls to a function is this module. It is the libdsp (“display”) which handles this. It fires a thread for rendering purposes, and sends information to this thread, detecting automatically if it’s necessary to acquire a mutex and update rendering informations. For the caller, this is transparent, one just has to call an update function from time to time. The module will even perform “dirty-reads” on a game state being calculated, to render things in real time, as soon as possible.

An experimental libvox module is under design/development and might, in the future, provide a real-time voxel renderer. Still pre-alpha stage.

To ease up the implementation of different graphics backends, a libgui module contains code which is meant to be used by any graphics backend. It’s just a factorisation module, containing common code and interfaces, related to displaying things. This is where, for instance, one can find a high level menu object. In the same spirit, libmat contains generic math, vector and matrix code, which is commonly used in 3D interfaces.

The libsnd module handles sound. It’s also an abstract class, an interface, which uses dynamic backends as implementations.

The libnet module is a wrapper over different network APIs, it handles Winsock and POSIX sockets in a uniform manner. The libcli and libsrv contain network client and server code, implementing the various protocols in dynamically loadable sub-modules. It’s the role of libp2p to glue this together, handle the list of available servers, the message queue, verifying nobody is cheating, and so on. All this modules share information about current game state using code & structures defined in libnod,use message utilities (format, parse) defined in libmsg and share code concerning connections in libcnx. Additionnally, libdat provides facilities to store old network messages and sort them.

The libsys module contains most system and convenience functions, it handles logs, type conversions, timer, memory allocation, it’s the fundamental module every other module depends on. It has a compation libglb module with all the Gnulib shared code.

The libhlp is used to handle keywords and internal self-documentation (this is what is used by --list and --about), libcfg knows how to read and save config files, libcns handles the console, and libdyn can load .so shared files dynamically.

To glue all this, there are some Guile bindings with helper functions available in libscm which fills two needs, one being an easy way to check if Guile linking is working correctly without requiring all other modules to be available, and also performing automatic checks on some actions such as registering or executing a function.

Finally there are small modules like libimg (to make screenshots of the game) which have been separated because they required special libraries to link with and/or did not really fit in existing modules for dependencies reasons.

So well, this is a lot of modules. The list might move a bit, but the big picture is here. Each module is testable separately.

Below is a Graphviz diagram, which shows the modules dependencies.

3.4 Memory structures

The most important memory structures in Liquid War 6 are:

• map (lw6map_level_t) : this contain the map immutable informations. This is what resides in memory after a map has been loaded from the disk. It contains all the various .png and .jpeg files stored as pixel arrays, resampled if need, and also contains the various map attributes. Once this structure is ready, the game is capable of displaying the map on the screen, but it can not do anything with it yet.
• game_struct (lw6ker_game_struct_t) : this one contains the same informations as the previous structure, only the information has been post-treated so that it’s ready for use by the core algorithm. It will, for instance, contain the famous mesh structure, which groups squares by packets of 1, 4, 16, 64 or more. The reason it’s been separated from the level is that operations such as creating the mesh might require a lot of time. So to allow players to see the level while black magic is still running in the background, it was required to make a difference between what is required to view the map (“level”) and what is required to play on it (“game_struct”).
• game_state (lw6ker_game_state_t) : contains all the variable, ever changing game data. This is where the position of fighters is stored, their health, and such things. It is designed to be synchronizable by using mostly simple calls to memcpy. It heavily relies on the previous structures, the idea is that one can have several “game_state” plugged on a single “game_struct”.

All these structures are defined in the ker/ker.h header.

3.5 100% predictable algorithm

The core Liquid War 6 algorithm is 100% predictable, that is to say, given the same input, it will produce the same results, on any computer. Previous versions of the game also had this property. This is very important for network games, since in a network only informations such as “cursor A is at position x,y” are transmitted. Every node maintains its own internal game state, so it’s very important that every node comes with the same output given the same input.

For this reason Liquid War 6 never uses floating point numbers for its core algorithm, it uses fixed point numbers instead. It also never relies on a real “random” function but fakes random behavior by using predictable pseudo-random sources, implementation independant, such as checksums, or modulos.

There are also some optimizations which are not possible because of the predictability requirement, for instance one can not spread a gradient and move the fighters in concurrent threads, or move fighters from different teams in different threads.

If you read the code, you’ll find lots of checksums here and there, a global checksum not being enough for you never know where the problem happened. The test suite uses those facilities to garantee that the game will run the same on any platform.

Not being able to rely on a predictable algorithm would require to send whole game states on the network, and this is certainly way too much data to transmit. A moderate 200x200 map has a memory footprint of possibly several megabytes, so serializing this and sending it to multiple computers at a fast-paced rate is very hard, if possible at all, even with a high bandwidth. We’re talking about Internet play here.