Generating a Random Dungeon Map...
Generating a Random Dungeon Map...
Generating a Random Dungeon Map...
Generating a Random Dungeon Map...
Generating a Random Dungeon Map...
Generating a Random Dungeon Map... Generating a Random Dungeon Map... Generating a Random Dungeon Map... Generating a Random Dungeon Map... Generating a Random Dungeon Map... Generating a Random Dungeon Map... Generating a Random Dungeon Map... Generating a Random Dungeon Map...
Generating a Random Dungeon Map... Generating a Random Dungeon Map...
Generating a Random Dungeon Map...
Go Back  Xtreme Visual Basic Talk > > > Generating a Random Dungeon Map...


Reply
 
Thread Tools Display Modes
  #1  
Old 06-16-2005, 09:53 AM
DubbleClick's Avatar
DubbleClick DubbleClick is offline
Contributor
 
Join Date: Mar 2005
Location: Tennessee
Posts: 511
Exclamation Generating a Random Dungeon Map...


Programming slashers are pretty fun. Playing them are fun too. The one thing I have found that makes the games old quickly is "static maps".

I've done a few games with great "map editors", but after a while, creating "new maps" get's to be a pain and, besides, if you create the map yourself... where's the adventure in that?

About the most famous of ALL games in which has random map generators is Diablo 1 & 2. I guess that's why those games stay popular for so many years... the maps are always different for each game.

In doing this, I have discovered it's no easy task to "do a good map everytime".

Plain "Map editors" are easy and aren't much of a challenge. I'm looking for something to make a game engine that will keep interest.

I've done a couple of generators, but the results are no where near satisfying.

I am wondering if there is anyone here who has successfully coded a Random Map Generator?

I'm NOT looking for code... What I am looking for is "approach", or flow of your code.

I'm starting with simple maps. 2D Square Dungeon maps. Rooms and Hallways and Doors.

My approach is starting top left, doing 1 square at a time. Do some logic on the surrounding squares, make a decision on what to make that square, move on to the next.

The problem is there isn't much structure to the map.

How would you do it? Generate Hallways for the Map, then fill in the spaces with Room, then Doors?
Or, Generate Rooms throughout the map, then fill in with hallways?
...etc.

Just looking for some Code "FLOW" ideas.

Thanks!
Reply With Quote
  #2  
Old 06-17-2005, 04:47 AM
BillSoo's Avatar
BillSooGenerating a Random Dungeon Map... BillSoo is offline
Code Meister

Retired Moderator
* Guru *
 
Join Date: Aug 2000
Location: Vancouver, BC, Canada
Posts: 10,441
Default

The only similar thing I have done is a maze generator. The basic algorithm required a 2D array representing the map and a list of pointers to map cells.

Basically, you start by initializing the map to empty cells, then pick one cell at random and add it to the list. Then:
1) pick cell at random from list
2) check adjacent cells to see if they are empty. If they are:
2a) pick an empty one at random and add it to the list
2b) update cell contents to indicate a path between these two cells (this also makes these cells no longer "empty")
3) Else If NO adjacent cells are empty
3a) remove cell from list
4) check list size. If list is now empty, we are now done
5) otherwise, goto 1

I suppose you could modify this so that each cell represents a whole TILE rather than a single square. If the tile has a single connection to the rest of the map, then you might select a tile pattern that is some kind of destination, like a lair. If the tile has two connections, then it could be a simple corridor. If it has 4 connections, maybe it could be a town or other kind of hub.

This results in an extremely random kind of map, maybe not as "structured" as you seem to want. But it might be worth a try.
__________________
"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder
Reply With Quote
  #3  
Old 06-17-2005, 06:46 AM
Maelstrom's Avatar
Maelstrom Maelstrom is offline
Centurion
 
Join Date: Jun 2004
Location: Hobart, Tasmania, Aussie
Posts: 117
Default

