**Open-source goodness.**

This is a project I took on for two reasons:

- I believe there aren't enough mazes in SL and
- 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**- 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.
- 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. - 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.