The XEvil Architecture Paper

Steve Hardt
Copyright © 1999,2000


This draft is not yet complete.  However, it provides quite a bit of information useful for understanding the XEvil source code and internal architecture. Updates will be posted on the XEvil Developer's Page, http://www.xevil.com/xevil/dev, as they are written.
4/2/2000

Preface

This paper was originally a snapshot description of the internal architecture of XEvil as it stands now.  But, this view doesn't give the complete picture.  Like all complex systems, XEvil the result of a long incremental and iterative process, specifically adding features, fixing bugs, removing dead and duplicate code, commenting interfaces, testing, porting, and preparing for beta and final releases.  Design and redesign.  Implementation and reimplementation.  So, I add a bit of historical context here and there, describing the issues, decisions, and earlier versions that led to XEvil its current state.

Although not strictly necessary, I recommend downloading a copy of the XEvil source code to read along with this paper.  This paper makes occasional reference to specific files, data types, and code fragments.

Related Documents:

Contents


Introduction

XEvil is a cross-platform UNIX and Windows, client/server networked or standalone, fast action explicitly violent game.

Physical vs. Logical Architecture
logical architecture, the abstractions and mechanisms that describe the behavior of XEvil. Classes, interfaces. Algorithms.

The bulk of this paper concerns logical architecture, the abstractions and mechanisms that describe the behavior of XEvil.  The physical architecture of XEvil consists of the concrete and pragmatic decisions about the source code itself,  For example, the choice of implementation language, set of supported platforms, allocating classes to files, directory structure of the source tree, file naming conventions, packaging the source for movement between developer machines and for distribution.

Object Diagrams

Notation

Very loosely based on Grady Booch's Object Oriented Analysis and Design with Applications.
 
X is-a Y
X has-a Y, one-to-one association, unless annotated with 'n' to indicate one-to-n assocation
X has a tree of child classes
Abstract class
Existence of a number of child classes not in the diagram

List of Diagrams


-Part I: Logical Architecture-

Modules

Diagram A: Toplevel Architecture

Module Overview


Here we describe each of the major players in the XEvil internal universe and how they interact with each other:

Main

Main runs the top-level event loop.  It creates the Game object and feeds events to it.

Create Game object.  Then, until the Game quits:

  1. Game::pre_clock().  All drawing here.
  2. Empty event queue, passing event each to Game::process_event().
  3. Game::post_clock().  All game logic for one turn of play.
  4. Game::yield().  Throw away time since end of previous yield().  Watch for incoming network data, if appropriate.  Implemented together, using select().
In order to respond to user key events as quickly as possible, we empty the event queue immediately before performing game logic.  On most machines, drawing will take the bulk of the time.  And, on machines with very fast graphics, throwing away time will be largest.  So, we are careful to not to put either of these between emptying the event queue and performing the game logic turn.

On hindsight, <pre_clock(), yield(), events, post_clock()> might have given better results.  For a Server,  this would avoid a drawing cycle between incoming Client commands in yield() and the game logic in post_clock().  This would also put drawing right before yield, so the user would see the most up-to-date picture while time is being thrown away.

Game

 

GameObjects

Beginning of each level, choose set of weapons and items for that level.
Tries to keep that set of weapons and items available.  Originally, counted held weapons/items.  But, this led to hoarding.  Instead, only count the number of available weapons/items.  Made it much easier to get weapons/items.  So put hard limit on the number of items and number of items of each class each player could hold.  So players can't wait around at the end of a level picking up 50 MedKits.
Very extendable, asks the Locator for a list of all Physical classes that have the potentialWeapon or potentialOtherItem property.

GameStyle

Diagram B: GameStyle

There are six "styles" of play in XEvil:
 

Levels
Kill all enemies on each level to advance to the next.  Except, every five levels you must complete a scenario.  A scenario is a mission with a specific goal, such as collect all the flags, find the exit before the Aliens kill you, or survive an onslaught of rabid dogs.
Scenarios Only
No normal levels, you only play scenarios.
Kill, Kill, Kill
Everything attacks everything, machine players even attack each other.
Duel
Good for multi-player tournaments, each player has three lives.
Extended Duel
"Death Match" style for multi-player network games.  Humans have infinite lives and the game keeps track of the number of kills per player.
Training
No enemies, good for learning the controls (and debugging).


