20 July 2015

Script Testing

Looking back to the original King of Dragon Pass scene compiler, there’s a comment (probably written by Shawn Steele) that reads
ToDo:
Different program: Batch test all of the scenes, follow all of the conditional paths, etc., to make sure that things are as we would expect.  This would go a long ways to making sure that the scenes are coded properly.
We never wrote that program, and with modern unit test frameworks it doesn’t need to be a separate program. But for Six Ages, I did want to test every script, at least for gross errors (they still need human testing). I’d written unit tests to make sure that a single script could run, but running every script is quite different.

First, I redefined the problem slightly. Rather than following all conditional paths, I just wanted to run every response of every scene. (Conditionals depend not only on dice rolls, but also on things like having a feud, or having run the same scene before and having made a certain decision.) This turned out to be very useful to catch script functions that weren’t actually implemented yet. It’s much faster running the tests than going through a scene manually. Plus being automated, any issue was going to stay visible until fixed, instead of possibly falling through the cracks.

Except that’s not strictly true, due to what I call “lucky dice.” There were scenes that would sometimes work and sometimes fail. Usually this was due to having a specific person on the clan ring. One answer to this would be to make dice non-random. They could generate the same sequence of numbers every time through. I chose not to do this for a couple reasons. First, it would be even further from the "all of the conditional paths” idea, since it would be the same path every time. In other words, it focused on making the tests work, and not making the game work. Second, due to the nature of what was being tested, it didn’t really guarantee repeatability. The dice rolls would be the same, but their contexts would be different as we added scenes or revised them. (In other words, the 57th roll might always be a 16, but that roll might determine a clan attack in one run, and random text in the next after we fixed a bug.)

Another factor is that running every scene is unnatural. Most scenes have some sort of condition (there is no point in having someone ask for a treasure if you have no treasure), or are explicitly designed to follow another scene. The unit tests didn’t test for this sort of continuity, but forcing a scene to run when its precondition wasn’t met often caused problems that would never show up in a real game.

For a while, I just lived with the false positives (a scene failing if there no friendly neighbors, or after your advisors died in an apocalypse) that came and went. We’re not using build automation, so it was annoying but not really gumming up the works.

It seemed like a more serious limitation that the test would run every response, but couldn’t handle other interactivity, like picking a clan to petition, the number of warriors to hunt down a monster with, or how large a gift to offer. OSL is designed to pause execution and wait for user response, then resume running the script. This is all implicit — the interpreter doesn’t literally sit there waiting (which would be a great way to run down your batteries), it sends a message and quits. It took me a while to figure out how to hook into this asynchronous process in a way that would work with unit tests (which are essentially synchronous, running a script until it is complete). Once I did, the tests suddenly got a lot more thorough. (A typical response might ask you for a clan, a diplomat, and a gift, all before resolving the negotiation. So a typical response had only been very partially tested before.) And this meant that there were more false positives, since there was more code being run, but depending on a particular story context.

I tried to ensure a proper context (when testing, hard-code a friendly neighbor), but false positives would still come and go depending on chance. I finally came up with an approach that allowed me to get broader coverage by having free-rolling dice, but also avoid testing scenes in a way that was almost guaranteed to fail.

The goal of this test was to exercise each scene as fully as practical. Randomness helped give broader test coverage within a scene (at least over multiple test runs). But randomness cascading through the test run was causing problems. Ergo, I needed to eliminate the cascade. The breakthrough here was to save the game at the beginning of the test, and restore before running each response. This minimized randomness in a scene’s context, so it would never be run in a known impossible situation.

The final step was to capture the clean setup in a script, which is run at the start of the unit test (before the game is saved).

So once again, we can run the test when coding up a scene, and the errors it reports represent real problems.

We’re still not going through every part of a script — the player decision maker doesn’t handle combat. (It also gets stuck in certain negotiations by refusing to up its offer.) And while saving and loading is fairly fast, doing so for multiple responses for over a hundred scenes does add up. But exercising every script still takes only 32 seconds on my development machine, and running all the unit tests is a single command, so it’s not really a big deal.

Everything this test catches would eventually be found by QA, but only much later. It’s always better to shorten the time between creating a bug and finding it, so things are still fresh in the coder’s mind. And test automation means QA can spend more time on bugs that only a human can catch. So it’s now part of our scene coding process.

13 July 2015

Unit Testing

One of the deep secrets of King of Dragon Pass is that we shipped a buggy program in 1999. No, not the normal sort of low priority issues, or bugs rare enough you didn’t find them in QA or beta testing. KoDP relies on its scripting language to execute interactive scenes, and there is a serious bug in the OSL interpreter.

Luckily, there’s a workaround: the logging we put in to help debug OSL masked the bug. So instead of shipping the “release version,” we shipped the “debug version.” (This sort of issue is not unique to KoDP, by the way.)

