Roguelike Map Generation

Page: 1 2
ID:1901533
 
Jul 22 2015, 4:14 am
Hey, so I've been busy lately but I've managed to fit in some time tonight to work on Roguelike map generation for the giggles.

My main resource is here: roguebasin guide

I was interested in hearing how you guys might implement this algorithm in DM and what your thoughts on this kind of generation are.

The Algorithm:
1. Fill the whole map with solid earth
2. Dig out a single room in the centre of the map
3. Pick a wall of any room
4. Decide upon a new feature to build
5. See if there is room to add the new feature through the chosen wall
6. If yes, continue. If no, go back to step 3
7. Add the feature through the chosen wall
8. Go back to step 3, until the dungeon is complete
9. Add the up and down staircases at random points in map
10. Finally, sprinkle some monsters and items liberally over dungeon

What I did tonight was allow the user to create structures on Level 1 of their map which they want to use in dungeon generation. The user specifies what structure they have created by using the lower left corner and upper right corner of the structure.

# define ROOM_LEVEL 1

var/list/rooms = list()

proc
    Generate_Rooms()
        rooms += new/Room(locate(1,1,ROOM_LEVEL),locate(25,16,ROOM_LEVEL))




Then I've got as far as Room.mesh which is 2D array of the structure with 1 for dense tile & 0 for non-dense. So now I should be able to see if 2 rooms collide because they will share a 1 in the same place.



In theory you should be able to create pretty non-trival structures with irregular shapes. (something more like Diablo 2)

~ Just what I've been up to tonight for fun. (Because friends are too mainstream)
Jul 22 2015, 4:26 am
I just realised there's a way better solution than a mesh. Instead I can just store the coordinates of all dense turfs of the structure in a single 1 dimensional list.

Comparisons otherwise would of course be O(n^2) otherwise which would be awful.

For now, sleep(timeUntilMorning)
Jul 22 2015, 5:33 am
you should totally make this a new library/demo I'd love to have a roguelike map generator or even a random map generator in general
Jul 22 2015, 11:24 am
In response to Mastergamerx
You should use the search function; there are a few dungeon generators already.

http://www.byond.com/developer/?text=map+generator
Jul 22 2015, 2:46 pm
Glad to see someone experimenting with Roguelike map generators. I have a special place in my heart for those.
Jul 22 2015, 5:19 pm
Mastergamerx wrote:
you should totally make this a new library/demo I'd love to have a roguelike map generator or even a random map generator in general

Yeah I'll keep working on this and see where it takes me. It's very fun :)

Lummox JR wrote:
Glad to see someone experimenting with Roguelike map generators. I have a special place in my heart for those.

Exactly, same here :)
Jul 23 2015, 2:20 am
Welp I finished:
5. See if there is room to add the new feature through the chosen wall

Intersection is a slow algorithm but I've sped it up as much as I possibly can.

world << room1.intersects(room2,0,0,4,5)

Where 0,0,4,5) represents how these rooms are offset on the map assuming they were both placed.

I've tested it and it works exactly as required.
Jul 23 2015, 5:39 am
The problem with that algorithm is that it generates tree structures - it's very hard to add cycles in any sensible way.

The algorithm I've found works best is in this library, but basically you plop down a bunch of predefined rooms, and then you link them all up by pathfinding through walls. Cycles can then be added on top by picking two spots on the 'outside' and pathfinding a new route between them. Also easily allows for cute tricks like rooms with chasms going through the middle of them (i.e., not all border turfs are reachable from any border turf) while maintaining full reachability over the entire map.
Jul 23 2015, 5:58 am
In response to Jp
You're right that it struggles with cycles. A very astute observation. My plan to solve that was to add random cycles later.

I went over your idea mentally before I got started on anything. I think it's what a lot of people would think of as their first idea. I liked that it had guaranteed connectedness and liberally assigned cycles. What I didn't like was that it's difficult to space rooms evenly and/or use available space as best as possible. Traditional Roguelike maps are very tightly packed, reflecting the memory space availability of the time I presume.

My hope is that by the time I get to cycles I will have thought of a good way to do it which gives straight and logically placed hallways as part of cycles.
Jul 23 2015, 5:59 am
In response to Jp
Also, as research before I got started I had a look at your library :) So I've already spent some time with it.
Jul 23 2015, 6:45 am
In response to Zecronious
I think the best thing you can do is select random border tiles (walls adjacent to floors) and pathfind between them, setting up the pathfinding so it generates 'straight' hallways preferentially.