These sytles are implemented by the GameStyle object and its children.  GameStyle's public interface gives methods to set up the world map and place human and machine players at the beginning of each level, decide what weapons/items to allow, choose the background music, decide when to advance levels, and decide when to end the game.  There is a separate child class of GameStyle for each game style, Normal, Levels, Scenarios, KillKillKill, Duel, ExtendedDuel, and Training.  (Difference between Normal and Levels described below.)

Internally, GameStyle provides some helper methods to its child classes.  The most complicated being the logic to clean up weapons, items, and enemies between levels.  We want to get rid of the extra crap, but don't delete human players, their weapons, items, or followers (Dogs, DoppelGangers).

KillKillKill, Duel, ExtendedDuel, and Training and fairly simple.  Random world, some specific number of human and machine players, start new levels every certain amount of time to keep things interesting.

As you might guess, Scenarios requires the most logic to implement.  Each Scenario is significantly different than the others.  The logic to go "Kill the FireDemon" is not much like "Capture The Flag", run around picking up flags  So, we create another hierarchy, rooted with Scenario (singular, not the same as Scenarios), with child classes KillTheFireDemon, CaptureTheFlag,  Hive, ThePound, JapanTown, etc.  The public Scenario interface is much like the GameStyle interface, logic to set up the World and human and machine players, to choose background music, etc.  However, an instance of GameStyle, e.g. Scenarios, has a lifetime equal to one game.  While, each Scenario generally lasts only one level.  Assuming you beat the Scenario, the Scenarios object will randomly chooses a different Scenario for the next  level.  If you fail the Scenario, e.g. you fail to "Kill the Baby Seals", the Scenario object will make you repeat the same Scenario until you get it.

The astute reader will notice there are seven different GameStyle classes, yet only six styles of XEvil game play.  There's some subtlty here.  Levels does not correspond to "Levels" in the game Ui.  Selecting "Levels" in the Ui, really gives you Normal.  Although, "Scenarios Only" does give Scenarios as you'd expect.  Unlike the others, Levels is only used indirectly by Game.  Normal is like Levels, except it throws in a Scenario every five levels to shake things up.  Normal does this by holding an internal instance of Levels and of Scenarios.  It delegates all behavior to its corresponding instance of Levels or Scenarios.  Normal has no logic of its own except to switch between using Levels and using Scernarios.

Originally, the GameStyle logic was all mixed in with the Game object.  Lots of switch statements and that type of crap.  Eventually, I got sick of it and spent a week refactoring the game style code, pulling it all out of Game and creating the separate object hierarchy for GameStyle.  It was well worth the effort , in avoiding bugs and simplifying later modifications.

World

World is a fairly reactive object, only responding to other objects' requests of it.  For example, the World does not enforce the constraint that objects cannot move through walls.  Physical objects must ask the world if they are about to bump into walls, and take appropriate action themselves.  Within the time frame of a single level, the World map is immutable.  The big benefit here is network play. The server sends the map once beginning each level, then never  worries about it again.  Movers, or elevators, are the exception to both the reactive and immutable nature of World.  Movers move of their own accord and clearly have continuous changing state.  On hindsight, it would have been simpler and cleaner to implement movers as Physical objects instead of the World.  To make drawing and network play work, I ended up having to implement a Physical class, PhysMover, to reflect the state of each Mover.

In the initial design stages of XEvil we went back and forth between having separate or unified representations for the components of the world and physical objects in the game.  On one hand, it would be nice to have one common superclass for all entities appearing in XEvil.  But, there are some very big differences between components of the world and other objects.  The blocks in the World are very numerous and generally immutable, while other objects are less numerous and have rapidly changing location and other state.  So we decided on a  we decided that

Maze algorithm, and specific mazes.  Would like to provide a more general interface for Scenarios to influence the world-generation algorithm, so we could take all scenario-specific information out of World and contain it all in the Scenario classes where it belongs.

