Procedural Riddle Generation II

Where we left off last time we had a series of clue planned. For a 2×2 puzzle, for example, the first clue might need to be “Top-Left is west of Top-Right and north of Bottom-Left”, and the second is “Bottom Right is next to Bottom-Left”. To do this, the game then finds a synonym for each clue component, all of which have a variety of synonyms. For example, a lizard can be referred to as a “reptile”, “sticky footed one”, “cold blooded one”, “scaly one”, “one who regrows tails” or “tree climbing reptile”, whilst a skull may be a “dead one”, “cranium”, “one of bone”, “memento mori”, “reminder of mortality” or “deathly visage”. One is chosen at random each time a particular block is in a puzzle, with plurals added appropriately.

An earlier release had a number of different ambiguous clues. One was “the reptile” – this could be a snake or a lizard. If only one of the blocks had generated that would be fine, but there was always the risk that both would generate and therefore the solution would be ambiguous until you’d tested both, at which point the player would know from that point on which was correct and which was false. A few people actually suggested to me that ambiguity of this sort was acceptable – the player needs to figure out the identities of vague clues – but this is a very bad idea. It fails to meet the three design goals I mentioned in the first part of this series, and given that some puzzles will be associated with traps in the coming version 0.4, I cannot allow any trial-and-error where’s something to stake.

It reminds me of the idea of “Guess what the teacher’s thinking”. Imagine a teacher says “Name a classical composer”. You say “Beethoven”, and the teacher says “Wrong! The answer was Mozart”. You did answer the question, but the question wasn’t worded well enough to make clear to you the range (or narrowness) of the expected responses. It question implied there were many possible answers, but since there was actually only one, a less stupid question would have been “Name a classical composer born in 1756”. This would be the same issue – the “lizard” clue could mean either, but only one will be accepted by the game. Another example of this was the “shadowed moon”. This was meant to be the eclipse, but it could be interpreted as being eclipse, crescent, half or even gibbous moon. Much too unclear. Another clue that I never realized was vague came to my attention in a very unusual way which I think says something interesting about the different ways people “read” games.

Boar

This is a young boar (this is also the only blog entry which will have such endearing pictures). It has stripes. One of the clues for a boar was something like “the one with the young stripes”. I realized most people might not instantly know this, but with a little bit of research, or a process of elimination, should have made this clear. However, consider the three variations of the boar block – two of them have things akin to “stripes”.

BOARS

One player suggested they found the clue confusing because one of the boar designs didn’t have stripes, and this made them wonder if the variations of image on blocks had some impact on the clues. Nothing like this even remotely occurred to me before release, but it made me realize (not for the first time) that others will “read” a game differently to you, especially if you’re the designer and have been staring at the game for a long time. I therefore removed this clue because it raised a little confusion about the relationship between the clue and the particular variation of the block.

Similarly, for those who follow the blog you may know of the endless confusion and debate over how to work one particular clue. “West of” is fairly self-explanatory, but there are a large number of clues that state one block is “opposite” another. This is meant to refer to a block that is orthogonal and as-close-as-possible to another block. For example, if you have a 2×2 clue, then the bottom-right could be “opposite” the bottom-left or top-right, but not the top-left. The lower-level clues were designed to build up an understanding of what exactly this term means that could then be applied to the higher-level challenges. This went through a number of different iterations. I tried “next to”, but that meant that if there was a gap between two pressure pads – even if orthogonally adjacent – some players were confused about whether this classed as “next to”. I also tried “adjacent to” but some players thought this meant only left-right, not up-down. “Touching” was equally unclear, whilst “proximate to” was vague and could include diagonals, conceivably. I don’t know if “opposite” is ideal, but it’s certainly less ambiguous than a bunch of the other options – it implies there are no other blocks in between A and B, and that it can be vertical as well as horizontal. This was another example where both my “reading” of the game differed from that of others (I thought “next to” was fine, at first), and that clues need to remain cryptic, “in character”, without being unclear. Of course, every clue could say “A is either left, right, up or down from B, without a block in the middle, and potentially with a blank tile in the middle”… but somehow that just doesn’t have the same ring to it.

Procedural Riddle Generation I

I’m now starting a little retrospective series on the last release. My approximate plan is to this week start with puzzle/riddle generation (part 1), finish it off with part 2 next week, then move onto a post about generating ziggurat interiors. We’ll probably then have an entry about designing the extra languages – aesthetically, not in terms of code – and at some point later, when languages are fully implemented, I’ll be talking about them.

So, this first entry will detail the design goals of the puzzles and the process of creating the puzzle solutions, checking the solution will be valid and assigning clues to them; next week’s entry will conclude this two-part series by covering how clues are generated and written by the game, and how to ensure clues are clear, even if they are cryptic (two apparently contradictory goals).

