Author Topic: My random dungen generator  (Read 25606 times)

corremn

  • Rogueliker
  • ***
  • Posts: 700
  • Karma: +0/-0
  • SewerJack Extraordinaire
    • View Profile
    • Demise RogueLike Games
My random dungen generator
« on: September 18, 2009, 03:46:06 AM »
Just mucking around with some new level generators.  I decided, just for fun, to use A* on the connection algorithms.  Even with my decent computer it takes from 30-90 seconds to generate one level for debug builds.  (Around 1 second for releases though.)   I seem to remember a slowness factor for visual studio using interators in debug builds, or something like that.  Off to the internet... Ah-ha _HAS_ITERATOR_DEBUGGING = 0. Fixed that up.  22 seconds for generation, almost workable.

These are my first two generated connected levels.  Tell me what you think.
obviuosly + are doors, '.' are floor and # are stone/rock/columns

Are the too many connections between rooms.

Code: [Select]
################################################################
################################################################
################################################################
################################################################
################################################################
####.......#####################################################
####.#####................................######################
####.+.#.##.#########.#######.##+####+###.##.+...###############
####.#...##.#########.#######.+.........#.##.#...###############
####.#.#.##.#.......#.#########..#.#.#..#.##.#...###############
####.+...##.#..#.#..#.###...###.........#.##.###.......#########
####.#.#.##.#.#...#.#.##.....############.....+.........########
####.+...##.#.......#.#.......###########.#...+.........########
######.#.##.+.#...#.#.#.......###########.#.###.........########
######...##.#.......#.+.......####..........###.........########
######.#.##.#.#...#.####.....#####+##+#####.###.........########
######...##.+.......#####...#.........#####.###.........########
######.#.##.#.#...#.#########..#.#.#..#####.###.........########
######...##.#.......#########.........#####.###.........########
######...##.#.#...#.#########..#.#.#..#####...+.........########
###########.#..#.#..#########.........#####.###.........########
###########.#.......#########..#.#.#..#...#.###.........########
###########.#################.........#...#.####.......#########
###########...#########################...#.####################
#############.##...################...+...#.###########.....####
#############.#.....###############.###...#.##########.......###
#############.+.....###############.###...#.##########.......###
#############.#.....#########.......###...#..........+.......###
#############.#.....#########.##+##.#######.##########.......###
#############.#.....#########.#...#.........##########.......###
#############.+.....#########.+...#####.###############.....####
#############.#.....#########.#...#####.########################
#############.#.....#########.#...#####.########################
#############.#.....#########.#...#####.########################
#############.#.....#########.+...#####.########################
#############.#.....########..#...#####.########################
#############.##...########...#...#####.########################
#############.###########...#.#...#####.########################
#####.....................###.#...##.##.########################
#####+##########.#######.####.+...#...#.########################
####...........#.#######.#....#...#...#.##########...###########
####.#.#.#.#.#.#.#.......#.##+#...#...#.#########.....##########
####...........#...#+###...#...####...#.#.......#.....##########
####.#.#.#.#.#.#..##...##..#...####...#.+..#.#..#.....##########
####...........#.##.....##.#...####...#.#.......##...###########
################.#.......#.#...#..+...#.#..#.#..################
################.+.......#.#...#.##...#.#.......+.##############
######...........#.......#.#####.##...#.#########.##############
######.#+#######.##.....##.......###.##...........##############
######.+...#####.###...########.############.###################
######.#...#####.##############.############+###################
######.#...#####.##############.#.............##################
######.#...#####.##############.#..#.#.#.#.#..##################
######.#...#####.##############.+.#.........#.##################
######.#...#####.################.............##################
######.#...#####.+...############.#.........#.##################
######.+...#####.+...############..#.#.#.#.#..##################
########...#####.+...############.............##################
########...#####################################################
########...#####################################################
########...#####################################################
########...#####################################################
################################################################
################################################################
Code: [Select]
################################################################
################################################################
################################################################
################################################################
#######......##...##############################################
#######.####+##+#.##############################################
#######.#.......#.###################.+.....####################
#######.#.......#..##################.+.....####################
#######.#.......##.##################.#.....####################
#######.#.......##...################.#.....####################
#######.#.......####.################.#.....####################
#######.#.......####..................#.....####################
#######.+.......#######.#############.#.....####################
#######.#.......#######.#...........#.#.....##...............###
#######.#.......#######.#...........#.#.....##.#############+###
#######.#.......#######.#...........#.########.#.............###
#######.#.......#######.#...........#....#####.#.............###
#######.#.......#######.#...........#.##.#####.#.............###
#######.#.......#######.+...........#.##.#####.#.............###
#######.#################...........#.##.#####.#.............###
#######......#.........##...........#.##.#####.+.............###
############.#.#.#.#.#.##...........#.##.#####.#.............###
############.+.........##############.##.#####.#################
############.#.#.....#.#############.............###############
############.#.........#############.###+#######.###############
############.#.#.....#.#############.#.........#..........######
############.#.........#############.+.#.#.#...#.######+#+######
############.#.#.#.#.#.#############.#.#.....#.#.###.........###
############.#.........#############.#.........#..##.#.#.#...###
############.#######################.#.#.....#.##..#.#.....#.###
############.#######################.#.........###.#.........###
############.#######################.#.#.....#.###.+.#.....#.###
###..................................+.........###.#.#.#.#.#.###
###+####++##.###+#####.#############.#.#.....#.###.#.........###
###.......##.##.....##.############..#.........###.#############
##.........#.#.......#.##########...##.#.....#.###.#############
##.........#.#.......#.##########.####.#.#.#.#.###.#############
##.........#.+.......#....######..####.........###........######
##.........#.##.....##+##.######.########################+######
##.........#.#######...##.######.##############...........######
##.........#.######.....#.######.#...........#.............#####
##.........#.######.....#.######.#.#.#.#.#.#.#.............#####
##.........#......+.....#.######.#...........#.............#####
##.........#..###.#.....#........+.#.......#.#.............#####
###.......###.###.+.....########.#...........#.............#####
#############...#.#.....########.#.#.......#.##...........######
###############+#.#.....########.#...........###################
###..#.#.#.#.#..#.#.....########.#.#.#.#.#.#.###################
###.............#.#.....########.#...........###################
###..#.#.#.#.#..#.##...#########.###############################
#.+.............#.##############.###############################
#.#..#.#.#.#.#..#.##############+###############################
#.#.............#.###.............##############################
#.#..#.#.#.#.#..#.###..#.#.#.#.#..##############################
#.#.............#.###.............##############################
#.#..#.#.#.#.#..#.###..#.#.#.#.#..##############################
#.#.............#.###.............##############################
#.#.............#.###..#.#.#.#.#..##############################
#.###############.###.............##############################
#.................###..#.#.#.#.#..##############################
#####################.............##############################
################################################################
################################################################
################################################################
« Last Edit: September 18, 2009, 04:52:59 AM by corremn »
corremn's Roguelikes. To admit defeat is to blaspheme against the Emperor.  Warhammer 40000 the Roguelike

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: My random dungen generator
« Reply #1 on: September 18, 2009, 08:14:27 AM »
One of the rooms in first level is not connected. There are maybe too many connections to the same corridor, but rooms could have more connections between another rooms to create loops. I can't believe it's taking 30 seconds to create one.