You could also try doing something like this:
1) Set the whole map to the wall tile
2) Make a few recangular open spaces, for rooms
3) record the position/size of said rooms
4) If two rooms are close to each other and on the same level, add a straight hallway between them.
5) Go back to you rooms again and add scenery/monsters/doors/etc.

I used to have a basic Random Map Generator (not quite what your looking for, as it was for open spaces not dungeons), and if you get stuck it might help a bit. Ill see if I cant dig it up.

EDIT:
The game I was talking about seems to have been deleted or something. Anyway, I was not able to find it. How the map generator for that worked wa like this:
1) Make the whole map the Grass Tile, with a border of water(was an island)
2) Add an island in a random corner, with a bridge going to the 'main land'
3) Add a few round clumps of trees
4) Add a few 'lakes' around the place
5) Add a village

The problem with that method, is that there was no logical thinking done by the generator. The village, pools, player, forest or anything could accidently start in the middle of a village/pool/forest. Made it very hard to play when the object of the level was hidden in the middle of a large, inpeneterable forest...
Anyway, im sure you can find your way around these problems. Good luck.
__________________
The distance between insanity and genius is measured only by success.
Bruce Feirstein

Last edited by Maelstrom; 06-17-2005 at 06:53 AM.
Reply With Quote
  #4  
Old 06-17-2005, 01:18 PM
noi_max's Avatar
noi_maxGenerating a Random Dungeon Map... noi_max is offline
Still asleep...

Retired Leader
* Expert *
 
Join Date: Nov 2003
Location: IronForge
Posts: 2,694
Default

I've thought about this 'random map' thing a while back and wondered...

How do we know that it's really that random?

Map coordinates consist of just ordinary data. Maybe thay had hundreds of different pre-defined map layouts that were simply chosen at random during run-time.

Each level has some parts of the map with a consistent theme. Take map 2 on the original Diablo game for example ("the Butcher")
Or how about the "Arcane Sanctuary" in DiabloII?

The random maps would have to follow the theme and allow for monster placement and passageways to get around.
It seems at that point placing anything at random could really mess things up.

Does that make sense??

Edit: It just occured to me that they might have done things in sections. Like piecing random legos together. The pieces fit like they're supposed to, but each individual piece is different. So maybe not individual random tile placement but rather larger sections that are made to fit together and with the theme. Just thinking out loud. Hope it helps..
__________________
~ Jason

Use [vb][/vb] tags when posting code :) || Search the forum and MSDN|| Check out the Posting Guidelines
Reply With Quote
  #5  
Old 06-17-2005, 03:56 PM
DubbleClick's Avatar
DubbleClick DubbleClick is offline
Contributor
 
Join Date: Mar 2005
Location: Tennessee
Posts: 511
Default

Well, you don't just place things "at random". That's not very structured now is it?

I'm sure everyone that creates random maps do it a bit different. I agree one approach is the "lego theory" you have going. However, that's not what I'm looking to do.

I am breaking it down to the very square. Wall/Doorway/Window/Open/InsideCorner/OutsideCorner.

That type of thing.

I'm hoping to have something that will have No static areas at all. Even "boss areas" will be random in size and shape.

Of course every area "type" will have guidlines, such as minimum and maximum length and width. Boss areas would have a guideline "type" to follow, if you follow me.

I've gotten some good feedback on the posts given so far. I like what I've read and want to say Thanks!

I'm going to work on some new code tonight. I'll post how it goes.
Reply With Quote
  #6  
Old 06-17-2005, 04:51 PM
TeraBlight's Avatar
TeraBlightGenerating a Random Dungeon Map... TeraBlight is offline
Captain Convoluted

* Expert *
 
Join Date: Jun 2005
Posts: 1,918
Default

I would say that an important consideration is whether you want the map to look "mad-made" or "natural".

For a natural "cave-system" kind of look, I would think the above suggestion of starting with a few random seed locations for "caverns" and then adding random connecting "tunnels" between them should do the job quite nicely.

