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!

The Roguelike Community, Kickstarter, Cult, and URR

A few months ago Cult: Awakening of the Old Ones, now known as Empyrea, received $34,000 worth of Kickstarter money. Despite this incredible investment for a largely “classic” roguelike project – and one from a developer without a large track record – the project has now all but collapsed, and indeed failed to really gain any steam in the immediate aftermath of the successful funding either. This blog entry aims to examine three things. Firstly, why this happened, and what is means for one-man development teams like myself; secondly the relationship of money in more general terms to roguelikes, particularly in the last few years; and thirdly what Cult and Kickstarter more generally mean for the roguelike community everyone reading this blog (I assume) would consider themselves a part of. This blog entry is a series of loosely-connected thoughts on these matters I’ve tried to give some kind of order to, and I would appreciate any/all thoughts on the issues within…

I first came across Cult at roughly the time I started URR. I think we began at roughly the same time, and quickly became aware of one another. We had similar scopes (in those early days) – massive procedural world, fantasy creatures, generated myth, legend, etc. I quickly came to feel we were, on some level, “racing”, or at least competing, to create this kind of game – something like an expanded DF adventure mode. I do not know if he feels the same way – and I hope he isn’t offended by my implying a rivalry! – but that has always been my feeling. A perfectly friendly rivalry, but still a rivalry. We both started with similar goals for world generation, and although he stayed with fantasy concepts whilst I moved towards “mostly-realistic-world-with-a-few-weird-goings-on”, our scope of ambition was very similar.

I’m a social scientist by trade (and soon, let us hope, to have a doctorate in that most noble of trades), but you don’t need to be one to know that all subcultures develop their own politics, their own important figures, and their own successes or failures that reflect on the rest of the subculture/community as a whole (I’m going to use those two terms interchangeably for the rest of this entry). Until recently, roguelikes were utterly free, and either ASCII, or tilesets. Since then we’ve seen two distinct trends. Firstly, you have the growth in “classic” RLs, a term I will use here to denote those that are grid-based and do not use special graphics, be they Cult, URR, Infra Arcana, Cataclysm, DF, whatever, that are in active development (except in Cult’s case, but we’ll get to that). Then you have roguelike-likes – Binding of Isaac, FTL, Spelunky, Rogue Legacy, etc. These use basic roguelike mechanics, but move away from the normal graphical styles. These games have generally not been free, and this has begun to drift into the classic RLs in development. No ASCII RL currently charges for downloads (or does it? Correct me if I am wrong), but they have been Kickstarted.

The two most obvious, and most noteworthy for the “classic” RL community, have been the ADOM resurrection campaign and the Cult: Awakening of the Old Ones campaign (there was also recently the successful Cataclysm DDA Kickstarter, but I won’t be covering that here). These were two very different things. Most agree ADOM is one of the most well-liked, well-played and “fundamental” classic roguelikes around. It’s over a decade old, has stood the test of time, and is routinely mentioned in sentences that include Nethack and Angband. That Kickstarter sought to “unfreeze” development, fix the small number of bugs the game has/had, and add a lot of extra content that the community would have some control over. Few were in any doubt about Thomas Biskup’s ability to deliver, after all-but-singlehandedly developing the original, and working on ADOM II since then. By contrast, Cult – and, it should be noted, the overwhelming majority of video game Kickstarters per se – was put forward by a developer without a track record of regular releases, roguelike development, or a game that already existed to build upon (only a very basic world-gen system). He promised a truly IMMENSE game that was only in its early stages – as, of course did I. The only difference was that I didn’t Kickstart, and nor did I ask for money per se (my donations button only went up after people actively asked to be able to donate).

Again, this is not meant as a criticism – had I kickstarted, I would on one level have been in an even “worse” position, having not even been able to code before beginning Ultima Ratio Regum. I specifically avoided going down this part for several reasons, many of which are becoming increasingly clear as more information about Cult’s slowdown become apparent. Firstly, I didn’t want to be financially beholden to anyone else. As mentioned in the 0.3 update, at this particular moment in time donations will speed up URR’s development, but they will not mean the game succeeds/fails, nor am I offering rewards (beyond the obvious prestige of your name in the Acknowledgements page in-game!). Kickstarters have to promise specific rewards, and that wasn’t something I was willing to do – because I knew what I wanted in the game already, and didn’t want to promise things I didn’t want to put in – nor felt able to promise, because I felt a project of this size lives or dies on the enthusiasm of its designer. In a sentence: Cult has proven this. By the developer’s own admission, he has simply lost interest/steam in the project. Now, I don’t know the specifics of this, but I know for sure what has kept my interest in this project going has been the ability to alter and mutate the game’s endpoint and interim objectives. We started high fantasy; then went to realism and army-building; now we’re onto something more like… I don’t know, Dark Souls meets Dwarf Fortress meets Europa Universalis meets Jorge Borges? The vision is clear in my head, though hard to articulate…