Victory

I had three objectives when beginning the process. These will also be applicable for future forms of puzzle too.

Firstly, all puzzles should be solvable on the first try. There must be no trial and error. Some puzzles may, later, come with traps of varying severity and lethality (traps will likely be integrated into puzzles for 0.4); they must be avoidable with perfect play. This is not to say they might not take a long time to solve, but you should always be able to submit the correct answer first time. If there is any ambiguity, there need to be more clues, or the puzzle needs reworking. Given the clues, puzzles can be cryptic, but they must never be ambiguous.

Secondly, the puzzle must have only one solution. This is not just because having multiple solutions makes a puzzle easier, but also because getting the software to recognize all solutions that meet the clue requirements on the fly, rather than upon the generation of the puzzle, was a far more challenging task.

Thirdly, all puzzles must use the smallest number of clues possible. That is to say that if the game provides you with four clues, but one is superfluous, it should be able to remove that clue and keep paring down clues until you have the bare minimum required. This once again increases difficulty, but also reduces the amount of data (potentially duplicated data) the player needs to process.

There are three stages to the puzzle, of which the second stage is the major focus. The first stage is deciphering the riddle – for example, understanding that “the creature of poison arrows sits north of the many-legged one” means “a frog is north of a spider”, which we’ll talk about next time because those phrases are generated quite late in the process. The second stage is working out the placement of all the different blocks based on the clues you’ve been given (which, as above, should be only just sufficient to solve the puzzle with), and the third stage (the most minor) involves maneuvering the blocks into position. The third is just a minor Sokoban puzzle in some situations, so let’s skip over that one.

The first stage in generating a puzzle is to determine how difficult a puzzle should be placed. There are two sizes of ziggurat, “medium” and “large”. I originally intended to have “small” ones as well, but I found them a little too small to really feel like a full dungeon (using “dungeon” in the broadest sense); whilst that feeling would decrease in future versions once I add more room types, for the time being we’re just going for medium and large. A medium ziggurat has four floors and a large has five. There are five different “levels” of puzzle, 1-5, of which level 5 are considered “boss” puzzles and can only be placed on the penultimate floor (so the third floor in a medium, or fourth floor in a large). The final floor always houses either a clue, or a secret item – in later versions there will be far more variety and these peaks will include treasure, loot, weaponry, various other items, and potentially “boss” level NPCs who have also made their way into that same ziggurat. For now, however, three ziggurats contain secrets, whilst the others contain clues directing the player towards those with secrets.

The floor the puzzle is being generated on determines the level of puzzle; harder puzzles appear on higher floors. It is weighted to give you a logical progression of puzzle difficulty in each ziggurat, but also to allow for unusually difficult puzzles to rarely appear on each floor (similar to “out of depth monsters” in Dungeon Crawl). I will focus on the placement in the later entry of ziggurat dungeons, but the game basically draws a route from door -> stairs or stairs -> stairs and places rooms of appropriate difficulty along that route. Some ziggurats will have a tougher combination of puzzles, some easier, but given that I’m making a procedurally generated game I certainly don’t mind a little variation, and once other factors are in play – such as traps in 0.4! – difficulty should equal itself out more easier than with just a single challenge from the puzzle rooms.

The next stage is to pick a puzzle. There are several for each level. For example, Level 1 puzzles can be 2×1, 3×1, or 4×2. Level 2 can be 2×2 or a “cross” (like the five dots on a die rotated 45 degrees). At the higher end, the Level 5 boss puzzles can be 12×1, 3×3, 5×2 or a “star” (3×3 with the middle removed but an extra pressure pad on each edge), as shown below:

BpssroomsOnce it has chosen a puzzle shape, it then selects correct blocks at random from a series of all blocks. So, if we have a 2×2 puzzle, it might select a Full Moon, a Snake, a Spider and a Winter Tree. Full Moon might be classed as block a, Snake as b, Spider as c and Winter Tree as d (the puzzle being ab on the top level, then cd below, to form the 2×2 square). The game then picks from a variety of what I’ve been called “clue orientations”. For 2×2, for instance, it may pick a particular corner then give two definite orientations next to it. So, if it picks the top-left corner, it would generate a clue (details next week) that says the top-left is on the east of the top-right and north of the bottom-left. It would then know that the second clue needs to relate the bottom-right tile, but because the earlier two clues are directional, this final clue doesn’t need to be.