See the Physics section for details on gravity and keeping players from going through walls.

UnionSquares, Themes, Movers.

Physical Tree

Diagram C: Physical Tree

Root is Physical, leaves are Actual.

contexts, Storing arbitrary parameters in easy to change form.  Nested.
PhysicalContext used as meta-data for objects, described in Locator.

Calling up the tree and _ methods.

There are quite a few classes in the tree of Physicals, we will only mention a few of the key ones.  Read the source, or look at classes.txt for the full tree.
 

Physical Root

Moving

Moving introduces the concept of Dir (direction).  Each Dir corresponds to a potential sequence of animation frames.  Since Dir exists in the Coord module, each Dir is prefixed with CO_.  Numbered in order, from 0 to CO_DIR_MAX.  There are two types of Dir.  Pure directions are the 16 cardinal directions, used for Shells and Missiles, CO_R to CO_UP_R_R.  For example, CO_R means straight right, CO_DN straight down, CO_DN_R down right at 45o, CO_DN_R_R down right depressed 22.5o from the horizontal (more right than down), CO_DN_DN_R down right depressed 77.5o from the horizontal (more down than right).

The other set of direction, non-pure Dir, are for Creatures with stances, described in the next section.

Use Lancer as an example of a typical Moving object, refer to the diagram.

Creature

The crux of Creature is Ability

Whereas pure Dirs are for missiles and objects that move in cardinal directions, non-pure Dirs represent the movement and animation for Creatures, e.g. running right, jumping left, climbing up ladder.  The non-pure directions are partitioned into seven stances:

Each stance has several Dirs associated with it.  CO_center has three Dirs, CO_center R - walking right, CO_center_L - walking left, and CO_center - standing facing the screen.  The file classes.txt, included in the top-level of the XEvil source code, has an ASCII art diagram showing all the possible Dirs.

Similar to Stance and Dir are the concepts of Touching and Hanging.

As mentioned above, death does not correspond with object destrucion. corpse,

follow movers

go through doors

interpret keys

Modifiers

Ability

Able to add/remove abilities at run time.

Solving the multiple inheritance problems, is-a vs. has-a.  E.g. Hero used to multiply inherit from Sticky, User, Fighter, and Healing, which were all children of Creature.  Now Hero singly inherits from Creature and "has" the Sticky, User, Fighter, and Healing abilities.

Can only have at most one Locomotion and one Holder ability.  Locomotion for movement, Holder for interacting with Weapons and Items.

Object Locator

Abstractly, the Object Locator is the set of all Physical objects in XEvil.  Is the only thing with a list of all objects.


Locator::clock(), runs one turn of game play.  Collision detection, intelligence, act() and update() described in Physical, adding new and deleting dead objects, updating Locator grid, reincarnate bringing human players back from the dead.  Was getting to large, so split into a number of sub methods.
 

Intel

Diagram D: Intel Tree

Strong distinction between Physical and Intel.   Soul-swapper, frog-gun, Transmogifier, can very easily swap the intelligence objects at runtime
 

Human Intelligence

A Human Intel mostly just buffers commands from the associated Ui viewport.

Stats such as score, and player name lie in the Human object.  Association between viewport in the UI and Human object.  So, viewport follows the human player, even when switched into a new body.  Viewport takes a keyboard command from the user and forwards it to its associated Human which sends it to the Physical itself.

Human players have multiple lives, the same Human object persists after the Physical object dies.  The same Human object is reincarnated in a new Physical body.
 

Artificial Intelligence

All Intels that inherit from Machine

strategy as finite state machine, filter_targets()

Enemy vs. DoppelGanger

Pet AI is enhanced DoppelGanger.  4 states, reltn between states here and strategy
 

User Interface

UNIX Specific UI

Ui can be NULL, for command-line server, i.e. the "-no_ui" option.

Panel class

Viewport

Windows Specific UI

Uses MFC.

Two UIs

Role

As much as possible, the Role class encapsulates all behavior related to networking, i.e. the Game's "role" in the current client/server network topology.   Role has three concrete class children: StandAlone, Client, and Server.