Rabiat

  • Rogueliker
  • ***
  • Posts: 88
  • Karma: +0/-0
    • View Profile
Re: My random dungen generator
« Reply #2 on: September 18, 2009, 09:14:41 AM »
Great looking maps, Corremn. Are you using fixed size or dynamic room templates? I like the bending corridors, too.

Krice is right though, the circular room in the bottom right is disconnected. I'd also avoid adjacent doors (appearing twice in the second level).

Unfortunately, 22 seconds for generation isn't acceptable for a game. If you can't get it below five seconds on a substandard CPU, consider pre-generation of the entire dungeon at game start and reading levels from file as required.

I'd be very interested in the source code (or pseudocode), if you're willing to share it.

purestrain

  • Rogueliker
  • ***
  • Posts: 172
  • Karma: +0/-0
    • View Profile
Re: My random dungen generator
« Reply #3 on: September 18, 2009, 10:53:33 AM »
I thought i read that level generation times are around 1 second in release mode... but even that seems very high (don't know your computer).

corremn

  • Rogueliker
  • ***
  • Posts: 700
  • Karma: +0/-0
  • SewerJack Extraordinaire
    • View Profile
    • Demise RogueLike Games
Re: My random dungen generator
« Reply #4 on: September 18, 2009, 01:06:15 PM »
Yeah release mode is much shorter, but still a bit high. It is due to the A* algorithm, when the connecting rooms with corridoors over long distances, the amount of calulations increase more than linearly.  Hence long times, however I could just find a shorter place to connect the corridoors.

Also I could probably use a quicker algorigm to connect two spaces.  I already had A* working and all I had to do was adjust the weights so the corridoor went around room walls and room floors.

The rooms are dynamically created, I have 5 basic room types that take a width and height.  I have just figured out how to do ellipse rooms correcly too.

As for disconnected rooms, simple flood fill fixed that.   However I like the double doors, they open and close as one.  Just imagine it as a large door.  Ogres have to get in thier rooms somehow.

Anyway the basic steps to produce this are, well, quite basic really.  The only trick is to mark cells that make up the walls of rooms and then mark valid door positions.  That and a working pathfinding algorithm. ;D

Create N randomly placed random rooms, mark the cells that make walls and valid door positions for each room.

Connect each room with a random room.
   Get a random door position for the two rooms and use A* algorithm to trace a path.
   The A* algorithm perfers already existing corridoor cells to follow but tunnels into non-wall and non-rooms when needed.

Run Flood fill and connect the unconnected parts.


If I add random weights to the dungeon cells as it is calculating its path I get slightly more natural tunnelling.  It looks less like the corridoor was carved with a laser. I will post one of them later.

I will post the code if wanted, but is is quite large and confusing.  However I think it is resonably structured, except the A* part.
   
corremn's Roguelikes. To admit defeat is to blaspheme against the Emperor.  Warhammer 40000 the Roguelike

corremn

  • Rogueliker
  • ***
  • Posts: 700
  • Karma: +0/-0
  • SewerJack Extraordinaire
    • View Profile
    • Demise RogueLike Games
Re: My random name generator
« Reply #5 on: October 01, 2009, 07:26:27 AM »
Now I am mucking around with random name generation using Markov Chains  http://en.wikipedia.org/wiki/Markov_chain . It takes a sample of names and analyses them for common letter transitions and generates strings from them. Nothing ground breaking here, I have been meaning to get around to this for a few years.

Now all I have to do is add random titles and last names.
E.g. Meoth the Destroyer, Anantuki Doomsbottom etc

DEMON NAMES taken from wikipedia demon names
Meoth
Anantuki
Ipopollous
Elemonialo
Cifron
Bueezleth
Aphantian
Queerihedum
Morgorine
Bitrinyaza
Aphezletty
Addonah
Haurmedutorofocel
Sepacrim
Setrum
Lemejel
Peneqa
Anaco
Caginaastor
Matat


BOY NAMES  taken from 300 common boy american names
Bobert
Glary
Jimmy
Mauliellie
Joserber
Maulio
Damie
Dathawn
Jaiguy
Dally
Damorry
Bencis
Rolawn
Paulio
Normax
Dancil
Dardandy
Edwill
Pathy
Handy


GIRL NAMES taken from 1000 common american names
Beree
Noebel
Sharie
Jewenah
Amerry
Melmady
Joharsusa
Detty
Delielina
Borrynn
Jorah
Sofia
Assie
Mabett
Marrithy
Dorine
Laristi
Gaberie
Bettis
Kathawna
Arina
Shasha
Dessicha
Malette
Briania
Nietti
Joraniele


corremn's Roguelikes. To admit defeat is to blaspheme against the Emperor.  Warhammer 40000 the Roguelike

Etinarg

  • Rogueliker
  • ***
  • Posts: 424
  • Karma: +1/-1
  • Idea archivist and game tinkerer.
    • View Profile
    • Gedankenweber Blog (German)
Re: My random dungen generator
« Reply #6 on: October 01, 2009, 09:07:41 AM »
I still dream of semi-sensible but randomly generated NPC dialogs.

Edit: That came from mentioning Markov-chains. The names look good :)
« Last Edit: October 01, 2009, 09:11:48 AM by Hajo »