But we’re getting off-topic. Had I needed to promise things I wasn’t necessarily keen on, that kind of incentive would likely have failed me. For instance, if I’d promised all the army-building stuff, then – as several months ago – lost interest in developing that aspect, I’d have been financially and ethically committed to developing a part of a many-year game project I no longer game a damn about. That was not a situation I wanted to trap myself in under any circumstances. Alternatively, if I promise things I already intended to develop… what am I actually promising? The third option, in-game rewards – a sword you can name, or similar – seem the best option, but even those I’m not massively keen on.

This situation, I think, also highlights some problems with one-man development teams. I’m a one-person team, and were I to ever bring on a second person, that would be a particular friend who already assists heavily with design/gameplay aspects of URR, not someone recruited because of existing programming expertise. The one-person team comes with advantages and disadvantages. I have the last word on creative control; I get to do all the interesting parts, be it coding or artwork or anything in the middle; and I’m proud of single-handedly making a game. On the other hand, with a second person, development would speed up massively, and there is something very appealing about working within a multi-person development team. I dearly wish for the development of URR to speed up because there are so many ideas I wish to see in the game’s reality. Nevertheless, to finish off the pros and cons of working on one’s own, the last is obvious - as a one-man team, if I fall, nobody can pick up the slack, unlike with someone else involved.

This leads onto my next concern. A large number of classic roguelikes in development are one-person teams, and rarely two people. Any more, like Crawl, is a relatively rare situation. I fear Cult’s issues will discourage people from contributing to similar games in the future, just as – this being a longer-term prediction – I believe Kickstarter will lose its allure more and more as time goes by and fewer and fewer projects successfully reach completion. In my case, for example, were I to Kickstart there would be nothing I can do but say “I will complete the project”. You cannot look into my head and see how much I care about this project; there is no external way for you, the reader/potential donator, to validate the truth of my statement. You have to take my word for it. If there are lots of people developing the game that means that even if the first person gives up, others can keep working and bring in a new coder/artist/designer/whatever. This is why, long-term readers of this blog will know, I keep toying nervously with the idea of doing a Kickstarter, and will likely continue to do so for some time. Would I love to speed up the next year’s development? Of course. A successful Kickstarter, even at a relatively low level of a few $k, would mean I’d have to take on no extra real-world work this year to keep myself afloat, and could devote more time to coding. That would be great. However, I don’t know how I’d handle promises, managing donations, and the like. It feels like an extra layer of bureaucracy, and more importantly, an extra layer of pressure, that I don’t need.

I am confident ADOM’s Kickstarter will be fully successful, and I am equally confident about Cataclysm. They both have proven teams and, from what I can see, seem to be zooming through their promises and the new developments at an impressive speed. But these are both “old” games, in the sense that the Kickstarter wasn’t to really get them off the ground initially. I wonder where Kickstarter will be in a few years, and how willing people will be to place their trust in the largely-untested developer. As for me – URR will continue, for now, un-Kickstarted for the reasons above, and as a one-man team. But who knows – either of these may change as time goes on.

Next week, we’ll probably have a retrospective on the previous release, either on dungeon generation or puzzle generation. There’s a whole bunch of information I want to give about 0.3 now that it’s out, and one of those two is where we’ll be starting!

URR Version 0.3.1 released; on to 0.4!

Ultima Ratio Regum v0.3.1 released. Click here to go to the download page; changelog below!

Fixes:

- Doors are white/grey like staircases and therefore easier to spot.
- A number of ambiguous clue orientations have been removed.
- A number of ambiguous block synonyms have been removed.
- “Next to” and “adjacent to” have been changed to “opposite” – this should make it clear that correct blocks may face others from any orthogonal direction, not just left or right.
- Controls have been moved to the “Controls” section of the Guidebook and removed from Options.
- New inventory system added in anticipation of 0.4.
- Shift + numpad on the world map works.
- Stone blocks can move over downward staircases, removing a very rare bug where boss puzzles could be generated with an inaccessible component block.
- “You cannot grab onto…” message now prints correctly, instead of after a delay.
- Continued error messages after generating the [ More ] tag in the message log do not crash the game.
- New donators added to acknowledgements.
- You no longer need to press enter after a map grid has loaded.

 

From now on I’m moving to at least weekly blog updates. I also intend to include some blog entries on game design in non-roguelike genres, as well as development updates. I’m now working on version 0.4, which will be released before the end of this year! Click here to head to the development plan and see the future of the game…

Viewing Direction and Multi-Layered Tiles

Most roguelikes have a single z level and a single perspective. What I mean by the first of these is simple – each floor of the dungeon is flat, and there are never objects you’re too “high” or too “low”, vertically, to see. You cannot be too low to see over a particular barrier, and nor can you ever be too high to see something hidden below a ledge, for example. What I mean by the second, however, is that tiles look the same irrespective of the angle they’re viewed from. Viewing a wall tile from any angle is always a wall, whether you’re in the chamber the wall makes up, or the corridor that the wall is just one side of. Viewing a door will always look like a door whichever side you view it from. Obviously there may be modifiers – spells of effects that reduce your line of sight, or cause hallucinations, or similar – but the objects remain stationary in your view under normal situations.

URR is a little different. Originally I only had z levels, and that means certain areas would have to look different. This is much the same as Dwarf Fortress. Areas significantly above the player print as a filled-in ‘^’ icon; areas above you produce a ‘v’; whilst your line of sight is obstructed by areas that are too high above the player’s current level. This needed a lot of work to implement because the characters that need printing on each tile are not fixed but relative to the player’s height. However, there’s also a second aspect which is becoming increasingly important – tiles which look different from alternative angles, not just from alternative heights. In this first screenshot inside a ziggurat, you’re in the room with the relevant clue, and that displays correctly. That’s obviously what’s meant to happen, and it does so fine.

I1

However, it is possible for the player to get behind this inscription and view it from the back. This could lead to the possibility that depending on the generation of the level, you could see a clue from behind before you actually reached that room with the clue! If the wall containing a clue was also a wall of a corridor leading to the clue, then you’d get to see the clue early (odd, but not a big issue), but also the player character would be able to magically read an inscription through the wall, which I deem to be a real immersion-breaker, and also warn the player about the location of a puzzle room in the dungeon. At the moment that final aspect doesn’t matter, but in the future with resource management and potential enemies, that kind of foreknowledge about the terrain might matter. So, I had to find a solution to this.

I considered what exactly the problem was; seeing the inscription tile, without being in the room the inscription refers to, should not show it. My first trial simply made the game notice which wall the clue was on, and print appropriately. If it was on the southern wall, any player north, north-west, north-east, west or east of the clue would see the ‘?’ whilst any player south of the clue would see the brick icon. This resulted in this:

I2

Which worked great. What this meant, however, was that being below the inscription, even if you couldn’t actually see it, would have it reprint. Moving across the horizontal or vertical axis for a clue would make its appearance change even if there was no way to view it from behind. This worked to fix the original bug, but made other possible situations rather less elegant. If you were north of a north-wall inscription but couldn’t see it, it would still reprint. This meant that moving around would randomly keep redrawing the visible inscriptions according to each axis for each inscription that you crossed. As above, this did prevent the reading-inscriptions-through-walls error, but there’s really no need to hide the inscription in this case because you cannot view this from behind. I needed a system that would do what was shown above – inscriptions viewed from behind vanish – but only if they can be viewed from behind, so that the image below could also occur:

I3

Without changing from the above code, the inscription to the south of me would vanish, for no good reason. So, I returned to the process and iterated it again. I added in a new piece of code that had it check whether that particular square can even be seen from behind. So, if an inscription is on the southern wall, it checks if the south-western, southern or south-eastern tile from that tile are “open” to the player, and therefore can be seen. If any of these registered as being open, then it would revert to the solution in the second square – being behind it print the wall instead. However, if they are register as closed – in the third picture it is on the northern wall, and the NW, N and NE squares are all walls – it doesn’t need to print anything new because you can never view that inscription from behind. This solution ensured that only in the very, very rare situation where the inscription can be viewed from behind will it print a wall instead.