In any case where a non-directional clue can be used, the game prefers to do that because it’s automatically more difficult. Saying “X is west of Y” is simpler than “X is opposite Y” and having to figure out whether that is north, south, east or west according to the rest of the clue. However – and 0.3.1b fixed a few issues like this – it soon became clear you simply had to have some directional clues. For example, the 3×3 grid is symmetrical in all four orientations, to simply saying “opposite” for all clues would mean the clue could be solved in four orientations. I felt this both made the puzzles easier, and possibly more importantly, would actually be a lot harder for the game to check if there were multiple solutions. For more advanced sets of pressure pads, there are a large number of potential methods by which the game can produce the clues. For example, for a 3×3 grid, it might create a clue for the top row, a clue for the bottom, then go from there; or it might create a clue for the top-right corner, a clue for the bottom-left corner, then three more; or it might create a clue for the three in the middle (vertically) then work out from there. Obviously the larger the pressure pad pattern, the more clue orientations there are, but the harder it was to make sure all clue orientations can be solved. Despite my best efforts 0.3.0 had a few that couldn’t be solved, but those were all fixed for 0.3.1’s release. Lastly, each puzzle can only contain a particular block once, so you can never get two of the same block in one puzzle, although variations upon a theme – ziggurats of different sizes or trees of different seasons – are allowed. This is again to be remove ambiguity – if there are two frogs in a puzzle, there might be multiple solutions, which means trial and error might come into it, and that was unacceptable according to the design plans at the top of this entry.

Thus, once it has selected it blocks and gone through a number of possible permutations, it then develops the clues. Next week I’ll be going over this process, and the tricky balance between keeping clues cryptic, but also unambiguous.

Also, 0.1.3c is out with a few small bug fixes, and one big one which nobody spotted but I realized was there, which I’m afraid breaks save compatibility. ENJOY, INTERNET!

June Progress II

The last week  has seen more coding than much of the last month – having lacked the internet for the past week, very little else has been done aside from it. As ever, the release is a mix of things I’m making public before-hand and a few secrets I want people to find, but here the updates I can share. I’m aiming for release probably around late July at the moment, but it might get pushed into early August. The first half of July is almost entirely full with academic work, so we’ll just have to see how it goes. I’ll be doing a lot of playtesting towards the end of June once I have a pretty stable build, but ziggurats are looking all but finished.

Puzzles are 100% finished. There are five “levels”, finishing off with “boss” level puzzles. Even when I know how to solve the puzzles, they still take me some thought. Playtesting it with people who don’t know how they are generated under the hood have found them so far genuinely challenging and really interesting to solve, so I have high hopes. They include a vast quantity of procedural art (something like 200+ images?) and over 300 possible puzzle permutations, and that’s not even counting the clues. You’ll have to play A Lot if you want to see even a small percentage of these things.

Ziggurats are 99% finished. They generate the entire buildings, all puzzles generate (as above), the structures inside and outside match up, dungeons are three-dimensional, which is to say staircases lead directly up and down, not to random points on the floor above, and some areas can only be accessed from floors above or below. It makes for a really interesting structure to explore, and it’ll be all the better in the future once a greater variety of rooms exist. Special ziggurats also have secrets atop them, whilst by the end of tomorrow other ziggurats will have clues pointing you towards the special ziggurats if you’ve taken the wrong one. In the future these will be treasure rooms etc. Lastly, as well as “Look-up” graphics for blocks, I’m adding ones for doors, iron gates, and a few other things. They look pretty cool.

A basic inventory system is now in place. This is not what it will look like in the future, but suffices for the time being to deal with the few items now in the game. It won’t be redone for the release after this (probably), but certainly will once a decent number of items actually enter the game.

Next update will be next Monday, and since I now have internet at my new place, they should be regular until release (I know I keep saying this, and failing to keep to it, but I’ll try). By this time next week, ziggurats should be totally finished and I should be onto bug fixing and optimizations. I’ve had a very crazy idea for hugely reducing save/load times I need to try out, amongst other things.

As a final note, I’ve taken to streaming games on Twitch. At the moment I’m doing a Dungeon Crawl Stone Soup extended endgame run, but I might stream coding and playtesting or similar in the future if people are interested, and it could be a cool way to just chat with you guys! Let me know what you think, and see you next week (or on a stream). My account is http://www.twitch.tv/maasbiolabs, and I’ll probably be streaming some DCSS half an hour after this blog entry goes up…

Early June Update

Short update-focused blog entry today. I’ve been working on a bunch of things, some which are bug fixes and small features, some of which are further development of the procedural graphics in the ziggurats, and some of which are secret for now. Here’s a list of what’s been done over the last week, and what the goals for next week are. Next week’s blog entry will be something a little different, hence why this week’s is both a retrospective for the past week’s work, and a… prospective?… on next week’s.