A lot of old roguelikes generated rooms in a loose grid pattern. I think Rogue divided the map into six segments - top left, top middle, top right, bottom left, bottom middle, bottom right - placed a single room in each segment, then linked them up. Each room was smaller than the segment, obviously. You could do something like that - don't just scatter the initial rooms randomly, place them in particular ways to make them close together.
Jul 23 2015, 7:46 am
My dungeon generation dream is to be able to randomly generate a dungeon from Zelda, with intelligent placement of puzzles and encounters and so forth for good pacing.

So, to this end, this is my favorite algorithm: http://www.roguebasin.com/index.php?title=Abstract_Dungeons

It's very easy to modify to add appropriately placed locked doors and keys, treasures, traps, puzzles, and other encounters.
Jul 23 2015, 8:48 am
Rogue did nine segments.
Jul 23 2015, 8:09 pm
Now this is my kind of thread. I have always had a strong love for Diablo II, and that love birthed a love for rogue-likes. The lack of rogue-like content and/or games as whole in BYOND has always saddened me, and been on my list to change.

Glad to see this thread moving things along to change that, and make them easier to do. JP has a good library, but for some reason I never did make heads or tails of it when I messed with it over about 2? years ago. It's probably just one of those subjects and libraries that takes someone of at least intermediate level skill, if not advanced, to understand; which I was not at the time.
Jul 23 2015, 9:31 pm
In response to Jp
Jp wrote:
I think the best thing you can do is select random border tiles (walls adjacent to floors) and pathfind between them, setting up the pathfinding so it generates 'straight' hallways preferentially.

A lot of old roguelikes generated rooms in a loose grid pattern. I think Rogue divided the map into six segments - top left, top middle, top right, bottom left, bottom middle, bottom right - placed a single room in each segment, then linked them up. Each room was smaller than the segment, obviously. You could do something like that - don't just scatter the initial rooms randomly, place them in particular ways to make them close together.

Ohhhhhh, that makes so much sense.

Jul 23 2015, 9:33 pm
In response to D4RK3 54B3R
Jp wrote:
My dungeon generation dream is to be able to randomly generate a dungeon from Zelda, with intelligent placement of puzzles and encounters and so forth for good pacing.

Now that I would really like to see.

Toddab503 wrote:
I have always had a strong love for Diablo II, and that love birthed a love for rogue-likes. The lack of rogue-like content and/or games as whole in BYOND has always saddened me, and been on my list to change.

My sentiments exactly :)
Jul 24 2015, 8:12 am
Today I've completed Room.place(). That's pretty much all the really tough code done I hope. Famous last words?

    var/Room/room = rooms[3]
    room.place(locate(3,3,2))


Really the last part now is working out how I want to organize the rooms. I've done some research into Diablo 2 to see how it works. Now I know how the original roguelikes worked.

I'm thinking something which will be between the two. It will require more thought.
Jul 26 2015, 2:58 am
Finished it. This is a dungeon made of 200 rooms formed from 19 pre-formatted rooms.

The results I think are disappointing. The generation is extremely slow taking about 15 seconds to do 200 rooms. The maps are also repetitive. I can imagine them getting boring quickly.

Jul 26 2015, 3:20 pm
It looks nice to me, but I'd have to see the whole map. The number of doors is rather high. I bet the generation could be sped up with some simple optimizations.

The problem of repetitiveness probably comes from the limited pool of options to choose from, but it could also be a flaw in the algorithm.
Jul 26 2015, 3:33 pm
In response to Lummox JR
Yeah, it's basically just amazing how fast you learn all 19 rooms pretty quickly. I can increase the pool size without affecting the speed of the actual generation algorithm which is nice at least.

Door count is interesting. If I only include the doors used in generation then the count is very low. If I however add doors always where logical (what it does now) then the door count may be too high.

If I have 2 rooms and place one between them, it might be logical to join all 3 rooms if they border each other. Currently it does this to increase connectivity.

There's probably a number of ways I can increase the algorithm speed. Where all the CPU use seems to come from is checking to see if a room can actually be placed and then continuing with random doors until I find an area it can be placed. Basically O(n^3) repeated 200 times.
Page: 1 2