Man-made would mean a MUCH more restrictive design, such as only single-width walls, not too many random turns in corridors, not too many corridors leading into dead ends, etc. etc. Seems to me that in that case, you'll basically want to start with the corridors and then add rooms, although of course you need to plan ahead so that the rooms don't get too random in shape and size either.
Maybe an iterative approach:

- create a random maze of corridors, with say 90% wall and 10% open, limiting the number of turns in these corridors (this should be easy to implement as an extension of billsoo's method, by weighing the probabilities so that if you have a path from cell (4,4) to (4,5), you extend the path to (4,6) with higher probability than to (3,5) or (5,5))
- identify large clumps of wall
- make (rectangular) holes into these clumps -> rooms
- now, move the corridors around a little to either eliminate or enlarge smaller clumps that don't make a good room yet
- repeat previous 3 steps as necessary

- finally add doors and windows, which should be easy at that stage.

Sounds like a lot of work

Last edited by TeraBlight; 06-17-2005 at 09:58 PM.
Reply With Quote
  #7  
Old 06-17-2005, 06:14 PM
jmanomega's Avatar
jmanomega jmanomega is offline
Centurion
 
Join Date: Jul 2004
Location: Missouri, USA
Posts: 170
Default

How about an in-between method?

You could take the pre-made Lego idea. But, instead of having all of the Lego like pieces pre-made you could randomly make them each time you would use one and randomly chose which one to use.

For example: Say you start out with a 5x20 hallway. Then your program chooses randomly from either another hallway moving in a random direction, a room, or some other sort of piece. Say the program chooses a piece of hallway that turns 30 degrees to the right and is 10 units long (unit = width of a tile). Next it could have a room that is 50x30 units and filled with a random set of monsters. You just keep repeating the process until and add checks to make sure that the piece that you are going to place isn’t colliding with an existing piece. You could even have paths branch off and keep track of multiple paths.

Hallways would be easy enough. For rooms you could have random obstacles, walls, and traps setup.
Reply With Quote
  #8  
Old 06-17-2005, 09:06 PM
DubbleClick's Avatar
DubbleClick DubbleClick is offline
Contributor
 
Join Date: Mar 2005
Location: Tennessee
Posts: 511
Default

Quote:
Originally Posted by TeraBlight
Sounds like a lot of work
Yes, this is going to be. Although once I get the basic functions for doing this, I will be able to port it over to other "more modern" languages (once I learn them).

I do plan to finish this one all the way in VB6 though. Once I get the map generators tweaked out, I'll probably use my DX8 isometric engine to display it. Of course I only have outdoor graphics for it right now. Some of those graphics are slight modifications from "other sources", but mostly not.

Here's an old screen shot of the map editor of that. It uses the same "map array" that I will be generating with this system. So I should be able to use that graphics engine pretty easily.

Thanks again for the replies.
Attached Images
File Type: jpg screenshot.jpg (96.9 KB, 80 views)
Reply With Quote
  #9  
Old 06-18-2005, 02:06 AM
Rockoon's Avatar
Rockoon Rockoon is offline
Joseph Koss

* Guru *
 
Join Date: Aug 2003
Location: Unfashionable End
Posts: 3,615
Default

Some links:

Generating random universes:

http://www.gamasutra.com/features/20010302/oneil_01.htm

Generating terrain:

http://www.vterrain.org/Elevation/artificial.html

Procedural RPG maker:

http://www.gamingw.net/tutorials/781

You might also want to check out the source code to NetHack, which generates random dungeons.
Reply With Quote
  #10  
Old 06-18-2005, 11:45 AM
shadowk's Avatar
shadowk shadowk is offline
Freshman
 
Join Date: Apr 2005
Location: Hell
Posts: 32
Default

http://markbutler.8m.com/subpages/vb-tutorial5.htm

You should check this link out, it has something that you could use, namely a good example of generating rooms+hallways+items+monsters

p.s. i like your graphics, is there any chance you could tell me where i could fine those "other sources" ??????please.......
__________________
>>May the Sky never fall on your Head
Reply With Quote
  #11  
Old 07-20-2005, 07:47 PM
DubbleClick's Avatar
DubbleClick DubbleClick is offline
Contributor
 
Join Date: Mar 2005
Location: Tennessee
Posts: 511
Smile Update... Some code done

Well, I have managed to get a little coding on this done.

I've attached if anyone wants to look at it and make comments.

What I've got so far are a few subs and functions that - basically
1) drops a bunch of random size (square only so far) rooms on a map,
2) resizes the rooms to fill some of the gaps
3) makes all the leftover tiles as halls
4) joins them up numerically.
5) shrinks the hall array down.

