Corridor Creation in a Roguelike
Monkey Forums/Monkey Programming/Corridor Creation in a Roguelike
| ||
| Hi all, I have been working on map generation in a roguelike. The map is a 2D array of ints. Currently I am using a panel system where a map of 100,100 is split into 10 vertical and horizontal panels. The room and door generation is fine and I am going to add more complexity as I go along. I have done the corridor generation several ways and haven't been happy with any of them. I have used lists of doors, lists of rooms and even used an astar pathfinder to create corridors between points. I know there are a lot of people on here smarter than me so I would be interested in more suggestions. I have looked at the one sample in the code section and read a lot of different articles online. I have even checked out open source code for some popular ones but the code is so long and detailed it is difficult to apply it to my method. So basically I need to work form either a list of rooms, doors that are already generated or I am open to changing either if there are some good suggestions. Thanks for taking the time. |
| ||
| I was looking into this pretty heavily for quite a while but I think I was using VB.NET at the time for it as I was going to do a true console-based roguelike. I believe what I did was very simple in that I would break my map into panels (maybe like you are doing) by splitting a panel in two either vertically or horizontally to a random size (with a minimum of like 5 blocks in either direction). I continued to do this until I had reached the minimum "room" size I allowed. At that point I would knock out random room shapes from a collection of shapes (round, square, rectangle, etc). At that point I had all my rooms (which appears to be where you are at). Where panels touched I would create doors in that side of the room on each panel and create straight corridors from one panel's room to the other panel's room. This would connect every room to another room. It worked for anything that would look like a dungeon or "built" structure, but if you were wanting more of a cave-like look, then you would need to replace those room "shapes" with more of a fractal room generation that would knock out random shapes in the panel (my room shapes were always smaller than the panel size but "caves" could be as big as the panel, creating it's own potential connections to the panels next to it without doors.) Then do the same with a random corridor routine. Say you have one panel above and one below. Generate a corridor from top to bottom by randomly deciding to go left, right, or down, with a much heavier emphasis on down (like 20% left or right and 60% down). You introduce a lot more random looking generation there, but you also run the risk of your rooms not joining because of the randomness of the corridor creation. I'm no math whiz, which is why I went with the more structured "built" look to my maps, but I think the above techniques might help you some. |
| ||
| I mostly use cellular automatons for cave-like systems. But thinking about rooms, here is what I would try: 1. Make rooms that are embedded in a fairly dense, not too regular, web of corridors. (But for a first attempt, the web can be a simple square grid.) 2. Start randomly removing corridor sections. If the map becomes disconnnected after one is removed, put it back. 3. Terminate when the corridors are sparse enough for your liking. There should be enough options there for quite a bit of variety. I implemented something similar though not identical once in C++ and it worked well. This page has examples and source, and even a Windows .exe for playing with parameters: http://newsgroups.derkeiler.com/Archive/Rec/rec.games.roguelike.development/2007-09/msg00042.html But it may well be that others have created better and simpler methods. Have you read the articles on Roguebasin? |
| ||
| Ack! That code is more complicated than I remember! But the algorithm is usable. I wanted to be able to make corridors of variable width. However the method I described above should be capable of doing that too, without the 'expansion' stage. |
| ||
| Thanks for the suggestions. I have read almost everything I could find, especially at roguebasin. I do intend to have cavelike dungeons and I have looked at cellular automatons for that. Kanati, I did look at a BSP method that sounds like what you are referring too. The problem is that the rooms don't always line up so the corridors can miss the adjacent rooms. I will look back into this. I am still open for more suggestions. Thanks so far, I appreciate the input. |
| ||
| Here are the two methods I've used to generate rogue-like dungeons. The first, generate a perfect maze, 'clear' out some 'areas', and then add/not add walled perimeters to those areas. There are no 'corridors' in the true sense, but some very interesting and complex maps are generated. I have some code in the Blitzmax code archives demonstrating that approach, but I've not yet ported it to Monkey. Alternatively search for 'perfect maze generation' on Google (there are plenty of examples out there) and then roll your own modifications. The second method produces more traditional, rogue-like dungeons, featuring rooms connected by corridors. Simple code for this is in the Monkey archives, so you've probably already seen it. IIRC, this is the procedure. 1. Create a completely filled dungeon. 2. Carve out some non-overlapping, non-adjoining areas at random locations and of random sizes, recording the areas' coodinates and dimensions in a list or array. 3. Carve out a corridor from each area to the next one, in sequence, using the following process: 3a. The starting coordinate of the current corridor is randomly chosen within the current area. 3b. The target coordinate of the current corridor is randomly chosen within the target area. 3c. The corridor may initially proceed vertically or horizontally, depending on the target area's location relative to the current area. 3d. When the corridor reaches the target's vertical/horizontal coordinate, then continue carving at a right angle if necessary until the target coordinate is reached within the target area. It may appear that some areas are connected by more than one corridor (this is good thing, IMO), because your carving process continues 'through' any areas that are not the target area. |
| ||
| Thanks, Impixi. I think I will play with method 3 and then I may experiment with creating the maze(corridors) first and then dropping rooms on it. I will also check out the max archives and take a look at that. |
| ||
| BTW, the real fun with rogue-likes begins with line-of-sight algorithms. ;) |
| ||
| How do you mean? For what? |
| ||
| Well, unless you want the player and other creatures to see everything within a specific radius, regardless of walls in the way, you're going to need to take a line-of-sight approach. Most rogue-likes do that, where walls obscure vision. It's more complicated than you might think to achieve 'accurate', 'realistic' results. For me it was, anyway... |
| ||
| My team had to do something similar in the ICFP this year to create test cases so our AI could apply machine learning algorithms. What I did what randomly make a number of seed points and give each a random score. Then I ran a simplified version of a particle swarm optimization algorithm to 'find' the highest scored seed point. If I marked wherever these 'particles' visited as open space, it made a pretty nice looking cave system. You do have to play with the seed generator and number of particles to get it looking right however. The other upside is that it was a really simple algorithm to code. |
| ||
| @maltic - I used a very similar method to create complete outdoor worlds for a map generator I created years ago in Blitz Basic. It worked really well. I am considering using it for this roguelike and having a full outdoor world with towns that are randomly generated and then quests can be picked up at different areas which lead to indoor roguelike dungeons. I want the dungeons to have a large range of types: caves, towers, crypts, dungeons, etc. |
| ||
| Line of sight is not too hard, really. Just employ Bresenham between centres of squares. An option I have found useful is to consider a square adjacent to an empty LOS square to be semi-visible. You can see what's on it but you can't target it with arrows etc., and it is shown shadowed. |
| ||
| Just employ Bresenham between centres of squares. The technique I employed used a modified Bresenham algorithm, projected into multiple quadrants, or something like that. It was a pain to implement at the time, maybe because the accompanying explanatory text wasn't clear on certain points. |
| ||
| Liking the dialog. I am open to any other roguelike tips/concerns. I have played around in Blitz for years and am finally devoting more time to overcoming issues. Since this is a hobby, I have a tendency to move to something else when I get bogged down. But I am thinking lately it would be nice to have a good roguelike on my shiny, red Lumia 920. |
| ||
| But I am thinking lately it would be nice to have a good roguelike on my shiny, red Lumia 920. There will be in a few days/weeks. ;) |
| ||
| Oh, do tell :) Thought you were working on a sub game? Let me know if you need a beta tester! |
| ||
| Hehe, yes. I usually work on 2 projects the same time. lol. Well actually my intention was NOT to demotivate you so sorry for that! It will be more a tiny game with a procedural created dungeon... |
| ||
| About the Line of Sight, I once implemented the LOS algorithm mentioned here: http://www.adamantyr.com/crpg/article_04.htm It's very simple with good results. |
| ||
| @xaron, no demotivation. As I said before, this is a hobby. I have a REALLY ambitious plan that I have been writing a doc for(One Note is awesome by the way and SO cross platform.) I think the scope is too large for mobile. I may do a subset for mobile, but if I do everything I want it will have to be PC, Mac and Linux based. I actually considered writing it in Max because of this, but I think I am going to stick with Monkey. I purchased Ignition for both Max and Monkey just in case. Right now I am just writing everything in straight Monkey though. Just in the initial prototyping stage and experimenting with different types of dungeon generation. I have already purchased the music and some of the best pixel art/tiles I have ever seen. The art is stunning. Unfortunately, it won't be finished for 6-12 months but I am rolling with placeholders and it will take me at least that long to get it all together anyway. Everything is going to be random. Outside world, towns, dungeons of all different types, quests, music is going to be randomly selected from predefined lists based on the scenario. I have worked out much of the skeleton. It needs fleshing out, especially the magic system, I can't decide how I want to go there. |
| ||
| Oh well that sounds awesome and is really some classes above what we do. I'll show it as soon as it's done which will be this year. Good luck with your project, it sounds really ambitious. |
| ||
| This is all good stuff. I've found some helpful articles on GameDev.net as well. My basic rogue-like game for Monkey Touch was about as basic as you can get. :-) I might plan on doing a sequel with more stuff at some point in the future... Looking forward to some rogue-likes! |
   |