Dark Bit Factory & Gravity
PROGRAMMING => General coding questions => Topic started by: Pixel_Outlaw on May 11, 2008
-
I'm just about done with my dungeon generator but I'm really stuck with adding rooms.
I'm using my own methods and I just need the last piece to the puzzle. That piece is creating rooms inside an array.
Basically I need an array. This array has the value 0 at cells that don't have any room in them and 1 for cells that would have a room in them. Room cells (1) are shown here as blue cells. Also no two rooms may touch, meaning that rooms need a 1 cell border between them. I just can't quite envision how this would be done. There should be a max number of rooms (once reached no more rooms are added). Also it would need to have a max room size and a minium room size. This is a very complex problem for me. Does anyone see any good methods?
(http://img341.imageshack.us/img341/120/imagekm7.png) (http://imageshack.us)
-
You've picked another reasonably hard problem ;) There's no 'best' solution to this, so you have to pick something that will work. In general this problem is called 'the napsack problem'. So you can ask google about that.
Do you know the room sizes and land size before you start?
If you do, then I have some stuff I used for Soduku and Boggle solving that might help - recursive stuff where you add one of the rooms and then pass the state down to an algorithm that knows where best to place new rooms.
Jim
-
Dont know if this will work but it may be worth a shot. Go through though array and look for junctions, decide randomly whether this junction is going to become a room or just remain a junction. Once thats done for all junctions use the length of the passage that the junctions lie apon half the length minus a random number this gives you a length in one dimension, the rooms wont overlap for the most part, they will be like an overlay on top of the passages. if rooms do overlap they will combine to form non rectangular rooms
-
I know that you probably have a good idea rain_storm but what do you mean by junctions?
-
I was assuming that you wanted to modify your maze generator to do this, was I mistaken?
-
Well this is for the maze generator yes but also I wanted to try using the A* algorithm to connect rooms. So the answer is yes but not specifically.