   Roguelike Dungeon Generation[C++]
  Hello.I've been screwing around with trying to make my own roguelike for a couple of weeks, on and off. I have a good event/message system and display going on, but I've become stuck at generating the dungeon.I've tried BSP trees, cellular automata (cave like), and a few others. I found the BSP trees to be good (using that to generate rooms), but I didn't like the corridors produced.My 'current' method of producing corridors is to:Go through each room (have a vector of them), and connect it to another random room. This should make everything connected, but it's failing for some reason.Generate a number of corridors between random rooms.I generate corridors by: (in pseudocode. My code is hard to read. D:) dy = first.y - second.ydx = first.x - second.x remainingY = dyremainingX = dxcurX = first.centre.xcurY = first.centre.y //start at the centre of the room//Distance to travelcontainer = abs(dx) + abs(dy)if(dx == 0 or dy is 0)just move straight up or straight acrosswhile(remainingY and remainingX and container are not 0)if(random between 1 and container <= remainingY) //proportional and random//move in ymake this tile a corridor tileremainingY--; container--; curY -- or ++ depending if dy is positive or negativeelsemake this tile a corridor tileremainingX--; container--; curX -- or ++ depending if dx is positive or negativeend whileThis is what is generated. Some of the rooms aren't connected, however when I generate corridors between rooms I set the isConnected of both rooms to true. I've checked, and everything *is* connected, but the corridors have not joined. So I think it's an algorithm issue, but I can't see why.Thank you very much for your time GD'ers.-MarkHere's my proper code, if you can read it. (sorry for the lack of comments, pseudo might be easier)int8 dy = two->GetCentre().y - one->GetCentre().y;int8 dx = two->GetCentre().x - one->GetCentre().x;int8 remDX = dx, remDY = dy; //How much to move.uint16 container = std::abs(dy) + std::abs(dx); //First dy values are dy, and the rest are dx. Helps for proportionate//Random number generation without needing integration.Point point(one->GetCentre());//StartPoint finish(two->GetCentre());//endstd::cout << "foo";while(remDX != 0 && remDY != 0 && container != 0)//While we need to move{if(dy == 0 || dx == 0) //Straight across or straight down; rare.{while(point != finish)//until we hit finish.{level->ReplaceTile(point.x, point.y, new FloorTile(point.x, point.y));if(dy == 0) { point.x++; }if(dx == 0) { point.y++; }}remDX = 0; remDY = 0; //Hack.}else if(random->Random(1, container) <= remDY){if(dy > 0) //We're moving in Y. This sees if it's up or down (true == down){if(level->GetTile(point.x, point.y)->id != FLOOR)level->ReplaceTile(point.x, point.y, new FloorTile(point.x, point.y));point.y++;remDY--; container--;}else if(dy < 0){if(level->GetTile(point.x, point.y)->id != FLOOR) // move up.level->ReplaceTile(point.x, point.y, new FloorTile(point.x, point.y));point.y--;remDY--; container--;}} else //X moving.{if(dx > 0) //We're moving in X. This sees if it's left or right (true == right){if(level->GetTile(point.x, point.y)->id != FLOOR)level->ReplaceTile(point.x, point.y, new FloorTile(point.x, point.y));point.x++;remDX--; container--;}else if(dx < 0){if(level->GetTile(point.x, point.y)->id != FLOOR) // move leftlevel->ReplaceTile(point.x, point.y, new FloorTile(point.x, point.y));point.x--;remDX--; container--;}}one->isConnected = true;two->isConnected = true;}[Edited by - The Communist Duck on May 22, 2010 5:17:45 AM]
  Set your corridors' floors to a "." tile, and set your rooms to have their floors a "_" tile, so you can tell the difference. My first guess is that you might be creating corridors that start and end in the same room. You've not shown the corridor endpoint selection algorithm here, only your corridor-drawing algorithm, which is essentially a messy rewrite of Bresenham's line-drawing algorithm.You're using C++; you should brew up a template-based Bresenham to easily exploit where needed. Rougelikes often need a line-tracing algorithm anyways, and Bresenham's is a cheap fit for the bill.   ;  I think the best general approach would be to randomly generate a graph in which rooms are nodes and corridors are edges, and then visualize the graph with an appropriate graph drawing algorithm perhaps one of the orthogonal ones. However, the above isn't really saying much because there are all kinds of graph drawing algorithms and finding and implementing a good one can get pretty complicated.   ;  Thanks guys for the responses (sorry about the delay in replying).Wyrframe: I thought I recognised what I was doing. I have a Bresenham implementation somewhere, I'll dig it up.jwezorek: I've heard a lot about graphs, but never really understood them past the fact they're not the same as the graphs you use for statistics, etc.By the looks of it, do they just have an N number of nodes, each of which are joined to other nodes?Can you point me perhaps to any other resources on this? I've been looking on google searches, but I'm not entirely sure of what I want/need.I have found this pdf, which looks hopeful. The two kinds that striked me as relevant were the orthagonal one, and the polyline one. However, the polyline I could forsee as either being more complex to implement, or slower to run (or produce strange corridors, seeing as I'm running at character level not pixel level).I'll try and implement both (for practice, can't go wrong there? :P), and see which I prefer. Or switch between them for more randomness, if there's any real difference.Thanks muchly again. :D-Mark.   ;Quote:Original post by The Communist DuckBy the looks of it, do they just have an N number of nodes, each of which are joined to other nodes?Can you point me perhaps to any other resources on this? I've been looking on google searches, but I'm not entirely sure of what I want/need.Pretty much. More here. I don't think graph drawing algorithms are going to help you though - usually they start with the graph and fit it onto a 2d area for viewing, whereas you've got the reverse - you're starting with a 2d area and want to generate a semi random graph on top of it. Plus graph drawing algorithms emphasise clarity for reading a whole graph - for a game you want something that's complex and interesting to explore.I think you've got two problems:1. Not all rooms are connected.2. You're not happy with the corridors that are generated.For '1' I think you're just going to have to sit down and debug it. Probably, as mentioned, you're occasionally connecting a room to itself (or to a room already inside another room). And making sure all rooms are connected to another room doesn't gurantee that you can get from any room to any other room.Usually you'd do a flood-fill to determine reachability from any given room. You might want to connect some random rooms, then flood fill from one of these to find an island of connected rooms, then connect the remaining rooms to rooms within the island.For '2' you should read unangband dungeon generation (parts 1-8). It's very detailed and will show you the approaches you can take.   ;My project uses graph-based procedural map generation, and seems to work rather well. You could take a look at the TreeNode class's createTree function. It creates a tree (a type of graph without loops) that fits nicely into a plane, and then creates a few loop edges to connect nodes that are close together in space but far apart when traveling only along the graph edges. I'm laboring under some constraints you probably don't have. For example, I care strongly if two edges intersect, or if two parts of the graph are connected and I don't know about it. That's because I'm trying to direct the player's motion through the game. Roguelikes generally don't have that kind of problem, though, which will simplify your map generation.   ;  Ok, thanks for all the input guys. Much appreciated. :DI was fiddling around, and made a short implementation of an idea I had. I would choose random points in the rooms, and go along-down or down-along, such as drawing a rectangle between the points.It's fully connected, and was quick to do. So that's good.However, it does have the downside of being very gridlike and regular. So I might need to fiddle with that. But hey. :DThankyou.P.S. Derakon, that project looks awesome.   