Game communicates with Role through Role's abstract interface, consisting of three parts:

  1. Access: Simple, Role returns some information about itself, e.g. whether it is connected properly, the Role's preferred GameStyle, etc.
  2. Notification:  Game tells the Role about important events like "new_level", "reset" (new game), "new_human_created", so that the Client/Server has an oppurtunity to communicate with the Server/Clients across the network.
  3. Timing: Two methods:
    1. clock() gives the Role a chance to perform per-turn behavior, e.g. Server tells the client what changed each turn, Client tells Server about movement/weapon command issued by the user.
    2. Game calls Role::yield at the very end of each turn, to throw away the remaining time before the next turn.  Since we are in a single-threaded environment, yield() is the one place where Role can afford to block and listen to the network for a period of time.
We describe Client and Server implementations of Role in the Networking section.  And, StandAlone is quite simple.  The Access methods are all one-liners.  The Notification methods are stubbed out, since there is no network communication.  StandAlone::clock() does nothing, and StandAlone::yield() simply sleeps for the remaining time in the turn.

Utilities

Geometric primitives, utils, coord, area

Utils
random, c-runtime wrapper, string manipulation, sorting,

Obviously, can't use Windows CRect, or X geometric primitives in XP code.  Make our own.  Try to use as much as possible in front-ends, especially in the interfaces.  Would like to refactor MFC out of Win front end more.

Coord
Pos, Size, Vel, Acc, Loc, Dim, Box, RoomIndex, Rooms.  Conversions.

Area, originally intended to allow non-rectangular areas.  "Region", "Shape", all had namespace collisions with Windows or UNIX graphics libraries.

Transform2D used for autogenerating bitmaps, described in Graphics section.

Stretched vs unstretched, comments to indicate whenever there is ambiguity.
Historical reason.  Take advantage of factor of two,

Give pointer back to Moving and Creature for Dir, Stance, Touching

Utils is c-runtime wrapper

DebugInfo class, can still be used in a release build.  Trivial overhead, allows detailed bug reports from installed applications.
 

Physics

Whatever works.  Have to deal with integer constraints.

All rectangle based.  Store position, mass, and velocity.   Position is integer constrained, Velocity is floating point. Acceleration is not explicity represented.  Acceleration exists as an instantaneous change in velocity in response to an event such as a collision or a user keypress.

Two classes involved, Physical, i.e. the tree of all Physical objects, and World.  So, we have two types of collisions Physical-Physical and Physical-World (world cannot collide with itself).

Physical-Physical collisions: Perfectly inelastic collision between two point masses.  Unmapped objects.  Can set objects not to collide with specific others, so you can't be hurt by own bullets. Objects of greater mass can push others. Objects of zero mass don't push at all.  Was too annonying when bullets pushed you back.

Physical-World collisions:  Avoiding going through walls.  Walking on floor and climbing on walls.

Gravity, Flying objects.

Graphics

Intertwined with the World and Physical objects.

Could have had abstract bitmap and pixmap objects, but difficult to define an abstraction that encompasses all the differences between Windows and UNIX.  Multiple displays, Sharing DirectDraw surfaces on Windows.  Did not have all the information available at design time.  So we chose separate implementations of the drawing code

Xvars Abstraction Layer.  More necessary on Windows because DirectX is such a buggy unpredictable piece of shit, while Xlib is stable mature technology.

xdata, CMN_*

Auto-generation rotations and reflections.  Transform2D, PH_AUTO_GEN in context.  Reduced size of executable by a third.  Greater ease of modification.

Mask and Invisibilty.  Shift bits of background.


 

UNIX Specific

Uses straight Xlib.

Drawing Algorithm

XPM

#included in the source.  Auto-generated from Windows bitmaps, see below.

Windows Specific

DirectDraw

Bitmaps

SurfaceManager

Drawing Algorithm

Very simple, since we have DirectDraw to give us low-level blitting routines, we simply redraw the entire screen each clock (25 fps).   Draw from back to front: background, then world blocks, then characters, then text messages overlayed on the top.

Shared Graphics

