Incursion: Return of the Forsaken –
A Case Study in Roguelike Game Development
By Julian Mensch
The Nature of Roguelike Games
The term “roguelike” describes a wide variety of popular shareware and freeware computer games that trace their ancestry back to the UNIX classic Rogue. Roguelike games have an essential similarity to CRPGs (computer role-playing games) such as Ultima (any of them), Neverwinter Nights or Diablo – the latter of which is probably the closest relative of true roguelikes in the commercial gaming milieu. While opinions vary widely as to what exact elements make a given game a roguelike, the most common list includes ASCII-based graphics, turn-based gameplay, permanent character death (in the sense that once you die you must start the game at the beginning with a different character), randomly generated dungeons and gameplay areas and mechanics loosely derived from the Dungeons and Dragons tabletop RPG (as almost all CRPGs have to one extent or another). Many speculate that the continuing popularity of these games is due to their replayability – the combination of randomness and a need for real strategy (as a result of permanent death) gives them an appeal quite distinct from mainstream CRPGs.
Roguelike games represent a very exciting field of work for hobbyist games programmers, because it is entirely feasible for a single programmer to create a very popular game without needing skills in graphic arts or trying to compete with the large teams of professional programmers and artists that produce modern graphical games. Thomas Biskup would have to be the cardinal example of this, having produced the enormously popular roguelike game ADOM single-handedly.
Every game needs a special edge to make it desirable to players; it has to be the best in its grouping, or have some truly unique element, or some combination thereof. In other words, the very first question a game designer should ask himself is, “what’s my hook?” What would make someone want to play my game above all the other games out there?
There are four central elements that make Incursion unique within its genre: extensibility, the d20 ruleset, an immersive world and long-term tactics.
While Incursion’s internal architecture is more technically involved than that of most other roguelike games, the strength of its basic structure will minimize the need for both repetitive and illogically-placed code, and allows it to support features that previous roguelike games could not.
The design goal for Incursion includes true modularity such as is commonly seen in commercial RPGs like Baldur’s Gate. The game includes its own script language and new modules describing monsters, quests, character classes and other elements of gameplay. It is possible to add a great deal to the game and change it drastically without altering the source code of the core executable at all. To date, there has been no released roguelike game that features this kind of extensibility, customization and modularity.
Obviously, this is the most difficult of the four design goals listed here to achieve, and the methods used to achieve it are explored in much more detail in the algorithms and strategies section below.
The d20 Ruleset
With the release of the 3rd edition of their best-selling tabletop roleplaying game, Dungeons and Dragons, Wizards of the Coast declared much of the rules content of that game to be open game content under their new Open Game License. While game developers cannot use Wizards of the Coast’s trademarks to advertise their games (such as “Dungeons and Dragons” or “d20 system”) the actual OGL material still provides a superior foundation upon which to base a roguelike game. The d20 rules are superior to previous fantasy RPG rules sets in many ways, including a streamlined approach to multiclassing, more detailed, realistic and tactical combat procedures and increased flexibility in character design and abilities.
Incursion does not adhere slavishly to the d20 framework – it uses a percentile speed system instead of a round-based combat system, damage-reducing armor and the manner in which spellcasting and metamagic feats are handled is more reminiscent of the “spell point” systems traditionally seen in computer games than the “fire and forget” spell slots systems seen in D&D and the d20 system. Both of these changes were made to streamline gameplay from the player’s perspective, minimize the amount of extraneous bookkeeping the player must do (such as choosing lists of spells to memorize) and exploit the fact that doing extra behind-the-scenes math does not slow down a computer game the way it would slow down a tabletop RPG.
Despite these (admittedly non-trivial) changes, as a designer I like to feel that Incursion still captures the spirit and design philosophy of the d20 system. Primarily, Incursion does not balk at the many intricate details that form the meat and potatoes of the d20 system. The many character creation options and tactical choices available in the tabletop game remain mostly intact in Incursion. Players can choose feats, clerical domains and spells for their characters that offer a much greater degree of customization than most other roguelikes do by simply allowing players to roll their character’s attributes and choose a race/class combination. The combat system includes much of the flexibility of the d20 system, with rules for attacks of opportunity, flanking, flat-footedness, grappling, tripping, disarming and many other nuances.
Plot versus World
Roguelike games traditionally have an influence on replayability over plot, and Incursion is no different. Death is intended to be permanent in a roguelike game, and while in Incursion there will be options for resurrection, the fact remains that a player will likely have to start anew from the beginning of the game many, many times before achieving victory. As a result, any kind of strong plotting (as is typically seen in commercial computer RPGs such as Baldur’s Gate or Morrowwind) is impractical, as the player will end up going through the same conversions with NPCs and plot-developing cut scenes again and again and again. Further, a single author could never achieve the sheer amount of plot and story development contained in a commercial RPG with whole teams of professional writers behind it.
As a result, the majority of current roguelike games simply discard the idea of immersion completely. NetHack’s idiosyncratic sense of humor smashes the fourth wall regularly, including samurai, kitchen sinks, light sabers and Norse gods in one vast patchwork setting; Omega’s world is based on the humor of anachronism, with the medieval player buying fast food and finding maps of NYC, and even the strongly Tolkien-themed Angband mixes characters from countless different time periods of Middle Earth and drops them all in one huge dungeon for the player to kill.
Obviously, immersion and believability are not highly-rated goals in these games.
Incursion is aiming for something a little different. Like most roguelikes, there will be very little true “plot” in Incursion; the game doesn’t strive to tell a story the way most CRPGs do. However, the world will be drawn seriously and with an eye toward detail even though the plot of the game itself is not high on drama. The primary method of achieving this is to focus on world detail rather than conversation. There will be no (or very, very few) branching conversation trees in the game, but items, myths, cities and locations are none the less described in consistent detail. The intent here is that a player can get to “know the world” of Incursion and appreciate it as a believable place with nuance and detail, without replayability being repetitive.
The descriptions of races and gods are where this element is most visible in the current stage of development of Incursion. The actual gameplay currently consists solely of the player character going into the dungeon and killing things, but the flavor text doesn’t reflect that limited experience. Instead of falling back on the generic “little vicious humanoids,” we are told that kobolds are “demons of the mines; creatures who poison wells, snuff out lantern flames, kidnap children and prick captured maidens with a thousand pins.” The pantheon of gods is designed and described not in terms of “adventurers of class X and alignment Y worship this god,” but in terms of the impact the religion in question would have on a real society of peasants, nobles, guilds and cities. The game’s religion alludes to Roman Catholicism, Norse paganism and classical Greek thought in various places, and the gods are described in terms of how they interact with society at large.
None of this has any impact on the actual gameplay, but I believe that the fact that the game is set in a consistent and colorful world will add to its appeal. More significantly, the flavor text generally occurs in the online help, as the result of using the ‘l’ook command, or as brief introductions and conclusions to quests. As such, it doesn’t become tiresome in gameplay the way conversations would.
Another advantage of the “write a world, not a plot” approach to game design is that it gives the player a much greater degree of freedom in the game. There are no plot-crucial NPCs that the game won’t let the player kill, because there is really no plot at all, beyond “kill one of the 13 big bad guys and win the game.” There are side quests and different choices, but there is really no story attached to those options, and that gives the game the freedom to be much more open in what it allows the player to do.
The final difference between Incursion and existing roguelike games is the emphasis on long-term tactics. Incursion aims to eliminate many of the elements of roguelike gameplay that detract from a player’s overall enjoyment of the game through careful design.
For example, in most existing roguelike games, the player effectively has a Ring of Regeneration on his finger all the time, recovering hit points and spell points nearly instantly. Resting is a trivially easy act, and the only fights which are dangerous are the ones which stand a chance of killing the PC because he can’t escape to rest up if he begins to lose, or because the monster can kill him in a single hit. Obviously, if the only way that a common monster (as opposed to a stat drainer or level drainer) can impair the player is to kill him, this makes encounters either trivial or terrifying, with little middle ground.
In Incursion, resting requires spending eight hours sleeping, which is both dangerous in a dungeon if precautions aren’t taken and a tactical loss – the player becomes hungrier, which consumes food reserves, and more monsters are generated in the dungeon, without the same quality of treasure that the original monsters on a given level had. Clearly, resting is something a player wants to do only when necessary, because it carries with it significant disadvantages.
The benefit of this is that it can make a much wider variety of things into serious disadvantages in gameplay. A monster’s attacks don’t have to have a chance to kill the player to be serious and worth avoiding; they just have to use up enough hit points to cause him to choose between resting and using a healing potion. A player can “lose” an encounter, in the sense of spending an undesirable amount of resources overcoming a threat, and keep his character while having suffered a non-trivial setback.
One of the clichés of roguelike games is the YASD (Yet Another Silly Death), where players lose their character to a single silly mistake or random event that is essentially arbitrary in nature, and must start the game from the beginning again. Incursion intends to remove (or at least minimize) this trend – ideally, the true death of a player character in Incursion should be the result not of a single event but of a longer stream of tactically imprudent decisions on the player’s part that have consumed resources and turned the odds against the character in question.
Further, Incursion aims to eliminate the benefit gained from the practice referred to as “scumming” – repeating a series of actions again and again in order to gain a desired outcome. The primary example of this is staying at a certain level of the dungeon and killing monsters over and over and over again in the hopes of gaining some particularly powerful magical item. The paradigm of Angband and related roguelikes is that items have a rarity level related to their power, and the player essentially trades play time for the acquisition of the item in question. This is undesirable because it leads to very repetitive gameplay and player frustration. (It can also make the game addictive, and certain commercial RPGs like Diablo have benefited from this, but the goal of a freeware games developer should be genuine fun and interest for his players, not addictiveness.)
Incursion, on the other hand, simply demands that a player’s character be powerful enough to survive to a given dungeon level, and they will then gain all the treasure that is available in that area on their “first sweep.” Our general design principle is that trivial or repetitive actions that are uninteresting to perform should not be rewarded by the game. If an item they very much want is not there, that’s unfortunate, but they can’t wait around and get it later. When the player rests, monsters are regenerated but significant treasure is not. (The game does regenerate items like healing potions and food rations, of course.) This also provides the player with a greater impetus to explore the world map – finding a new dungeon is valuable, because the “dungeon near town” contains finite amounts of treasure and the things the player wants may just not be there. Finally, ironically, this approach makes finding the truly rare special items much more of an enjoyable experience, because in many games a given item may “just not be there” at all, so they become a pleasant surprise rather than something that is expected, and thus causes impatience and frustration until it is found.
This is the only one of the four primary design goals that the current version of Incursion fails to meet adequately, in the author’s eyes. The elements are there in play, but it’s still too easy to die quickly and arbitrarily, and there are still parts of the game where it can be very profitable to “scum” for resources. One of the primary issues to be addressed in further development of the game will be bringing the gameplay more in line with this design goal.
Algorithms and Strategies
Incursion benefits greatly from having had a clear picture of the intended design goals and features before coding began. Abilities like player polymorphing, multiplayer capability, scripted resources and flexible d20-style multiclassing can be very difficult to implement if they are not taken into account in the early stages of game development. Fortunately, Incursion accounts for all of these features and many more in the design of its basic skeleton. Not all of them have been implemented yet, but the important element is that the code has been written in such a way that they can be implemented, without needing to tear apart the program and start from scratch.
The Object Registry
Like any large C++ program, the fundamental data structures of Incursion are objects. While object-oriented programming is a significant asset to many kinds of projects, it is exceptionally beneficial to the modeling of a world that is composed of quite literal “objects” (monsters, magical items, area maps, weapons, etc.) rather than more abstract data structures like financial portfolios or Internet usage tables. However, one of the shortcomings of the C++ language is that it does not include a fully standardized way of saving and restoring objects to files. A significant part of the problem with this is that objects usually contain pointers to specific locations in memory which cannot be guaranteed to be the same when the program is next run, making these values useless.
In order to create persistent data structures that can be maintained from one execution of the program to the next (saved games, in RPG parlance) the typical response is to create a file format for saved games consisting of state information in static records, and then rebuild the program’s data structures every time a saved game is loaded. Incursion forgoes this method on the ground that it entails too much coding overhead for the high complexity of Incursion’s data, as well as generally lacking elegance. The alternative is to use an object store – a system where all of the game’s classes are derived from one base class that includes within itself the ability to serialize itself and anything derived from it. Many class libraries, such as the Microsoft Foundation Classes, include a pre-coded object store among their many features, but I decided to forego using one of these for two reasons: using a commercial class library severely restricts the portability of a project (and roguelike games are otherwise very easily and cleanly ported to other platforms) and it involves adding a large base of foreign code to the project, which makes debugging all the more difficult. So, I decided, it would be necessary to create my own object store.
This is simple in theory, though the exact mechanics proved more difficult to implement. First, every object in the game is assigned a unique 32-bit integer as a handle, and all the object pointers and object pointer dereferences in the program are replaced with handles and handle lookup function calls. Since these handles retain the same meaning across every instance of the program’s execution, it is now possible to write the memory image of an object to disk and restore it later, with links to other objects in the game intact. The object registry, then, is simply the database that stores the memory locations of every object, along with their handles, translating handle into pointer whenever the game requests. Since the object registry also lists all the objects and sorts them into groups (based on what map level they are currently on) it becomes trivial to save and restore all of the game’s objects when needed. Certain other technical details – the replacement of “const char *” strings with a specialized String class that can be safely serialized, for example – complete the object save and restore process.
In addition to allowing the player to save and restore the game, the object registry provides several useful secondary functions. The 32-bit object handles mesh with the game’s 32-bit virtual machine (described below) much more neatly than pointers (whose size is arbitrary based on the target architecture, and could theoretically if not practically exceed 32 bits) would have. Further, the object registry is exceedingly useful in debugging – while an invalid pointer reference will usually crash a program, an invalid handle lookup allows the system to wind down neatly, and can even offer options for figuring out whether that handle was ever valid, and if it was what it used to point to and when that object was deleted.
Finally, the object registry can be very easily extended to support the use of temporary files, storing the areas of the game other than the one the player currently inhabits to disk in order to preserve memory, then recovering them individually whenever they are needed. Remember that unlike CRPGs, roguelikes generate all their levels randomly, so there is a great deal more data to be saved than in a game with pre-defined maps. Some scheme for memory management is essential, and the object registry provides that.
The Resource System
Incursion relies on a vast volume of static data used for describing elements of the game; this information is collectively known as resources. There are many different types of resources used by the game – monster definitions, item definitions, magical effects, terrain types, predrawn submaps, sets of numeric parameters for generating larger random maps, descriptions of rooms and dungeon features and even the individual topics of the game’s online help. All of these things are resources, and are represented by classes derived from the main Resource class. Resource classes are always prefaced by a T; for example TMonster or TEffect. While a Monster class would hold the statistics and state information of a specific kobold currently located at map grid (37,72), the data of the TMonster class tells the game that all kobolds as a monster type have 1d4 hit points and claw for 1d6 points of slashing damage.
The game’s resources are loaded from .MOD (module) files created by the resource compiler (described below). A single game of Incursion can involve one or more modules being active and loaded at once. Every resource in an Incursion game has a unique 32-bit resource ID associated with it. Resource IDs are not the same as object handles discussed above; while object handles remain consistent for the duration of a single game of Incursion, resource IDs remain constant across all games of Incursion played with the same set of modules. The upper eight bits of a resource ID describe which of the 256 module slots Incursion supports holds the module it came from. The lower 24 bits describe which resource within that module is being referred to. The primary advantage of this resource system is the degree of extensibility and memory management it allows. A third-party author who wants to extend the game can simply create a new module to do so, without having to modify either the C++ source code for the game itself, or the IncursionScript source code for any previous modules.
Consider the example case of a module that contains a single new quest for the player to undertake, given to him by an NPC in the main town. The new module can add its NPC to the map of the town tavern, which is described in a different module, along with an entrance to a new dungeon being added to the wilderness map. (The game presently has neither a town nor a wilderness – just one big dungeon – but accept this for the sake of an example.) The new module is able to refer to resources in previous modules, either directly by resource ID or by looking them up by name. In this way, the resource system has a functionality similar to a linker that is used to turn compiler output files into a true executable: it matches external references in modules with other modules’ resources. However, in Incursion this is done at run-time rather then build-time, allowing the player to load an arbitrary set of modules to run the game with, provided that all of those modules’ “prerequisite modules” are met.
One of the strongest advantages of Incursion’s resource system is that resource descriptions can be of variable length by adding annotations to the resources. For example, a powerful demon lord might have 30 innate spell-like abilities, but most monsters have none. Rather then allocating an array of 30 spells within every TMonster object to describe the spell-like abilities it has, they can simply be added to the monster description as an effectively arbitrary number of annotations. This also allows such features as adding equipment lists to humanoid monsters and redefining an arbitrary number of dungeon generation constants in a dungeon description. Far more significantly, however, it provides the framework for allowing resources to override events, as described below.
The IncursionScript Compiler
Module files themselves are generated by Incursion’s built-in resource compiler, which takes human-readable resource files (.IRC) written in the custom IncursionScript language and compiles them into binary data files, or modules (.MOD). The IncursionScript language includes grammar for describing all of the various types of resources that Incursion uses. An example of an IncursionScript definition of a monster – the flesh golem – can be seen in the sidebar two pages below.
In addition to simply being a data entry language, however, IncursionScript also contains a variant of Small C that can be used to write scripts defining custom behavior for a given resource or module. This script language incorporates most of the functionality of C, with the exceptions of pointers and arrays. It is not a true object oriented language in the sense that new classes can be defined – writing anything comparable to a C++ compiler would be a task equal in scope to, if not exceeding, that of writing a roguelike game – but it does include a rather clever hack that allows IncursionScript to access the member functions and variables of objects of classes already defined in the core C++ source code of Incursion. This is more than sufficient for the task which it was intended, and the syntax that results is surprisingly elegant and clear.
The game includes a 32-bit device-independent virtual machine that executes the bytecode produced by the compiler whenever necessary. This ensures that while the core executable will have to be altered when porting Incursion to different platforms, the actual modules themselves are fully platform independent, at least in theory. (In practice, there may be a few function calls that perform differently on different platforms, so a given module cannot be guaranteed to work perfectly on every possible platform.)
Writing a compiler (or more accurately, a bytecode-based interpreter) is a daunting task, but fortunately many tools exist to simplify the process. Rather then relying on the traditional combination of LEX and YACC, a freeware compiler generator named ACCENT was used. ACCENT is similar to YACC, but generates an Earley parser rather then a LL or LR parser. What this means is that it handles grammar ambiguity in a superior manner and avoids the frustration of YACC’s shift/reduce conflicts. Further, YACC supports only straight BNF grammar description, while ACCENT extends the BNF notation in a number of ways that make for much simpler compiler design. The only downside is that a compiler produced by ACCENT is slightly slower than one produced by YACC, but not (in this case) by a very noticeable degree. The lexical scanner is still generated with FLEX, a GNU implementation of the industry-standard LEX.
The other major timesaver I managed while writing IncursionScript was to include an existing C preprocessor whole-cloth! All that was necessary was to find the source code for a public domain preprocessor – I used the Decus CPP preprocessor – and modify it ever so slightly to accept the few lexical elements of IncursionScript that differ from ANSI C, such as multi-line strings, without complaint. This proved to be an immense benefit to the project for very little work time – not only does the IncursionScript language now benefit from #define macros and the ability to split up a module’s source code over several files through the #include directive, since the preprocessor syntax is identical it can share some header files with the core C++ source code, such as those that define long lists of flags and constants using the #define directive. Maintaining a single header file for bit-flags and constants usable by both the C++ and IncursionScript sources means a great deal less book-keeping and avoidance of many minor bugs, as these constant lists change quite frequently in development.
Most commonly associated with graphical operating systems (such as any version of Windows or Mac OS), event-driven architecture is a programming philosophy in much the same vein (and equally vague) as object-oriented design. Essentially, its central idea is that signals of events (which can be anything that can happen in relation to the program – in a graphical interface, for example, a mouse click or the closing of a window) are send out to a wide variety of places in an established order of priority, until one of these destinations responds that it has handled the event. If traditional programming can be described as a philosophy of process and procedure, step-by-step instructions on how to accomplish a task, and object oriented programming is a philosophy of nouns, describing the properties of various classes of things and how they interact with each other, then event-driven programming is a philosophy of verbs: when something happens within a program’s domain, events are thrown to determine how the program will handle that occurrence.
Incursion is (to my knowledge) the first roguelike game developed from the ground up to use an event-based structure. This is largely because the most popular roguelike games are increasing chains of variants and improvements built upon codebases that date back to the primeval days of Unix mainframes – Angband and NetHack fall into this category, though ADOM does not. (I have no idea if ADOM is event-driven, as its source code has never been released.) Since making them truly event-driven would involve a full rewrite of years worth of tested, stable code, it’s hardly in the programmers’ interests to explore this route fully. Conversely, one of the strongest advantages that Incursion has is that it is not an enhancement of any older game, or a structure built on any existing codebase. While this entailed a degree of “reinventing the wheel,” the upside was that more modern programming techniques were employed from the very base of the structure on up. (This is not in any way intended to condescend to the creators of earlier Roguelikes. Many of the top-level design principles I employed creating Incursion result from studying the source code for both NetHack and Angband and striving to discern how those tasks could be accomplished more elegantly. In other words, I only knew what not to do, or how things could be done better, through drawing on the previous experience of other developers.)
Events in Incursion are composed of an integer value describing exactly what event is happening, up to four pointers to objects (the EActor, or creature performing the event, the EVictim/ETarget, which is the object or creature affected by the event, the EItem and EItem2, being objects used in the event, and the EMap, being the game map upon which the event occurs), along with a truly huge number of flags and numeric values describing the exact parameters of the event: the number of hit points of damage inflicted, the resource ID of a spell just cast, flags stating whether an attack was an attack of opportunity or a critical hit, and so forth. All of these values are stored in a single EventInfo structure, which is passed by reference to the event-handler routines of all the involved objects in a defined order until one of these routines returns DONE (1) instead of NOTHING (0), stating that it has completely addressed the event and handled all of the activities it needs to cause. (The event architecture of Incursion is very loosely inspired by the similar architecture of Windows NT, but the similarity is generic enough to be meaningless.)
Events in Incursion are recursive. The game has an event stack composed of EventInfo objects, moving up the stack as new events are thrown. In this manner one event’s handler can throw a new event, and execution will return to the original once the new event has been handled. This is an extremely useful feature because it allows a single large event with many possible facets, such as a melee attack, to be broken up into a number of different sub-components and handled separately. Nested events can either be thrown “fresh,” with a whole new set of values in their EventInfo struct, or “re-thrown” using the same EventInfo struct as the parent event, both in terms of values in and in terms of being able to modify the parent event’s EventInfo values. Incursion also throws two special events for every normal event thrown – a PRE_ event and a POST_ event. These are exactly what they sound like: an extra event that occurs early, allowing default behavior to be over-ridden by objects lower in the priority chain, and an event that allows aftereffects to be added to its base event after the full normal processing has already been done.
Consider the example case of a melee attack by a paladin character with a broadsword against a kobold. The first event thrown will be EV_WATTACK, the weapon attack event. It will, in order, be thrown to the map the paladin and kobold are currently located on (class Map), the broadsword (class Weapon), the kobold (class Monster) and finally the paladin (class Player) object. EV_WATTACK handles only the most general elements of a melee attack, loading the EventInfo struct with combat values (the damage dice of the weapon, the base attack bonus of the attacker, the defense class of the victim, and so forth). It then throws a second event, EV_STRIKE, to resolve the actual attack. (EV_WATTACK can actually throw more than one EV_STRIKE, in the case of multiple attacks due to Cleave, Whirlwind Attack, two-weapon fighting, or whatever.) EV_STRIKE then adds many situational modifiers (flanking, invisibility, surprise, favored enemy bonuses, and many, many others) and resolves if the attack is a hit, a miss, a critical hit or something else entirely. If the attack hits, the EV_STRIKE event handler then throws an EV_HIT event, which in turn determines all of the effects of a successful attack – base weapon damage, the effects of special weapon properties like vorpal or flaming burst, sneak attack damage and so forth. In applying different types of damage (such as a flaming sword, which generates base damage of the slashing type, and bonus damage of the fire type), EV_HIT spawns one or more EV_DAMAGE events, which is the generic event thrown whenever a creature or object is damaged. EV_DAMAGE resolves the damage, handles (Incursion’s damage-absorbing) armor and possibly throws an EV_DEATH event if appropriate. By using a whole sequence of nested events to resolve a melee attack, Incursion gives the option of interrupting that sequence at any time in order to handle a given special case.
Events are not only thrown to event handlers that are methods of the core C++ classes of the game (Monster, Player, Item, Map, etc). They are also first thrown to the resources associated with any given instance of those classes. This means that every resource has a chance to override an event when one of the objects in the event is associated with that resource, or when the resource’s ID is in one of a few special fields within the EventInfo struct. For example, a lightning bolt will usually do damage to a monster. If the monster resource has the “immunity to lightning” flag set, however, the lightning bolt will do nothing. All of this is handled in the code for the Creature class, which is the parent class of Monster and Player. However, one specific monster, the flesh golem, is neither damaged by nor immune to lightning; when struck by a lightning bolt, this monster will instead be slowed down and made lethargic. This special case is not handled in the C++ source code of Incursion itself, but in the EV_DAMAGE event script attached to the flesh golem. The flesh golem’s script will check if the EventInfo::DType value is equal to AD_ELEC, indicating a lightning attack; if it is, the golem is slowed for 2d6 rounds, and the script returns DONE, signaling that the event has been handled and the game does not need to do anything else about it. Otherwise, the script returns NOTHING, signaling that the event should be handled normally. (The actual flesh golem script covers more special cases than just lightning; it’s shown on the next page.)
(Above) The complete text of the $“flesh golem” resource from the Mon1.IRC incursion script file, including the event handler that describes the special way that a flesh golem interacts with direct magical attacks. (Below) The event handler, written in IncursionScript, is compiled by the resource compiler into a bytecode that a virtual machine within the game can then execute when the proper event is thrown. The game can also be convinced to display the disassembled byte code on screen using a debug option, as shown below.
The downside of this design structure is that the mechanics of processing all these events leads to a significant amount of overhead and wasted processor time – for example, PRE_ and POST_ events are always thrown, regardless of whether there is any code hanging on them in this specific case. However, the overhead of basic game control flow tends to be trivial for text-based games running on modern computers, so this is not a significant problem. Further, application of a source profiler shows that event dispatch and the handling of “empty” events takes a very trivial amount of time in comparison to the more intensive work done by the monster AI and the vision calculations. So what exactly does all this complexity gain for the engine that isn’t found in conventional Roguelikes?
Roguelikes are games of special cases, where the unusual properties of monsters, weapons, spells and character classes compromise a body of code that far outweighs the complexity of the “general case” scenario. It is these many special cases and unique rulings that give these games their depth of gameplay that make them compare in any way favorably to commercial, graphical CRPGs. The event architecture allows every special case to be implemented systematically, with the code that governs it exactly where one would expect it to be (in the description of the item the case is tied to) rather than scattered throughout four different files.
The greatest strength of Incursion’s event architecture, however, relates to how it works with the resource system. Any resource involved in an event can modify the way that event operates, before it is handled normally by the hardcoded C++ event handlers. This modification could be as simple as changing one or two of the values in the EventInfo structure, then passing the event on to its usual handler to be processed otherwise normally. This makes resources vastly more powerful and flexible than they would otherwise be. Normally, a game would handle a monster as a struct filled with static data – base attack bonus, hit points, attack forms and so forth. Incursion does this, but it can also link bytecode event handlers to resources, allowing them to modify the behavior of the game in an essentially arbitrary way without needing to modify the actual C++ source code at all. This is obviously a great boon to code organization and game extensibility, especially when we consider that it applies not only to monsters, but to items, spells, classes, races, predefined maps and regions, randomly generated dungeons and anything else the game treats as a resource.
The combinatorial explosion effectively produces spaghetti code if one tries to implement truly flexible quests in a conventional roguelike. Omega goes the farthest of any roguelike game in this direction, and examining its source shows just how convoluted these quests and their inter-related possibilities have made it. Incursion, however, can handle quests with a level of complexity similar to Omega’s, but without having to alter the core source code at all. This means that far more quests can be implemented because individual quests don’t make the game more convoluted; it also means that different designers can independently write quests for Incursion without having to coordinate their source base. Individual designers can create their own .MOD files to expand the game, with no need to change what is in the others, and all the .MODs can run concurrently in the same finished game.
The Dungeon Generation Algorithm
Incursion’s method of dungeon generation is much more a work of craft than true innovation. Superficially, it uses the same method to generate a dungeon as Angband and its many variant games do: divide the map area up into a grid of squares, place a single dungeon room inside of each grid square by choosing two random points and making them the corners of a rectangle and then connecting these rooms by carving out corridors in random directions until every room has been touched by a corridor. This method works very well for generating a rather plain dungeon, but there are several enhancements to it implemented in Incursion to give the dungeon a greater personality and aesthetic interest.
First of all, Incursion can draw a wide variety of room types instead of just a simple rectangle. Different room types include octagons, cross-shaped rooms, rooms filled with columns, circular rooms, rooms composed of overlapping squares and circles, and so forth. Three special room types are worthy of note: the dungeon generator can place predefined maps of rooms into the larger randomly-generated map, either as “vaults” that hold more powerful monsters and better treasure, or simply as an added aesthetic element to supply special rooms that have a clear sense of purpose and human design. The second notable room type is the life cave, generated by using the “game of life” algorithm to “grow” a blob shape on the map over the course of multiple iterations. This produces a room with smooth, irregularly curved walls that resembles a natural cave. The final special room type is the rough cave, which is produced by taking a grid square filled with stone and hollowing out hundreds of L-shapes in random directions and orientations. This produces a rough-looking chamber with lots of irregular spaces in the walls and solid blocks scattered around the edges, growing more open toward the center of the room. Both of these latter two algorithms were first described on the roguelike development web page (www.roguelike-development.org) but the implementation is entirely my own.
The life cave algorithm produced some very nice looking caves, but it also added an additional complication: it could generate two (or more) unconnected areas in the same map grid, thus foiling the typical (and imperfect even without life caves) method of connecting rooms by “digging” random tunnels. The improved tunneling algorithm I used in Incursion uses a flood-fill routine as the basis for connecting rooms. First, a number of random tunnels are drawn, as before, to ensure that at least a large majority of the dungeon is connected. Then, a random open area is chosen and all open areas that can be reached from it are marked as connected by the same flood-fill algorithm that paint programs use. Then the game scans the map for open areas that are not marked as connected and, if any are found, draws a tunnel from a random open area marked as connected to a random open area not marked as connected. Then the newly connected area is flood-filled as well. This process is repeated until the entire map area has been flood-filled, and thus it is possible to reach any point on the map from any other without needing to teleport or meld into stone.
The dungeon generator also benefits from the fact that the data structure used for each map cell is more complex than that commonly used in older roguelike games. Each map square has a terrain type associated with it as well as a region code. Terrain types include walls, open floor, pillars, gaping chasms (that lead down to lower levels) and so forth, while region types describe the purpose of a room – a mage’s laboratory, kobold warren or hall of knights. Because of Incursion’s script engine and resource system, it’s very easy and elegant for a region type to change the behavior of the game for creatures presently in that area – an ice cave might have a slippery floor that renders characters prone on 1 in 10 random moves, while an alchemical laboratory might grant a circumstance bonus to Alchemy skill checks. Perhaps more significantly, however, even giving each square room a simple name (always visible on the game’s status line) aides the player in seeing a kobold lair or ancient royal hall instead of yet another boring square made of little ASCII dots. Since roguelike games run a significant risk of becoming frustrating due to repetition, any improvements to the dungeon generator that make the dungeon less pedestrian and more interesting to explore are always a positive thing.
The Monster AI
Incursion has an extremely advanced monster AI, in comparison to similar games in its genre. The basic process of deciding on an action for each monster every turn is performed by composing a list of all possible actions the monster could take and assigning each a priority, then choosing a random action from the list in the highest priority category and trying to perform that action. If the circumstances are not right for that act, it fails and the monster moves on to a randomly chosen action of the next highest priority.
Monster movement is determined by a “sum of gravities” algorithm. Every thing that the monster is attracted to within its line of sight – an enemy it wants to attack, a magical item it wants to pick up, a portal it wants to jump into – asserts what is essentially a gravitational pull on the monster. Each target has a priority, which determines the base strength of the pull; the attraction gets stronger the closer the monster is to the target in question, meaning that it will “go for” nearby enemies in favor of far-distant ones of higher priority. If none of the monster’s targets are within its line of sight, it remembers the last known location of each target and will attempt to go to that location.
If it is stymied even in this – it can’t reach the last known location, or it reaches the location and still can’t see the target, having no idea where it might be now – or if it just has no targets to begin with, then it will create its own. The monster will choose a random point on the map and attempt to walk toward that point. When it gets stuck and can go no further, it will consider that point resolved and choose another one. Further, when no actual real enemies are in sight, a monster will never step away from a wall. These factors together essentially allow the monsters to explore the dungeon on their own – by “following the right wall” and striving to reach random points on the map, they can navigate the dungeon on their own accord.
When they are severely injured, or become scared as a result of a magical fear effect, monsters will turn and flee from their attackers. This is accomplished by turning the gravities of enemies into negative values, making them repel the monster instead of attracting it. When monsters are troubled by injury or maladies such as disease or blindness, they can diagnose this and will correct it if they have the means available to do so. For example, a monster struck by a poisoned sword will then drink a Potion of Neutralize Poison if it has one in its possession. Monsters can also fix maladies among their allies – an orc shaman might cast cure critical wounds on its fellows in battle, for instance.
Monsters not only desire items, they are capable of using them with reasonable intelligence. Whenever a monster picks up a new item, it goes over its inventory and optimizes it, calculating which weapons and armor give it the best bonuses in combat. It then equips those items. Similarly, monster spell-casters will cast several “buff” spells to make themselves more powerful before entering combat, provided that they have time to do so. Spells are grouped into a number of different “purposes” to allow monsters to use them intelligently. For example, when attempting to flee from the player, a monster might cast slow on the player character or dimension door on itself – both of these spells have the “foil pursuit” purpose set. Monsters are also able to choose when to use any metamagic feats they have (such as Quicken Spell or Maximize Spell) intelligently, based on their degree of injury, their Challenge Rating in contrast with the enemy’s, and the amount of mana (magical energy) they have remaining. In the future, the AI will be expanded to counter specific actions – if the player casts invisibility, a monster will cast see invisible; if the player shoots the monster with an arrow, the monster will cast protection from arrows next turn. This functionality is not yet implemented, but the framework for it has already been laid.
The monster AI has been one of the most problematic areas of Incursion to develop. It still needs a great deal of fine tuning, as monsters occasionally do erratic or illogical things. Worse, though, is that it presently operates far too inefficiently, causing Incursion to suffer slowdowns even on a very fast computer. One of the primary focuses of future versions of Incursion will be to optimize the AI and improve the amount of time that it takes to decide on monsters’ actions by eliminating superfluous options.
The Spell Engine
Some spells have effects that are purely unique, such as bestow curse, animate dead or chromatic orb. These are defined by IncursionScript code contained in the spell resource in their entirety. However, many spells share elements in common with each other – fireball, fire storm, and burning hands all inflict fire damage that scales with the caster’s level, for example. These spells and many others benefit from the design of Incursion’s spell engine, which allows complex spells to be built from simple, abstract blocks of existing code. Much like powers in the tabletop RPG Champions, Incursion’s spells are represented by a spell archetype and various parameters attached to that archetype. The fireball spell, for example, is an EA_BLAST effect that has an AR_BALL area of effect, inflicts (LEVEL_MAX10)d6 damage of type AD_FIRE, and allows a REF saving throw for half damage.
The spell engine interprets this collection of constants and produces a fireball. The variety of spells that can be created from the basic spell archetypes currently defined by Incursion is very diverse already, but it is made even more so by the fact that one particular parameter or element can be overridden by IncursionScript code while all the rest are left preformed. For example, by adding an EV_ISTARGET event handler, one could define a “holy fire blast” spell that was exactly like fireball except that it only injures demons, devils and undead, leaving all other targets unhurt. Furthermore, a spell can be defined to include two or more separate spell archetypes linked together. Holy smite is a good example of this – it has an AR_GLOBE area, and all MA_EVIL targets within the area suffer (LEVEL_1PER2)d8 points of AD_HOLY damage from EA_BLAST, but are also given the BLIND status condition by EA_INFLICT if they fail a FORT saving throw.
To appreciate the full complexity of spells that can be designed using Incursion’s spell engine, browsing the source files “WSPELLS.IRC” and “PSPELLS.IRC” (which contain the wizard and priest spells, respectively) is recommended. The full definitions of fireball and holy smite in IncursionScript are shown below.
The Devil in the Details
Roguelike games are more detail-oriented than games of nearly any other genre. It is the complexity of gameplay that keeps them interesting in lieu of streaming movies, voice actors and real-time 3D graphics. As a result, a vast amount of the work of coding one goes into nuances rather than central features. Like a Chinese puzzle box, a great deal of the appeal of roguelike games is figuring out how the various elements can be made to interact and simulate a world in superficially logical ways. To a limited extent, roguelikes share this element with the text adventure games made by companies like Infocom, but the emphasis is much more on strategy and character building than true “puzzle solving.”
Grammar. It’s traditional for roguelike games to narrate to the player in true English rather than simply broken video-game speak. This is important because in a graphical game the player can see what is happening – a kobold looks like a kobold, and a critical hit will be signified by an extra-gory spray of blood – whereas in a text-based game the player’s attention is focused much more directly on the game messages, and thus if the messages are shoddy, immersion is damaged much more directly. Thus, rather than say “Player hits kobold for 7 damage” Incursion will say something like “You swing low, hitting the kobold.” This seems deceptively simple, but Incursion has a wide variety of messages and needs to account for the fact that pronouns can refer to a him, a her or an it arbitrarily, be able to pluralize arbitrary nouns correctly and display messages based on what is happening only if the player character can see it.
Incursion resolves these issues by using a special string-formatting library built into the game. Similar in structure to the classic C printf field, these routines replace fields in a string with supplied parameters, or with objects stored in the current EventInfo struct. For example, consider the following message about dropping objects, from the ‘Drop’ option of the priest’s command spell:
“The <EVictim> drops <his:EVictim> <hObj>.”
The EVictim field will be replaced with the name of the object referred to by the EventInfo struct’s event victim field, while the his:EVictim field will be set properly to either “his,” “her” or “its,” depending on exactly what sort of being the player just cast command on. Furthermore, if the EVictim has a proper name, the message formatting routines will automatically remove the unnecessary “The ” before the name field, and if the string literal name of the object handle passed is “loaf of cottonberry bread” and the object’s Quantity is set to 6, the game will correctly parse the final message as “Brandobis drops her 6 loaves of cottonberry bread.” If the player can’t see Brandobis when the spell is cast (say, by a spellcasting monster) then no message will be printed at all. The intelligence of the message formatter is a real asset to designing custom spells, because it means that unique messages can be given to every spell effect without the creator of the spell having to worry about (most of) the low-level nuances of English grammar.
Object Identification. It’s traditional in roguelike games that you don’t automatically know what found magical items do, yet you can use them anyway, and if the use logically reveals function, then you have identified the item. Further, certain classes of items all appear the same, as signified by a flavor descriptor attached to them. For example, the player might find a metallic blue potion in the dungeon, drink it and find that it heals his wounds. The game then recalls that the player knows all blue potions are Potions of Healing, and identifies them automatically in the future. Furthermore, items can be identified by spells such as identify, and sometimes by watching a monster use the item. If a monster drinks a Potion of Diminution, the effects will be obvious, whereas if the monster drinks a Potion of Giant Strengths the effects are not obvious, and the potion will thus not be identified.
This all sounds extremely straightforward and logical, and from a player’s perspective it hopefully is. However, from a design perspective, the identification of items adds a significant amount of complexity to the game. For example, if the player dons an unidentified Girdle of Giant Strength, not only will his Strength score increase, but so will his attack bonus, weapon damage and several other factors. Since neither the player nor his character is supposed to know about these changes, however, they are not shown on the character sheet, but are used internally by the game none the less. Two sets of attributes are maintained for the player – the “known” attributes that only account for identified magical equipment, and the “actual” attributes that take all magic into account. A clever player might thus note that he has an unidentified beneficial magic item based on the fact that he hit when the numbers say he “should” have missed.
Light and Vision. Another feature typical of the roguelike genre is the accurate simulation of a field of vision for the player. The player has no facing, and thus effectively has a 360º field of view, but otherwise Incursion accurately simulates line of sight for both players and monsters. The player’s torch illuminates squares within a given range; beyond that the player can make out only shadowy forms. The game incorporates a number of different vision-influencing spells and effects – wall of fog, globe of darkness, call light and so forth. Most spells require a line of sight to be cast, and archers suffer a miss chance when shooting at targets they can’t see. Light and vision can thus become very important tactical elements in the game.
In addition, there are a number of perceptual abilities the game models other than normal vision. Infravision, tremorsense, blindsight, telepathic awareness and detection spells such as detect evil all allow creatures to perceive each other and the world around them, and are assigned specific traits and limits by the game. For example, tremorsense relies on vibration and thus cannot detect flying or levitating creatures, while telepathic awareness does not register mindless creatures such as golems and oozes.
Given all of the possible problems that could arise with a program as complex as Incursion, the implementation state actually went remarkably smoothly.
Incursion was compiled using Microsoft Visual Studio version 6.0. The compiled source produces a 2 MB Win32 executable file. A typical instance of Incursion running in Windows 2000 with 10 dungeon levels generated in memory uses just under 9 megabytes of memory, as measured by Windows’ Task Manager. Incursion consists of 36 CPP source files and 16 .H header files, not counting the files for the Decus CPP preprocessor or the ACCENT runtime module. Overall, the program consists of just over two megabytes of C++ source code, along with approximately 750 K of IncursionScript resource definition code.
The current version of Incursion is 0.4.0. Incursion has technically been in development for four years now, from 1999 to 2003. In practice, the actual development time would be closer to nine months of focused attention at various spans over that time period. This includes the time for at least one major redesign and rewrite – Incursion was not originally conceived as a d20 roguelike, as the d20 license was not yet released when I began it. All of the technical aspects of the internal architecture were considered from the very beginning, however.
Problems in Implementation
No project has an entirely smooth implementation, and Incursion has had more than its share of difficulties.
Difficult Bugs. Among the most difficult bugs to track and locate were the “off by one” bugs in the implementation of control flow statements in the IncursionScript compiler. For example, the break statement would skip over one opcode too many when terminating a switch statement. This usually did not cause the script to crash, but instead produced behavior that was very difficult to trace, and necessitated the creation of the “dump script bytecode” debugging option. A similar bug caused for statements to always execute once, even if their expression was initially false. While obvious in retrospect, these bugs took two weeks of solid work to track down because they were so very subtle in their effects.
Another kind of recurring bug involved the use of 16-bit integers for the length variable in IncursionScript’s String class, which provides functionality for manipulating variable-length strings. The String class was initially also used to hold the entire text segment of a module, which worked just fine until I had typed enough online help and monster descriptions for the total text size to exceed 64K, at which point it obviously began causing memory corruption. This is admittedly an amateurish mistake, but an understandable one (text string are rarely over 64K in length, and the design of C++ encourages a programmer not to think about the “internals” of his base classes once they have been proven to be stable.
Incursion still has some internal glitches that cause data corruption that is very hard to track. I suspect that a more extensive internal debugging framework will have to be implemented in order to locate these, because the tools to figure out where things are becoming unstable just aren’t available to me at present. This will be one of the major objectives for future work on Incursion.
Speed Issues. Much of Incursion was written based on the assumption, commonly made by roguelike programmers, that speed of basic game processing is largely an irrelevance when designing a text-based game to run on modern computers – the processing power is sufficient to “absorb” any moderate code inefficiency, and good programming practice thus suggests that one place clarity and elegance above optimization. This proved to be a fallacious assumption.
Incursion sometimes experiences slowdowns even on my extremely fast 1.8 GHz development machine, and it is intended to run well even on older computers as slow as 200 MHz. Theoretically, Incursion should be able to run smoothly on any common computer; there are no conflicts between the target machines and the actual amount of processing that must be done, as with the frame rate for a graphical game. Rather, the problem lies in the use of inefficient algorithms. Using a source profiler, the problem has been tracked down to three bottleneck areas: the execution of the highest level of the main game loop, the monster AI and the vision calculation system. All three of these areas are scheduled to receive major optimizations and rewrites before the next release of Incursion.
Version 0.4.0 represents a major milestone in Incursion’s lifespan – it is a functional, playable and semi-stable version with all of the core engine features implemented. While certainly not up to the standards of a full professional release version, it is nonetheless very complete and functional. However, there are several elements of the implementation which in hindsight I feel to be very suboptimal. These are:
· The internal format of the virtual machine that executes the bytecode of compiled scripts would be much cleaner and faster to execute, and the resulting faux-assembly code much easier to understand if each opcode could use three parameters instead of two, taking up 48 bits instead of 32.
· The event dispatch system is beginning to look like spaghetti code; as it was one of the first things written, it does not always reflect the current design of the program, and can be very difficult to follow in places.
· The data structures governing a player character’s race and class abilities – both in resources and in an individual character – failed to adequately account for the different kinds of information that need to be stored about such abilities. Currently, this is addressed by using a series of individual kludges for the abilities in question (turning undead, wizard school specialization, etc.), but it could be implemented much more elegantly.
· The current memory management scheme is very poor, keeping every level of the dungeon in memory at once. In the current, short game there is no problem with this, but for a larger world it would prove disastrous. The object registry was written to allow elegant memory management and the use of temporary files to store world elements; the game should now be adjusted to take full advantage of that functionality.
· Currently, feats are all hardcoded into the program rather then being treated as resources. While this has advantages in terms of simplicity, it is clearly desirable in the long run that certain “feat archetypes” be defined to allow IncursionScript writers to define new feats without having to alter the core C++ source code, just as is currently done for spells and magical effects. This is a major design objective for the next version.
· The vision and line-of-sight algorithms are currently very slow, both due to lack of optimization and overall design. This (vision algorithm efficiency) is a field that has received much thought among roguelike developers, with a number of very fast algorithms being known, one of the most popular being shadow-casting. I was not aware of these newer algorithms when the vision system was written, very near the beginning of Incursion’s development.
· The ability to debug IncursionScript code is presently very limited. As I move into the design of more complex quests and longer scripts, it will become very important to have a greater ability to monitor script execution and a better suite of IncursionScript debugging tools.
· Following standard programming practice, the complex algorithms are coded initially for coherence and ease of debugging. Now that they have been proven to be stable, but also overly slow, it is time to rewrite several sections of the code (monster AI, central game loop, event dispatch, resource ID lookup, etc.) for speed optimization.
Now that a fully functioning “proof of concept” version of Incursion exists and runs, it is clearly time to go back and rewrite much of the code for elegance, efficacy and overall clarity. This may involve a rewrite of as much as 15% to 20% of Incursion’s existing codebase, and forms the next major task in the game’s development. It was necessary to write the game as it is now in order for these shortcomings to be realized and understood; very little that is listed here (except the vision system) could have been foreseen and avoided. Rather, it was necessary to write somewhat archaic code once in order to understand how and why some of the given tasks could be accomplished more elegantly. This cycle of “write-scrutinize-rewrite” tends to be a natural part of my programming style.
Another thing that needs to be revised is the balance of the game. The d20 system is written assuming that a party of adventurers will explore a dungeon together, while Incursion depends on a single player working alone, or with weaker allies and followers. It is only through playtesting that the ideal balance of numbers and challenges will be achieved in the game, and finding that balance will be a major objective of the next phase of development.
After this rewrite, the goal is to begin realizing the world of Incursion beyond a single dungeon. A large-scale wilderness screen will be added, along with towns, cities, ruins, temples and multiple dungeons. Quests will be scattered across the world, and development of the epic plotline concerning the Forsaken will begin.
The goal of any game designer should be to create something better than what has come before, and I feel that in the area of roguelike games Incursion stands the potential to achieve this.
Most early-era roguelikes are vastly complicated, with countless features piled upon a simple skeleton. Certainly, this is not to insult the truly professional level of maintenance that development teams have put into keeping these games vital in the modern era, but there is only so much that can be done with a codebase grounded in the programming methodologies of the early eighties. NetHack and Angband are always evolving, and always spawning new variants, but many possible features (such as truly detailed, interactive quests) are not easy to implement within either of these games’ basic structures, and the lack of an event-based architecture means that it takes much more effort to implement new features than it rightly should. Despite the vast amount of work put into “reinventing the wheel,” I cannot help but feel the decision to implement Incursion as a truly independent game, rather than a NetHack or Angband variant, was a wise one.
The greatest strength of Incursion, I feel, is the robustness of its engine and the flexibility of its resource and scripting system. It is not nearly as mature in its development stage as the giants of the genre, but internally its design is far superior, and I feel that in the future it, or other roguelike games with a design philosophy similar to it, will surely come to dominate this genre.