Randomly Generated Mazes

ID:169116
 
Jul 27 2005, 8:41 am
This subject is a strange subject in that with all of the randomly-generating maze applications on the hub, none of them seem to do precisely what I'm looking for. So I'm looking for some direction.
First of all, to prevent you from misguiding me towards a dungeon generator... I'm looking for a maze generator that makes traditional mazes. By traditional, I mean doesn't have any rooms, doors, stairs, or any more than 1-tile-wide corridors. Think of the mazes on the back of your cereal. ;P
Hopefully no one will ignore my post and direct me in the way of yet another dungeon generator or a maze generator which is incapable of creating traditional mazes.

Thanks in advance.
Jul 27 2005, 11:53 am
http://developer.byond.com/hub/Jp/MapGenerator

It's by me, of course. No free advertising for anyone else!

If you look at it, it's quite capable of drawing mazes. It only draws one-square wide corridors in various directions. They can intersect, though, and you can get them 'staking up' to get two-square wide corridors, or massing up in one area to get an amorphous blob, but if you have a large map it often comes out fairly well.
Jul 27 2005, 8:10 pm
Here's my source code from my maze game I did awhile back. It's laregly undocumented though.

DeadEnd
{
    var
        turf/loc
        startdist

    New(p_loc, p_startdist)
    {
        loc = p_loc
        startdist = p_startdist
    }
}

Maze
{
    var
        DeadEnds[] = newlist()
        turf/start
        turf/fardeadend
        fardeadendlength = 0
        seed
        twist
        players[] = newlist()
        maxbranch
        maxx
        maxy
        floort
        wallt

    proc
    {
        Generate(floor, wall, z, pmaxx, pmaxy)
        {
            maxx = pmaxx
            maxy = pmaxy
            floort = floor
            wallt = wall
            if(world.maxx < maxx)
                world.maxx = maxx
            if(world.maxy < maxy)
                world.maxy = maxy
            seed = rand(0,65535)
            rand_seed(seed)
            WipeOutLevel(z)
            var/x = rand(2,(maxx-2)/2)*2
            var/y = rand(2,(maxy-2)/2)*2
            maxbranch = rand(3,15)
            twist = rand(0,100)
            MazeRec(x, y, z, 0, 0, NORTH)
            start = locate(x,y,z)

        }

        MazeRec(x,y,z,recdepth, branchdepth, dir)
        {
            var/dirs[] = list(NORTH, SOUTH, EAST, WEST)
            var/i
            var/j
            var/temp
            var/tunnels

            //Remove direction comming from
            switch(dir)
                if(SOUTH)
                    dirs.Cut(1,2)
                if(NORTH)
                    dirs.Cut(2,3)
                if(WEST)
                    dirs.Cut(3,4)
                if(EAST)
                    dirs.Cut(4,5)

            //Shuffle directions
            for(i = 1; i <= 3; i++)
                j = rand(1,3)
                if(j != i)
                    temp = dirs[j]
                    dirs[j] = dirs[i]
                    dirs[i] = temp

            //(100-twist)% chance that we maintain direction
            if(prob(100-twist))
                j = dirs.Find(dir)
                temp = dirs[j]
                dirs[j] = dirs[1]
                dirs[1] = temp

            CarveRoom(x,y,z)

            if(branchdepth <= maxbranch)
                for(j in dirs)
                    var/turf/newturf = GetTwoSteps(locate(x,y,z),j)
                    if(newturf)
                        if(InBounds(newturf, 1, maxx - 1, 1, maxy - 1))
                            if(IsSolid(newturf))
                                Tunnel(x,y,z,j)
                                if(tunnels)
                                    MazeRec(newturf.x, newturf.y, newturf.z, recdepth+1, 0, j)
                                else
                                    MazeRec(newturf.x, newturf.y, newturf.z, recdepth+1, branchdepth+1, j)
                                tunnels++

            if(!tunnels)
                DeadEnds += new /DeadEnd(locate(x,y,z),recdepth)
                if(recdepth > fardeadendlength)
                    fardeadend = locate(x,y,z)
                    fardeadendlength = recdepth

            return 1

        }

        IsSolid(loc)
        {
            return (istype(loc, wallt))
        }

        CarveRoom(x,y,z)
        {
            new floort(locate(x,y,z))
        }

        Tunnel(x,y,z,dir)
        {
            var/turf/T = get_step(locate(x,y,z),dir)
            new floort(locate(T.x,T.y,T.z))

        }
        
        InBounds(turf/T, minx, maxx, miny, maxy)
        {
            if(T.x > minx && T.x <= maxx && T.y > miny && T.y <= maxy)
                return 1
            return 0
        }
        GetTwoSteps(loc, dir)
        {
            loc = get_step(loc,dir)
            if(loc)
                loc = get_step(loc,dir)
            return loc
        }
    
        WipeOutLevel(z)
        {
            var/i
            var/j
            for(i = 1; i <= world.maxx; i++)
                for(j = 1; j <= world.maxy; j++)
                    new wallt(locate(i,j,z))
        }
    }
}


Just create a maze datum, set up maxbranch and twist if you want, then call Generate. maxbranch sets the limit for how far each branch from the main path can go. If you set it low you'll end up with a lot of branches that quickly lead to a dead end. Set it high and you can have really long paths that end up no where. Twist is the probability after each tile that the current branch will change direciton. If you set it low you'll get long straight pathways and if you set it to 100 it'll change direction whenever possible. The parameters for Generate are pretty straight forward, floor is the type path of the turf used for floors and wall is the type path for the wall turf, z is the z level where the maze gets generated, and the other two parameters are for the size. Once created the start variable holds the "starting" turf for the maze and the fardeadend variable holds the turf which is the deadend of the maze furthest from the start so it makes an effective end point. DeadEnds is a list of DeadEnd datums containing the turfs which are the dead ends of the maze along with how far they are from the start(not direct distance but the number of moves it takes to move there) so this list holds a good list of places to drops stuff like treasures since obviously they need to be at a dead end rather than any old corridor :P.

And I think that is it.