Lock and Key Dungeon Generation

link to the past

Awhile back I had gotten into playing some rom randomizers. These are programs made by retro game enthusiasts that take old games data and using some clever programing rearrange that game to make things different. Pokemon has one that will change what types pokemon are, or where they appear. But I have been pretty taken by the randomizer for The legend of zelda: a link to the past.

The game is made up of a series of dungeons with items and bosses. You gotta go through the dungeons, getting the stuff and defeating the bosses to eventually save the world. What makes it interesting is that you can diverge from the order if you feel like it. You aren’t forced to do something. It’s just what’s intended. You can do dungeons out of order and indeed my preferred route in the dark world is 1, 2, 4, 3, 6, 5, 7

With the randomizers however all item locations can be shuffled. Along with many other things but it’s the shuffling of the items that I really like.

The obstacles that need the items stay in the same place. So rocks and wooden pegs don’t get changed. The location of the gloves to lift the rocks or hammer to pound the pegs is changed though and that means that the entire game has a new unknown hierarchy of items to find. Generally the later levels take more obstacles to overcome to complete so the order is somewhat maintained but things can nearly be anywhere.

The logic is incredible as well. There won’t be an arrangement of getting the items that is impossible to solve. The key to a door basically is never behind the door it unlocks. Except when it is inconsequential like the big key in some levels may be locked in the big chest but then you don’t need the key so who cares?

While playing these randomizers I was also working on an idea for a grid maze generation algorithm based on really simple rules. Pick a spot on a grid and then roll a d16. Which will give us a random 4 bit number. Each bit corresponds to a wall for that cell. For every side without a wall go and do the same thing there.

The result was a very organic looking maze generation. That was really cool but also very chaotic

first maze attempt

I’d also played around with the idea of not doing pure random but rather doing weighted probabilities. So some cell configurations would be more likely than others. This produced noticeably different results and the types of structures made depended greatly on these weights.

Another aspect that was explored was doing lists of cells as well. So instead of randomly pulling from probabilities. A predetermined list of cell walls was drafted and then looped over. This had some really bizarre but amazing results. Sometimes these combinations would result in incredibly complex repeating patterns. Much like those found in conways game of life.

Repeating pattern

Once it even produced a fantastically large repeating pattern out of a list of 76 cells in the pattern

Huge repeating pattern

Overall this method of generation resulted in a lot of very organic looking mazes but also with no clear structure or design. Not what you would call a dungeon like those in zelda or even metroidvanias. This type of generation might lend itself to very organic levels though. Like an overworld or a literal cave. Since its chaoticness is structured but incomprehensible. Kinda like nature.

After this doors were introduced and I went with a room based concept instead of handling things on a per cell basis.

Room mazes

This gave it a lot more structure in ways and the results were more like what I would expect a dungeon to look like. Also made a few more graphical versions because it was neat.

Isometric maps

However the same issues of lack of structure was present.

The mazes looked like dungeons but this was only the shell and I want to see it filled with locks, keys, obstacles, enemies and items.

After studying some dungeons and doing research into what other people had found on dungeon design, I’d determined I would need really advanced A.I. which was interesting but outside of the scope of what I wanted to invest.

The project was shelved until a new idea occurred. It was so difficult to find a plausible path through the dungeon because I had made the dungeon first and tried to find a path. Instead it might be way more possible to make the path first and fit the dungeon as you go.

Full maze

Now the maze is generated as the path is created. The path generator is prevented from doing things that might make the path impossible. It has to place a key before it can go through a locked door for instance. Crossing over a path that would mean circumventing a locked door will create a one way door to compensate automatically. Keeping the path integrity by not allowing backflow down the path.

generation process

This leads me up to the current exciting phase of figuring out the basis of the A.I. path generator. In a sense this is me figuring out what senses it has, the things it needs to be able to detect in order to make dungeons.

No matter what type of A.I. I go with these sense will need to be implemented. They’ll first be used to give me an idea of what I’m doing when I generate a maze. Then it will be easier to pick an A.I structure to generate them. Really like an evolution algorithm idea though, where it makes X versions and then you pick the ones you like and uses those to generate X more. Maybe eventually even a game? Game tech is fun because you don’t need to design it for anyone to play :D

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>