This was actually something I forgot when I converted the game to iOS. (Looking back at my notes, I may have rediscovered this a day after releasing for iOS…) And I ended up making the same decision. It works in debug, so ship debug.

It turned out that even with debugging output turned on, there were a few extremely rare situations where the bug would surface. I believe I found and fixed some of those, but with tools, interpreter, and save files all revolving around the original implementation of lists, it was hard to make enough changes to be certain. And this was tricky code.

Back in 1997, we were very concerned about size (on disk and in memory) so we went to a lot of trouble to make lists (of clans, people, tribes) very compact. In retrospect, we committed one of the cardinal sins of programming: premature optimization. It was a noble goal, but at the start of the Six Ages implementation, I looked at KoDP saved games. Out of 1549 saved variables, 8 were lists. So compact storage was completely unnecessary. Lists are used far more frequently than they’re saved (for example, in picking a random clan from a list of neighbors who don’t hate you), so correct behavior was really the key.

While I didn’t really want to rewrite part of the game that was basically working, there was no guarantee that it would continue to (mostly) work with a whole new game. So Six Ages has a new implementation of the scripting language, from the bottom up. This supports new features, but is also an attempt to get it to work correctly in all situations.

So how do you guarantee correct behavior in a complex program? At one level, you can’t — or if you could, it would take too long to prove. But you can write code to test your code. The new implementation of OSL needed unit tests. (The original game had none — it would have been very unusual in the late 1990s.)

Various testing methodologies are big in business software (often combined with build automation), and a sign of a quality open source project is having tests. But it can be tricky to test games. There are ways to deal with randomness, but specifying a situation (like having exactly one non-hating neighbor, the right mix of advisors, or a raid history) or expected behavior for a multi-stage interactive scene can be tricky. And a lot of a game is its user interface, which poses its own testing challenges. Fortunately, while a game as a whole can be difficult to test, subsystems can be tested. The scripting language is just such a system. And even better, the handling of lists requires no testing tricks.

All tests pass!
While I didn’t really use test-driven development, I did start writing unit tests very early, and once in a while did write the test first (specifying correct behavior) and then the code. And when I find a bug in the low-level code, I’ll add a test to make sure the bug is actually fixed, and not reintroduced by later changes. Looking back at the development diary, I see comments like
  • Working on iteration. Hooray for unit tests.
  • And glad I made a unit test, it looks like I need to add a copy of the treasure if I’m mutating them
  • Again, hooray for unit tests. Did it for children, since that’s a kind of complex thing. And it caught a problem with setGoods: too.
  • Oops, that type broke stuff. Hooray for unit tests!
Next post, even more automated testing. (The previous post discussed some of the design changes in OSL.)

06 July 2015

Scripting Changes

King of Dragon Pass’s interactive scenes are the core of the game, and at their heart is the Opal Scripting Language (OSL). Since Six Ages will follow in the tradition of KoDP, it too will rely on OSL.

Or would it? OSL has some limitations, and I considered switching to Lua, which is a much more powerful scripting language (and widely used in games). If I was going to have to rework OSL (see below), why not just move to a well-known and reliable language? In the end, I decided to stick with OSL. Its syntax was designed around the needs of KoDP-style scenes, which makes it easier to convert from an author’s script to a runnable script. And OSL scripts can be saved saved in a single file but loaded individually, which didn’t fit the Lua model. (This is likely to be important on memory-constrained mobile devices.) Finally, I already had an OSL compiler and interpreter.

They just needed updating. One of the biggest problems was that the number of scripts and variables had to be known when a game was saved. This made adding new content difficult. This meant some significant changes under the hood to allow for future growth.

I also wanted to make scripting easier to use. It was already safe (in that problems with a script were very unlikely to crash the game), but you sometimes needed to jump through hoops to work within the syntax or implementation details (you could only get the properties of some variables, not all). Placeholders could be easier: <duel/fight> rather than <d2:duel/fight>. And could allow nesting: <it was not {t}’s fault/{t} was blameless>. Or even allow music to change in the middle of a scene.

Another usability improvement would be to allow scripts to run other scripts, or to check the scene queue.

A few small changes would allow the clan questionnaire to be a script, rather than custom-coded. And we could tag scenes, for example to make sure they appeared at random at the right dramatic phase.
scene: scene_1Friendmaking
scene001, left, [CouldBefriend <> 0], @Diplomacy, @actOne, @staple, mayRepeat
music: "CouldBeGood"
[SceneUsed(scene_1Friendmaking)] {
  f = false
} else {
  # Never been used, so this must be the start of the game
  f = true
}
And there was another reason to rework OSL, which I’ll get into next time.