Welcome to the Second Life Forums Archive

These forums are CLOSED. Please visit the new forums HERE

Discussion: 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.
Chrysala Desideri
Scarlet Scriptrix
Join date: 4 Mar 2007
Posts: 65
Simple and sweet
04-25-2007 11:00
Big thanks Apotheus for this script!

To the guy who it didn't work for: the scripted wall segment goes in the rezzer prim along with the rez script.

prim heavy for sure... is there any way to have it stretch prims once it's defined the walls, then kill all the extra prims? i did this by hand once i rezzed my maze (visit the work in progress in Turmus - which is a mature area)

or: could it be made with a 5x5x0.5 wall segment that gets rotated into position instead of all tight prims aligned to same rotation? that would make it resizable once rezzed...

I know zip about scripting, i'm scouring these forums and the wiki to try and learn, and i'm sorry if i just asked two retarded questions. i do not know what all is possible or not possible yet.

anyway thanks again for the open source goodness!! sweet!

93/93,
Chryssy

Edit: also, where do i stick an llRemoveInventory call so the maze walls get rid of the script once in place? in the wall script or rezzer, and in which state? probably another dumb nu-b question, but that's what i am ;-)
Winter Ventura
Eclectic Randomness
Join date: 18 Jul 2006
Posts: 2,579
04-25-2007 11:34
From: Chrysala Desideri

Edit: also, where do i stick an llRemoveInventory call so the maze walls get rid of the script once in place? in the wall script or rezzer, and in which state? probably another dumb nu-b question, but that's what i am ;-)


In the Wall Segment script. in the lower part:
P.S. There's only one state in this script... and it's "default"

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);
llRemoveInventory(llGetScriptName()); // delete this script
}

}
}
_____________________

● Inworld Store: http://slurl.eclectic-randomness.com
● Website: http://www.eclectic-randomness.com
● Twitter: @WinterVentura
Finkel Flossberg
Registered User
Join date: 25 Nov 2006
Posts: 23
12-30-2007 12:42
This is a truly great script. Thank you very much for sharing.

I would like to enhance it with two features:

1. Make the paths inside the maze wider. 1 m. seems to be a little too narrow.
So knowing where to alter the rez position to accomodate for larger wall segments
would be nice.

2. Remove the outer walls to replace them with a fixed wall.
To save prims....It will dramatically change the prim usage even for small size mazes.


Any pointers are very much apreciated. Thank you!
Damen Hax
Explorer
Join date: 7 Aug 2007
Posts: 5
Error
03-31-2009 01:45
The Wall script should only have one on_rez event.
_____________________
~A Watched Clock Never Boils~
Void Singer
Int vSelf = Sing(void);
Join date: 24 Sep 2005
Posts: 6,973
03-31-2009 14:47
true, but it was valid at the time of creation (over 4 years ago). I'm sure it could be built more efficiently now.
_____________________
|
| . "Cat-Like Typing Detected"
| . This post may contain errors in logic, spelling, and
| . grammar known to the SL populace to cause confusion
|
| - Please Use PHP tags when posting scripts/code, Thanks.
| - Can't See PHP or URL Tags Correctly? Check Out This Link...
| -