The interface is hideous... it is just a form with some freaky color lables. But it's just to see what's happening. Nothing like this will be part of the engine.

Things I am going to work on next
1) creating a flow through the map (start and exit location, add doors to rooms, place keys to locked doors in areas so the flow will work)
2) Item generator to place in various places.

Haven't decided if I will add NPC placement generator in this Module or if that will be a new one.

Please, if anyone see's any code that looks totally hideous, let me know. I just banged this one out. I am SURE it has a few bugs/ innefficent code...etc.

I have "thought" about further modifying the hallway system, as it does leave small meaningless ones at times. Haven't decided or not. I can and will make use of the way they generate as of now.

Any feedback is appreciated.
Attached Images
File Type: jpg image.jpg (132.6 KB, 62 views)
Attached Files
File Type: zip MapGen.zip (9.6 KB, 51 views)
Reply With Quote
  #12  
Old 07-20-2005, 09:10 PM
TeraBlight's Avatar
TeraBlightGenerating a Random Dungeon Map... TeraBlight is offline
Captain Convoluted

* Expert *
 
Join Date: Jun 2005
Posts: 1,918
Default

For version 0.00000001a it's not bad at all, really!
No, seriously, the approach seems to yield almost exactly the results you were looking for, so well done! I just knew that iterative was the way to go

Suggestions:
  • In Type Room, change "FirstX" and "FirstY" to "Left" and "Top", since you are already using "Width" and "Height".

  • Put all off the display code in the form.
    I'm not just saying this because of the "bad practice to access a Form's controls externally" debate, but because it'll make for a much cleaner structure if you put all the temp code in the form. You could change your public sub to something like
    Code:
    Public Function GenerateMap(xmax As Long, ymax As Long) As Tile()
    The caller of the module would this way request a map of a given size, which would be created and returned. It's then up to the caller to decide in what fashion the map is displayed. (Just need to make the UDT Public, of course...)

  • Numbering the hallways could be simplified by using a recursive approach.
    Whenever you encounter a hallway without an ID, you create a new ID and call something like
    Code:
    Private Sub JoinHallway(ID, x, y)
    which would tag the tile (x,y) as belonging to hallway ID and add the tile to the new slot in Hall(). Then, you look at all neighbouring squares, and if they too are hallways, you call JoinHallway with the same ID and the neighbours x and y. That way, you would catch all connecting tiles without having to keep track of the number of junctions in a hallway.
    I wrote a MineSweeper clone that uses this technique to reveal connected empty regions... if you need some coding inspiration, it's shown here:
    http://www.xtremevbtalk.com/showthread.php?p=1012219
    This is a typical situation in which recursion reduces the complexity of the code you need to write by a LOT.
Hope those are useful
__________________
"To learn without thinking is to labour in vain" - Confucius
Reply With Quote
  #13  
Old 07-20-2005, 09:31 PM
DubbleClick's Avatar
DubbleClick DubbleClick is offline
Contributor
 
Join Date: Mar 2005
Location: Tennessee
Posts: 511
Default

Thanks, those are some Good tips. I really do need to clean it up before pressing on. I got a bit sloppy with the form code in the module.

So that'll be the first thing I do.

