Thread: Adventures in labyrinth generation.

FWIW, I thought this was simply genius.

#
# Unicursal: One way to create a random unicursal Maze is to take a perfect Maze, seal off the exit so there's only the one entrance, then add walls bisecting each passage. This will turn each dead end into a U-turn passageway, and there will be a unicursal passage starting and ending at the original Maze's beginning, that will follow the same path as someone wall following the original Maze. The new unicursal Maze will have twice the dimensions of the original perfect Maze it was based on. Small tricks may be done to have the start and end not always be next to each other: When creating the perfect Maze, never add segments attached to the right or bottom walls, so the resulting Maze will have an easy solution that follows that wall. Have the entrance at the upper right, and after bisecting to create the unicursal routing, remove the right and bottom wall. This will result in a unicursal Maze that starts at the upper right and ends at the lower left.

Image: http://www.astrolog.org/labyrnth/maze/unicursl.gif
Webpage: http://www.astrolog.org/labyrnth/algrithm.htm

But now I see that you've already seen that page.
http://www.gamedev.net/community/for...page=1�
[edit=2] Weird, that link was either copied or transmitted incorrectly. Here it is again.
http://www.gamedev.net/community/for...page=1� [/edit]
[edit=3] Urf, it happened again! I guess it's the sequence <ampersand><hash> in the link that makes vBulletin mess up.
Just go here and scroll down. http://www.gamedev.net/community/for...opic_id=501637 [/edit]

[edit] Anyway, here's my very ugly half-hour-to-code C++ labyrinth generator that gives you all of the possible labyrinths for a given size.

Yes, it takes forever to execute. And yes, I know positions are reversed. No, I can't be bothered to fix it.

Code:

#include <iostream>
#include <cstdlib>
#include <ctime>

class Position {
private:
    int xp, yp;
public:
    Position(int xp, int yp) : xp(xp), yp(yp) {}
    
    void add_xp(int add) { xp += add; }
    void add_yp(int add) { yp += add; }
    
    int add_direction(int add, int dir);
    int get_dirs() { return 4; }
    
    void set_xp(int xp) { this->xp = xp; }
    void set_yp(int yp) { this->yp = yp; }
    
    int get_xp() { return xp; }
    int get_yp() { return yp; }
};

int Position::add_direction(int add, int dir) {
    switch(dir) {
    case 0:
        xp += add;
        break;
    case 1:
        xp -= add;
        break;
    case 2:
        yp += add;
        break;
    case 3:
        yp -= add;
        break;
    }
}

class Map {
private:
    static const int WIDTH = 6, HEIGHT = 6;
    char cell[WIDTH][HEIGHT];
public:
    Map() { clear(); }
    
    void set_cell(int x, int y, char c) { cell[x][y] = c; }
    char get_cell(int x, int y);
    
    bool is_empty(int x, int y) { return get_cell(x, y) == get_empty_char(); }
    
    char get_empty_char() { return '-'; }
    int get_width() { return WIDTH; }
    int get_height() { return HEIGHT; }
    
    void clear();
    void display();
    bool map_is_full();
};

char Map::get_cell(int x, int y) {
    if(x < 0 || y < 0 || x >= get_width() || y >= get_height()) {
        return -1;
    }
    
    return cell[x][y];
}

void Map::clear() {
    for(int x = 0; x < get_width(); x ++) {
        for(int y = 0; y < get_height(); y ++) {
            set_cell(x, y, get_empty_char());
        }
    }
}

void Map::display() {
    for(int x = 0; x < get_width(); x ++) {
        for(int y = 0; y < get_height(); y ++) {
            std::cout << get_cell(x, y);
        }
        
        std::cout << '\n';
    }
}

bool Map::map_is_full() {
    for(int x = 0; x < get_width(); x ++) {
        for(int y = 0; y < get_height(); y ++) {
            if(get_cell(x, y) == get_empty_char()) return false;
        }
    }
    
    return true;
}

void trace_labyrinth(Map &map, Position &pos);

int main() {
    std::srand((unsigned)std::time(0));
    
    Map map;
    Position start(
        std::rand() &#37; map.get_width(),
        std::rand() % map.get_height());
    
    map.set_cell(start.get_xp(), start.get_yp(), '@');
    
    trace_labyrinth(map, start);
    
    return 0;
}

void trace_labyrinth(Map &map, Position &pos) {
    Position next = pos;
    
    int startdir = rand() % next.get_dirs();
    int dir = startdir;
    bool found_move = false;
    do {
        next = pos;
        next.add_direction(1, dir);
        
        if(map.is_empty(next.get_xp(), next.get_yp())) {
            map.set_cell(next.get_xp(), next.get_yp(), "v^><"[dir]);
            
            trace_labyrinth(map, next);
            found_move = true;
        }
        
        dir ++;
        dir %= next.get_dirs();
    } while(dir != startdir);
    
    if(!found_move) {
        map.set_cell(pos.get_xp(), pos.get_yp(), '$');
        
        if(map.map_is_full()) {
            map.display();
            std::cout << std::endl;
        }
    }
    
    map.set_cell(pos.get_xp(), pos.get_yp(), map.get_empty_char());
}

[/edit]