Cellular Dungeon Generator

Have a project in the works but not much media? How about an idea you are turning into a project? Maybe a game design document you want to start with. This is the place.
Post Reply
User avatar
Renavoid
Posts: 60
Joined: Sat Feb 23, 2013 7:48 pm

Cellular Dungeon Generator

Post by Renavoid »

In another post I was making some preparations to work on a project which I split into separate chunks. I have since dropped Unity (though not the project), though still have this sample of the algorithms I was working with for dynamic dungeons. The art assets are not interesting, but it works more or less as intended.

The idea is to have dungeons which can be "infinitely" grown as a user progresses through its stages - but the edges should be more maze/cave-like than a standard dungeon with long halls and large square rooms. I discovered an article on cellular automata which used particular cell rules to carve out, and then smooth out cave-like maps. It was intended on a macro scale, but I morphed it into a micro scale and stuck lots of them together to create "seamless" winding mazes.

The Javascript showing the 2D bird's eye of the dungeon generated can be found here: http://rusyninventions.com/demos/cellular-automata/ Refresh the page to re-seed and get a new dungeon room.

http://rusyninventions.com/demos/cellular-dungeon/ uses the algorithms on terrain heightmap generation to carve out the walkable areas - limited to a 5x5 grid which persists. Refresh to see a different seeded world. Note that the character is on top of the terrain in the demo instead of down in the "caves" because it's easier to see what the terrain looks like from above. Careful not to fall off! Walk towards the seams of the terrain to see a new chunk appear.

http://rusyninventions.com/demos/cellular-dungeon-v2/ allows you to fly around to see how terrain generation occurs. This one is not limited to a 5x5 grid. And here, the terrain does not remain rendered. At most, you will see 5 terrain grids at a time (depending on intelligent-randomly generated walls). What's more, if you go back to a terrain piece you were just at, it will re-render and be the same. But, if you leave for more than 10 seconds, the terrain will randomly generate anew.

This project had a very specific purpose, and I think it turned out quite nicely, even if it isn't pretty to look at.
The winds of change are blowing; will you heed their call?
User avatar
vitinho444
Posts: 2825
Joined: Mon Mar 21, 2011 4:54 pm

Re: Cellular Dungeon Generator

Post by vitinho444 »

Wow.. it looks really awesome! I've always wondered how procedural worlds are created, you followed some kind of tutorial? Or went hardcore by yourself? Either way, congrats ;)
My Company Website: http://www.oryzhon.com

Skype: vpegas1234
User avatar
Renavoid
Posts: 60
Joined: Sat Feb 23, 2013 7:48 pm

Re: Cellular Dungeon Generator

Post by Renavoid »

Thanks. I didn't follow any specific tutorial. I did follow small tutorials along the way to learn how to do things like alter Terrain at runtime and stitch the pieces together, but the implementation of the construction and destruction of inter-connecting pieces is just me. I started to write it all up in a blog. But, I don't have the patience for blogs and wound up only writing 4 of the 5 posts about the project! I know. Terrible, right? I suppose you could read the four parts that I did write up, though. Cellular Dungeon Series The content itself is finished. The blog only goes up to the 5x5 demo (it also includes at least one youtube video describing how things work). I just didn't want to blog regularly anymore.

Originally, I was looking at methods using voxels (volumetric elements) like Minecraft, EverQuest Next: Landmark (and EQN itself), and the 3 million other Minecraft clones, but they didn't suit my specific needs.