I also thought of the idea of using MAP_X and Y as parameters for calling the generate map.. 'cause ya know there would be lotsa map sizes in the game anyway. I just never thought of having it RETURN the Tiles() though. Good one.

About the Hallways. MAN I HATED THAT! I had the most trouble with those boogers. I will DEFINATELY look into your mind sweeper code and take a look at how you handled it. I struggled with that part. Recursion is not my strong point. Need to get better at it for sure.

Welp, bed time. Zzzzzzzzzz

Last edited by DubbleClick; 07-21-2005 at 09:13 AM.
Reply With Quote
  #14  
Old 07-21-2005, 10:03 PM
zelg37Generating a Random Dungeon Map... zelg37 is offline
Contributor

* Expert *
 
Join Date: Dec 2004
Location: Oregon, USA
Posts: 606
Default "Smart"-ly random maps

Quote:
Originally Posted by DubbleClick
About the most famous of ALL games in which has random map generators is Diablo 1 & 2. I guess that's why those games stay popular for so many years... the maps are always different for each game.
I have a friend who is totally obsessed with Diablo II: LOD (as well as the other Diablos...even the lame HellFire commercial mod) and he says that after you've played a couple 1000 times the "patterning" of the randomness becomes evident.

I think it all comes down to what it takes to automatically generate a "good" rpg map (and the "randomness" quality/quotient seem to be very low on the list).

Even though I think SimCity is pretty boring, it's based on using a set of AI rules. Like if you have any decent size community you need to have a water supply, roads, some kind of food supply, etc. Translated to RPG-ness, this means if you have a dungeon, then of course you are going to have monsters, treasure, traps, and some kind of nasty NPC scheme behind it all.

So instead of geography/architecture being primary focus, may you need to "back into" the actual layout. What do I mean by that? Think about the layout of an rpg (whether an outdoor or dungeon-based) in terms of a lego-ing together story elements. Are there a tribe of orcs hanging around anywhere in your RPG world? If so, what exactly are they doing beside just "hanging out"? Do they have some purpose? Perhaps "taking over" a geographical feature (a certain end of a valley) or are they busy fighting some other set of creatures (bugbears? centaurs? etc.) How are they going to use the geography to their advantage.

Perhaps if you're doing something underground, what about some abandoned dwarf or drow city. What was the main purpose of locating the city in that certain place? (Mythral mine? Search for arcane magic? Some weird religious cult?) Why was the city abandoned? Who/what has taken over? (and how did the re-occupy-ers re-shape things?

A map layout AI driven by story line(s) - what a concept, hmm..

If you think up a bunch of scenarios (each with a set of pre-made geographic/building elements) then it will add a certain sense of "purposeness" to the assembling/placement --this can be reflect in a set of rules about what goes with what (i.e. if you have element "E" then there is certain set of statistic chances that other elements will be present - element "g" (61%), element n (21%), elements "q","t", and "w" (6%) each or whatever ratio you can come up with).

Just make sure when doing 'imagineering" of scenarios that they are all based around the concept of "something-about-to-happen". A war about to breakout, some personal tragedy about to unfold, something that is just on the cusp/verge/brink of "getting out of control" and/or some sort of chaos is about to insue demanding a hero (or group of heros) to "set things right" --or at least have some fun! ).

You might be turned off by this level of thought-complexity, but it would probably add to the 'replay-ability" if you take the time to develop a rules based AI for assembly, placement, and snap-together backstorying.

Anyway just some thoughts I had reading through this thread..

Last edited by zelg37; 07-21-2005 at 10:15 PM.
Reply With Quote
  #15  
Old 07-22-2005, 06:03 AM
DubbleClick's Avatar
DubbleClick DubbleClick is offline
Contributor
 
Join Date: Mar 2005
Location: Tennessee
Posts: 511
Default

Thoughts.... good ones at that. However, let's not get too ahead of ourselves, just yet anyway.

1 Step at a time. We'll get there. Eventually.

