Maze algorithm in python libtcod rl

[Aukustus]

I have used the python tutorial from roguebasin for some time for my project and now I'm wondering how to make a maze. Since the dungeon builder is designed on filling the map and then carving rooms and drawing lines from center to center and maze generators seem to be made for printing. Does anybody have an idea how to implement an algorithm such as this?

Example code from Rosetta Code:

Code: [Select]

from random import shuffle, randrange
 
def make_maze(w = 16, h = 8):
vis = [[0] * w + [1] for _ in range(h)] + [[1] * (w + 1)]
ver = [["|  "] * w + ['|'] for _ in range(h)] + [[]]
hor = [["+--"] * w + ['+'] for _ in range(h + 1)]
 
def walk(x, y):
vis[y][x] = 1
 
d = [(x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)]
shuffle(d)
for (xx, yy) in d:
if vis[yy][xx]: continue
if xx == x: hor[max(y, yy)][x] = "+  "
if yy == y: ver[y][max(x, xx)] = "   "
walk(xx, yy)
 
walk(randrange(w), randrange(h))
for (a, b) in zip(hor, ver):
print(''.join(a + ['\n'] + b))
 
make_maze()

My dungeon building algorithm is make_map() from http://roguebasin.roguelikedevelopment.org/index.php?title=Complete_Roguelike_Tutorial,_using_python%2Blibtcod,_part_13_code

Code: [Select]

1. Fill map with blocked tiles
2. Select random spot for first room and width and height
3. Carve room
4. Carve another
5. Join the rooms
6. Loop phases 2-5

I would like to be able to do the carving with using

Code: [Select]

            map[x][y].blocked = True
            map[x][y].block_sight = True

and
            map[x][y].blocked = False
            map[x][y].block_sight = False


[pat]

there's a heap of relatively easy different ways to make a maze.

Probably the easiest that comes to mind is to 1) place a random open spot anywhere on the map, 2) loop through a pre-defined number of times looking for a closed spot which borders an open spot, 3) open that closed spot as long as it doesn't have another open spot on a diagonal

That will get you a really tight and windy, and to be honest annoying to navigate, maze with very little effort and the reason you avoid the diagonals is that kinda messes it up but that's a matter of personal taste. You can make the maze take up more of the available space by looping through more times, but there obviously is a point where there's no point going any further because there's no more available spots

You'll have to put in a bit more effort to get it looking better with longer corridors if that's what you're after, but it's not tremendously hard if you just have a go at it and incrementally improve your algorithm with trial and error.

If you want to get a bit more advanced then a cool way to go is to look at cellular automata such as this and adapt that:

[Azathotep]

Found the maze algorithm output at http://rosettacode.org/wiki/Maze_generation:

Code: [Select]

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|        |     |     |                    |     |
+  +  +  +  +  +  +  +  +--+--+--+--+--+  +--+  +
|  |  |     |  |  |     |     |        |        |
+--+  +--+--+  +  +--+--+--+  +  +--+  +--+--+  +
|     |     |  |  |  |        |     |  |        |
+  +--+  +--+  +  +  +  +  +  +--+  +  +  +--+--+
|  |           |  |     |  |     |  |     |     |
+  +--+  +--+--+  +  +--+  +--+--+  +--+--+  +  +
|     |  |        |     |           |        |  |
+--+  +  +  +--+--+--+  +--+--+--+--+--+--+--+  +
|     |  |  |        |        |           |     |
+  +--+--+  +--+--+  +--+--+  +--+  +--+  +  +  +
|        |        |        |        |     |  |  |
+  +--+  +--+--+--+  +  +--+--+--+--+  +--+  +  +
|     |              |                       |  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

The code design is the problem. It's bollocked for anything other than printing "+--+---" to screen. Nearly all the examples on that rosettacode page are anti-reusable. They tightly couple the maze generation to the renderer so that it's a pain in the ass to swap in a new renderer to eg carve without having to touch the generation itself. Kind of defeats the point of having code samples for maze generation if we can't just copy paste them and apply them to something useful. Can't help fix it because I don't know python.

[Quendus]

It's not just the renderer that's incompatible with standard RL maps, it's the format. The sample on rosetta code generates mazes with thin walls between tiles, rather than walls filling tiles.
Rosetta code also has a license incompatible with most other software licenses.

[Krice]

There was some discussion back a while with so called "diggers". It's an entity with location, lifetime and digging direction. You can change parameters but it goes like this:

1. Digger moves to some random direction for selected number of tiles (in a level filled with wall tiles, changing them to floors).
2. It can then turn and/or create a clone of itself
3. The clone turns to another direction and starts to chew its own corridor
4. Digger dies when it reaches dead end

It's really simple and changing how often cloning happens and what is the random variation in turning changes the result in quite interesting ways.

[guest509]

That was here.

http://forums.roguetemple.com/index.php?topic=2830.0

Krice and I did some mock ups. It was a fun drunken walk method of making dungeons. I was able to fiddle with it and get caverns and squarish labrythns depending one how often the digger made a turn.

[Aukustus]

Thanks for your inputs. It does seem that basic maze algorithms are useless. I'll try out those suggestions. Diggers seem quite interesting.

[Quendus]

There's nothing wrong with basic algorithms, just ones that make thin walls. Take a look at the examples at http://www.astrolog.org/labyrnth/algrithm.htm .

[Zireael]

I'm poking around level generation too (the code is in Lua) and I have no idea how to get the closest room for the tunneling function.

[Azathotep]

One way would be each time you dig a room out you tag each floor tile you dig out with the property "room1", the next room you dig out "room2", etc.

Then to find the nearest room to a tile just scan all the tiles on the map and return the nearest one with a room tag. Then if say that tile is tagged room14 you can gather all the other tiles on the map with the same tag. Now you have all the tiles belonging to the closest room. You can use them to find a suitable wall tile facing in the right direction you can use as a new entrance to that room.

[Zireael]

Yeah, I figured that out, but I don't know how to scan all the tiles and return the nearest one (the room tag bit is easy).

[Quendus]

Go in a spiral. Test all the tiles at distance 1 from the start point, then all the tiles at distance 2, etc. Don't test tiles that are outside the map space.

[Beelzebob]

I've been toying with that rogulike in python libtcod tutorial myself. I'm taking python classes on Udacity and Coursera but I admit I still suck. I get as far as adding the controls, and lalt for fullscreen and escape for exit. but then when i run it , it freezes up on me. So I tried just copy paste the code from the tutorial and the same thing happened. I might have a library in the wrong place or something. I know squat about libtcod. Anybody familiar with this issue ? I'm using python 2.7 and notepad++. On a windows XP machine.

[george]

It's hard to tell without seeing your exact code here. Can you make a new bug thread and paste the code in between code tags? Freezing up could mean an infinite loop or something like that run amok.