Instead, I focused on Cellular Automata, which are basically models of a given state. So you are given a 3x3 grid, and each cell in this grid has a rule that it must obey. The rules basically govern whether or not a particular cell should be allowed to remain On (Live) or if it should be turned off. The automation part would be where you run through the whole grid and apply the rules to each cell X number of times. Some are infinite, (see Conway's Game of Life), and some are finite, like mine.

Rules would be something like:
  1. A Cell can remain Live if at least 3 cells next to it are Live.
  2. A Cell can be switched Live when it is Dead if at least 5 cells next to it are Live.
  3. A Cell on the edge of the grid is always Live.
So you would take a grid much larger than our 3x3 example, go through every cell in the grid and randomly set the cell to either Live or Dead. Now we apply these rules to every cell in the grid and see what happens. Rinse and repeat as many times as you like. Changing the rule criteria changes what shapes emerge. In the Javascript link above, you can see each step as it first uses a very vigorous set of criteria to greatly shape the grid, and then a series of more lenient criteria to smooth the edges (it also does some cell division to make the smoothing more apparent as higher resolution).
The winds of change are blowing; will you heed their call?
User avatar
vitinho444
Posts: 2825
Joined: Mon Mar 21, 2011 4:54 pm

Re: Cellular Dungeon Generator

Post by vitinho444 »

Wow very cool indeed!!

Yeah I've tested your javascript demo and I ran it and it began generating a random cave, then started smoothing the areas, I enjoyed it very much :).

I imagine this is something near "impossible" for a normal 3d terrain like Unity to behave as a Minecraft terrain per example. Maybe if you scale the 1m cube size of the minecraft terrain/world you get something a little more realistic?
My Company Website: http://www.oryzhon.com

Skype: vpegas1234
Sim
Posts: 412
Joined: Sat Dec 26, 2009 5:37 pm

Re: Cellular Dungeon Generator

Post by Sim »

feels left out. I don't have Unity!!


I made a maze generator in php before -_-
oRPG Creator - Make Your Own Browser Game
oRPG Creator on Facebook
User avatar
Renavoid
Posts: 60
Joined: Sat Feb 23, 2013 7:48 pm

Re: Cellular Dungeon Generator

Post by Renavoid »

Sim, I did this with just the free version of Unity. Or do you mean you don't have/can't get the Unity web-player to see what it looks like? It's not pretty, just an interconnected version of the javascript bit.

Yes, lots more smoothing can be done, and it's certainly very different from Minecraft. I actually didn't want to make Minecraft, so that didn't bother me. My thought was actually that these lines would serve as guidelines, and then follow-up operations would render random rock outcropping meshes which generically follow the shape, but add realistic rock-like noise. Since I've left Unity though, I won't be using this approach at all in the future. I'll probably take the same knowledge and re-apply it in a new, fresh, and more complex way.
The winds of change are blowing; will you heed their call?
User avatar
vitinho444
Posts: 2825
Joined: Mon Mar 21, 2011 4:54 pm

Re: Cellular Dungeon Generator

Post by vitinho444 »

Renavoid wrote:Yes, lots more smoothing can be done, and it's certainly very different from Minecraft. I actually didn't want to make Minecraft, so that didn't bother me. My thought was actually that these lines would serve as guidelines, and then follow-up operations would render random rock outcropping meshes which generically follow the shape, but add realistic rock-like noise. Since I've left Unity though, I won't be using this approach at all in the future. I'll probably take the same knowledge and re-apply it in a new, fresh, and more complex way.
Good luck then :) I'm having a hard time getting out of Unity to UDK because it's so much user friendly...
My Company Website: http://www.oryzhon.com

Skype: vpegas1234
User avatar
Jackolantern
Posts: 10893
Joined: Wed Jul 01, 2009 11:00 pm

Re: Cellular Dungeon Generator

Post by Jackolantern »

Wow, very impressive indeed! Procedurally-created content is handy for all kinds of games :D
The indelible lord of tl;dr
User avatar
Renavoid
Posts: 60
Joined: Sat Feb 23, 2013 7:48 pm

Re: Cellular Dungeon Generator

Post by Renavoid »

Thanks. Oh, one thing I neglected to mention about those demos - the random generation is actually semi-intelligent. When a chunk of terrain is generated, it first looks at all of its neighboring terrain chunks to determine if it needs to have an opening to that chunk or not. If a neighbor is not present (was not generated) then it will decide randomly whether to make an opening or not. Also, it is rare, but it's possible for the terrain to be generated such that a dead-end is generated around an opening. The algorithm for generating the terrain itself has been scaled and altered enough times so that the areas are not always wide-open like they frequently are in the javascript demo, but not so dense that the dead-ends happen too frequently. Now, if there's a dead-end, it should still be possible to back up and find another route (usually... the game would have an escape feature just in case).
The winds of change are blowing; will you heed their call?
Post Reply

Return to “Project Showoff Tier I”