for the past few days straight I’ve been working solely on level generation. it turned out to be a lot harder than I expected, and I went in with the expectation of it being pretty hard already.
from the get-go I've wanted procedural levels. just naively placing fully random geometry would be guaranteed to create some very unpleasant or even impossible scenarios, depending on how carefully set the constraints are. due to this fact I decided to go for a technique of combining hand-made level ‘fragments’ or rooms together contiguously.
this is similar to what Spelunky does – have a fundamentally tile-based layout divided into chunks, such that each chunk is a hand-made room. rooms are then combined with a few connective rules to ensure that you have a guaranteed solution path. a key connective rule for Puddledash we decided on was to never have two ‘up’-traveling rooms in a row, as vertical movement in multiplayer platformers gets slow and often too punishing if e.g. one player slips and falls off a platform. we want these races to be close!
the big thing I aimed to exploit here was that we AREN’T making a tilebased game – I didn’t want rooms to have to be constrained to a grid.
initial test rooms we madeso my initial attempt was to have rooms built such that they contained ‘start’ and ‘end’ points. when a new room was added, it would just ensure its start point was aligned with the previous room’s end points. initial tests of this were super promising:
however, we ran into problems very quickly. there were 2 fundamental problems:
1) it's very hard to ensure rooms never overlap or spiral into each other
2) difficult to know whether we’d designed a ‘valid’ room with correct start and end points that would work in all cases
after battling with this for a while, I started to look at exactly how Spelunky does it, and what constraints are placed on each room. if anybody is interested in this and isn’t familiar with the article, darius kazemi made
a great breakdown of how it’s done.
spelunky-style level generator with placeholder rooms. solution shown in whiteI battled for a day with implementing a spelunky-style algorithm to get a guaranteed solution path before realising it made no sense for Puddledash. the room-generation rules in the article hinge on downward movement – if you want to ensure that levels can twist around on themselves (as we would like) things get more complicated, particularly with variably sized rooms.
it was at this point that I realised I could instead create a path that loops in on itself while still guaranteeing a solution by building a MAZE
plausible level path in magentaI settled on a fixed width and height standard for all rooms – my logic was that if we wanted rooms of different dimensions, they would only need to be integer multiples of the base width and height. then in cases where we had e.g. two rooms traveling left in a row, it would be a potential candidate for spawning a 2x-width room. I implemented the maze just using a basic depth first search graph traversal (for those inclined,
this post is a nice conceptual breakdown of it, plus implementation!). the level path is then found by solving the maze with another depth-first search.
- ..but hold on a second, didn’t we agree we never wanted two ‘up’ tiles in a row?
oh yeah, ok. well we can’t just remove additional ‘up’ tiles since we could overlap ourselves. let’s just identify where we have multiple ups in a row and stair-step them along the last direction of movement, shifting the level as we go.
=>
see?
it ẁor͞ks p̱̻̠̺e̛̝̗̮r̷̼̳̰̜f̱e̵̩͍͙͇̦c̜̲̼͔͕̖̜t̩̰̫l͖̀y̺̦͉̲̜̰ --
so basically screw the maze. I looked a little into modifying the directional heuristic such that it never goes up more than once in a row, but it was very difficult for me to make heads and tails of on a conceptual level and I’d been spending a lot of time in what felt like a hole. so I tried to shift perspective, searched around a bit, and came across the term ‘self-avoiding walk’, which is exactly what I’m after (given the upward movement constraint). the maze was essentially just a conduit for this all along.
the random walk code I wrote is not very tough to grasp but took a while to get bulletproof. the theory is:
- pick a random direction – if it’s not visited, add a room here
- if all possible positions from the current room are taken and we still need to place more rooms, backtrack (delete rooms) and try a new path
I also of course made sure it couldn’t pick ‘up’ more than once in a row. I actually ended up prototyping this in flash of all things for quick visualisations and so the recursion wouldn’t destroy my computer while I debugged it.
this gives a nice little path! the next hell-hole we collectively dived into was getting a consistent room ‘tileset’ to work with, but SafetySnail may put up a post about that later.
the last thing to do is bias our random direction sampling to favour horizontal motion over vertical, as our game is one of more scurrying than falling.
final horizontally biased level pathand that’s the level generation at present! always guaranteed to have a connected solution path, randomized and (hopefully) fun, particularly so once we get enough variation in each room’s tileset. I’ll also be adding probabilistic trap locations, so even rooms themselves will have a bit of randomised procedural cajun flavour sprinkled atop.
SafetySnail is working hard at creating some fun tilesets. in the meantime I’m going to be fleshing out the level gen to ensure you can’t take unintended shortcuts by walling in appropriate path edges, and some other ZANY trap / traversal mechanics.
also, as ever, we greatly appreciate all the interest so far! nothing warms us more than your cheerful moods.
Community