Fenrir

  • Rogueliker
  • ***
  • Posts: 473
  • Karma: +1/-2
  • The Monstrous Wolf
    • View Profile
Re: My random dungen generator
« Reply #7 on: October 01, 2009, 12:17:05 PM »
Cool stuff. I've been looking for a good way to generate random words. Is this all part of a game or are you just experimenting?

corremn

  • Rogueliker
  • ***
  • Posts: 700
  • Karma: +0/-0
  • SewerJack Extraordinaire
    • View Profile
    • Demise RogueLike Games
Re: My random name generator
« Reply #8 on: October 02, 2009, 10:06:13 AM »
It is now part of my game engine, the name lists will have to be more specific to the game I am working on though. I am currently developing a future war based game.  So I will probably make random names based on last names.  I will need chaos sounding names as well.
corremn's Roguelikes. To admit defeat is to blaspheme against the Emperor.  Warhammer 40000 the Roguelike

corremn

  • Rogueliker
  • ***
  • Posts: 700
  • Karma: +0/-0
  • SewerJack Extraordinaire
    • View Profile
    • Demise RogueLike Games
Re: My random name generator
« Reply #9 on: October 08, 2009, 05:17:06 AM »
Here are some random first and last names for humans.  These are based on common names in America. 

Poor Conya.