Don't want separate set of graphics.  Maintanence, easy of extension.   Network compatibility.
Could make custom file format.   Instead used Windows BMP files, tools already exist.  Easier for artists to contribute graphics.  Tool to convert BMP files to UNIX XPM.  Thus, do all graphics work w/ Windows BMP files, and run the auto-generate for the UNIX builds.  Only have to run the tool when the graphics change.

Generate all graphics.  Init all, then ask World to list all graphics, Locator to list all Physical classes,  then each Physical class to list all graphics.  Include transparency when appropriate.

Describe command line args to do so.

UNIX includes XPM files as

Networking

Describe the Server and Client implementations of Role, and the XETP Network protocol.
 

Table A: Network Layers
Layer Classes in Layer
Role Client, Server
XETP XETP
Stream TCP:   NetInStream, NetOutStream
UDP:   UDPInStream, UDPOutStream
UNIX Socket API <implemented by operating system>

Streams

Don't reinvent the wheel.  Use both TCP and UDP.  Made simple, platform independent, big-endian input and output TCP (NetInStream, NetOutStream) and UDP streams

Methods like read/write_int(), read/write_char(), read/write_string().  Handles platform-specific differences in lengths of  the C++ language "char", "short", "int", "float", and in the signedness of "char".

UDPStream poorly named.  Really deals with packets.  For efficiency, multiple XETP methods are buffered up and sent in a single UDP packet.
 

XETP (XEvil Transport Protocol)

Simple binary network protocol.  Static methods in XETPBasic and XETP to connect, disconnect, send/receive objects, commands, chat messages, world maps.
 

Serialization

serialization (get_write_length() and write_to_stream()), and deserializaiton, create_from_stream().  Used for network play, only writes enough so that client can draw itself, emphasis is on minimizing the number of bits stored.  E.g. if we ever wanted to implement a save-game feature, we would have to write enough to completely restore the state of each object.

Server

Server, non multi-threaded.  List of Connection.
Adjust Data flow.
Disconnect clients after time.
Plays the game, like standalone
Role::clock() and yield()

Client

Just display what Server sends.  Send commands back to server.  Dead-reckoning
Role::clock() and yield()
 

Network Compatibility


XEvil clients and servers can only connect if the same XETP version.  Startup, XEvil displays XETP version number.  Generally, both client and server need the same set of graphics and the same Physical/Actual tree.  Can add new scenarios, change client or server Ui, change game logic and still maintain network compatibility.  But, if you add a new character/weapon/item, add new graphics, or add/change XETP methods, you  must increment the XETP version number.

Naturally, this influences our release management decisions.  E.g. XEvil 2.0, 2.01, 2.02 are all network compatible, XETP version 1.00.  We delayed any incompatiblity-inducing changes until XEvil 2.1.  In XEvil 2.1 we (will) introduce a number of new characters and graphics, as well as some changes in XETP itself.

If necessary, we can introduce compatibility modes to clients and servers to talk to other versions.  Of course this is a giant versioning headache, and we will only do it if users request it.  Ideally, we'd have ways of automatically downloading new graphics and characters from a server.  When a client connects, it compares its set of characters/world graphics to the server and downloads any that it needs.  Maybe for my next game.
 

Server Ping

To enable web-based server monitors, XETP has a special method, XETP::SERVER_PING.  When an XEvil server receives this request, it replies with info about the current state of the server, e.g. number of players, player names, style of game being played, etc.  Thus, a web-based application can display a list of running XEvil servers, with continuously up-to-date information.

Sound

SoundManager, SoundRequest, and SoundNames
 

UNIX Sound

Dummy UNIX SoundManager.
An implementation of SoundManager for key, if not all, UNIX platforms is exactly the type of thing that developers on the net could work on (hint, hint, to any of you reading this).

A UNIX server must provide approprite sounds for Windows clients.  When a Client connects, it tells the Server whether it would like sound events.
 

Windows Sound

Background music as MIDI files, sound effects as WAV. CD for background music.
temp file system
 


-Part II: Physical Architecture-

Big constraint is the cross-platform requirement.  Having separate, independent sets of files for UNIX and Windows XEvil is unacceptable.  Costs of merging code and dealing with mistakes from incorrect merges would quickly escalate out of control.  We would be forced to chose which version was the "real" XEvil, and then abandon the other.