I have, in fact, thought through this in pretty good depth. Your thoughts pretty much line up with what I've had on my mind. I suppose I could go ahead and give a layout of what I plan to do, and what's left to plan.

Hmmm... this may be a bit rough (just got outta bed), but should give you the jist of things.

I will create 4 map generators
1) Dungeon (currently in work)
2) Town/City (easy mod to this one)
3) Forest/Landscape (already have one of these, but am going to modify it a bit)
4) Detailed area/room for Combat mode (kind of a zoomed in view of where you are)

Each of the first 3 generators will include NPC generation and placement along with any and all items.

5) There will have to be an NPC generator that creates random (but structured) NPCs
6) And Item generator that is capable of creating thousands of unique items. These are pretty common in games now-a-days and are easy to make.
7) Random script generator for NPC's. Shouldn't be too hard. Most of this time will be spend just writting the many hundreds of "npc text" lines to pick from. I may recruit some "volunteers" to help with this.

Last thing I have on my list is a random STORY generator. This will take the most care and effort.
You know how the Diablo series is. Random area maps, but STATIC game story. I'm going to take a stab at some sort of random game story. May not work, but we'll see when we get there.

Again though, 1 step at a time. Still have LOTS of work to do on the map generating. So I'm not even going to fret over AI and Story right now.
Reply With Quote
  #16  
Old 07-22-2005, 06:34 AM
DubbleClick's Avatar
DubbleClick DubbleClick is offline
Contributor
 
Join Date: Mar 2005
Location: Tennessee
Posts: 511
Default

One quick thing I had to change... When expanding the rooms, it always expanded them in the same order (up, down, left, right)... which resulted in most of the rooms being tall and few being wide.

So I changed that sub as follows.
Code:
'============================================================================== Private Sub ResizeRooms() '============================================================================== 'The random room generator leaves a lot of blank areas on the map. Take eacyh room ' and see if it can be expanded to fill in the blank areas. We only want to expand ' to 1 emppty square. We don't want to collape hallways. '============================================================================== 'Ver#2 - Had a problem with most rooms being too tall and skinny. So I am changing it to ' randomly select the order in which is expands. Dim i As Integer, r() As Long, x As Integer For i = 1 To UBound(Room) r = GenerateRandomLongArray(1, 4) 'Function to generate a random order array For x = 1 To 4 Select Case r(x) Case 1 ExpandRoomUp i Case 2 ExpandRoomDown i Case 3 ExpandRoomLeft i Case 4 ExpandRoomRight i End Select Next Next End Sub
There's a function to do the random array as well.

Just wanted to post this incase anyone had noticed the "tall room" syndrome the engine had.
Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off

Forum Jump

Advertisement:





Free Publications
The ASP.NET 2.0 Anthology
101 Essential Tips, Tricks & Hacks - Free 156 Page Preview. Learn the most practical features and best approaches for ASP.NET.
subscribe
Programmers Heaven C# School Book -Free 338 Page eBook
The Programmers Heaven C# School book covers the .NET framework and the C# language.
subscribe
Build Your Own ASP.NET 3.5 Web Site Using C# & VB, 3rd Edition - Free 219 Page Preview!
This comprehensive step-by-step guide will help get your database-driven ASP.NET web site up and running in no time..
subscribe
Generating a Random Dungeon Map...
Generating a Random Dungeon Map...
Generating a Random Dungeon Map... Generating a Random Dungeon Map...
Generating a Random Dungeon Map...
Generating a Random Dungeon Map...
Generating a Random Dungeon Map... Generating a Random Dungeon Map... Generating a Random Dungeon Map... Generating a Random Dungeon Map... Generating a Random Dungeon Map... Generating a Random Dungeon Map... Generating a Random Dungeon Map...
Generating a Random Dungeon Map...
Generating a Random Dungeon Map...
 
Generating a Random Dungeon Map...
Generating a Random Dungeon Map...
 
-->