Welcome to the Second Life Forums Archive

These forums are CLOSED. Please visit the new forums HERE

Maze Generator

Apotheus Silverman
I write code.
Join date: 17 Nov 2003
Posts: 416
08-10-2004 07:34
Open-source goodness.

This is a project I took on for two reasons:
  1. I believe there aren't enough mazes in SL and
  2. LSL is especially ill-suited for certain algorithms (such as this one) and I wanted to see just a) how much obfuscation is required for a project like this and b) how much it could subsequently be optimized.
    [/list=1]


    Overview
    The scripts presented below are the final result of a few weeks' worth of taking a maze generation algorithm I first encountered back in 1986 (yes, I've been coding that long) and smashing it into LSL with as much finesse as I could muster. This algorithm builds a 2-dimensional maze guaranteed to have only one solution and no open loops. It does this by using a "depth-first" pathing algorithm... that is, it starts with (picture this in memory...) nothing but "rooms" with four walls and walks a random path while "breaking down" walls until it gets trapped, at which point it chooses another room at random and starts again until the entire maze is filled. There are some more subtle details to create the final product, but that is the basic operation of the generation algorithm.


    The Process
    Step 1) Translate the original algorithm directly from BASIC into LSL and make the necessary modifications/additions just to get a working model. Used ListReplaceList() from the LSL Wiki to simulate arrays, which this algorithm is incredibly heavily dependent on. Outcome: successful, but horribly slow and the largest maze that could be built was 10x10 units (20m x 20m). Generation of this size maze took around 10 minutes. Also the wall segments furthest from the center did not move into position properly because of the 10m limit of llRezObject().

    Step 2) Work all bugs out of the existing scripts. Used Christopher Omega's SetPos() function in conjunction with a vector-packing algorithm I came up with. The wall segments are now "told" where to go without requiring communication elements. Outcome: Perfect. Couldn't be happier. It also looks neat to see the pieces move into place instead of simply appear where they belong.

    Step 3) Kill two birds with one stone -- dramatically decrease memory usage while dramatically increasing generation speed. I already had access to a bit-packed version of this algorithm, but it was put together so badly that I ended up scrapping it and using Huns Valen's bitwise functions along with my own routines. Outcome: Astounding success! Maze size can theoretically scale to ~(320x320) units. That is 640m x 640m! Speed increased roughly 500% over steps 1 and 2. Despite the speed increase, maze generation is still slow in my opinion.

    Step 4) Make the generator slightly user-friendly. Added voice-activated generation. Usage: maze build [XxY]


    Outstanding Issues
    1. Currently the BuildMaze() routine is sim-specific. That is, a maze cannot cross sim boundaries. I will leave that exercise up to someone else, because I have done what I set out to accomplish.
    2. Also, mazes are rather prim-heavy. I will leave this optimization up to someone else as well.




    Script 1, the wall segment script
    Create a box that is 1x1xsomething. I have found 1x1x3 to work well. Put the following script inside.
    CODE

    // Maze Wall
    // by Apotheus Silverman
    //
    // SetPos() by Christopher Omega


    // Unpacks a vector which was previously packed into an integer with a precision of one meter
    vector UnpackVector(integer vectorInt) {
    integer x = vectorInt / 1000000;
    integer y = (vectorInt - (x * 1000000)) / 1000;
    integer z = vectorInt - (x * 1000000) - (y * 1000);
    return(<x,y,z>);
    }

    // SetPos() by Christopher Omega
    // /15/a4/9900/1.html
    SetPos(vector dest) {
    float dist = llVecDist(dest,llGetPos());
    vector prevPos;
    while(dist > 0) {
    prevPos = llGetPos();
    llSetPos(dest);
    if(llGetPos() == prevPos) {
    // Yipes! The object didnt move! Occurs with float error.
    //llSay(0,"Float error detected and recovered from.");
    return; // return from this function immediately.
    }
    dist = llVecDist(dest,llGetPos());
    }
    }


    default {
    state_entry() {
    }

    on_rez(integer startParam) {
    if (startParam == 0) {
    llDie();
    } else {
    vector myPos = UnpackVector(startParam);
    //llSay(0, "Moving to " + (string)myPos);
    SetPos(myPos);
    }
    }
    }




    Script 2, the generation script
    Create the object you wish to use as the maze generator (I just use a default box), put the Wall Segment into its contents, and add this script:
    CODE

    // Maze Generator
    // by Apotheus Silverman
    //
    // Adapted from txtmazea.bas and txtmazec.bas by Jonathan Dale Kirwan
    // http://users.easystreet.com/jkirwan/new/zips+src/txtmazea.bas
    // http://users.easystreet.com/jkirwan/TXTMAZEC.BAS
    //
    // ListReplaceList() from LSL Wiki
    //
    // SetBit(), ClearBit(), GetBit() by Huns Valen
    //

    integer mazeWidth = 6;
    integer mazeHeight = 6;
    float relativeZ = 0.0;
    integer packBits = 32;
    list westWalls;
    list southWalls;


    // Packs a vector into an integer with a precision of one meter
    integer PackVector(vector vec) {
    return((integer)vec.x * 1000000 + (integer)vec.y * 1000 + (integer)vec.z);
    }

    // Rezzes a wall segment and sends it to the appropriate location
    RezWall(integer mazeWidth, integer mazeHeight, integer x, integer y) {
    vector rezPos = <-mazeWidth + x - 2, -mazeHeight + y - 2, relativeZ> + llGetPos();
    integer packedRezPos = PackVector(rezPos);
    llRezObject("Wall", llGetPos() + <0,0,1>, ZERO_VECTOR, ZERO_ROTATION, packedRezPos);
    }

    // ListReplaceList() from LSL Wiki
    // replaces item number _pos_ in list _dest_ with list _src_
    // negative values for _pos_ means count from the end of
    // the list instead, so a _pos_ of -1 means replace the last item in the list
    list ListReplaceList(list dest, list src, integer pos) {
    if (pos > llGetListLength(dest)) {
    llSay(0, "Error: Index " + (string)pos + " is greater than list length " + (string)llGetListLength(dest));
    return(dest);
    }
    if (pos < 0) {
    pos = llGetListLength(dest) + pos;
    }
    return llListInsertList(llDeleteSubList(dest, pos, pos), src, pos);
    }

    // Sets a bit in an integer bitfield and returns the bitfield
    integer SetBit(integer x, integer bit) {
    return(x | ((integer)llPow(2, (float)bit)));
    }

    // Clears a bit in an integer bitfield and returns the bitfield
    integer ClearBit(integer x, integer bit) {
    return(x & (~(integer)llPow(2, (float)bit)));
    }

    // Reads a bit in an integer bitfield and returns the bit
    integer GetBit(integer x, integer bit) {
    if(x & (integer)llPow(2, bit))
    return(TRUE);
    else
    return(FALSE);
    }


    // Spit out the "maze build" command usage.
    Usage() {
    llSay(0, "Usage: maze build [XxY]");
    llSay(0, "maze build by itself will build a maze with the default size of " + (string)(mazeWidth * 2) + "x" + (string)(mazeHeight * 2) + ".");
    llSay(0, "maze build 10x10 will build a maze that is 10 meters on each side.");
    }







    // This routine accepts a width and height for a maze and calculates a
    // random maze into two arrays designed to hold the west and south walls
    // of each room or cell in the maze grid. These can then be used to print
    // or use the maze, as desired (such as a random labyrinth for a game.)
    GenerateMaze (integer mazeWidth, integer mazeHeight) {
    integer i;
    integer j;
    integer k;
    integer exitCount;
    integer selection;
    integer unvisitedRoomCount;
    integer currentRoom;
    integer count;
    integer element;
    list visited;
    list exits;
    list paths;

    for (i = 0; i < 4; i++) {
    exits += 0;
    }

    // This code redimensions the west and south wall arrays, as needed.
    // These arrays must be redimensionable, or an error will result.
    // As an important side effect I'm depending on, redimensioning
    // these arrays causes their element values to be initialized to 0.
    for (i = 0; i < (integer)((((mazeWidth + 2) * (mazeHeight + 2)) + 15) / packBits); i++) {
    westWalls += [0];
    southWalls += [0];
    visited += [0];
    paths += [0];
    }

    // Set up our local copy of the visitation status array. Since the
    // grid uses a perimeter around the maze itself, we need to mark the
    // rooms in the perimeter as having been used, so that the intervening
    // walls are not removed (since those walls are the maze's boundary.)
    j = (mazeWidth + 2) * (mazeHeight + 1) - 1;
    for (i = 0; i <= mazeWidth + 2; i++) {
    element = i / packBits;
    visited = ListReplaceList(visited, [SetBit(llList2Integer(visited, element), i % packBits)], element);
    element = (i + j) / packBits;
    visited = ListReplaceList(visited, [SetBit(llList2Integer(visited, element), (i + j) % packBits)], element);
    }
    j = mazeWidth + mazeWidth + 3;
    for (i = 1; i <= mazeHeight; i++) {
    element = j / packBits;
    visited = ListReplaceList(visited, [SetBit(llList2Integer(visited, element), j % packBits)], element);
    element = (j + 1) / packBits;
    visited = ListReplaceList(visited, [SetBit(llList2Integer(visited, element), (j + 1) % packBits)], element);
    j += mazeWidth + 2;
    }

    // Arrays are set up, the perimeter is initialized, we're ready to go.
    // Compute the maze! (See the discussion on the web site for details.)
    unvisitedRoomCount = mazeWidth * mazeHeight;
    j = (integer)llFrand(unvisitedRoomCount);
    currentRoom = (1 + i / mazeWidth) * (mazeWidth + 2) + (i % mazeWidth) + 1;


    while (unvisitedRoomCount > 1) {
    unvisitedRoomCount -= 1;
    element = currentRoom / packBits;
    visited = ListReplaceList(visited, [SetBit(llList2Integer(visited, element), currentRoom % packBits)], element);

    while (TRUE) {
    exitCount = 0;
    element = (currentRoom - mazeWidth - 2) / packBits;
    if (!GetBit(llList2Integer(visited, element), (currentRoom - mazeWidth - 2) % packBits)) {
    exits = ListReplaceList(exits, [1], exitCount);
    exitCount += 1;
    }
    element = (currentRoom + mazeWidth + 2) / packBits;
    if (!GetBit(llList2Integer(visited, element), (currentRoom + mazeWidth + 2) % packBits)) {
    exits = ListReplaceList(exits, [2], exitCount);
    exitCount += 1;
    }
    element = (currentRoom - 1) / packBits;
    if (!GetBit(llList2Integer(visited, element), (currentRoom - 1) % packBits)) {
    exits = ListReplaceList(exits, [3], exitCount);
    exitCount += 1;
    }
    element = (currentRoom + 1) / packBits;
    if (!GetBit(llList2Integer(visited, element), (currentRoom + 1) % packBits)) {
    exits = ListReplaceList(exits, [4], exitCount);
    exitCount += 1;
    }
    if (exitCount >= 1) {
    jump endLoop;
    }
    j = (integer)llFrand(mazeWidth * mazeHeight);
    k = ((1 + j / mazeWidth) * (mazeWidth + 2) + (j % mazeWidth) + 1) / packBits;
    while (!llList2Integer(paths, k)) {
    k -= 1;
    if (k < 0) {
    k = ((mazeWidth + 2) * (mazeHeight + 2) - 1) / packBits;
    }
    }
    for (i = 0; i < packBits; i++) {
    if (GetBit(llList2Integer(paths, k), i)) {
    jump endFor;
    }
    }
    @endFor;
    paths = ListReplaceList(paths, [ClearBit(llList2Integer(paths, k), i)], k);
    currentRoom = k * packBits + i;
    }
    @endLoop;

    if (exitCount > 1) {
    element = currentRoom / packBits;
    paths = ListReplaceList(paths, [SetBit(llList2Integer(paths, element), currentRoom % packBits)], element);
    }
    selection = (integer)llFrand(exitCount);
    if (llList2Integer(exits, selection) == 1) {
    currentRoom -= mazeWidth + 2;
    element = currentRoom / packBits;
    southWalls = ListReplaceList(southWalls, [SetBit(llList2Integer(southWalls, element), currentRoom % packBits)], element);
    } else if (llList2Integer(exits, selection) == 2) {
    element = currentRoom / packBits;
    southWalls = ListReplaceList(southWalls, [SetBit(llList2Integer(southWalls, element), currentRoom % packBits)], element);
    currentRoom += mazeWidth + 2;
    } else if (llList2Integer(exits, selection) == 3) {
    element = currentRoom / packBits;
    westWalls = ListReplaceList(westWalls, [SetBit(llList2Integer(westWalls, element), currentRoom % packBits)], element);
    currentRoom -= 1;
    } else if (llList2Integer(exits, selection) == 4) {
    currentRoom += 1;
    element = currentRoom / packBits;
    westWalls = ListReplaceList(westWalls, [SetBit(llList2Integer(westWalls, element), currentRoom % packBits)], element);
    }
    }

    // Add an entrance and exit to the maze. These could be placed
    // anywhere around the perimeter, if we wanted to. For now, it's
    // hard-coded at the upper-left corner and the lower-right corner.
    southWalls = ListReplaceList(southWalls, [SetBit(llList2Integer(southWalls, 0), 1)], 0);
    j = (mazeHeight + 1) * (mazeWidth + 2) - 2;
    element = j / packBits;
    southWalls = ListReplaceList(southWalls, [SetBit(llList2Integer(southWalls, element), j % packBits)], element);
    }


    // This routine accepts a width and height and rezzes the wall segments
    // appropriately to create the maze.
    BuildMaze(integer mazeWidth, integer mazeHeight) {
    integer i;
    integer j;
    integer p;
    integer element;

    for (i = 1; i <= mazeWidth; i++) {
    RezWall(mazeWidth, mazeHeight, i * 2, 1);
    element = i / packBits;
    if (!GetBit(llList2Integer(southWalls, element), i % packBits)) {
    RezWall(mazeWidth, mazeHeight, (i * 2) + 1, 1);
    }
    }
    RezWall(mazeWidth, mazeHeight, (mazeWidth * 2) + 2, 1);

    p = 0;
    for (i = 1; i <= mazeHeight; i++) {
    p += mazeWidth + 2;
    for (j = 1; j <= mazeWidth; j++) {
    element = (p + j) / packBits;
    if (!GetBit(llList2Integer(westWalls, element), (p + j) % packBits)) {
    RezWall(mazeWidth, mazeHeight, j * 2, i * 2);
    }
    }
    element = (p + mazeWidth + 1) / packBits;
    if (!GetBit(llList2Integer(westWalls, element), (p + mazeWidth + 1) % packBits)) {
    RezWall(mazeWidth, mazeHeight, (mazeWidth * 2) + 2, i * 2);
    }
    for (j = 1; j <= mazeWidth; j++) {
    RezWall(mazeWidth, mazeHeight, j * 2, (i * 2) + 1);
    element = (p + j) / packBits;
    if (!GetBit(llList2Integer(southWalls, element), (p + j) % packBits)) {
    RezWall(mazeWidth, mazeHeight, (j * 2) + 1, (i * 2) + 1);
    }
    }
    RezWall(mazeWidth, mazeHeight, (mazeWidth * 2) + 2, (i * 2) + 1);
    }
    }


    default {
    state_entry() {
    llSetText("", <1,1,1>, 1.0);
    llListen(0, "", llGetOwner(), "");
    }

    on_rez(integer start_param) {
    llResetScript();
    }

    listen(integer channel, string name, key id, string message) {
    string myMessage = llToLower(message);
    if (myMessage == "maze reset") {
    llResetScript();
    } else if (llGetSubString(myMessage, 0, 9) == "maze build") {
    integer myMazeWidth = mazeWidth * 2;
    integer myMazeHeight = mazeHeight * 2;
    // This entire validation block could be handled with a single regexp test.
    if (llStringLength(myMessage) > 13) {
    if (llGetSubString(myMessage, 10, 10) == " " && llSubStringIndex(myMessage, "x") > -1) {
    list dimensions = llParseString2List(llGetSubString(myMessage, 11, -1), ["x"], []);
    if (llGetListLength(dimensions) == 2) {
    myMazeWidth = llList2Integer(dimensions, 0);
    myMazeHeight = llList2Integer(dimensions, 1);
    } else {
    myMazeWidth = 0;
    }
    } else {
    myMazeWidth = 0;
    }
    }

    if (myMazeWidth == 0 || myMazeHeight == 0) {
    llSay(0, "Invalid parameter " + llGetSubString(myMessage, 11, -1));
    Usage();
    } else {
    llSay(0, "Generating " + (string)myMazeWidth + " x " + (string)myMazeHeight + " maze. Please wait...");
    GenerateMaze(myMazeWidth / 2, myMazeHeight / 2);
    //llSay(0, "Maze generated. Building...");
    //llSay(0, llDumpList2String(southWalls, ""));
    //llSay(0, llDumpList2String(westWalls, ""));
    BuildMaze(myMazeWidth / 2, myMazeHeight / 2);

    llResetScript();
    }
    }
    }

    on_rez(integer start_param) {
    Usage();
    llResetScript();
    }
    }






    I highly suggest you do not attempt to build a maze larger than 80m x 80m unless you know exactly what you're doing.