C++

Comments and Interfaces

Comments on interfaces appear in .h files, generally not duplicated in .cpp files.  When trying to understand a method/function/variable, you should look in the header file first.  Comments in .cpp files describe implementation details, algorithm, special cases, use of other modules.

Update comments when code changes.  If you update code, interfaces, without updating the corresponding comments, the comments become useless, perhaps even dangerously misleading.

In the case of a child class method overriding a superclass method, the comment on the interface will generally appear in the top-most class that first defines the method.  No point in cut-n-pasting the method description and risking the descriptions becoming out of sync.  Child overriding class methods will only be commented if there is something novel or unintuitive about that method or its use.

Directory Structure

After porting XEvil to Windows, we went back and merged the Windows and UNIX versions into a single codebase that could build on both platforms We make active efforts to suck code from the platform-specific directories to the common directory.  Code duplication is bad.  Fixing the same bug twice is bad.  If a piece of code is only used by one platform, but might someday be used by others, it should reside in the cmn directory.

#ifdefs

Platform-specific #ifdefs seem to be a necessary evil.  In theory, every difference could be hidden behind an appropriate cross-platform interface or typedef, with platform-specific implementations.  But, cost is often prohibitive.  Many point fixes where anything other than an #ifdef would require significant costs in rearchitecting and reimplementation.  In particular, #ifdefs often need to be added late in the game as final tweaks, when large structural changes are prohibitively costly and risky.  E.g. doing final builds, trying to make XEvil work on yet one more UNIX platform.

So, there are platform-specific #ifdefs in the XEvil codebase.  We fight to keep them to a minimum, however.

Graphics

UNIX Graphics


bitmaps and gen_xpm directories
 

Windows Graphics

res dir, bind all graphics to executable
 

Sound

Windows Sound

MIDI files and WAV files are bound as resources to the executable.

"Bitmaps" Files

UNIX Platforms

Windows Platforms

We support Window 95, NT, 98, and 2000.  The build problem isn't nearly as difficult as with UNIX, since they all use the Win32 API and the same binary can run on all platforms.  But we must still test on all platforms.  Like most Microsoft products, they claim to be compatible, but really have all sorts of undocumented weirdness and differences that translate to great pain for developers and users. <RANT>Microsoft: Fuck the user.  Fuck the developer.  We're a monopoly and we own you.</RANT>

Win 3.1 is simply not worth the effort, all the 64K memory management  foolishness, poor development environment, crashes randomly, no DirectX.  And most Windows gamers are on Win32 or moving there soon.

Packaging and Installation

Binary

Single file executable for Windows and UNIX.  Self-extracting EXE for Windows.  Standard compressed tarred, ".tar.Z", file for UNIX.  Should probably change to use GnuZip, ".tar.gz".

Made RPM file for Red Hat Linux.

Source

We use the same distribution file for UNIX and Windows.  Simplifies maintenance and distribution, and, most importantly, makes it easy to bring changes back and forth between UNIX and Windows machines.

The UNIX Makefile has a target, distzip, such that "make distzip" will package up all the source and create xevilsrc.zip.  Windows has a batchfile, dist.bat, that does the same thing.

All text files are stored in the zip file with Windows CRLF line break conventions.  The choice of UNIX or Windows conventions was largely arbitrary, but we had to choose one.  On UNIX, "make distzip" will take care of the conversion in making the zip file. but developers must be careful to "unzip -a" (autoconvert text files) when unzipping the file.  Some versions of unzip don't autodetect the XEvil binary files correctly, so we include the script "unzipxevil" to unzip the source.

For XEvil 2.0 and 2.01 we created a "Source RPM" file for use on Red Hat Linux.  This may or may not be supported in the future.
 


-Appendix-

List of files

This gives the mapping from the physical architecture(files) to the logical architecture(classes).

cmn directory (common to all platforms):

x11 directory (UNIX/X only):


win32 directory (Windows only):

TODO

Would have done Differently

Evolution

See the XEvil timeline for specific dates.

Instances of large-scale code refactoring: