Programming Exercise: Dice

A short exercise for the reader: come up with a domain specific language for rolling dice. This is a recurring mechanic in Rogue-likes.

Exercise 1. The conventional notation in Dungeons and Dragons is to write "mdn + k" (where "+ k" is optional) to roll m separate n-sided dice, sum them together, then add k to the result and return it. Write a function to accept a string of this form.

What happens when m is not a positive integer? When n is not a positive integer?

Exercise 2. In Dungeons and Dragons, when creating a character, you roll 4d6 but take the highest 3 values. How would you extend the domain language to include this situation?

The source for these exercises are the original Rogue-likes had a function which rolled dice based on a domain specific language, and this idea was picked up by Troll.

One scheme to world-building

What makes this game fun? That's the question I want to ask when I've finished a game (or as I'm playing it). I recently re-played Fallout 2, and I noticed there's a lot of small quests which piece together to form a tapestry. Individually, the elements are not complex (deliver this item to so-and-so, talk to [person] about [subject]), but they compose together like lego blocks.

This post will discuss one way to world-building, which is necessary to coming up with quests and a game-plot. This is more a "review article" than anything innovative on my part.

Levine's "Stars" and "Passions"

Ken Levine has a great talk on "Narrative Legos". Basically, each location (village, fort, etc.) has around a half-dozen named characters ("Stars"), where each character has three "Passions". A "Passion" is what a character cares about relative to what the player can impact upon; it is transparent to the character, and responsive to the player's action. Effectively a "Passion" is a "bank account" for a Star (or a number between -10 and +10, starting at 0); helping a Star with their Passion results in that Star's invest positive points into their "account", thereby improve the Star's opinion of the player.

When a Star's opinion of the player (formed by combining the three Passion scores together somehow, e.g., adding them together, taking their geometric or harmonic mean, or whatever) reaches a certain high point, it unlocks certain bonuses. Blacksmiths offer additional bonus gear, Clerics offer additional services, etc. Conversely, if a Star's opinion diminishes, services cost more or are outrightly refused.

But two characters could have conflicting passions. This is a goal for writing a plot, because conflicting Passions for Stars means the player is thrust into a zero-sum game...which is fun for the player, and encourages the author to say, "Yes, and I can work this into another story arc!"

Example. Consider a simple fantasy setting. The player is tasked to fetch a McGuffin for the elf village. Elves hate Orcs (and Orcs hate Elves). A "Passion" shared by Elves is "Hurt Orcs".

Now, one of the Stars — Romeo the Elf — has a Passion: he loves Juliet the Orc. (Romeo the Elf's "Hurt Orcs" has the caveat "...except Juliet the Orc".)

For the quest (fetch McGuffin for the Elves), the player needs to take along a character from the elf village. Along the way, the player and companion are ambushed by Orcs, including Juliet the Orc. If the player takes Romeo the Elf, then Romeo will help kill the Orcs except for Juliet; the player is forced to choose what to do, kill Juliet the Orc, or run away somehow? And if the player takes along anyone else, then how does the player avoid killing Juliet the Orc?

Such is one way to have two different Passions interact with each other in a surprising way. It forces the game author to consider how to reconcile conflicting passions with "no wrong answer".

The number of characters should be around 5 or 6 to avoid over-burdening the player, and the number of passions should be 3 to avoid accidentally conflicting with too many other character passions (rendering the game unplayable accidentally).

There's a lot to digest here, and how we implement varies considerably. If we formalize a "passion" using a data structure (a few counters) and functions, we could [should] test the rewards and punishments are triggered properly upon shifting an NPC's opinion of the player. But this is just the observer pattern.

Exercise. Look at Fallout 1 and Fallout 2 (or any RPG you enjoy). For each town, write down who are the Stars and what are their Passions.

Begin with a Map and Needs

I've been playing a lot of post-apocalyptic games recently. I found it helps to begin with a map and asking myself, "How does society reproduce itself? Who produces what goods, and how are those exchanged among the cities producing them?" Looking at a real-world map, I can pick out a few cities that survived the apocalypse, think about trade routes, goods produced [at least food, water, armor, weapons, clothing], and this organizes and frames the thought-process about factions, their aims and beliefs.

These questions lead to more interesting power dynamics: multiple factions within a city disagree with how to distribute the goods, who to trade with, what to prioritize. How far are these factions willing to go to enact their policies?

Example. In one post-apocalyptic game, purified water is rare. Growing crops or raising livestock requires purified water. So for the survival of humans, purified water is absolutely critical (otherwise agriculture is impossible). But only one town has a prototype water purifier that can filter out radiation. As the only source of purified water, traders flock to the town to trade for the water. This makes the town a target for raiders, since traders regularly go to it. Fearing the raiders may damage the water purifier, the town has built sturdy fortifications around it...which has created an "inner city" within the fortifications, and an "outer city". One faction wants to keep outer city dwellers out as second-class citizens, another faction wants to keep the status quo. How far will the first faction go? Will they collaborate with raiders to drive out their rivals?

This "first draft" of an idea for quests sounds promising, but it has a problem: it's close to a "Jesus versus Hitler" morality choice. We need to make the status quo faction morally flawed somehow. There are many ways to do this — the status quo faction could support slavery, be violent imperialists refusing trade with cities that don't submit to their rule, etc.

Now that we have some idea of the factions and issues at hand in this town, we can apply Levine's "Stars" and "Passions" idea to further refine the idea. Each faction has a leader, but there's also the "head mechanic" in charge of maintaining the water purifier and its bottling, as well as the town doctor and the town trader. Thus we have our five stars for the town.

A town that produces nothing except coordinates trading (like the Hub in Fallout) has its own unique concerns. Just to rattle off a few:

• If a single partner (call it McGuffinsburg) is its sole source of McGuffins, then the internal politics of McGuffinsburg is a concern of the trading hub.
• Raiders are a perpetual problem.
• Power dynamics among competing traders; when there's little or no law, it gets quite cut-throat.
• Arms dealers in particular encourage secret agents to incite war between two neighboring powers, to profit from selling arms to both sides.
• Any of these could be reversed (McGuffinsburg exerting power over the trade hub, raiders as sympathetic figures, lawkeepers trying to maintain order, etc.)
• Any two or more of these could be combined.

One bit of advice: just as each Star has 3 Passions (for the sake of foregiving the player for acting unfavorably against one Passion without alienating the Star, thereby cutting off a potential quest-giver), we should take care to have several sources for each commodity. This is a rule-of-thumb, not a Law: sometimes, it's fun to have a single provider for a good, which causes tension and drives the plot ("We need to finish the [apparatus] to provide [goods] to save the world").

Remark (On Economy). At this point, it may be problematic determining the value of goods in the game. I'd advocate a Neo-Ricardian framework for determining the value of goods, if we are really concerned about a sensible economy. This works well for the settings I'm interested in, it works well. Each firm has its own methods-of-production and this determines the value of goods.

As far as the goods considered, we can consider every conceivable item in the game. This is hard. Instead we could start with some basic goods — grain and iron suffice for a first pass, we could successively add more as needed, like wood, weapons, coal, ammunition, etc. Traders add a markup to the value of the goods they transport in their caravan, which has been studied by Robert Vienneau.

Arguably, this doesn't need to be maintained. Prices could be determined as the sum of the cost of inputs, plus some markup, along the lines of Kaleckian economics...because if you aren't careful with your economy, your model may trigger hilarious/player-unfriendly results.

Note: although I have been thinking about a game in a post-apocalyptic setting, there's nothing preventing us from applying it to any setting. It's just a little harder if we have no map. (Post-apocalyptic settings let me be lazy, and use existing maps.)

Recap. So far, we have considered using the economy as a way to organize towns and factions. Each town produces some goods, and need to trade with each other to survive. This leads to identifying factions within towns, tensions between towns, and problems to be sorted out. It also leads naturally to using Levine's "Stars" and "Passions" to further refine the game. Both provide natural motivations for quests.

The map gives us a way to visually organize factions, consider how society sustains itself, the relationships between different towns and factions. Such considerations naturally give rise to Stars and their Passions. Altogether we have not formed a plot, but the fertile grounds for a plot as carried out through quests.

We have thus the basic process of world-building naturally give us ideas for quests and plot-lines. The "bottom up" approach with Levine's Stars and Passions combines well with the "top down" approach of drawing a map, determining the villages and towns, coming up with economies, inserting Stars and their Passions within each town, generating factions, and so on.

How real is the economy?

We need to decide how much detail the economy needs. This can serve a variety of purposes: just fluff, determine the actual value of goods, or as grounds for certain quests. Let's consider this last point in particular.

Missed Example 1. I was pleasantly surprised in Fallout 1 to learn the "gun runners" use historically accurate method of sulphur-less gunpowder production (using animal dung and urine). Although just lore and backstory, it could have served as a quest-line for players with high enough Science to suggest more modern methods of gunpowder production (leading to superior ammunition produced for the user, from gun runner traders alone).

This could also have led to the quest of finding sulphur sources (or other chemical sources). If using pre-war stockpiles, then there could be a limited amount of "superior ammunition" produced and provided to the player. If trading for chemical sources, then this could serve as grounds for multiple ways to obtain it: negotiate for trade, kill for obtaining it, etc. Perhaps there is some mistrust between the producer of the chemicals and the gun runners, the player needs to negotiate this (either by using a middle man caravan, thereby increasing the price of the superior ammunition, or by helping the factions bury the hatchet).

All told, I'm glad Fallout 1 didn't do this, because there's a time limit to the game, and this would have been a huge time sink.

As for modeling the value of commodities using economics, this has problems in the real world using textbook economics. As far as world building cares: value matters for trade routes, and for player bartering with merchants. For trade routes, we only need them to feel "about right" (e.g., goods expensive in one town is imported from a town where those goods are cheap, don't import goods when "domestically produced" versions are cheaper than the imported version, etc.).

Suggestion: Update the world map to reflect trade, specifically roads and ports are built (and improved) over time to better facilitate trade between partners. The quality of roads and ports reflect the trade power between partners.

For the player, accuracy can conflict with fun. When this happens, always side with fun (unless we want to create a constraint for quest lines, e.g., iron shortage causes more expensive equipment...motivating the player to, y'know, fix that shortage). The real concern is that the player has access to equipment matching the challenge. We don't want to give the player overpowered gear too early, nor do we want to force the player to have access only to mediocre equipment.

Economy for lore, well, this provides the grounds for quests. Town A wants to open trade with town B since B produces silk cloth. This isn't reflected in the goods sold in either town, but provides a new quest-line. Alternatively, if B were instead the sole source of iron, then town A could supply only, say, bronze equipment. This combines lore and player experience (which is good and desired: the player should experience consequences of their choices).

In short, put yourself in the world, and ask yourself, "What goods would I have access to? How would I get food? Water? Who produces them? How would I get them? What about luxury goods? Or equipment?" Answering these questions require us to consider the towns further, and increases the realism. It's not enough to have farms randomly placed around towns (Fallout 4 tried to do that): we must also consider the infrastructure, the shortages, needs, scarcities and abundances. This leads us to consider how towns interact, how factions within a town interact, and helps us build a world.

Generating History and Culture

History, Myth, State formation. If we consider how these Stars and villages interact, we can generate a history from conflict. Items of our Stars become revered artifacts. Music and art memorialize these events. Myths emerge from misunderstanding or deliberate lies. Rivalries build up, grudges between Stars and factions emerge over time. Villages band together, forming quasi-states, which dissolve under stress and strain.

Governments. It's worth noting that we could borrow liberally from history. For example, the Polish–Lithuanian Commonwealth had a unique form of government that is seldom discussed...it could easily generate problems to be remedied for plot-line. The ducy of Venice picked its leader through a lottery (well, a lottery picked an electorate, who then picked another electorate, and so on — the convoluted process of lotteries and indirect elections resulted in a new duke).

Religion. I don't have much to comment on here. Post-apocalyptic games tend to seldom discuss religion, and the fantasy games I play have similar pantheons. One thing worth considering, the original Rogue had "daemons" responsible for updating the health, etc., for players. I don't think anyone has made these daemons the Pantheon for the game, which could lead to interesting gameplay: praying to daemons leads to temporary buffs, destroying temples related to a daemon results in temporary negative buffs, etc. Or it could have the same effect as praying to the laws of physics (i.e., nothing noticeable).

Communication. And the most underappreciated point of consideration: it takes time to communicate these events. When an event occurs, news of it spreads through caravans and travelers. Spreading information takes time, and plans revolve around information. This is a challenge to code up, because we no longer have a simple observer pattern to update dialog and quest lines.

Testing the Game

I've come to the opinion, when writing software, you should test it...usually unit testing suffices. But a game is a special kind of software. So special, one naturally faces the question, "Should we still unit test a game?"

To be clear, there are varying degrees and different notions of "testing" a game. We could test the software (make it "bug free", or at least have fewer bugs), test the enjoyability of the game (e.g., make sure it's fun, winnable, etc.), test the UI behaves as desired, "integration tests", end-to-end testing (some sort of "autmated player" searching for specific bugs). I'll discuss a few of these notions.

Testing the Code

If we have adopted a model-view-controller architecture of some flavor, then we can unit test the models. I contend we should unit test the models, and use contracts to enforce the assumptions of the model methods. What would this look like?

We can encode assumptions like Actor::dies() should demand the actor's health is non-positive (i.e., either zero or negative). This could be encoded with an assertion ("precondition"). Then we could write a unit test to create an actor, give the actor some amount of health points, cause damage, then try to call actor.dies(). There are three test cases (when actor.health() is positive, zero, and negative) which should result in the death of the actor in two cases.

Organizing Unit Tests

For object oriented languages, I'm inclined to follow some kind of xUnit testing framework or JUnit: each class we write (say class Thinger) should have some corresponding test class (e.g., class ThingerTest) where each method of the class is tested several times...so Object Thinger::methodOne() should have several corresponding methods void ThingerTest::methodOneShouldDoXTest(), and so on.

For Lisp, there's usually a framework given (Clojure has clojure.test, Common Lisp has several frameworks, etc.). The organization is analogous as for object-oriented languages (functions in module.lisp like (defun thinger-method (...)) should have several test cases handled in module_tests.lisp).

Terminology: JUnit organizes test cases as methods using assertions on a Test class, which are organized into test suites (analogous to how files are organized into directories). A test runner then iterates through the test suites and executes each test case, recording results (both successes and failures) for later use. The exact terminology varies (some xUnit systems, e.g. in smalltalk, have test case classes), but the intuition remains the same: test cases organized into test suites, and a test runner that executes the test cases and records the results.

We organize code by modules, which contain classes, which contain methods. These terms are used loosely: C programmers lack any module system, but use structs instead of classes, and functions instead of methods; Haskell programmers use modules, data types, and functions; etc. Whatever the terminology, we have some kind of ersatz class and ersatz method. Each "class" should have a corresponding test suite, each method should have several tests. Depending on how we organize classes, we should have a corresponding organization of tests: if we have one file per class, we should have an analogous file per test suite. The motivation for this scheme is to make it obvious where to place tests for code (all the tests for /game/src/models/my_module.code is placed in /game/tests/models/my_module_tests.code for example). It's more important to be consistent in whatever scheme you choose.

What to Unit Test

Test only code you have written. There's no need to write tests for third-party libraries. We trust ncurses works as expected, the GNU Scientific Library functions, and so on. It's only the code we wrote that we want to test.

We should unit test all public functions. While aiming for 100% coverage is ideal, if we get to "a lot" (I dunno, say, ~90% or whatever), we can say it's "good enough". The rationale here is that public functions are used to build our game, so if we have tested them thoroughly enough, then we can have greater confidence in their correctness (they do what we think they should).

Test all code paths. Has each statement in the method been tested? Has each edge in the control-flow graph been tested? Has each branch of every if-else statement been tested? (Or every case in a switch statement been tested?) Has every boolean subexpression of each conditional been tested? Complicated conditional tests could be refactored into predicate functions, which can be independently tested.

Each function should do one thing, and unit tests make sure the function does what we expect/hope. For example, the Actor::dies() method does one thing; once it is called, we should have Actor::isAlive() return false. This gives us two cases to consider: one where Actor::dies() fails (e.g., when Actor::health() is positive), the other when Actor::dies() succeeds. The former case should have Actor::isAlive() return the same result as Actor::health() > 0, the latter should have Actor::isAlive() == false.

Tests should be atomic. Each test case will test exactly one thing. If a test case is testing more than one thing, we should refactor it into multiple test cases.

Tests should be independent of each other. They should not rely on each other (in the sense that they don't call each other). A unit test should test exactly one thing.

Tests should be readable. Think of them as not just testing the behavior of the function, but also as an example of how to use the function. This gives us a name for the test (e.g., Actor::diesShouldNotBeAliveTest() or Actor::healthy_should_not_be_dead_test(), etc.).

Tests should be repeatable/deterministic. We should test the mechanical parts of the game (e.g., marking an Actor with zero health as "dead") where the same inputs produce the same outputs. If we are testing randomness ("rolling a die"), we should have some way to "mock out" that randomness with something deterministic ("load the die", "use a two-headed coin", etc.) to make sure the methods do what we expect.

Tests should be fast. Since each test case tests exactly one thing, we should make them small and fast.

Tests should be automated and tracked. We should be able to run the tests with a single command (e.g., "make test" or whatever), and we should include the test code in our git repository. Best practices suggest running the tests and make sure they pass before pushing code out to the repository's master branch ("don't break master").

Testing the Game

"Testing the game" has several distinct meanings: make sure the game is playable, make sure the game is fun, etc. In some sense, unit testing is like checking to make sure each square of the board is flat: but if we glue the edges badly, we could actually end up with a curved board. Unit testing checks locally each function does what we hope, but it doesn't check the game does what we hope. This motivates integration testing and end-to-end testing.

Integration testing can be useful. If we want to make sure dialog options trigger quests and completes quests, we need integration testing. This amounts to setting up a mock game, simulating dialog, then checking the game state matches what we expect. Since multiple "units" are being tested in conjunction (dialog, quests, etc.), we're really testing that they're "integrated" correctly. For people trying to create an old-school Fallout or Wasteland-type game, this can be very useful.

Testing from the Player's Perspective

I would suggest testing the game from the user's perspective. This is harder to do, and varies depending on the type of game you're making. In my mind, I assume you are programming something like a Baldur's Gate, Fallout, or Wasteland-type game: a mixture of quests, dialog, combat, and possibly more.

What do we hope to test? We'd like the game to be playable (quests "fit together" in a way that the player can get to the end of the game), but we'd also like the game to be fun. This is where design decisions are needed: how do we specify a game to be "fun"? Is there sufficient choice architecture?

Test the game is playable (quests sequence properly). For example: quest A occurs before quest B, wherein quest A requires killing actor X, but actor X issues quest B after completing quest A, rendering quest B un-triggerable. (More concretely: if the king gives us a quest after completing his minister's quest, and the minister asks us to assassinate the king, then there better be some mechanism for us to continue after killing the king...like the minister takes over. Otherwise, if we are waiting on the deceased king to give us our next quest, we'll be stuck.)

If we have a domain specific language for quests, actors, items (and if we store these in .info files), then we could have a simple helper program which runs through the quests, makes certain the quest items are fetchable, the quest-issuing actors are alive, and there are chains of dialog/quests which start with a specified initial quest and end at the specified final quest.

The helper script should record sequences of quests which are unwinnable, or when there are disconnected components (e.g., killing actor X early in the game prevents quests B, C, and D). At the end, it will print out to the screen a summary (along the lines of "M paths succeed, N paths tried with K character builds") and a more verbose explanation to a file ("Character build C played the quest chain Q₁, ..., Q_m then got stuck at quest X") possibly with the trajectory of events for reconstruction. We could automate this script to try all variations of skills and stats, too.

I've discussed this idea in passing a few times, I'll probably make it the subject of a future post...maybe have a minimal working example for people to play with, we'll see. It'll involve a variation of depth-first search along a few distinct play-styles...we'll see, friends, we'll see.

Test you aren't a jerk to the player. Suppose our game has factions and the player has a reputation (loved, liked, undecided, disliked, hated). If our game penalizes the player's reputation when the player kills a member of the faction, then we should beware of the situation when the player witnesses the death of a faction's member: will this tarnish the player's reputation or not? This is a prime candidate for sticking away into a unit test, for regression testing.

If this is part of the plot (the player, witnessing a murder, is then falsely charged with the murder), then it should be written into the game manually. The last thing a player wants is to find the police are after them for...apparently doing nothing. That may be amusing to the programmer (I certainly chuckled), but it's no fun to the player.

There are other similar cases which, when programming, do not immediately sound consequential. But for the player, it feels like the game is designed by a vindictive jerk. It may not be easy to discern when this happens, but once discovered we should try to create unit tests to ensure we aren't jerks.

Heuristic "Tests"

These are measurements of symptoms which boring games exhibit. Alas, there's no way to automate the underlying "boring-ness" away.

Test the game has choice and consequences. Does dialog change to reflect the player's actions? Are new quests opened up specific to the player's choices? Do new interactions [dialog, NPC encounters, quests offered] occur after the player chooses particular outcomes?

Is it possible to have a playthrough where the player kills everyone before talking to them? This forces us to design the quests with constraints that force the game to have consequences and the player to have freedom. Chris Sawyer noted this design decision in an interview with IGN as key to game reactivity and player choice. We can enforce this check with a particular playthrough in our helper script.

Test the game takes you to all the locations. What locations are visited by the play-throughs? We could dump the trajectory of locations visited for further analysis. Sometimes a location is visited more frequently than intended, other times a location is never visited. This is a symptom of possibly less fun games, which can't be automated to enforce: it's an aid to help revise quest considerations.

In general, test for symptoms of fun. Depending on what your game is trying to accomplish, the criteria for "having fun" varies. Each criteria has different symptoms, and we should figure out how to automate ways to check these symptoms are present in our game. On the flip side, there are certainly symptoms of anti-fun: fun-killing elements we want to avoid. We should also automate ways to check these anti-fun elements are not present in our game.

In some sense, this is the best we can do with automated testing: test for proxies of what we want, and regression-checks against what we dislike. There's no way to properly "test for fun", but we can test the game can be played in different playstyles and for the "kill everyone before you even interact with them" heuristic Chris Sawyer noted.

Concluding Remarks

Game developers tend not to test their games, at least not in the same way that software engineers test their programs. Unit testing is generally discouraged among game developers, for good reason (having unit tests give false sense of being "correct", whereas games seek fun not correctness).

But we can test for an RPG "being playable". We can further make such testing automated. Insofar as we can make such testing scripts, I think we should...at least, I should. Such automated testing checks the quests are ordered correctly and unlockable, speakers are referenced properly, and so on. Again, this doesn't test gameplay, but it tests the game can be played.

As for what this looks like, I'm working on a minimal RPG I've decided to refer to as "project Delaware". (Why Delaware? Nothing special: I've just opted to use the names of states in the U.S. by order of admission to the union. And Delaware is the first state admitted to the union.) I hope to have something to share soon-ish.

Dialog Trees: Basic Design and Implementation

The basic mechanics of dialog trees amounts to describing a directed graph, with some bells and whistles. Specifically, the edges are possible player responses, the nodes are NPC statements, and we have them both be subjects of observers (so selecting the line "I accept this quest" in dialog will trigger the start of that quest). Arguably, dialog nodes and edges are also observers (different dialog options reflecting the player's progress through the story).

The basic structure of a directed graph, with some bells and whistles attached, occurs frequently in RPGs (though seldom in Rogue-likes). I'll be using vague names like "edge" and "node" (instead of "response" and "dialog-node").

Software Design

I'm not going to discuss, "How to write narrative dialog for your RPG". This is a very important topic, one I don't think I am skilled at, but it assumes we have a data structure for storing dialog. We first must introduce the data structures and algorithms for software to work with dialog, then some additional code to facilitate authoring dialog more easily.

The design varies depending on granularity. The basic elements require two classes, a node class which has the NPC's line and the player responses; and the edge class, which represents one possible player response to an NPC line.

(defclass edge ()
  ((text :initarg :text
         :type string)
   (next-node-id :initarg :next-node-id)))

(defclass node ()
  ((id :initarg :id)
   (npc-line :initarg :npc-line
             :type string)
   (speaker :initarg :speaker)
   (responses :initarg :responses)))

Arguably we could give an ID to each edge, but the schematic design should be clear.

We could go further, and introduce a subject class, a notify method for the subject, and have edge inherit the subject class. This design choice depends on whether the subject's notify method requires additional parameters (e.g., an event keyword or whatever).

Contingent Responses

We also need to consider the situation where some player responses are only displayed when events occur, or a skill check is passed. If we use Common Lisp, for example, we can consider something along the lines of:

(defclass edge ()
  ((show? :initarg :show?
          :initform t ;; default to true
          :type (or boolean (function (edge) *))
          :documentation "Either a check to show if this edge should be shown, or its result.")
   ;; other slots ("fields") as before, not shown
   ))
         
(defun edge/show? (edge)
  (declare (type edge edge))
  (let ((edge-show? (slot-value edge 'show?)))
    (if (typep edge-show? 'boolean)
      edge-show?
      (funcall edge-show? edge))))

This permits handling one-time checks by the second-order function along the lines of:

(defun one-time-check (check-callback)
  (declare (type (function (edge) *) check-callback))
  (lambda (edge)
    (declare (type edge edge))
    (let ((result (funcall check-callback edge)))
      ;; coerce the result to a boolean value
      (setf (slot-value edge 'show?) (if result t nil)))))

;; ostensibly used as (one-time-check (skill-check :strength :at-least 10))

The only requirement I would recommend: during a dialog, the show? should evaluate to the same value. So a skill-check that happens each dialog should store that check's result until dialog ends. Alternatively, it should only update the show? value upon success, and keep its function/callback version for future checks.

Hack: Scripts

We can take advantage of this to invoke a script when a response is selected. This amounts to making the observer notified (of the response selected) trigger the desired code instead. Common Lisp simplifies the observer pattern to a function call-back, the subject pattern is a class with a slot observers for a list of functions.

(defclass subject ()
  ((observers :initarg :observers
              :initform nil
              :type list)))

(defgeneric notify (self event-keyword &key &allow-other-keys))

(defmethod notify ((self subject) event-keyword &key &allow-other-keys)
  (loop for observer in (slot-value self 'observers)
        do (funcall observer self event-keyword)))

(defgeneric add-observer (self observer))

(defmethod add-observer ((self subject) observer)
  (setf (slot-value self 'observers)
        (cons observer (slot-value self 'observers))))

;; trigger a script by something along the lines of
;; (add-observer edge
;;               (lambda (self event)
;;                 (declare (ignore self event))
;;                 (script)))

(Note to Lispers: maybe the type of the observers slot should be (vector * (function (subject keyword &key &allow-other-keys) *)), or else the notify loop may require an additional line when observer to avoid null observers. But the intuition is to have a collection of callbacks, which we invoke with notify.)

Related Work

We haven't factored in the speakers yet, which could be done by proxy (using an entity component system). Instead of inserting the NPC's data structure directly, use the unique ID for that NPC. We store in a separate hash-table the NPCs (using their IDs as keys).

Also Emily Short's amazing work on conversation and Beyond Branching: Quality-Based, Salience-Based, and Waypoint Narrative Structures. More generally, the art of writing the actual dialog text itself has been discussed since Aristotle's Poetics.

Last, the authoring tools have not been discussed. We could look at interactive fiction for inspiration (e.g., Ink). The idea we should fix in our mind: create a DSL for authoring dialog, so it's more along the lines of markup instead of coding. For example:

(with-speaker doc-harris
  (node "Hello, how can I help you?"
    ;; a response is either a list (string optional-next-id &key observers ...)
    ;;               or terminal, i.e., just a string or lacks a next-id
    :responses (("Tell me about this town" :dialog.doc-harris/town-guide)
                "Nothing today, thank you")) ; terminal response
  
  ;; a "node" which circles back until terminated
  (circuit-node "Anything else you want to know?"
                :id :dialog.doc-harris/town-guide ; unless an :id is given, autogenerates a unique ID for dialog nodes
                :initial-npc-line "Sure, what do you want to know?"
                :responses (("Is there a place to rest?" "Sure, there's an inn down the street")
                            ("Where can I get supplies?" "There's a blacksmith on the East side of town, and a trader next to the inn.")
                            ("Where can I get patched up?" "Right here! Doc Harris, medical practitioner, at your service!")
                            "Eh, I think I'm good now. Thanks and good bye!")) ; terminal response

  ;; trigger a quest if accepted through dialog
  (node "You're here! I need your help! My daughter's been kidnapped!"
    :show? ...
    :responses ("Uh, sorry, we're *really* *busy* at the moment..."
                ("Of course! Who apprehended her?" :start-quest :doc-harris.quest/kidnapped-daughter)
                ("We need to know some more questions first..." :dialog.doc-harris/urgent-quest-circuit)))
  ;; etc.
  )

If combined with an entity component system, we can write some code to check the edges point to existing nodes, the speaker is a valid NPC, the quests started (and finished) through dialog all exist. I'm in the middle of writing a proof-of-concept of this validation toolkit, and will probably talk about it soon-ish.

Design Patterns and Architecture Patterns in Rogue-likes

Since the '90s, "patterns" have been stolen borrowed from Christopher Alexander's work on architecture. Alexander was curious about designing rooms, buildings, even entire cities, using a sort of "language" which addresses recurring problems like "What do we do with people waiting around?" In a house, this would be a drawing room; for a city, with a transit system, this would be benches (or whatever). Programmers realized they analogously face recurring problems which are solved with "very similar" solutions, and introduced design patterns to the world of software engineering.

For RPGs, we similarly divide it up into patterns: the players go on quests, which occur on levels, whose objectives are typically one of some half-dozen varieties ("fetch quests", "assemble parts for an artisan" quest, "kill quests", "defend quests", "follow quests", etc.). There are Non-Player Characters the user interacts with, Enemies to kill, etc. UC Santa Cruz has done some work on RPG patterns in this vein.

The goals of using patterns in programming include: speeding up development, decreasing the number of bugs, increasing stability, making it easier to extend the program's capabilities, aid testing, and so on.

Munificent Bob wrote a wonderful book, Game Programming Patterns. Design patterns address recurring problems which regularly crop up, and were the "hot new thing" in the '90s. What's an example of this in games? A recurring pattern in, e.g., Steam games are achievements, which are precisely the observer pattern.

Since design patterns have been well discussed by Munificent Bob, I'll focus on the less discussed architecture patterns for Rogue-likes. Specifically, MVC and its variations.

Architecture Patterns

"Architecture patterns" refers to particular ways to structure the code to cleanly separate concerns. For most rogue-likes, this is some variant of MVC: the rules to the game is coded up in the models, the UI rendering is handled by the views, and the translation of user input to game commands is handled in the controller.

If we wanted to have a "poor man's" Fallout-type Rogue-like, where there's a separate dialog interface showing possible responses to the NPC's statement, another interface for traversing the "world map", and a third for traversing the "local region" map, then we can handle this cleanly with an MVC-architecture. One controller for handling user inputs for the dialog, another for traversing the world, and a third controller for the local world map.

We can organize the code to reflect this architecture:

/game/

/game/models/actor.c
/game/models/dialog.c
/game/models/item.c
/game/models/quest.c

/game/controllers/dialog_controller.c
/game/controllers/world_map_controller.c
/game/controllers/combat_controller.c

/game/views/dialog_view.c
/game/views/world_map_view.c
/game/views/combat_view.c

All the logic of dialog is handled in /game/models/dialog.c, which can trigger quests, complete quests, or otherwise update the game state to reflect the choices made. In an object-oriented language, the model is the subject of a view observer. Schematically, in C++, a model would look like:

// make this a template class (parametrized by Model)?
class Model {
public:
    Model() : observers_() { };
    ~Model();
    // business logic methods not shown
    // subject methods, for observer pattern
    void addObserver(const Observer &observer);
    void removeObserver(const Observer &observer);
    void notify() {
        for (Observer o : observers_) {
            o.update(*this);
        }
    }
private:
    std::vector observers_;
};

The only place where UI occurs should be swept into the views. Ostensibly we could create subdirectories for the different libraries use (e.g., /game/views/ncurses/ for the code handling NCurses-rendering, /game/views/sdl/ for the analogous code using the SDL library, etc.). If we were implementing the game in an object-oriented language, the view would be an observer of the model, and be notified when the game state has changed. Schematically, in C++, a view class would look like:

// make this a template class (parametrized by Model)?
class Model;
class Observer {
public:
    virtual ~Observer() { };
    virtual update(const Model &model) = 0;
};

class View : public virtual Observer {
public:
    View(...);
    ~View();
    void render();
    // observer pattern method
    void update(const Model &model);
    // action patterns to dispatch events to the controller
    void addMouseClickListener(const MouseClickListener &listener);
    // etc.
};

Controllers come in pairs with views. We attach the view to the model within controllers, and the action listeners are populated within the controller, too, for handling events (like mouse clicking or keyboard events, possibly inspired by DOM events). The generic controller resembles:

class Controller {
public:
    Controller(View *view, Model *model) {
        view_ = view;
        model_ = model;
        model->addObserver(view);
        // attach action listeners here, too
    };
    ~Controller();
    // high level user interactions
private:
    View* view_;
    Model* model_;
};

A variation of this architecture, for the Fallout-type game with several interfaces (dialog, world map, local map) may take a hierarchical MVC: intuitively, a "maestro controller" which delegates the game-loop to the dialog controller from the start of dialog until dialog ends, whereupon the game-loop returns to the maestro controller.

Such an architecture permits unit-testing the models, which lets us catch bugs in the boring mechanics (e.g., "marking a quest complete works as expected, right?"), and make it easier to swap out the UI.

Following the Lisp philosophy, we want to create a DSL within which we implement the game. The models describe this DSL. We can store the game data in a separate directory (say, /game/data/) encoded in JSON or YAML or S-expressions. If we wanted to make sure there are multiple ways to solve a quest (through dialog, sneak, or violence as three alternatives, for example), we could setup a small helper program or routine to check each quest has this property...thereby checking a sneaky player could win the game, as could a violent player or a dialog-focused player.

This also permits several people to work on the game. If the DSL is minimally specified and worked on by everyone, there could even be a team working on the game script independent of the game engine. A small Lisp script could check that the game script is playable, an emacs mode could be written to make development faster (a simple C-k C-q to develop a new quest, or whatever, with a skeleton newly inserted at the cursor).

Thus is the goal for such an architecture: to make it easy to develop the game, separating the fun parts from the boring reptitive parts so that the boring repetitive parts are implemented only once. The fun parts could be extended by a team, independent of the boring parts.

References and Concluding Remarks

The Model-View-Controller architecture has evolved over time into something idiosynchratic to each language. Java's MVC in Swing is slightly different than the original MVC in Smalltalk (and when Ruby-on-rails hit the scene, MVC changed into a core component of web development). Admittedly, I am drawing upon the Java tradition (see also MVC Structure, Examples of Model-View-Controller Pattern, Java SE Application Design With MVC).

Java has the Controller class track View objects and Model objects; whereas a vanilla approach would have the View create and track an instance of a corresponding Controller class, and both the Controller and View would observe a Model object. Doubtless there are many other variations of this theme, I won't pretend to be comprehensive reviewing them here. And, in my experience, it's easy to transform an MVC architecture into a Presentation-Abstraction-Controller architecture (again, this is fine, but I just want to emphasize that following a plan should not deter us from doing what works).

• Model-View-Controller. In Pattern-Oriented Software Architecture, Volume 1 (Peter Sommerlad, Michael Stal, Frank Buschmann, Hans Rohnert, Regine Meunier), Wiley, 1996, pp. 125 et seq.

Rogue 3.6 Investigation Part I: Data Structures

Table of Contents:

• Roadmap
• License
• Investigating Data Structures
• Help List
• Coordinate Data Type
• Magic Items
• Dungeon Data Structures
• Room Structure
• Traps
• Monster and Item Data Structures
• Stats
• Structure for Monsters (and the Player)
• Information on the Taxonomy of Monsters
• Data Structure for the Inventory of a Monster
• Actions As Data Structure

Roadmap

We can find the source code to Rogue 3.6 here (or more precisely here), and we will study it first. It is the earliest example of a roguelike that I could find, after all!

This is part I of a several part series investigating the structure and code behind the Rogue 3.6 program. We will consider the data structures used in the game.

License

I think I need to follow the License and reproduce it here

Rogue: Exploring the Dungeons of Doom
Copyright (C) 1980, 1981 Michael Toy, Ken Arnold and Glenn Wichman
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:
1. Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
   notice, this list of conditions and the following disclaimer in the
   documentation and/or other materials provided with the distribution.
3. Neither the name(s) of the author(s) nor the names of other contributors
   may be used to endorse or promote products derived from this software
   without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) AND CONTRIBUTORS ``AS IS'' AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR(S) OR CONTRIBUTORS BE LIABLE
FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
SUCH DAMAGE.

===========================================================================

Portions of this software (save/restore game state) are based on the work 
of Nicholas J. Kisseberth. Used under license:

Copyright (C) 1999, 2000, 2006 Nicholas J. Kisseberth

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:
1. Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
   notice, this list of conditions and the following disclaimer in the
   documentation and/or other materials provided with the distribution.
3. Neither the name(s) of the author(s) nor the names of other contributors
   may be used to endorse or promote products derived from this software
   without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) AND CONTRIBUTORS ``AS IS'' AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR(S) OR CONTRIBUTORS BE LIABLE
FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
SUCH DAMAGE.

===========================================================================

Portions of this software (encryption) are based on the work 
of David Burren. Used under license:

FreeSec: libcrypt

Copyright (C) 1994 David Burren

All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:
1. Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
   notice, this list of conditions and the following disclaimer in the
   documentation and/or other materials provided with the distribution.
3. Neither the name(s) of the author(s) nor the names of other contributors
   may be used to endorse or promote products derived from this software
   without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) AND CONTRIBUTORS ``AS IS'' AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR(S) OR CONTRIBUTORS BE LIABLE
FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
SUCH DAMAGE.

Source: /rogue3.6.3-src/LICENSE.TXT

Investigating Data Structures

We see that there are the following files in the source code:

armor.c    LICENSE.TXT  move.c         rip.c           rogue.r    weapons.c
chase.c    list.c       newlevel.c     rogue36.cat     rooms.c    wizard.c
command.c  machdep.h    options.c      rogue36.doc     save.c     xcrypt.c
daemon.c   main.c       pack.c         rogue36.html    scrolls.c
daemons.c  Makefile     passages.c     rogue36.sln     state.c
fight.c    mdport.c     potions.c      rogue36.vcproj  sticks.c
init.c     misc.c       readme36.html  rogue.6         things.c
io.c       monsters.c   rings.c        rogue.h         vers.c

As per usual in C, the header files usually contain the data structures. Fortunately, we only have a few header files to consider: machdep.h and rogue.h. We will investigate rogue.h, since machdep.h is all the boring machine dependent code.

Unfortunately, the rogue.h file is some 530 lines long. So we will investigate the data structures first (the structs), then in another post investigate the relevant methods.

The data structures start on line 268 of rogue.h (the big hint is the comment "Now we define the structures and types"). It's some 133 lines of code defining all the data structures, so lets keep a close eye on each data structure!

Help List

/*
 * Help list
 */

struct h_list {
    char h_ch;
    char *h_desc;
};

extern struct h_list helstr[];

lines 272-281 /rogue3.6.3-src/rogue.h

This defines some data structure, which has an index variable char h_ch and a corresponding string char *h_desc which describes (presumably) the key stroke.

This is stored into a global variable extern struct h_list helstr[] which consists of all the help strings. It's appropriately the help list.

Coordinate Data Type

/*
 * Coordinate data type
 */

typedef struct {
    int x;
    int y;
} coord;

lines 283-289 /rogue3.6.3-src/rogue.h

This is a simple Cartesian coordinate pair (x,y). When we work the the terminal (the console, command line, whatever you want to call it), we have a discrete sort of geometry: usually 80 characters wide and 30 characters tall.

To specify a character on the console, we need a coord to specify its location.

Magic Items

/*
 * Stuff about magic items
 */

struct magic_item {
    char mi_name[30];
    int mi_prob;
    int mi_worth;
};

lines 305-313 /rogue3.6.3-src/rogue.h

We skipped a few (e.g. the struct linked_list that are straightforward to understand) to get to something exciting: magic items!

They consist of char mi_name[30] a string of 30 characters' length, which is the name of the item.

The int mi_prob is, I think, the probability of finding the magic item. Remember in stdlib.h in C, the maximum random number is specified to be RAND_MAX=32767. I would suspect that if the random number is greater than mi_prob, then the item is created.

The last field, int mi_worth is the value (in gold pieces) of the item.

Dungeon Data Structures

Room Structure

/*
 * Room structure
 */
struct room {
    coord r_pos;                        /* Upper left corner */
    coord r_max;                        /* Size of room */
    coord r_gold;                       /* Where the gold is */
    int r_goldval;                      /* How much the gold is worth */
    int r_flags;                        /* Info about the room */
    int r_nexits;                       /* Number of exits */
    coord r_exit[4];                    /* Where the exits are */
};

lines 315-326 /rogue3.6.3-src/rogue.h

Now we are starting to define the dungeon's data structures. The first logical place to begin when building a dungeon is to build rooms.

We specify the upper left corner of the room (and the lower right corner of the room) by coord r_pos (and coord r_max respectively). This tells us the maximum size the room can be, the actual size is something randomly determined by these parameters.

We are then concerned about the contents of the room, specifically about gold and other things. The gold is specified by its position coord r_gold and the quantity int r_gold (since it's not unsigned, could there be negative gold?!).

The "other stuff" is specified by the int r_flags field.

The doorways into (and out of) the room are specified by the next (and last) two fields int r_nexits which give the number of exits, and coord r_exit[4] which gives the coordinates of the exits. We see that there can only be, at most, 4 exits.

Traps

/*
 * Array of all traps on this level
 */
struct trap {
    coord tr_pos;                       /* Where trap is */
    char tr_type;                       /* What kind of trap */
    int tr_flags;                       /* Info about trap (i.e. ISFOUND) */
};

extern struct trap  traps[MAXTRAPS];

lines 328-337 /rogue3.6.3-src/rogue.h

We begin getting to something interesting: traps! What do we need to know about a trap? Well, where do we put it, what kind is it, and has it been detected yet?

This corresponds to coord tr_pos (the position of the trap), char tr_type (the identifier for the type of trap it is), and int tr_flags (the flags giving more information about the trap).

We then collect all the struct trap into one giant list, a global variable which is the last line of code: extern struct trap traps[MAXTRAPS]. It contains the information about all of the traps on this level.

Monster and Item Data Structures

Stats

/*
 * Structure describing a fighting being
 */
struct stats {
    str_t s_str;                        /* Strength */
    long s_exp;                         /* Experience */
    int s_lvl;                         /* Level of mastery */
    int s_arm;                         /* Armor class */
    int s_hpt;                         /* Hit points */
    char s_dmg[30];                     /* String describing damage done */
};

lines 339-349 /rogue3.6.3-src/rogue.h

In most role playing games, the monsters have some set of statistics (a list of numbers indicating its strength, dexterity, etc.). Rogue is no different!

Here we have only a certain subset of the rich structure from, e.g., Dungeons and Dragons. We have str_t s_str for the strength of the creature. But wait...what is a str_t data type? It's not ANSI C!

We go back and look, and the data structure we skipped after introducing coord is precisely the culprit! We produce it here:

typedef struct {
    short st_str;
    short st_add;
} str_t;

lines 291-294 /rogue3.6.3-src/rogue.h

which consists of two shorts. Interesting that the "strength" statistic would depend on a "composite" data type!

Returning to our data structure at hand, line 344 specifies the long s_exp field. It's precisely what one expects, it specifies the "experience points" the creature has (indicating how "experienced" it is at...killing stuff...).

When the creature has accumulated certain amounts of experience, it then increments its int s_lvl field indicating that the creature has "leveled up".

The armor class, or how well protected the creature is, is another statistic of interest. It's precisely contained in the int s_arm field.

When armor fails, the creature has some stamina...some "hit points". This is the next entry int s_hpt which is the maximum hit points the creature has (not its current hit points!).

The type of damage the creature can do is specified by a string, char s_dmg[30]. I guess that it doesn't make any real difference what type it is, it's just frosting.

That kind of bothers me that the type of damage is a facade, but that is easier to program.

Structure for Monsters (and the Player)

/*
 * Structure for monsters and player
 */
struct thing {
    coord t_pos;                        /* Position */
    bool t_turn;                        /* If slowed, is it a turn to move */
    char t_type;                        /* What it is */
    char t_disguise;                    /* What mimic looks like */
    char t_oldch;                       /* Character that was where it was */
    coord *t_dest;                      /* Where it is running to */
    short t_flags;                      /* State word */
    struct stats t_stats;               /* Physical description */
    struct linked_list *t_pack;         /* What the thing is carrying */
        int t_reserved;         /* reserved for save/restore code */
};

lines 354-365 /rogue3.6.3-src/rogue.h

We now get to the data structure representing the player! We need to specify a few things first about the monster, specifically its stats and its coord position. This is precisely done on lines 355 and 362.

We can also specify if the monster is slowed. Perhaps a spell was cast on it, it's drunk, caught in a spider web, something (anything!) to make it slower. If it is slowed down, then bool t_turn is true to indicate it takes 1 entire turn to move.

We also should worry about what sort of monster is it?! Is it the player (yes, the player is a monster!)? Is it an orc? Or something else? This is specified by char t_type.

Since a roguelike is played on the command line, each monster is represented by a character. I can't say which field specifies it. This is specified either by char t_oldch or char t_disguise, I can't really say.

But monsters go places too. This is kept track by the thing's data structure itself, specified by the line coord *t_dest.

The monster is sort of like a finite state machine. Consequently, it has a state. This state is specified by the line short t_flags which gives it various characteristics.

Monsters (well, the player at least) have inventories. They have stuff, like armor or weapons. The field struct linked_list *t_pack specifies the monster's inventory.

In case we want to do anything else, we reserve some space int t_reserved for saving the monster or restoring it.

Information on the Taxonomy of Monsters

/*
 * Array containing information on all the various types of monsters
 */
struct monster {
    char m_name[20];                    /* What to call the monster */
    short m_carry;                      /* Probability of carrying something */
    short m_flags;                      /* Things about the monster */
    struct stats m_stats;               /* Initial stats */
};

lines 367-375 /rogue3.6.3-src/rogue.h

The taxonomy of monsters specifies, like the biological taxonomy, what kind of creature we are dealing with. Orcs are different from dragons, which are different from coyotes, which are different from...

We keep track of all this with this particular data structure. The char m_name[20] lets us name the monster type (e.g. "orc", "dragon", "coyote", etc.).

The short m_carry is the odds that it's carrying stuff, e.g. an orc is more likely to have stuff than a coyote.

The short m_flags specifies the flags telling us miscellaneous facts about the monster.

Like all monsters, it has struct stats m_stats specifying its statistical attributes.

Data Structure for the Inventory of a Monster

/*
 * Structure for a thing that the rogue can carry
 */

struct object {
    int o_type;                         /* What kind of object it is */
    coord o_pos;                        /* Where it lives on the screen */
    char o_launch;                      /* What you need to launch it */
    char o_damage[8];                   /* Damage if used like sword */
    char o_hurldmg[8];                  /* Damage if thrown */
    int o_count;                        /* Count for plural objects */
    int o_which;                        /* Which object of a type it is */
    int o_hplus;                        /* Plusses to hit */
    int o_dplus;                        /* Plusses to damage */
    int o_ac;                           /* Armor class */
    int o_flags;                        /* Information about objects */
    int o_group;                        /* Group number for this object */
};

lines 377-394 /rogue3.6.3-src/rogue.h

This specifies the items that the user (or some monster) can carry. This is a bit against the spirit of modern Roguelikes since it seems that everything "is-an" item (in the object oriented sense of the word). But bear in mind this is an early version of the original game!

The first two fields are self-explanatory. The third field char o_launch is foreign, however, and the comment doesn't help much. I suspect that it tells us information about whether the item is ammunition for e.g. a bow or a sling.

The next two fields tells us how the item damages a monster if we use it "like a sword" or if we hurl it at the monster. These are strings informing us HOW it would harm a monster, but not how much it would hurt.

The next field int o_count allows us to "stack" multiple items of the same type together, saving memory.

We (similar to the taxonomy of monsters) have a "taxonomy of items", which we use to specify the field int o_which which sort of item we have.

Any modifications to hitting or damaging a monster are specified by the int o_hplus (and int o_dplus) fields (respectively).

If the monster wears the item like it were armor, it modifies the armor class. This modification is specified by the field int o_ac.

As per usual, the miscellaneous features are lumped into int o_flags some "flags" field of the data structure.

The "group number" (whatever that means) is the last field entry in the data structure int o_group.

Actions As Data Structure

struct delayed_action {
    int d_type;
    int (*d_func)();
    int d_arg;
    int d_time;
};

lines 396-401 /rogue3.6.3-src/rogue.h

This is rather interesting, an action is a data structure! But what exactly does the data structure specify?

Well, the first field int d_type specifies what sort of event it is, and int (*d_func)() is a function pointer which points to the function that specifies what happens.

The int d_arg field, I suspect, specifies the argument to the function, but I can't say for sure at this time.

The int d_time may specify how frequently it happens, or what turn it will happen. It's presumably the latter.

Morals from the UNIX Philosophy

This "post" really just lists a bunch of morals we should learn from the UNIX philosophy.

1. You cannot tell where a program is going to spend its time. Bottlenecks occur in surprising places, so do not try to second guess and put in a speed hack until you've proven that's where the bottleneck is.
2. Measure. Do not tune for speed until your performance analysis tool tells you which part of the code overwhelms the rest.
3. Fancy algorithms tend to run more slowly on small data sets than simple algorithms. They tend to have a large constant factor in O(n) analysis, and n is usually small. So don't get fancy unless Rule 2 indicates that n is big enough.
4. Simplify your algorithms and data structures wherever it makes sense because fancy algorithms are more difficult to implement without defects. The data structures in most programs can be built from array lists, linked lists, hash tables, and binary trees.
5. Data dominates. If you have chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming.

Additionally, Mike Gancarz mentions some that are overlooked:

1. Small is beautiful.
2. Make each program do one thing well.
3. Build a prototype as soon as possible.
4. Choose portability over efficiency.
5. Store data in flat text files.

Eric S. Raymond also gives a few worth noting:

Rule of Modularity:

Write simple parts connected by clean interfaces.

Rule of Clarity:

Clarity is better than cleverness.

Rule of Composition:

Design programs to be connected to other programs.

Rule of Separation:

Separate policy from mechanism; separate interfaces from engines.

Rule of Simplicity:

Design for simplicity; add complexity only where you must.

Rule of Parsimony:

Write a big program only when it is clear by demonstration that nothing else will do.

Rule of Transparency:

Design for visibility to make inspection and debugging easier.

Rule of Robustness:

Robustness is the child of transparency and simplicity.

Rule of Representation:

Fold knowledge into data so program logic can be stupid and robust.

Rule of Least Surprise:

In interface design, always do the least surprising thing.

Rule of Silence:

When a program has nothing surprising to say, it should say nothing.

Rule of Repair:

When you must fail, fail noisily and as soon as possible.

Rule of Optimization:

Prototype before polishing. Get it working before you optimize it.

So What Have We Learned?

Well, each data structure should do one thing and only one thing. We should also start out by writing the data structures in header files, and the various "accessor/mutator" methods for the data structures should be prototyped in the corresponding header files.

I think that I will try to use a more "data-driven" approach than a "purist object oriented" approach, composing data structures instead of using kind of bloated inheritance.

In fact, I may use regular, old fashioned C and use Phil's Object Oriented ANSI C approach. To reproduce his example (with some modifications), we have

 /* FooObj.h */
#ifndef FOO_OBJ_H_
#define FOO_OBJ_H_

struct fooobj {
    int privateint;
    char *privateString;
    /* Depending on your preferences, you
     * may prefer privateString to be a char buffer[],
     * OR malloc it and free on delete.
     */
};

typedef struct fooobj * FooOBJ;
FooOBJ newFooOBJ();
void setFooNumber(FooOBJ,int);
void setFooString(FooOBJ,char *); /* make comments about copy or not here */
void dumpFooState(FooOBJ);      /* dumps debug contents of FooOBJ to stdout */
void deleteFooOBJ(FooOBJ);
#endif /* def FOO_OBJ_H_ */

See the beauty here? And if we have, say, Bar extend fooobj, we can do the following:

 /* bar.h */
#include "FooObj.h"

#ifndef BAR_H_
#define BAR_H_
struct bar{
    fooobj *super;
    /* rest not shown */
};

typedef struct bar* Bar;

Bar newBar();
void deleteBar(Bar);
FooOBJ toFooOBJ(Bar); /* simply "return Bar->super;" */
#if __STDC_VERSION__ >= 199901L /* if C99 compliant */
inline void setBarNumber(Bar B, int i) { setFooNumber(B->super,i); }
inline void setBarString(Bar B, char *s) { setFooString(B->super, s); }
#else /* not C99 compliant, use macros instead of inline functions */
#define setBarNumber(B,i)       setFooNumber(B->super,i)
#define setBarString(B,s)       setFooString(B->super,s)
#endif /* if C99 compliant*/
/* rest not shown */
#endif /* def BAR_H_ */

This is precisely what happens with C++ when it does its inheritance voodoo. At least, in memory this is how it looks like.

If one is using a C compiler that does not allow explicit declaration of inline functions, one could easily use macros instead for setBarNumber() and setBarString. Or one could use a full blown function.