Roguelike Procedural Level Generation

merrak

  • *
  • Posts: 2472

I got a few interesting comments on my Ludum Dare 35 game, "Evolution Dungeon", that gave me some ideas on how to take the concept further.

I had imagined a much more complex game than I could put together in 48 hours, so I had to scale the design way back. The final product was closer to the classic "Rogue" than the intended metroidvania/roguelike hybrid I imagined. Armed with some more time and direction, it's time to have some fun with procedural level generation.

Two goals of this project: (1) make a complete game, and (2, the primary focus) write the basic algorithms that will be used later to generate levels for Thief of Vallas.

In metroidvania style, the updated Evolution Dungeon will require the player to obtain power-ups in order to access deeper portions of the world. The problem is similar to the one in Hectate's "Metroid Generator", although for a different type of game.

The generation algorithm for Evolution Dungeon produced playable levels, albeit with a few quirks. I think the general outline is fine, but the implementation needs polishing. Here's the algorithm and example result:

Code: [Select]
1. Initialize a 32x32 grid of walls. Carve out a starting room in a random location. Mark a doorway along all four walls.
2. Until a suitable percentage of the map has been filled...
   2A. Pick an unused doorway at random*.
   2B. Pick a type of room to construct and its size. (Choices: Rectangle room, Ellipse, Junction, Corridor)
   2C. Check if there is space to build the room. If not, go back to Step 2.
   2D. Carve out the room. Mark a doorway along all four of its walls (except for the doorway leading to the previous room)
3. Place enemies, objects, etc.


If a uniform distribution is applied to pick the doorways (Step 2A), then this algorithm has a tendency to clump the rooms together.

The updated game will have an overworld/dungeon type layout. I'd like to have different types of dungeons and terrain in the overworld. An immediate nuance will be making sure the same overworld terrain is generated when the player returns to that particular area.

The player will need to obtain various items to progress (e.g. fire to make light to see in dark areas), so obstacles will need to be placed in a logical order. So far, here is the plan:

First: Write a bunch of maze generation algorithms, so that there is a nice bit of variety in the dungeons.. and also write the overworld generation algorithm.

And more important, second: Write an algorithm that generates a set of rules. I wrote a graph extension late last year that ought to power this thing. The graph will essentially house the instructions for all the dungeon generators--the order power-ups and bonuses should appear in, what technologies the player should already have, as well as obtain in this level, what monsters the player will encounter, etc.

The fun part is the solution to the nuance mentioned above. One way to ensure the same levels are generated when the player returns is to use seeds. When the player selects a new game, the first few accessible levels are assigned a "DNA sequence" via the "rules algorithm". This sequence will generate the dungeon. Dungeons that have been cleared will be removed from the gene pool. The first time the player enters a new dungeon, it can be bred from pairings of the surviving dungeons.

The desired effect is that the types of levels the player can easily clear are not generated later in the game--more like "death of the weak" than "survival of the fittest".

Bombini

  • *
  • Posts: 1295
Interesting!!!

merrak

  • *
  • Posts: 2472
I made some progress on the overworld map generation. I'm calling the algorithm "Islands and Bridges", which generates exactly what the name would suggest. The overworld is divided into a 10x10 array of screens. Each screen will have at least one large island, on which most of the action will take place. Bridges and little islands can join the larger masses.

Below are a few outputs with different parameters. The tests have all 100 sectors with the same parameters (density, etc.) In the next version, each sector can have a separate density setting, which will make for a lot more variety. I'd also like to be able to have some islands span multiple sectors--so there's still more work to be done.



The islands themselves are generated using something called metaballs. Thus, each sector has a single, connected landmass. I'll only need to worry about inter-sector connections.

Since I don't need to trace the edges of the metaballs, I managed to simplify the algorithm in the linked page. It's pretty simple to generate a landmass:

Code: [Select]
Place an initial circle and store its center x,y and radius in a list of circles. Set all points inside the circle to "land"

