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.