This week:

Seven new procedural graphics have been finished off for ziggurats, leaving all the block graphics finished. These include various creatures and locations, each of which has a wide variety of different poses, positions or permutations. As ever, generated art is a central part of the game, and I’m pretty damned happy with how these are looking.

Ocean travel is now temporarily enabled for the next few releases. In the future, you’ll  need ships or similar to travel, but for the time being, you can travel across ocean squares when you’re in the fast travel screen (‘T’). This ensures you can get to all the imporant ziggurats in this release.

Ziggurat rewards have been largely programmed in. Right now, these are either a) secrets, or b) hints towards which ziggurats you can find secrets in. Naturally in the future there will be a far greater variety, but for the time being, 0.3 is focused on locating these items.

Various bugs have been fixed, and various small features added, generally in the direction of clarity and ease of use. A few small things have also been removed as they aren’t fully implemented yet (for instance, the skills menu), to focus on the exploration in this release.

This coming week, I’m going to be focusing on finishing off all the possible puzzle generation. There’s a very large number of components coming together so that the blocks, clues, codewords, puzzles, pressure pads and gates all combine correctly, and ensuring the game places puzzles of the correct difficulty on appropriate floors. Expect easy puzzles at the bases of ziggurats, and ones that pretty much require a pen and pad at the top. I’m also going to be trying to deal with a few more little bugs and features, and generally continue cleaning up 0.3 for release in a month or so. Next week’s blog entry will likely be a tribute to one of my favourite authors, Iain Banks, who died this week, but after that normal service will resume. By the time of the next URR update all aspects of ziggurats should (fingers crossed) be completed, at which point I’ll give a little postmortem on that process, and keep you all updated on finishing things for this release off. See you then, and remember – clues might be hidden anywhere.

Moon

Ziggurats and Skulls

Despite my relative silence this past week on Twitter/Facebook, I’ve been doing very little except coding. As I think I mentioned, I’d given myself a mini-crunch-time to see how much of the ziggurats I could get done by the end of yesterday. The things I wanted to get done I didn’t finish, but a ton of other stuff I worked on instead did, so I’m happy with how it all turned out. I’ve created about half a dozen new block designs, and I’ve started the actual level generation for ziggurats! I debated showing an aerial image of one of the interiors, but that would give far too much away, as so much of the emphasis here is on exploration.

However, the current situation is that you can find your way from the bottom floor, to the top, via a number of puzzles, which have a selection of blocks, pressure pads, gates, clues inscribed on the wall, and the puzzles get tougher and tougher as you go upwards. The gate-pad-block triumvirate is coded fully, and can be expanded to any potential puzzle. Currently only the easiest levels of puzzle generate (2-4 blocks), but I’ll be working on tougher ones in the near future. I also need to add a lot more to the ziggurats, so that not just every room is a puzzle, but now I reach a question, which is – how much should I put in ziggurats for this release? I could just put in puzzle rooms and blank rooms, which would be one thing, or I could put in puzzle rooms, rooms with statues, other features, hidden doors, treasure rooms, vaults, etc…

The problem is that for treasure rooms, there has to actually *be treasure* worth picking up, and that requires an inventory system; for statue rooms I have to code statue generation based on myth; for more complex puzzles I have to have multiple sources of clues, or clues that tie into mythology, or encyclopedia entries… and you get the idea. If I do make ziggurats “just puzzles” I want to stress that in the future there will be a lot more there, *and* a greater variety in the puzzles themselves, but I’m not really sure how much I have the time to put in for this release, given that history and myth generation, while coming along nicely, are still a long way from being finished. So, I have reached a conclusion – they will be puzzle-focused, but completing specific ziggurats will give you… let’s be vague… a component of a clue, and when you have enough of the components, then there will be some hints towards what later versions will hold. That’s vague enough for now. There will be things to “accomplish” this release, but many will hint towards later offerings. I think I have to stop somewhere for this release, and this is how. In later releases, when I add an inventory system, then treasure rooms will be added to ziggurats; when I add NPCs, then maybe other characters exploring them will be added, etc; it’s an iterative process.

For those who don’t follow on Facebook or Twitter, I’m aiming for the summer of this year for this release (probably/hopefully the most new content yet), to coincide with a talk I’ll be giving at the International Roguelike Developers Conference. I’m not sure what exactly will be in 0.3 yet in gameplay, but there will at least be puzzles to ponder, and something snazzy to find on the top floors of the ziggurats. In the mean time, here’s a picture of the “skull” block. I can’t recall how many different procedural variations of this image are possible, but it’s probably around a dozen:

Skull