• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Aercom

Dungeon generation method

7 posts in this topic

Hi all,

 

I'm having trouble coming up with a way to generate a specific kind of dungeon. My goal is something like this:

 

Example_zps76c5fd6c.png
 

I've read several articles concering dungeons but they all generate a more classic lay out, separate rooms connected with corridors.

Thus the issue is that I can't come up with a good approach to split a given square area (32x32 for example) up into tightly placed rooms, who shouldn't be rectangular all the time, but also not to randomly shaped (think of jagged edges etc, since I will only be using horizontal and vertical walls).

Currently I'm just adding in random rectangles that either clip or merge with existing ones until the area is covered, which is slow and not always satisfactory. I tried using some variety of drunk-walk approaches, which was too random, and binary space partitioning which didn't really yield either.

So, what would be the most likely to work out? How can I tackle this?

Thanks in advance

0

Share this post


Link to post
Share on other sites

If you are trying to make a rouge-like type game, you should have randomness. From what I played this randomness isn't exactly unique, and there is some repetition in dungeon layout. My approach would be (in case this is grid based) to define each room shape and later only position them so they are next to each other, by cheking next free (square) space on the side of the room.

0

Share this post


Link to post
Share on other sites

Thanks for your reply!
Randomness is very important, and I know some repetition is ok but I want to steer clear from it as much as possible. It tends to stand out in larger dungeons pretty soon.

 

It's especially the shape of the rooms that I want to be  more complex than just rectangles; predefining such rooms would lead to a lot of puzzling to get it all to fit, which would be slow. It doesn't have be done blazingly fast, but I do need to generate a lot of these sections to form a decent dungeon at some point, so it be great if it was.

 

 

I suppose some form of metatiling wouldn't be a bad idea though. I hadn't really considered that. Metatiles with some partial walls on them would be relatively easy to piece together and would form rooms automatically. I'll have to try it see it though.
And the dungeon is grid based, yes.

0

Share this post


Link to post
Share on other sites
Just spit-balling here:

Looking at your example, it looks like a rectangle based generation (BSP tree or other) - but with random regions (leaf nodes) joined together. Perhaps you can get the same affect with a second pass over a BSP generated dungeon, joining random regions (within size constraints)?

Also, I'm not really sure if this is applicable here, but it might be worth experimenting with: http://doryen.eptalys.net/articles/dungeon-morphing

Perhaps you could "lerp" a type of pseudo-random noise with a BSP dungeon to get something like this.
2

Share this post


Link to post
Share on other sites

Thanks for your insights! It indeed does look like it's a lot of smaller nodes joined together.
I'll give that a try right away.

I think I can use such a morphing function somewhere, but I'll have to play with it a bit first.
 

I have a free afternoon to try both tiling and the second-pass bsp, so hopefully I have some cool results in a few hours.

0

Share this post


Link to post
Share on other sites

I might try a method a bit like this:

  1. subdivide the grid in both dimensions at many random points. eg. if it's a 50x50 grid, drop in 20 horizontal lines and 20 vertical lines at random positions. Re-select or remove duplicates. The lines you added divide the area into various rectangular regions of different sizes.
  2. Pick a region and merge it with a neighbouring region, by removing any wall parts that they share. Each region will be adjacent to several others so I'd weight this heavily towards picking the adjacent region that shares most wall parts with this one, to reduce jaggedness.
  3. Repeat step 2 a number of times.

The downside here is that you need a good representation of a region and ways to quickly determine adjacency. It might be the case that defining a region as a simple list of grid squares is sufficient, providing you can quickly find a region ID from a grid location as well.

1

Share this post


Link to post
Share on other sites

Thanks for your input, Kylotan.

I've been trying out the options in this thread and so far it seems a combination of a (small) bsp-tree and what Kylotan described seems to give the best results. It will require some tweaking still but it's going in the proper direction, and I'm confident it will turn out the way I want it too.

Basically what happens now is that the grid is split at least two times, to make four different sized sections. This is to prevent long streaks of similar sized blocks in the next step.

Then randomly placed horizontal and vertical walls are added, and the resulting rooms are somewhat randomly merged.

This starts to look like the picture above, but there's still a bit of noise and jaggedness because my merging decision-making isn't optimal right now.

But I can work from here, thanks for help everyone!

0

Share this post


Link to post
Share on other sites

Another potential approach:

  • Generate random rectangles within your dungeon region.
  • If the rectangle intersects another existing room, merge it into that room.
  • If the rectangle does not intersect another existing room, make it a new room.

 

There are several options for scenarios where a rectangle intersects multiple rooms.

  • Discard the rectangle entirely and generate another.
  • Merge the rectangle with one of the rooms it intersects, either entirely (ie subtracting from the rooms it overlaps), or only the portions that do not overlap.

 

At some point, it'll likely be more efficient to switch to iteratively walking through any unused squares and adding them to existing rooms.  That, or you can just leave a certain amount of unused squares as solid regions of the dungeon.

 

Try various limits on the upper and lower bounds of the rectangles dimensions to produce different dungeon results.  Higher bounds should produce less jagged dungeons with fewer/larger rooms, while lower bounds would produce more jagged dungeons with more/smaller rooms.

 

After all that though, there's still the issue of adding doorways between rooms.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0