Author Topic: Cave generation I've been using  (Read 16102 times)

Ex

  • IRC Communications Delegate
  • Rogueliker
  • ***
  • Posts: 313
  • Karma: +0/-0
    • View Profile
Cave generation I've been using
« on: May 17, 2014, 12:39:09 PM »
I was inspired by Krice's post to post about the cave generation algorithm I've been using recently. Rather than hijack his thread, I thought I'd post a new thread.

This is a pretty simple algorithm. I'm sure several of you already use it, but I thought I'd post it here anyway. It's not great, but it's pretty simple and can create some pretty good results.

Here's how it works: you select a bunch of random points on the map, and assign each point a unique ID number. Then connect the closest two points that have different ID numbers using a line with a width greater than 1. After connecting the closest two points, loop over the points and change the unique ID of any point that has the same unique ID as the second point in the pair to the unique id of the first point. Wash, rinse, repeat until all points have the same ID. Here's an outline:

1. Add random points to list with unique ID numbers
2. Loop:
  3. Find closest two points that have different IDs
  4. Draw line between the two points
  5. Loop over all points and change the ID numbers of any points that have the same ID as the second point to the ID number of the first point
  6. You are done when all points have the same ID number

Using higher numbers of points gives a more satisfying and cave-like look. Because the algorithm always connects the closest points, a very large number of points can be connected in a sane and aesthetically pleasing way in very small areas. This algorithm is also useful for rivers.

This algorithm doesn't create loops. Technically it links everything together into a perfect maze, so if you want loops you have to (for each loop you want) connect two (distant/non-neighboring/not already connected) points that have the same IDs. If you connect points completely at random (instead of the closest two), you end up with a pretty crazy spiderweby thing that doesn't look very good, but may be useful to you.

reaver

  • Rogueliker
  • ***
  • Posts: 207
  • Karma: +0/-0
    • View Profile
Re: Cave generation I've been using
« Reply #1 on: May 17, 2014, 01:20:17 PM »
Sounds interesting. Example pictures?

Quendus

  • Rogueliker
  • ***
  • Posts: 447
  • Karma: +0/-0
  • $@ \in \{1,W\} \times \{1,H\}$
    • View Profile
    • Klein Roguelikes
Re: Cave generation I've been using
« Reply #2 on: May 17, 2014, 02:49:35 PM »
Sounds like Kruskal's algorithm.

Endorya

  • Rogueliker
  • ***
  • Posts: 513
  • Karma: +0/-0
  • The non-purist roguelike lover
    • View Profile
    • Email
Re: Cave generation I've been using
« Reply #3 on: May 17, 2014, 05:41:00 PM »
Sounds like Kruskal's algorithm.

I was about to say the same thing.
"You are never alone. Death is always near watching you."

Ex

  • IRC Communications Delegate
  • Rogueliker
  • ***
  • Posts: 313
  • Karma: +0/-0
    • View Profile
Re: Cave generation I've been using
« Reply #4 on: May 19, 2014, 07:41:01 PM »
I'll post some examples later.

Ex

  • IRC Communications Delegate
  • Rogueliker
  • ***
  • Posts: 313
  • Karma: +0/-0
    • View Profile
Re: Cave generation I've been using
« Reply #5 on: May 19, 2014, 08:08:42 PM »
30 points:


100 points:


200 points:

Rickton

  • Rogueliker
  • ***
  • Posts: 215
  • Karma: +0/-0
    • View Profile
    • Weirdfellows
Re: Cave generation I've been using
« Reply #6 on: May 19, 2014, 10:52:56 PM »
Looks pretty cool. Could be a mine, or ant colony, or something. It's interesting that in two of the pictures it seems to kind of have a main corridor with branches off of it, is that something that's "supposed" to come out of it or is it just coincidence?
Creator of the 7DRL Possession: Escape from the Nether Regions
And its sequel, simply titled Possession

Endorya

  • Rogueliker
  • ***
  • Posts: 513
  • Karma: +0/-0
  • The non-purist roguelike lover
    • View Profile
    • Email
