Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Rooms and Mazes: A Procedural Dungeon Generator

journal.stuffwithstuff.com

Post reply on HN
Print view View original

11–20 of 51 posts

Re: Rooms and Mazes: A Procedural Dungeon Generator

#11

Post by dirkk0 »

jmartinpetersen wrote: post #10

It is an amazing article. The "fluff" prose is well written and the visualizations are awesome. Kudos. An honest question, though, is maze generation generally useful? Other than for generating mazes and dungeons, obviously, not that isn't a worthy goal in and of it self.

I think some of the ideas behind maze generation can be applied to procedural level generation in general, whith some clever tweaks at least.

Here is an approach in Python albeit not as interactive as the mentioned article: http://pixelenvy.ca/wa/ca_cave.html

In case people didn't recognize, the author of the articel is also the author of this book which is for free (kudos!) on the interwebs and can be bought as a eBook. http://gameprogrammingpatterns.com/

Re: Rooms and Mazes: A Procedural Dungeon Generator

#12

Post by applekor »

jmartinpetersen wrote: post #10

It is an amazing article. The "fluff" prose is well written and the visualizations are awesome. Kudos. An honest question, though, is maze generation generally useful? Other than for generating mazes and dungeons, obviously, not that isn't a worthy goal in and of it self.

Last time I needed a maze I implemented Kruskal's algorithm, which is generally useful for finding the minimum spanning tree of a graph. You just run it on a lattice graph where all edge weights are the same and you have yourself a perfect maze.

Re: Rooms and Mazes: A Procedural Dungeon Generator

#15

Post by ralfn »

A long time ago i also wrote a maze generator. It's helpfull to understand the algebra of (fully accessible) mazes:

1. Every wall may intersect with some other wall at most once. (this includes the outer wall)

With the above rule in mind, you can create mazes with any type of random proccess (without the need for backtracking or bookkeeping). You don't have to check wether places are still accessible -- they just always are and will be. Back in those days (qbasic on a 268) just drawing randomly from some point in random directions was about ten times faster than the common path walking (backtracking) style algorithms. Taking two seconds instead of a full minute.

Don't take my word for it. Grab a pencil. Start drawing random lines. They may only cross some other line at most once. You'll end up with a fully accessible maze.

The maze may be complicated -- the walls in a proper maze are not. Its a great example of how understanding the invariants and rules that govern your problem domain will help you write faster and simpler code.

Re: Rooms and Mazes: A Procedural Dungeon Generator

#16

Post by jmartinpetersen »

dirkk0 wrote: post #11
jmartinpetersen wrote: post #10

It is an amazing article. The "fluff" prose is well written and the visualizations are awesome. Kudos. An honest question, though, is maze generation generally useful? Other than for generating mazes and dungeons, obviously, not that isn't a worthy goal in and of it self.

I think some of the ideas behind maze generation can be applied to procedural level generation in general, whith some clever tweaks at least. Here is an approach in Python albeit not as interactive as the mentioned article: http://pixelenvy.ca/wa/ca_cave.html In case people didn't recognize, the author of the articel is also the author of this book which is for free (kudos!) on the interwebs and can be bought as a eB…

But what about something completely different? I get that generation of "content" is (going to be) a big thing, but I'm curious if there's something about it that was applicable in a completely different setting (medicine, finance, whatever).

Re: Rooms and Mazes: A Procedural Dungeon Generator

#17

Post by gus_massa »

> It’s not perfect, though. It tends to produce annoyingly windy passages between rooms.

One possibility is to straight some corridors in a new final step, but I don't know how well this work in the actual mazes. For example, transform:

  -+ +-   ==>  ----- 
   +-+
and

  |          |
  | +-  ==>  +---
  +-+

Re: Rooms and Mazes: A Procedural Dungeon Generator

#20

Post by munificent »

akanet wrote: post #3

I think this article is a fantastic example of how you can blend prose with working interactive examples. The examples make you really trance out watching dungeons being carved out of nothing. I think an often-discounted aspect of JavaScript's appeal is its ability to breathe life into a bunch of fascinating but otherwise dry concepts. Another terrific example is this page by the prolific Mike Bostock: http://bost.oc…

I agree totally. I love the ability to write blog posts with interactive animated content. We take for granted that the web platform can do all this, but it's rare to find content that takes advantage of it. Mike Bostock and Amit Patel's sites are notable counter-examples.

I'd like to do more posts like this, but I can see why they aren't common. This one took me forever to finish. Easily eight times as much effort as a regular text + code samples blog post.

I think I'd get faster as I did more in this style, but it's really hard to for me to stay energized on a single concept long enough to finish posts like this.

Post reply on HN