Table of Contents

Shortnote

This script was tested and works on OpenSim version 0.7.4!

"Punch Path" is an example of a depth-first algorithm solver that follows a defined path specified in a notecard. Several applications can be forked from the labyrinth solver. Here are a few examples:

Video

Algorithm

Suppose that we wanted to draw the letter T. A possible ASCII representation of the the letter T could be: 

######
  #
  #
  #

The above letter can be converted to a matrix of 6 columns by 4 rows where we substitute each hash (#) with a 1 and each space with a 0:

$$ \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1\\ 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0\\ \end{pmatrix} $$

We do this because we want to represent each hash sign as a possible destination. In other words, you can imagine that the number 0 represents walls or nodes that cannot be visited whereas the number 1 represents a tile or node that can be visited.

One way to traverse the connected nodes in the graph would be to scan each line of the matrix in order to determine the next destination. However, the algorithm asserts that walls cannot be crossed and that the movement from one tile to the other must be made by visiting a valid node.

For example, for three tiles, the following path is valid: 

  +------+------+
  |      |      |
  | *--------*  |
  |      |   |  |
  +------+---|--+
         |   |  |
         |   |  |
         |   *  |
         +------+

However, the following path is not valid: 

   +------+------+
   |  *   |      |
   |   \  |      |
   |    \ |      |
   +-----\+------+
          \      |
          |\     |
          | *    |
          +------+

because it crosses the bottom left tile which is not a valid node.

Coming back to the matrix, we pad the matrix with a zero-column:

$$ \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & | 0\\ 0 & 0 & 1 & 0 & 0 & 0 & | 0\\ 0 & 0 & 1 & 0 & 0 & 0 & | 0\\ 0 & 0 & 1 & 0 & 0 & 0 & | 0\\ \end{pmatrix} $$

and then fold the lines and the columns into a list of zeroes and ones: 

1111110001000000100000010000

Since we know that the matrix now has 7 columns, we can determine the directions up, down, left and right by performing arithmetic from a point of reference. For example, taking the list of elements above, suppose that we find ourselves on the tile represented by the before last 1: 

              up     down
              -7      +7
            *------*------*
            |      |      |
   1111110001000000100000010000
             left *** right
              -1   ^  +1
                   |
                we are here

In order, from our point of reference:

In order to determine the next node to visit: for all directions, check if the tile is a valid tile (greater than 1) or if it is an invalid tile (represented by 0). Then, increment the current value on the current tile and move in that direction. By incrementing the value, we reduce memorize that we have already visited the current tile.

Additionally, since we increment each tile, we decrease the overall probability whenever all the tiles have a value larger than 1. This is to make sure that we do not overstep the integer bounds.

Code

punch_path.lsl
///////////////////////////////////////////////////////////////////////////
//  Copyright (C) Wizardry and Steamworks 2011 - License: GNU GPLv3      //
//  Please see: http://www.gnu.org/licenses/gpl.html for legal details,  //
//  rights of fair usage, the disclaimer and warranty conditions.        //
///////////////////////////////////////////////////////////////////////////
 
list wasListSubtract(list input, integer value) {
    integer v = llList2Integer(input, 0);
    input = llDeleteSubList(input, 0, 0);
    if(input == []) return [v-value] + input;
    return [v-value] + wasListSubtract(input, value);
}
 
list dualQuicksort(list a, list b) {
 
    if(llGetListLength(a) <= 1) return a+b;
 
    integer pivot_a = llList2Integer(a, llGetListLength(a)/2);
    string pivot_b = llList2String(b, llGetListLength(b)/2);
 
    a = llDeleteSubList(a, llGetListLength(a)/2, llGetListLength(a)/2);
    b = llDeleteSubList(b, llGetListLength(b)/2, llGetListLength(b)/2);
 
    list less = [];
    list less_b = [];
    list more = [];
    list more_b = [];
 
    integer i = 0;
    do {
        if(llList2Integer(a, i) > pivot_a) 
        {
            less += llList2List(a, i, i);
            less_b += llList2List(b, i, i);
        }
        else
        {
            more += llList2List(a, i, i);
            more_b += llList2List(b, i, i);
        }
    } while(++i<llGetListLength(a)*2);
 
    return dualQuicksort(less, less_b) + [ pivot_a ] + [ pivot_b ] + dualQuicksort(more, more_b);
}
 
list program = [];
integer cursor = 0;
integer PUNCH_COLUMNS = 0;
 
key nQuery = NULL_KEY;
integer nLine = 0;
string nName = "Punch Path";
 
default {
    touch_start(integer num) {
        PUNCH_COLUMNS = 0;
        state data;
    }
}
 
state data
{
    state_entry() {
        integer itra = llGetInventoryNumber(INVENTORY_NOTECARD)-1;
        do {
            if(llGetInventoryName(INVENTORY_NOTECARD, itra) == nName)
            jump found_notecard;
        } while(--itra>0);
        llOwnerSay("ERROR: Failed to find notecard.");
        return;
@found_notecard;
        nQuery = llGetNotecardLine(nName, nLine);
    }
 
    dataserver(key id, string data) {
        if(id != nQuery) return;
        if(data == EOF) {
            state compute;
        }
        if(data == "") jump next_line;
        if(PUNCH_COLUMNS == 0)
            PUNCH_COLUMNS = llStringLength(data)+1;
        if(PUNCH_COLUMNS != llStringLength(data)+1) {
            llOwnerSay("ERROR: Differing number of columns. Please check the notecard.");
            state default;
        }
        integer itra=0;
        do {
            program += (integer)llGetSubString(data, itra, itra);
        } while(++itra<llStringLength(data));
        program += 0;
@next_line;
        nQuery = llGetNotecardLine(nName, ++nLine);
    }
 
}
 
state compute {
    state_entry() {
        // Decrease overall probability of paths.
        // This is to prevent going out of bounds
        // with integer values.
        if(llListStatistics(LIST_STAT_MIN, program) > 1)
            wasListSubtract(program, 1);
 
        // Decrease probability.
        integer current_tile=llList2Integer(program, cursor)+1;
        program=llListReplaceList(program, (list)current_tile, cursor, cursor);  
 
        // Determine next direction. 
        // up, down, left, right
        list directions = [ 0, 0, 0, 0 ];
 
        // up, current position - number of columns
        if(cursor-PUNCH_COLUMNS >= 0)
            directions=llListReplaceList(directions, (list)llList2Integer(program, cursor-PUNCH_COLUMNS), 0, 0);
        // down, current position + number of columns
        if(cursor+PUNCH_COLUMNS < llGetListLength(program))
            directions=llListReplaceList(directions, (list)llList2Integer(program, cursor+PUNCH_COLUMNS), 1, 1);
        // left, current position - 1
        if(cursor-1 >= 0)
            directions=llListReplaceList(directions, (list)llList2Integer(program, cursor-1), 2, 2);
        // right, current position + 1
        if(cursor+1 < llGetListLength(program));
            directions=llListReplaceList(directions, (list)llList2Integer(program, cursor+1), 3, 3);
 
 
        directions = dualQuicksort(directions, [ "up", "down", "left", "right" ]);
        integer itra=llGetListLength(directions)-1;
        do {
            if(llList2Integer(directions, itra-1) == 0) jump next;
            string d = llList2String(directions, itra);
            if(d == "up") {
                cursor -= PUNCH_COLUMNS;
                state up;
            }
            if(d == "down") {
                cursor += PUNCH_COLUMNS;
                state down;
            }
            if(d == "left") {
                cursor -= 1;
                state left;
            }
            if(d == "right") {
                cursor += 1;
                state right;
            }
@next;
        } while (~(itra-=2));
    }
}
 
state up {
    state_entry() {
        vector cPos = llGetPos();
        llSetPos(<cPos.x, cPos.y, cPos.z+.5>);
        state compute;
    }
}
 
state down {
    state_entry() {
        vector cPos = llGetPos();
        llSetPos(<cPos.x, cPos.y, cPos.z-.5>);
        state compute;
    }
}
 
state left {
    state_entry() {
        vector cPos = llGetPos();
        llSetPos(<cPos.x-.5, cPos.y, cPos.z>);
        state compute;
    }
}
 
state right {
    state_entry() {
        vector cPos = llGetPos();
        llSetPos(<cPos.x+.5, cPos.y, cPos.z>);
        state compute;
    }
}