MEN
Traudeance Port
Jerne Chan
Biltomary Pruirdy
Wilguy Woloung
Jaight McCard
Fern Gooley
Brene Hencas
Sidne Dodges
Bricharlex Shen
Lenhamel Gomed
Wal Dolsh
Lacet Kenaldwalder
Ran Willownson
Ian Walbercard
Berreddie Mon
Stine Boodwinse
Dane Youghend

GIRLS

Elisharlia Payley
Berna Bauglaws
Adallese Boynaler
Annaly Blairbeace
Jestelie Munnedoun
Maryn Tielerayley
Livia Stang
Nanne Rogalds
Avis Huffman
Jana Grad
Annandrane Silars
Conya McPhuckners

The following are made by reducing the state history in the Markov Chain, they are somewhat more removed from actual names, but use the same file.  Increased the length to make some hard to pronounce Dragon names.

Berssalllitons
Terasensokigs
Ninernicospis
Bankebborinsesog
Ssorichericalkin
Chizayasotron
Haraviquguervez
Wotovaydwstkes
Goremilawertt
Avarowatatorrast
corremn's Roguelikes. To admit defeat is to blaspheme against the Emperor.  Warhammer 40000 the Roguelike

Ex

  • IRC Communications Delegate
  • Rogueliker
  • ***
  • Posts: 313
  • Karma: +0/-0
    • View Profile
Re: My random dungen generator
« Reply #10 on: October 08, 2009, 07:26:47 AM »
These are much better than my name generator. I used a simple system: consonant-vowels-consonant. I'd then have a list of consonants and vowels. But this is far, far superior.

corremn

  • Rogueliker
  • ***
  • Posts: 700
  • Karma: +0/-0
  • SewerJack Extraordinaire
    • View Profile
    • Demise RogueLike Games
Re: My random name generator
« Reply #11 on: October 08, 2009, 09:30:38 AM »
All you need do is supply it with example names and voila, random names based on  It works well for LOTR names, elf and dwarf, etc.  I just need to come up with a themed name generator though to create Diablo style named. 

This sight has great working examples of random name generators. (among other random generated content) I particularly like the diablo style names.  Puts my feeble efforts to shame.
http://seventhsanctum.com/index-name.php

P.S  I can change the topic name but it does not stick for the next poster.  (Especially since I spelt dungeon wrong in the first post)
corremn's Roguelikes. To admit defeat is to blaspheme against the Emperor.  Warhammer 40000 the Roguelike

Etinarg

  • Rogueliker
  • ***
  • Posts: 424
  • Karma: +1/-1
  • Idea archivist and game tinkerer.
    • View Profile
    • Gedankenweber Blog (German)
Re: My random dungen generator
« Reply #12 on: October 08, 2009, 09:52:05 AM »
Maybe a moderator can split the topics and also fix the title?

The seventh sanctum is a very inspiring site for all sorts of generators.