Repeat a set number of times:
      Pick a random circle from the list of circles, and a random point x', y' on the edge of the circle
      Pick a new random radius (r')
      Set all points inside the circle (r', x', y') to "land"
      Add the circle (r', x', y') to the list of circles

Use the metaballs method to smooth out the overlaps between all circles

Next up: refining the method to generate a more pleasing map, and connecting the dots with bridges.

Meestar

  • Posts: 652
Very cool.  I've actually done Roguelike dungeon generation like that found in Pok√©mon Mystery Dungeon, Chocobo's Dungeon, etc.  I've not done the metroidvania styled generation yet, but it does seem to be an interesting subject to approach.  I read an interesting article recently about how it might be possible to break down The Legend of Zelda: A Link to the Past and procedurally generate the world.
PM me if you require help.  I'm always glad to help out!

mdotedot

  • Posts: 1560
Indeed: Very Cool.

Unfortunately I probably don't have much time this Adventure Jam to incorporate your graph extension into it.

I would love to do some experiments with it when the grid = array changes. So what happens if there are two players in the maze and there are some blocs they can move and thus alterating the solved state. It really makes my head hurt when trying to do AI on that. Or when areas of the maze gets flooded with water (which is a dynamic thing).  First the path is available and during game play the path becomes unavailable. I would still like to compute if there is a path left.

I hope your graph extensions could help me solve those 'dynamic' grids. The way I now think I'm going to do it is to do a kind of brute force on each change of the maze/grid data?!

Any ideas on that?
Hanging out in the Chat:  http://www.stencyl.com/chat/

Proud member of the League of Idiotic Stencylers! Doing things in Stencyl that probably shouldn't be done.

merrak

  • *
  • Posts: 2472
I read an interesting article recently about how it might be possible to break down The Legend of Zelda: A Link to the Past and procedurally generate the world.

I'd be interested in reading that if you have a link.

So what happens if there are two players in the maze and there are some blocs they can move and thus alterating the solved state. It really makes my head hurt when trying to do AI on that. Or when areas of the maze gets flooded with water (which is a dynamic thing).  First the path is available and during game play the path becomes unavailable. I would still like to compute if there is a path left.

I hope your graph extensions could help me solve those 'dynamic' grids. The way I now think I'm going to do it is to do a kind of brute force on each change of the maze/grid data?!

Any ideas on that?

The graph extension implements A*. In fact, you can duplicate the existing A* extension's functionality by making a graph that corresponds to the scene's tiles. I'd expect the existing extension to be faster, though, but the graph extension can handle warps, named connections and nodes, multiple floors, and non-map related decision making.

Checking that a maze is solvable can be done by looking for the existence of a path from the player to the exit. A* appears to run fine in real-time, so I don't think you'd run into any problems even if you check for solvability every frame (although this shouldn't be necessary).

If the maze itself changes, then you'd just need to edit the graph and run A* again.

mebloo

  • Posts: 128
It's not that different. It's just that in a pure roguelike procedural generation, you don't really care about a lot of things and rules wheras for a metroidvania or zelda game that would be procedurally generated, you must add a layer of specific generation.

Let's say you have X number of items (or keys, or dungeons to complete, whatever) you have then X + 1 key points (the X + the start point in the map). You randomly choose a destination point in the whole map and generate the screens between those points, with the key rule that you can go through each screen in this path in the current state of the game, then you get to the next point and generate the map between the last point and the new one, with the key rule that you can go through all the generated screens with the new state of the game (the previou state + the item or power you previously got) and so on. In a latter step of the process, you generate some screens around the generated ones to populate the world a bit, with some secrets and so on.

The pros for a Zelda-like game is that the process can be reuse as well for the dungeons (with key points : keys to open doors, item of the dungeon, mid-boss room, boss room, and so on)

Hectate

  • *
  • Posts: 4643
I read an interesting article recently about how it might be possible to break down The Legend of Zelda: A Link to the Past and procedurally generate the world.

I'd be interested in reading that if you have a link.
I think he might be referring to the article I linked in my Metroidvania Generator topic:
http://bytten-studio.com/devlog//2012/11/30/lock-and-key-puzzle-generation/
There's several other interesting posts as well, such as how they generate a zelda-like overworld which also uses the lock/key structure; but also thematically resembles it (e.g. mountains at top, coast at bottom, one lake with a connecting river running south, etc).
:
:
Patience is a Virtue,
But Haste is my Life.
Proud member of the League of Idiotic Stencylers; doing things in Stencyl that probably shouldn't be done.

merrak

  • *
  • Posts: 2472
The Lock and Key Puzzle Generation is the one I remember and, given the way I'm generating the land, I think will be the better model of the two.

Here's what I have so far:


(click image for bigger version)

The red dot is the center of a sector, from which a number of circles are generated. The center of each circle is a blue dot, and will be reachable from a red dot. I completed the "bridges" phase of the procedure, which ensures that every red dot is reachable from every other red dot. As a consequence, every blue dot is reachable from every other blue dot.

I can then create a graph linking each red dot to the blue dots that were generated from it, and use that data to create the locks and keys.  The next piece will need to be some sort of "sever" procedure that isolates sectors behind locked doors. I'll probably use the terrain for this, rather than cutting the land mass.

Speaking of which, the land mass is below. The screen you're seeing is the sector highlighted in the image above.


(click image for bigger version)

The actual land is created with a "painting" procedure that uses the graph to figure out what kind of tiles should be placed. It's rather barren right now, since I don't have trees, etc. yet. But--it's coming along 8)

CmdrWhitey13

  • Posts: 503
Here is another link to look at in terms of the generation of dungeons. Might help aid in this merrak.

http://www.nathanmwilliams.com/files/AnInvestigationIntoDungeonGeneration.pdf

merrak

  • *
  • Posts: 2472
Here is another link to look at in terms of the generation of dungeons. Might help aid in this merrak.

http://www.nathanmwilliams.com/files/AnInvestigationIntoDungeonGeneration.pdf


Indeed! I found a good solution to half of the third problem--creating a minimum spanning tree of connections between sectors using Prim's algorithm.

I think an update to the AITools extension will be in order soon. Some simple functionality--like being able to delete nodes--was missing from the set of blocks (although is available in code mode).

Bombini

  • *
  • Posts: 1295
Wow so cool!
I wish i would be capable of this.

Thanks for sharing!

merrak

  • *
  • Posts: 2472
Wow so cool!
I wish i would be capable of this.

Thanks for sharing!

I can imagine generating random ships procedurally, too.

merrak

  • *
  • Posts: 2472


While it may not look like much, I made some significant progress toward generating the overworld. Not everything is shown.

What is visible in the different colored blobs is a map of which tiles belong to which sector. Now that I know where the edges of the sectors are, I'll be able to place the "doors" in the appropriate spaces.

What is mostly invisible is a map of how to reach each sector. I used Prim's algorithm to create a minimal spanning tree mapping sector-sector connections. Hand-drawn example below:



Finally, A* is used to find a walkable path between each linked sector. These paths can be manipulated so that a passable road between linked sectors is guaranteed to exist. In cases where a sector should be locked, this road will be the only way to access the sector, and the door can be placed in the road.

Next up: Place some real terrain features

Meestar

  • Posts: 652

Actually it was a 2 part gamasutra article. I'll see if I can find it.
I read an interesting article recently about how it might be possible to break down The Legend of Zelda: A Link to the Past and procedurally generate the world.

I'd be interested in reading that if you have a link.
I think he might be referring to the article I linked in my Metroidvania Generator topic:
http://bytten-studio.com/devlog//2012/11/30/lock-and-key-puzzle-generation/
There's several other interesting posts as well, such as how they generate a zelda-like overworld which also uses the lock/key structure; but also thematically resembles it (e.g. mountains at top, coast at bottom, one lake with a connecting river running south, etc).
PM me if you require help.  I'm always glad to help out!