Re: Cave generation I've been using
« Reply #7 on: May 20, 2014, 12:00:56 PM »
Looks pretty cool. Could be a mine, or ant colony, or something. It's interesting that in two of the pictures it seems to kind of have a main corridor with branches off of it, is that something that's "supposed" to come out of it or is it just coincidence?

No coincidence. That's how the algorithm behaves.

@Elig with 200 points the result appears perfect to me :)
« Last Edit: May 20, 2014, 01:20:26 PM by Endorya »
"You are never alone. Death is always near watching you."

guest509

  • Guest
Re: Cave generation I've been using
« Reply #8 on: May 20, 2014, 06:34:16 PM »
Nice.

No fill it with goodies protected by baddies!

mushroom patch

  • Rogueliker
  • ***
  • Posts: 554
  • Karma: +0/-0
    • View Profile
Re: Cave generation I've been using
« Reply #9 on: May 21, 2014, 01:00:37 AM »
I don't claim the following is anything amazing, but it is produced by four lines python (six if you include imports):

Code: [Select]
##########################################################################
##########################################################################
#################      ###  # ###########  ########## #########   ### ####
#############                      ### #     ######    # # #      ### ####
########    #                         # #  ###                ##   ##  ###
#######       #             ###        #  ####      ####     ###       ###
#######                ##   ## #        ######       ####              ###
#######                ##   # #          ######       ##   ##          ###
#######    #         # ###     #         ######       ##    #          ###
###        ##       ##  ##    ### ##    ##   ##             # #        ###
###        ##    # ###      ########   # ##   #     #      ####        ###
####       #    #######         ##     #                    ###        ###
####      #  # ####  #          ##     ##                  ####       ####
###         ##  ###             #       #  #                          ####
###    #  #####  #   # #        #       #                             ####
###     #######      ####       #       #    #  ###                    ###
###      ######      ####      ####           ####         #          ####
###      ###        ### #      ####            ###        #           ####
###        ##     #####          ###      #######        #            ####
###   #    ##     #####      #           ########    #####        ########
##   ###   ##    ######     #           #  #######   # ###             ###
##    ###   #   ##### #                  # #######      #    ##        ###
###    ##   ###### ##         #         ###   ####     ###             ###
###  ####   ######  #     #             ##             ###    #        ###
###   ##    ##      ##    #  #    #     ###                            ###
###   #     ######  #       #   ###      ###                          ####
########   ############  ##### ######    ##############    ### ### #######
##########################################################################
##########################################################################


The point is: if you want amorphous, cavernous dungeons, you don't need to try hard to get them. If you're worried about connectedness, with a bit of tuning you can get a connected dungeon this way almost every time and, if you really care, you can pick out a connected component easily with about five lines using libtcod.

guest509

  • Guest
Re: Cave generation I've been using
« Reply #10 on: May 21, 2014, 02:12:31 AM »
It's fairly easy to run a connection check and rebuild any levels that aren't connected.

Bear

  • Rogueliker
  • ***
  • Posts: 308
  • Karma: +0/-0
    • View Profile
Re: Cave generation I've been using
« Reply #11 on: July 02, 2014, 09:00:00 PM »
It's also easy to just connect them. I use cellular automata to create caverns.  They sometimes create unconnected caverns, so I've got code in my mapgen that is specifically to connect unconnected caverns without altering their shapes, by moving the open spaces together.

You can also use it more generally to connect unconnected rooms-and-corridors maps. 

mushroom patch

  • Rogueliker
  • ***
  • Posts: 554
  • Karma: +0/-0
    • View Profile
Re: Cave generation I've been using
« Reply #12 on: July 03, 2014, 01:10:11 AM »
The map above is generated by populating a numpy array with noise, applying a low-pass filter (i.e. convolve with some kernel, see scipy.signal for convolve2d), and then applying a threshold function, somewhat carefully calibrated. I've always been surprised how well this five line dungeon generation algorithm stands up against more complicated stuff. Obviously, it's nothing special, but five lines!