Blog 549: The Procedural Dungeon of Y4 R02

Sometimes, the development process runs away with you. One day, you just want to make a weapon based only the vague assertion that “it should be the most powerful weapon in the game”, but then you have the bigger problem of finding somewhere to put it.

Then, after a while, you come up with the answer… And it’s terrifying.

The Mausoleum

So we’ve previously established that the Necropolis is a bonus area that will be unlocked in the mythical release R02 of Project Y4 (“soon”).

As its name implies, the Necropolis naturally includes tombs with readable inscriptions. The Dazzle Alpha, the area’s own micro-boss, guards a particular tomb naturally, as it stands at the “end” point — what else would be at the end of a graveyard but another tomb? On the other hand, with that tomb as a focal point, it would need to be made special…

System Shock 2 includes a level where a keycode is hidden around a(n annoyingly large) area in pieces — the player has to find all the pieces and assemble the code. I figured that this would be a good way to make the Dazzle Alpha’s tomb special: hide a code around the rest of the Necropolis, and have its input keypad there at the end.

Step by step, I inexorably introduced a fatal hole into the game. What could that keycode lead to?

I decided fairly early on that I wanted it to be some kind of dungeon, with a bonus challenge guarding the aforementioned epic loot best swords. But the reality of dwindling map space (at least, space that hasn’t been marked for Gala’s Trench and Skyward Fire) means that adding any more dungeons is impossible.

On the other hand… What do computer screens and node hacking mini-games have in common? They take a totally blank area and fill it… with life. So why not do the same thing again with “physical” elements instead of “cyberspace” elements?

There is one fairly chunky problem with this solution, and it’s one that I neatly sidestepped with the node hacking minigame’s objective. The collection of gems while hindered by enemies is trivial to overlay onto a generated maze — there are no preconditions for layout, you just iterate over all the open tiles and drop an enemy or a gem (or both) according to a set probability.

But a dungeon? Dungeons require an entrance and a distinct target location. (Okay, you could make a loop dungeon or defence or something totally meta, but let’s not get nasty.)

My initial hope was that, instead of only carving the the root from which the maze grows, I could also carve the end point and the two mazes would naturally grow together. Unfortunately, this was a stupid idea: by the very nature of the logic that chooses which untouched tiles are safe to carve into and which should become walls, this cannot happen. The Growing Tree algorithm is designed specifically to not create loops; it cannot know that the maze has two roots instead of one and that it’s now safe to connect some paths (but not others).

This is in annoying contrast to the Cellular Automata algorithm, which is great for this kind of thing, as demonstrated by preliminary work on a potential reboot of Asteroid Wars — all you need to do is pick points in the initial grid of noise and draw clear paths between them, and the algorithm will naturally generate smooth passages. You can thus guarantee that your pre-chosen points will be connected and part of the game area.

The dungeon is thus: there is a special containment crate at the opposite end of the dungeon from the entrance, which is initially protected by a barrier. The barrier is powered by two generators placed half-way through the dungeon. The player must destroy the two generators before they can open the crate.

That makes three locations that we cannot predetermine, since we cannot guarantee that those preset points will even be part of the final maze — no, they must be placed flexibly onto a finished layout.

The simple solution is just to iterate over all the cells in a candidate subsection of the maze — when the system finds an end tile (i.e. walls on three sides) where it’s safe to place a generator, it does so.

You’re right, there is absolutely no guarantee that it will ever find a tile on which it is safe to place a generator. However, it is probabilistically quite unlikely — the maze is currently 9×12 or so, and it grows up from the bottom centre, so it is pretty much guaranteed that there will be end tiles somewhere beyond the mid point (the growing tree maze algorithm is great like that — it greedily eats up the entire grid). The placement system just has to be careful to keep on going up the rows until it finds a good tile, rather than locking itself to one or two. As long as it starts in the right space and grows out from there, it’ll always favour that location.

The rest is rinse and repeat. The special containment chamber wants to be at the far end of the dungeon, so it iterates down from the centre of the top row rather than in from the middles of the sides. Bingo.

Now this dungeon is going to hold the Most Powerful Weapons In The Game (hint: it’s not the Dragon’s Tooth because the max weapon level in Y4 is 3 (out of 8) — future proofing!), so it has to be fairly brutal.

I cooked up the Artillery Bulwark because I am a fiendish bastard — they have a high minimum range, but there are so many of them that you’ll be constantly dodging shells, while their temporary barriers and heavy concrete damage reduction makes them a real pain to destroy. I also added two (invulnerable) factories constantly spawning shielded Deltas with cannons — plus there’s an initial wave of electronic warfare Deltas (stunning) and Betas with rams (fodder).

As I said, best weapon in the game. Got to make you fight for it! (Before it renders the entire rest of the game a cakewalk.)