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

41–50 of 51 posts

Re: Rooms and Mazes: A Procedural Dungeon Generator

#41

Post by dsp1234 »

jfoutz wrote: post #40
dsp1234 wrote: post #39

Earlier quoted context omitted.

Start drawing random lines. I got this on my first try: +------------------+--+---+ | - | | | -| | | + | | |- -| | | + | | |- -| | + + | -| | | - | | | - | | | - | +----------------+----+---+ I got that by drawing an exterior square with a single entrance in the bottom right hand corner. I then drew a line from the top wall to the bottom wall parallel to the left and right walls. I then drew a diagonal line from abou…

Ah! Each wall is one continuous line, regardless of twists and turns. Connecting the top to the bottom is what got you stuck. Edit I guess each wall can only be anchored at one end. Trying to think about how to restate it in a clear way.

This additional twist makes the original statement of:

without the need for backtracking or bookkeeping

appear to be misleading. You have to do some bookkeeping in order to know if the wall that your line just hit is connected to the start point, or any midpoint of the line you are drawing. The complexity is just hidden behind simpler words (They may only cross some other line at most once.).

Also, I'm not sure how the backtracking is missing. Once you've hit a new wall with your line, and check connectivity, if it's actually connected, then you have to backtrack that line until it's back to a place where it's no longer connected. Connectivity could be checked right before hitting a wall, but then it's just backtracking by another name. So I'm really not understanding how this would be implemented in an simpler and/or faster way.

Re: Rooms and Mazes: A Procedural Dungeon Generator

#42

Post by jfoutz »

dsp1234 wrote: post #41
jfoutz wrote: post #40

Earlier quoted context omitted.

Ah! Each wall is one continuous line, regardless of twists and turns. Connecting the top to the bottom is what got you stuck. Edit I guess each wall can only be anchored at one end. Trying to think about how to restate it in a clear way.

This additional twist makes the original statement of: without the need for backtracking or bookkeeping appear to be misleading. You have to do some bookkeeping in order to know if the wall that your line just hit is connected to the start point, or any midpoint of the line you are drawing. The complexity is just hidden behind simpler words ( They may only cross some other line at most once. ). Also, I'm not sure how…

I'm coming around to your way of thinking.

If you have a way to draw a wall (twisty line) that doesn't intersect with any other wall, then it's trivial. Just draw a new wall optionally anchored on a wall. The line crossing bookkeeping seems annoying. If i had to do something right now, i'd use a bitmap of cells to indicate the presence or absence of a wall. Can't set a bit with more than 1 adjacent (north/south/east/west) bit set.

Re: Rooms and Mazes: A Procedural Dungeon Generator

#43

Post by stonemetal »

munificent wrote: post #27
mjn wrote: post #25

Earlier quoted context omitted.

As another resource, here's a draft chapter on dungeon generation, from a textbook on procedural content generation in games: http://pcgbook.com/wp-content/uploads/chapter03.pdf (Draft in part because some of the figures still need work. I'm a coauthor of the book, but not of this particular chapter.)

Can I take a moment to be critical here? I hate sounding negative, but I'll try to be constructive. I was really excited when I first stumbled onto this book. As you can imagine, it's perfectly in line with my interests. But, when I tried to read it, the prose just killed me. I think there's good ideas in there, but I can't bear to wade through the heavy-handed academic style get there. I understand writing for a cer…

"linquistic" -> What other kinds of phrases are there?

Musical phrases.http://en.wikipedia.org/wiki/Phrase_%28music%29

Means almost the same thing as linguistic phrases except it is about groups of notes rather than groups of words.

Re: Rooms and Mazes: A Procedural Dungeon Generator

#44

Post by dsp1234 »

jfoutz wrote: post #42
dsp1234 wrote: post #41

Earlier quoted context omitted.

This additional twist makes the original statement of: without the need for backtracking or bookkeeping appear to be misleading. You have to do some bookkeeping in order to know if the wall that your line just hit is connected to the start point, or any midpoint of the line you are drawing. The complexity is just hidden behind simpler words ( They may only cross some other line at most once. ). Also, I'm not sure how…

I'm coming around to your way of thinking. If you have a way to draw a wall (twisty line) that doesn't intersect with any other wall, then it's trivial. Just draw a new wall optionally anchored on a wall. The line crossing bookkeeping seems annoying. If i had to do something right now, i'd use a bitmap of cells to indicate the presence or absence of a wall. Can't set a bit with more than 1 adjacent (north/south/east/…

