Yet another dungeon generation algorithm

403 views
Skip to first unread message

Kusigrosz

unread,
Dec 18, 2008, 9:59:46 AM12/18/08
to
Experimenting with dungeon generation, I stumbled upon an algorithm
that makes interesting, organic-looking patterns:

http://tinyurl.com/4c9zyj
http://tinyurl.com/3h2j5h

The algorithm operates on a rectangular grid; I think it can be easily
generalized to hexagons or other regular grids. It starts with an
initial seed of some dug-out cells, with their diggable neighbours in
store. The main loop: Get a random diggable cell from the store; if it
has between n_min and n_max dug-out neighbours, and digging it won't
connect previously unconnected cells, dig it out and store its diggable
neighbours. Repeat until reaching the desired number of cells, or no
more cells are found in the store.


The resulting patterns are "seed-centric". Because of the "no new
connections" condition, if the seed contains no loops neither does
the finished pattern. If loops are desired this condition can of
course be ignored with some chosen probability. There are many
pairs of (n_min, n_max) that give interesting results, for example
(1, 1) makes a narrow maze without 90 degree turns, (1, 8) a cavern
with fractured edges, (3, 7) a cavern with somewhat smoother edges,
(2, 3) and (2, 4) a dendritic (brownian tree -like?) pattern, etc.

A C implementation:
http://tinyurl.com/3o8lzl

--
Kusigrosz To send mail, remove 'erase' from the address
You see here a scroll labeled "cV2NpPqIHnw"

Gerry Quinn

unread,
Dec 18, 2008, 10:06:14 AM12/18/08
to
In article <gidoh2$guq$1...@news.ett.com.ua>, tvkera...@tvk.torun.pl
says...

> Experimenting with dungeon generation, I stumbled upon an algorithm
> that makes interesting, organic-looking patterns:
>
> http://tinyurl.com/4c9zyj
> http://tinyurl.com/3h2j5h

Interesting, if not conventionally roguelike! The first could be a
insect nest of some sort, the second an underground storage room with
some walls...

- Gerry Quinn
--
Lair of the Demon Ape (a coffee-break roguelike)
<http://indigo.ie/~gerryq/lair/lair.htm>

Andrew Doull

unread,
Dec 18, 2008, 6:51:50 PM12/18/08
to
On Dec 19, 1:59 am, Kusigrosz <tvkerase0...@tvk.torun.pl> wrote:
> Experimenting with dungeon generation, I stumbled upon an algorithm
> that makes interesting, organic-looking patterns:
>
> http://tinyurl.com/4c9zyjhttp://tinyurl.com/3h2j5h

>
> The algorithm operates on a rectangular grid; I think it can be easily
> generalized to hexagons or other regular grids. It starts with an
> initial seed of some dug-out cells, with their diggable neighbours in
> store. The main loop: Get a random diggable cell from the store; if it
> has between n_min and n_max dug-out neighbours, and digging it won't
> connect previously unconnected cells, dig it out and store its diggable
> neighbours. Repeat until reaching the desired number of cells, or no
> more cells are found in the store.
>
> The resulting patterns are "seed-centric". Because of the "no new
> connections" condition, if the seed contains no loops neither does
> the finished pattern. If loops are desired this condition can of  
> course be ignored with some chosen probability. There are many    
> pairs of (n_min, n_max) that give interesting results, for example
> (1, 1) makes a narrow maze without 90 degree turns, (1, 8) a cavern
> with fractured edges, (3, 7) a cavern with somewhat smoother edges,
> (2, 3) and (2, 4) a dendritic (brownian tree -like?) pattern, etc.
>
> A C implementation:http://tinyurl.com/3o8lzl
>
> --
> Kusigrosz       To send mail, remove 'erase' from the address
> You see here a scroll labeled "cV2NpPqIHnw"

Looks great. What license is it under? Public domain or GPL would be
ideal if possible.


Andrew

corremn

unread,
Dec 18, 2008, 7:42:34 PM12/18/08
to
> Andrew- Hide quoted text -
>
> - Show quoted text -

Looks great, you should also put some comments at the top the file,
author, licence, version etc.
So if I use it I can remember to give credit to you.

You have weird curly brace placement, I have never seen it like that
before :P

Gerry Quinn

unread,
Dec 18, 2008, 10:24:47 PM12/18/08
to

> You have weird curly brace placement, I have never seen it like that
> before :P

Not really, IMO - he moves braces a tab right to differentiate
functions; I don't do that myself, but it doesn't seem unclear in any
way.

- Gerry Quinn

Kusigrosz

unread,
Dec 19, 2008, 4:35:40 PM12/19/08
to

Public domain.

Andrew Doull

unread,
Dec 19, 2008, 6:06:33 PM12/19/08
to
On Dec 20, 8:35 am, Kusigrosz <tvkerase0...@tvk.torun.pl> wrote:

Thanks - much appreciated for your contribution to the noosphere.

Andrew

Jeff Lait

unread,
Dec 19, 2008, 9:19:16 PM12/19/08
to
On Dec 18, 7:42 pm, corremn <corr...@gmail.com> wrote:
>
> You have weird curly brace placement, I have never seen it like that
> before :P

I actually used to use that curly brace standard. It was a result of
learning C from Laser C,
http://www.atarimagazines.com/st-log/issue25/78_1_LASER_C.php
You can see a screen shot of some Laser C example code part way down
that review. The review is a bit of a blast from the past too.
--
Jeff Lait
(POWDER: http://www.zincland.com/powder)

Kusigrosz

unread,
Dec 30, 2008, 4:18:36 PM12/30/08
to
On 2008-12-18, Kusigrosz <tvkera...@tvk.torun.pl> wrote:
> The resulting patterns are "seed-centric". Because of the "no new
> connections" condition, if the seed contains no loops neither does
> the finished pattern.
I made a version that generates less compact patterns. It also takes
as an argument the chance of new connections being allowed. An example:
http://tinyurl.com/aydonp
The irregular character is more visible in large patterns - too
large for roguelike levels I suppose. Maybe they could be used for
psychological tests ;-)
http://tinyurl.com/7yys3o
http://tinyurl.com/9nb3ku
The source:
http://tinyurl.com/855dwy

ark.t...@gmail.com

unread,
Aug 4, 2017, 3:39:14 AM8/4/17
to
I welcome, unfortunately the links do not work =(

David Damerell

unread,
Aug 4, 2017, 10:38:12 AM8/4/17
to
Quoting <ark.t...@gmail.com>:
>I welcome, unfortunately the links do not work =(

That's because you replied to a post from 2008.
--
David Damerell <dame...@chiark.greenend.org.uk> Distortion Field!
Today is Wednesday, July.
Tomorrow will be Thursday, July.

ark.t...@gmail.com

unread,
Aug 4, 2017, 11:11:24 AM8/4/17
to

> That's because you replied to a post from 2008.


I hope that the author still has the source code.

Auric__

unread,
Aug 6, 2017, 1:45:42 AM8/6/17
to
ark.tarusov wrote:

>> That's because you replied to a post from 2008.
>
>
> I hope that the author still has the source code.

He hasn't posted to this group in 3 years. Don't hold your breath.

--
- You look awfully young to me.
- That says more about you than about me.
Reply all
Reply to author
Forward
0 new messages