This is part of a much wider requirement for the game. There are multiple other types of tile that have to display differently based on the player situation. For example, doors can only display if the player’s height is less than or equal to the door’s location. For example, if there is an area with a height of 20, and levels 18/19/20 contain a three-level door, then standing atop that tile must hide it, whilst being anywhere below it must show it. This means a hefty part of the rendering code is basically for “exclusions” – for showing things if the player is at certain heights, or certain angles. Most tiles can be trivially displayed regardless of your angle, but a few tiles of these sorts require special treatment. Indoor areas, because they lack height, are significantly simpler because nothing has to be rendered specially to take account of the player’s location on the z axis. I haven’t yet decided how to handle things like bridges that you can walk under, but it’ll probably be handled like walking underneath tree leaves. I don’t yet know how many other aspects like this there will be, but I’m sure more will arise as time goes by. In the mean time, however, version 0.3.1 will be released in the coming week with a set of minor bug-fixes, and will be the last version until 0.4 later this year, in which – I am proud to announce – you will be able to die. I’m hyped.

Version 0.3, “Ziggurats”, Released!

After seven months of development, I am proud to announce the release of Ultima Ratio Regum v0.3! 

Main Additions:

16 hand-drawn languages, assigned to ancient civilizations.
Ziggurats, containing fully three-dimensional dungeons (multiple staircases which retain coordinates between floors). – Procedural generation of riddle puzzles in ziggurats. – Extensive graphical update for many items, accessible through the ‘l’ook function – stairs, doors, walls, stone blocks.
- Several secret items and hints towards future features and story.
- Over 100 tweaks, bug-fixes, and general improvements.

 

The focus of this release is the ziggurats. Version 0.3 is partly a “proof of concept” for procedural puzzle generation, partly experimentation with dungeon-generation algorithms more interesting than most roguelikes produce, and also a number of under-the-hood factors that work towards moving the game closer to what I want it to be. Naturally in later versions ziggurats will contain more than merely puzzles (and secrets), but they are the focus for this release. Remember to use ‘l’ (lower case L) to look at clues, and ‘g’ to grab blocks. Head to the link below to acquire the latest version, and do let me know what you think.

Click here to go to the download page.

Lastly, I’d like to make a request. If you like the game (or like my future plans for the game!), please consider donating. To do so either click the button on the right, or click HERE then click the button on the right. This is the first time I’ve explicitly asked for donations outside a passing comment, and the reason is as follows. I’m doing a doctorate at the moment, and going into my final year. However, I am self-funding, which has required me to search high and low for sources of funding. It’s been fine these first two years, but my rent has almost doubled this year, and combined with paying the registration on the course, I’m in a spot of financial trouble. I have no intention at this point to Kickstart the game (unless a lot of replies on this post encourage me to and would be willing to contribute), but any donations would go a long way to my living costs this year, to reducing the amount of paid work I have to take on to keep myself going through the PhD, and therefore boosting the amount of coding I can do. I’d like to have three more versions released in the next twelve months. The details of them are as follows:

0.4:

- Limbs – damage, healing, movement penalties/bonuses, etc.
- Expanded basic inventory system.
- Traps – trap rooms, lethal/non-lethal, gas/acid/spikes/poison/fire and more.
- Jumping/dodging/falling mechanics.

 

0.5:

- History Generation – war, rulers, families, artworks, discoveries, etc.
- Myth & Legend generation – deities, beliefs, heroes, monsters, etc.
- City Exteriors – cities show up on map, city walls can be accessed.
- Religion/Civilization generation – policies, governments, etc.

 

0.6:

- Improved World Gen – new biomes, swamp/plateau, natural wonders, redo polar, etc.
- Pyramids – map generation, light puzzles, second “dungeon” type.
- Special dungeon floors – hall, labyrinth, crypt, etc.
- OTHER COOL STUFF.

 

Whilst I know in the past I’ve stressed “donating will not speed up development”, at this particular point in time, and at least for the next year, it will. The game will be free forever, but if you like what I’m working on, please give it a thought. Your name also gets added to the “Acknowledgements” list in game! Thanks, and I hope you enjoy version 0.3. Please leave as much feedback as physically possible, here or anywhere else that URR has a presence, about what works, what doesn’t work, what you’d like to see in future versions, etc.