Can't set a bit with more than 1 adjacent (north/south/east/west) bit set.

Then you couldn't make a T (or + intersection) because as the newly incoming line was about to attach to the existing wall (regardless of any other connectivity), the final "bit" that would attach to the line and existing wall would have 2 adjacent bits set. ex: assuming a wall that travels east/west, and a line coming from the south northwards, when drawing the last pixel of the line before it attaches to the wall, the test would fail. The "south" bit would be set because that bit was set just one step prior, and the "north" bit would be set because that's where the wall is.

  ---------
      x   
      |
      |
Can't set "x" because there is more than one "adjacent" bit set (north and south).

Re: Rooms and Mazes: A Procedural Dungeon Generator

#45

Post by Pfhreak »

Maze generators are a lot of fun to play with, but don't always come up with the most compelling gameplay environments.

One of the techniques I've heard works well is to step up the abstraction level one click, and create interesting environments and set pieces, then combine those to create a compelling environment for your players. One approach to do this uses herringbone Wang tiles to place various precreated environment tiles in a random, pathable way.

http://nothings.org/gamedev/herringbone/

The results are similar, but allow the developer to inject a little bit of human direction along the way.

Re: Rooms and Mazes: A Procedural Dungeon Generator

#46

Post by mjn »

munificent wrote: post #27
mjn wrote: post #25

Earlier quoted context omitted.

As another resource, here's a draft chapter on dungeon generation, from a textbook on procedural content generation in games: http://pcgbook.com/wp-content/uploads/chapter03.pdf (Draft in part because some of the figures still need work. I'm a coauthor of the book, but not of this particular chapter.)

Can I take a moment to be critical here? I hate sounding negative, but I'll try to be constructive. I was really excited when I first stumbled onto this book. As you can imagine, it's perfectly in line with my interests. But, when I tried to read it, the prose just killed me. I think there's good ideas in there, but I can't bear to wade through the heavy-handed academic style get there. I understand writing for a cer…

A reasonable point. I've been doing a bit of editing for style recently, and will make another pass before sending off the manuscript. At the moment the style is very uneven from chapter to chapter, partly because the authors come from different backgrounds. If you include chapter authors, we live in 6 countries and have 9 native languages between us, and different views on how a textbook should read. To generalize really broadly, the text from Americans and Scandinavians seems to use shorter sentences and a more conversational tone than that from others. (Of course, country/language isn't the only reason people vary on style and level of formality.)

But yes, I'm aiming to bring it in a more conversational direction. It still needs editing too, but Ch. 8 is closer to the style I'm personally aiming for.

Re: Rooms and Mazes: A Procedural Dungeon Generator

#47

Post by jpasden »

Pfhreak wrote: post #45

Maze generators are a lot of fun to play with, but don't always come up with the most compelling gameplay environments. One of the techniques I've heard works well is to step up the abstraction level one click, and create interesting environments and set pieces, then combine those to create a compelling environment for your players. One approach to do this uses herringbone Wang tiles to place various precreated envir…

Another good example of this approach is indie 2D platformer Spelunky. Here's an illustration of the method:

http://tinysubversions.com/spelunkyGen/

Re: Rooms and Mazes: A Procedural Dungeon Generator

#49

Post by ajanuary »

munificent wrote: post #27
mjn wrote: post #25

Earlier quoted context omitted.

As another resource, here's a draft chapter on dungeon generation, from a textbook on procedural content generation in games: http://pcgbook.com/wp-content/uploads/chapter03.pdf (Draft in part because some of the figures still need work. I'm a coauthor of the book, but not of this particular chapter.)

Can I take a moment to be critical here? I hate sounding negative, but I'll try to be constructive. I was really excited when I first stumbled onto this book. As you can imagine, it's perfectly in line with my interests. But, when I tried to read it, the prose just killed me. I think there's good ideas in there, but I can't bear to wade through the heavy-handed academic style get there. I understand writing for a cer…

To nitpick your nitpick (and not to imply your ultimate conclusion is wrong):

    "originally devised" -> "Devise" implies originality.
The word original in the original text is used in the sense of "from or in the beginning; at first", while you seem to be taking it in the sense of "in a novel and inventive way".

The phrase "originally devised" implies the usage of the devised thing has since changed or expanded beyond the purpose of its invention. This is important, because it is in a passage talking about one of those new usages - dungeon generation.

Yes, your sentence has the same meaning, and in a weak sense has the same implication, but "originally devised/invented" has a history that boosts that implication to make the purpose clearer.

Post reply on HN