_____________________
Apotheus Silverman
Shop SL on the web - SLExchange.com

Visit Abbotts Aerodrome for gobs of flying fun.
Surreal Farber
Cat Herder
Join date: 5 Feb 2004
Posts: 2,059
03-08-2005 02:17
Origianl Thread
/15/51/19730/1.html



I had a lot of fun playing with this. Thanks for putting it up.
_____________________
Surreal

Phobos 3d Design - putting the hot in psychotic since 2004

Come see our whole line of clothing, animations and accessories in Chaos (37, 198, 43)
Cartman Ludd
I'm with stupid ---->
Join date: 25 Mar 2005
Posts: 11
03-31-2005 00:35
Ohhhhh, I might try this, it looks cool.
_____________________
Siggy's are stupid. 'Hey, look! Its that really random signature that I have had to read for the last 6 weeks, because that darn person is to defective to change it!' If this is you, I think we should get our freakin' panzerfrausts and blow every signature on this forum to kingdom come. Thank you for ignoring my signature, and if you went through painstaking process of reading it, then either you have to much time on your hands, or you have the I.Q of the slug.
Mendoza Catron
Registered User
Join date: 22 Jul 2006
Posts: 17
09-23-2006 11:00
I keep getting a message saying "Couldn't find object Wall". Any ideas why this may be happening?

Thanks,
Mendoza
Moose Pegler
Registered User
Join date: 22 Apr 2006
Posts: 33
Thanks!
11-04-2006 07:56
Great stuff, Apotheus. Thanks much for doing the work and for posting it.

For those into mazes, there's a generator with source code for all sorts of mazes (including 3D mazes) at:

http://www.astrolog.org/labyrnth/daedalus.htm

Enjoy.

Cheers, Moose
rubiq Campbell
Registered User
Join date: 4 Apr 2006
Posts: 22
How does it work again?
03-26-2007 12:43
I created the first wall object and dump the first script and then created another object and uploaded the second script. It didn't work for me. Can you please enlighten me again to play with it too.
Nada Epoch
The Librarian
Join date: 4 Nov 2002
Posts: 1,423
Discussion Thread
04-09-2007 05:12
/54/0a/176345/1.html
_____________________
i've got nothing. ;)
Katryna Jie
Registered User
Join date: 24 Jun 2007
Posts: 187
11-07-2007 16:26
Is it possible to limit the number of prims used to build? For the moment, I need to keep my prim count for the maze at 100-150~ including floors and roof