Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm creating a Roguelike and I'm having constant troubles with map generation, it's just something I have a lot of difficulty wrapping my head around.

I currently have my map as a 50x50 square of tiles, which is then cut up into a 6x6 grid. The grid resembles as follows

+---+---+---+----+----+----+
| 1 | 2 | 3 | 4  | 5  | 6  |
+---+---+---+----+----+----+
| 7 | 8 | 9 | 10 | 11 | 12 |
+---+---+---+----+----+----+

etc etc up to 36. I can generate perfectly an identical room into each of these map sections but what I'm actually concerned about is filling a small number of them and connecting them.

Is there a known approach to this? Currently what I'm doing is just looping through the sections, taking a 50/50 coin toss and making a room there but I'm unsure how I can tell where to make paths, what if I have my map set out as follows

+---+---+---+----+----+----+
| 4 |   |   | 1  |    |    |
+---+---+---+----+----+----+
|   |   |   |    | 2  |    |
+---+---+---+----+----+----+
|   |   | 3 |    |    |    |
+---+---+---+----+----+----+

How do I intelligently map between 1 and 2? How do I map between 2 and 3, much less how do I map between 3 and 4?

I'm very new to game development, so please excuse me if this is a silly question

share|improve this question
3  
There are a lot of good answers for this question, although most are too long to fit in the margins of this page. -- Jimmy's Last Theorem. In seriousness, check out this page –  Jimmy Mar 6 '13 at 23:57
add comment

3 Answers 3

I think you have a few options:

  • Use a path finding algorithm like A* to find the shortest paths between rooms. This would give you a quick algorithm, but the paths would all be optimal, so it might be boring. There are some tweaks you can do to add some randomness to the path finding and make the hallways a little less optimal and maybe more interesting.

  • Pick your rooms, then fill the rest of the grid with "hallway" nodes. Pick a hallway node at random to remove, and remove it if doing so doesn't affect the connectivity of your rooms. Continue until there are no removable hallway nodes left. This would use something like a breadth first search to ensure connectivity among the rooms.

  • Test out some alternative algorithms for generating rooms, like a BSP generator or read up on Unangband dungeon generation.

share|improve this answer
add comment

The first roguelike game, the Rogue have such algoritm to connect the rooms:

1.Pick direction of corridor: vertical or horizontal based on room's relative position:

x1, y1 - coords of first room
w1, h1 - size of first room, etc.

if(x1 + w1 < x2 || x2 + w2 < x1) then vertical
if(y1 + h1 < y2 || y2 + h2 < y1) then horizontal
if(both) then random
if(none) they overleap and doesn't need to be connected via coridor

2.Pick a point on side of each room (that side in the direction), like this:

Second step

3.Pick a random X coordinate between (or Y if you're doing vertical)

enter image description here

  1. Draw a line from first point to that X, than from second point to that X:

enter image description here

  1. Last step: connect it vertically:

enter image description here

share|improve this answer
add comment

I'm also a newbie C++ programmer and happens to write one maze generation program a couple of days ago. I believe BSP or A* are too complex for me and I won't touch them until I'm comfortable with data structures and algorithms. So what I did is the following:

  1. Find the center of each room;
  2. Connect the centers. Say you generated rooms at 1, 4, 8, 10 and 12 so simply connect the center of 1 to the center of 4 and go on until there is no more room that is not connected.

It's very easy and very fast, but also boring and sometimes gives me double hallways which I think it's OK.

Hope this helps!

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.