Pathfinder
Revision as of 04:17, 8 December 2007 by Babbage Linden (talk | contribs) (New page: <pre> // Pathfinder PotentialField by Babbage Linden // // Part of the Pathfinder Open Source Pathfinding Demo // // The potential field maintains a representation of the navigation space ...)
// Pathfinder PotentialField by Babbage Linden
//
// Part of the Pathfinder Open Source Pathfinding Demo
//
// The potential field maintains a representation of the navigation space
// as a string containing the number of steps to the exit for each square.
// The potential field lists for various commands: SETSIZE sets the size
// of the navigation space, the exit and intializes the potential field;
// ADDOBSTACLE and ADDOBSTACLEINDEX sets one point in the navigation space
// to an obstacle that must be navigated around and updates the potential
// field; NEXTPOS queries the potential field to find the next point to
// for an agent at a given point to move to. When the potential field is
// updated, care is taken to only update parts of the field affected by
// the change and to spread the update across a number of timer events to
// avoid blocking and so becoming unresponsive to NEXTPOS queries.
//
// Available under the Creative Commons Attribution-ShareAlike 2.5 license
// http://creativecommons.org/licenses/by-sa/2.5/
integer gPotentialFieldChannel = 1;
integer gDigitsPerElement = 2;
integer gMinValue = 0;
integer gMaxValue = 255;
integer gWidth = 0;
integer gHeight = 0;
integer gMaxUpdates = 10;
integer gCurrentUpdateMinX;
integer gCurrentUpdateMinY;
integer gCurrentUpdateMaxX;
integer gCurrentUpdateMaxY;
integer gNextUpdateMinX;
integer gNextUpdateMinY;
integer gNextUpdateMaxX;
integer gNextUpdateMaxY;
string gPotentialField;
integer min(integer a, integer b)
{
if(a < b)
{
return a;
}
return b;
}
integer max(integer a, integer b)
{
if(a > b)
{
return a;
}
return b;
}
string replace(string s, integer index, string newString)
{
integer newStringLength = llStringLength(newString);
string result = "";
if(index >= 1)
{
result += llGetSubString(s, 0, index - 1);
}
result += newString;
if(index < (llStringLength(s) - newStringLength))
{
result += llGetSubString(s, index + newStringLength, -1);
}
return result;
}
string hexc="0123456789ABCDEF";
string int2hex(integer x)
{
integer x0 = x & 0xF;
string res = llGetSubString(hexc, x0, x0);
x = (x >> 4) & 0x0FFFFFFF;
while( x != 0 )
{
x0 = x & 0xF;
res = llGetSubString(hexc, x0, x0) + res;
x = x >> 4;
}
return res;
}
integer hex2int(string hex)
{
return (integer)("0x" + hex);
}
string setElement(string elements, integer index, integer value)
{
string stringValue = int2hex(value);
while(llStringLength(stringValue) < gDigitsPerElement)
{
stringValue = "0" + stringValue;
}
//llSay(0, "setElement " + elements + " " + (string)index + " " + stringValue);
elements = replace(elements, index * gDigitsPerElement, stringValue);
return elements;
}
string getElementString(string elements, integer index)
{
if(index < 0)
{
return int2hex(gMaxValue);
}
return llGetSubString(elements, index * gDigitsPerElement, index * gDigitsPerElement + gDigitsPerElement - 1);
}
integer getElement(string elements, integer index)
{
return hex2int(getElementString(elements, index));
}
sayPotentialField(string elements)
{
string s = "\n";
integer y;
for(y = gHeight - 1; y >= 0; --y)
{
integer x;
for(x = 0; x < gWidth; ++x)
{
s += getElementString(elements, squareToIndex(x, y)) + " ";
}
s += "\n";
}
llSay(0,s);
}
integer squareToIndex(integer x, integer y)
{
if(x < 0 || x >= gWidth || y < 0 || y >= gHeight)
{
return -1;
}
return x + y * gWidth;
}
string addObstacle(string elements, integer x, integer y)
{
elements = setElement(elements, squareToIndex(x, y), gMaxValue);
expandUpdateRegion(x, y);
return updatePotentialField(elements);
}
expandUpdateRegion(integer x, integer y)
{
gNextUpdateMinX = min(gNextUpdateMinX, x - 1);
gNextUpdateMinX = max(gNextUpdateMinX, 0);
gNextUpdateMinY = min(gNextUpdateMinY, y - 1);
gNextUpdateMinY = max(gNextUpdateMinY, 0);
gNextUpdateMaxX = max(gNextUpdateMaxX, x + 1);
gNextUpdateMaxX = min(gNextUpdateMaxX, gWidth - 1);
gNextUpdateMaxY = max(gNextUpdateMaxY, y + 1);
gNextUpdateMaxY = min(gNextUpdateMaxY, gHeight - 1);
}
resetNextUpdateRegion()
{
gNextUpdateMinX = gWidth - 1;
gNextUpdateMinY = gHeight - 1;
gNextUpdateMaxX = 0;
gNextUpdateMaxY = 0;
}
string updatePotentialField(string elements)
{
// If current update region finished, switch to next region.
if(gCurrentUpdateMinY > gCurrentUpdateMaxY)
{
gCurrentUpdateMinX = gNextUpdateMinX;
gCurrentUpdateMinY = gNextUpdateMinY;
gCurrentUpdateMaxX = gNextUpdateMaxX;
gCurrentUpdateMaxY = gNextUpdateMaxY;
resetNextUpdateRegion();
// If next region empty, stop updating.
if(gCurrentUpdateMinY > gCurrentUpdateMaxY)
{
llSay(0, "updatePotentialField:DONE");
llSetTimerEvent(0.0);
return elements;
}
llSay(0, "updatePotentialField:(" + (string)gCurrentUpdateMinX + "," + (string)gCurrentUpdateMinY + ") (" + (string)gCurrentUpdateMaxX + "," + (string)gCurrentUpdateMaxY + ")");
}
// Recalculate potentials.
llResetTime();
integer x;
integer updates = 0;
while((updates < gMaxUpdates) && (gCurrentUpdateMinY <= gCurrentUpdateMaxY))
{
//llSay(0, "updatePotentialField:" + (string)gCurrentUpdateMinY);
for(x = gCurrentUpdateMinX; x <= gCurrentUpdateMaxX; ++x)
{
elements = calculatePotentialField(elements, x, gCurrentUpdateMinY);
++updates;
}
++gCurrentUpdateMinY;
}
llSetTimerEvent((llGetTime() * 2.0) + 0.1);
return elements;
}
string calculatePotentialField(string elements, integer x, integer y)
{
integer currentValue = getElement(elements, squareToIndex(x, y));
// Don't update obstacles or exits.
if(currentValue == gMaxValue || currentValue == gMinValue)
{
return elements;
}
integer minValue = gMaxValue;
minValue = min(minValue, getElement(elements, squareToIndex(x - 1, y)));
minValue = min(minValue, getElement(elements, squareToIndex(x + 1, y)));
minValue = min(minValue, getElement(elements, squareToIndex(x, y - 1)));
minValue = min(minValue, getElement(elements, squareToIndex(x, y + 1)));
minValue = min(minValue + 1, gMaxValue - 1);
if(minValue != currentValue)
{
//llSay(0, "calculatePotentialField:" + (string)x + "," + (string)y + " currentValue " + (string)currentValue + " newValue " + (string)minValue);
elements = setElement(elements, squareToIndex(x, y), minValue);
expandUpdateRegion(x, y);
}
return elements;
}
string nextStep(string elements, integer x, integer y)
{
integer nextX;
integer nextY;
integer minValue = gMaxValue;
integer currentX = x - 1;
integer currentY = y;
integer currentValue = getElement(elements, squareToIndex(currentX, currentY));
if(currentValue < minValue)
{
minValue = currentValue;
nextX = currentX;
nextY = currentY;
}
currentX = x + 1;
currentValue = getElement(elements, squareToIndex(currentX, currentY));
if(currentValue < minValue)
{
minValue = currentValue;
nextX = currentX;
nextY = currentY;
}
currentX = x;
currentY = y - 1;
currentValue = getElement(elements, squareToIndex(currentX, currentY));
if(currentValue < minValue)
{
minValue = currentValue;
nextX = currentX;
nextY = currentY;
}
currentY = y + 1;
currentValue = getElement(elements, squareToIndex(currentX, currentY));
if(currentValue < minValue)
{
minValue = currentValue;
nextX = currentX;
nextY = currentY;
}
if(minValue == gMaxValue)
{
return "";
}
return (string)nextX + "," + (string)nextY;
}
setSize(integer width, integer height, integer exitX, integer exitY)
{
gWidth = width;
gHeight = height;
gPotentialField = "";
integer y;
for(y = 0; y < height; ++y)
{
integer x;
for(x = 0; x < width; ++x)
{
gPotentialField = setElement(gPotentialField, squareToIndex(x, y), llAbs(exitX - x) + llAbs(exitY - y));
}
}
resetNextUpdateRegion();
sayPotentialField(gPotentialField);
}
init()
{
llListen(0, "", NULL_KEY, "");
llListen(gPotentialFieldChannel, "", NULL_KEY, "");
}
default
{
state_entry()
{
init();
}
on_rez(integer param)
{
init();
}
timer()
{
gPotentialField = updatePotentialField(gPotentialField);
}
listen(integer channel, string name, key id, string s)
{
list message = llCSV2List(s);
string command = llList2String(message, 0);
integer x = llList2Integer(message, 1);
integer y = llList2Integer(message, 2);
if(command == "ADDOBSTACLE")
{
gPotentialField = addObstacle(gPotentialField, x, y);
}
else if(command == "ADDOBSTACLEINDEX")
{
y = x / gWidth;
x %= gWidth;
gPotentialField = addObstacle(gPotentialField, x, y);
}
else if(command == "SETSIZE")
{
integer width = x;
integer height = y;
x = llList2Integer(message, 3);
y = llList2Integer(message, 4);
setSize(width, height, x, y);
}
else if(command == "NEXTPOS")
{
integer channel = llList2Integer(message, 3);
if(getElement(gPotentialField, squareToIndex(x, y)) == 0)
{
llSay(channel, "RESET");
}
string nextStepString = nextStep(gPotentialField, x, y);
if(llStringLength(nextStepString) > 0)
{
list nextStepList = llCSV2List(nextStepString);
x = llList2Integer(nextStepList, 0);
y = llList2Integer(nextStepList, 1);
llSay(channel, "NEXTPOS," + (string)x + "," + (string)y);
}
}
//sayPotentialField(gPotentialField);
}
}
// Pathfinder Rezzer by Babbage Linden
//
// Part of the Pathfinder Open Source Pathfinding Demo
//
// The rezzer listens for SETSIZE commands, which causes it to rez
// a grid of Square objects of the appropriate size and set the
// entry and exit points as exits. Touching the rezzer
// causes it to rez and agent above the entry point at the origin.
//
// Available under the Creative Commons Attribution-ShareAlike 2.5 license
// http://creativecommons.org/licenses/by-sa/2.5/
float gSquareWidth = 1.0;
float gPeriod = 5.0;
vector gOrigin;
vector gEntrance;
integer gEntranceX;
integer gEntranceY;
integer gPopulation = 0;
integer gMaxPopulation = 10;
integer gPotentialFieldChannel = 1;
integer gSquareChannel = 2;
integer gAgentChannel = 3;
init()
{
llListen(0, "", NULL_KEY, "");
}
default
{
state_entry()
{
init();
}
on_rez(integer param)
{
init();
}
listen(integer channel, string name, key id, string s)
{
list message = llCSV2List(s);
string command = llList2String(message, 0);
integer x = llList2Integer(message, 1);
integer y = llList2Integer(message, 2);
if(command == "SETSIZE")
{
integer width = x;
integer height = y;
integer exitX = llList2Integer(message, 3);
integer exitY = llList2Integer(message, 4);
gEntranceX = llList2Integer(message, 5);
gEntranceY = llList2Integer(message, 6);
gOrigin = llGetPos();
gOrigin.x -= ((width - 1) * gSquareWidth) / 2.0;
gOrigin.y -= ((height - 1) * gSquareWidth) / 2.0;
gEntrance = gOrigin;
gEntrance.x += gEntranceX * gSquareWidth;
gEntrance.y += gEntranceY * gSquareWidth;
gEntrance.z += 1.0;
for(y = 0; y < height; ++y)
{
for(x = 0; x < width; ++x)
{
vector pos = gOrigin;
pos.x += x * gSquareWidth;
pos.y += y * gSquareWidth;
pos.z += 0.5;
integer channel = (x + y * width);
llRezObject("Square", pos, <0,0,0>, <0,0,0,0>, channel);
}
}
llSay(gSquareChannel, "EXIT," + (string)(gEntranceX + gEntranceY * width));
llSay(gSquareChannel, "EXIT," + (string)(exitX + exitY * width));
gAgentChannel = 3;
gMaxPopulation = 10;
llSetTimerEvent(gPeriod);
}
else if(command == "RESET")
{
gPopulation = 0;
llSay(gSquareChannel, "RESET");
integer channel;
for(channel = 2; channel <= gAgentChannel; ++channel)
{
llSay(channel, "RESET");
}
llSetTimerEvent(0);
gMaxPopulation = 0;
}
else if(command == "FINISHED")
{
--gPopulation;
if(gPopulation < 0) {gPopulation = 0;}
llSetTimerEvent(gPeriod);
//llSay(0,"Population:" + (string)gPopulation);
}
}
timer()
{
if(gPopulation >= gMaxPopulation)
{
llSetTimerEvent(0);
return;
}
integer channel = gAgentChannel++;
llRezObject("Agent", gEntrance, <0,0,0>, <0,0,0,0>, channel);
llSay(channel, "POS," + (string)gEntranceX + "," + (string)gEntranceY);
++gPopulation;
//llSay(0,"Population:" + (string)gPopulation);
}
}
// Pathfinder Agent by Babbage Linden
//
// Part of the Pathfinder Open Source Pathfinding Demo
//
// The agent periodically makes NEXTPOS queries to the PotentialField
// script to find the next point to move to and can have its current
// position set with the POS command.
//
// Available under the Creative Commons Attribution-ShareAlike 2.5 license
// http://creativecommons.org/licenses/by-sa/2.5/
float gSquareWidth = 1.0;
float gStartPeriod = 2.0;
float gPeriod = 2.0;
integer gChannel;
integer gX;
integer gY;
integer gSquareChannel = 2;
integer gPotentialFieldChannel = 1;
default
{
on_rez(integer param)
{
gChannel = param;
llListen(gChannel, "", NULL_KEY, "");
}
listen(integer channel, string name, key id, string s)
{
list message = llCSV2List(s);
string command = llList2String(message, 0);
integer x = llList2Integer(message, 1);
integer y = llList2Integer(message, 2);
if(command == "POS")
{
gX = x;
gY = y;
llSetTimerEvent(gPeriod);
}
else if(command == "NEXTPOS")
{
integer dX = x - gX;
integer dY = y - gY;
vector pos = llGetPos();
pos.x += dX * gSquareWidth;
pos.y += dY * gSquareWidth;
llSetPos(pos);
gX = x;
gY = y;
gPeriod = gStartPeriod;
llSetTimerEvent(gPeriod);
}
else if(command == "RESET")
{
llSay(0,"FINISHED");
llDie();
}
}
timer()
{
llSay(gPotentialFieldChannel, "NEXTPOS," + (string)gX + "," + (string)gY + "," + (string)gChannel);
gPeriod *= 2.0;
llSetTimerEvent(gPeriod);
}
}
// Pathfinder Square by Babbage Linden
//
// Part of the Pathfinder Open Source Pathfinding Demo for Second Life
//
// The square listens for various commands: RESET causes it to kill itself;
// EXIT causes it to turn black and set itself as an exit. Touching the
// causes it to grow and to send the ADDOBSTACLEINDEX command to the
// PotentialField script.
//
// Available under the Creative Commons Attribution-ShareAlike 2.5 license
// http://creativecommons.org/licenses/by-sa/2.5/
integer gSquareChannel = 2;
integer gPotentialFieldChannel = 1;
integer gIndex;
integer STATE_DEFAULT = 0;
integer STATE_OBSTACLE = 1;
integer STATE_EXIT = 2;
integer gState = STATE_DEFAULT;
default
{
on_rez(integer param)
{
gIndex = param;
llListen(gSquareChannel, "", NULL_KEY, "");
}
touch_start(integer num)
{
if(gState == STATE_DEFAULT)
{
llSay(gPotentialFieldChannel, "ADDOBSTACLEINDEX," + (string)gIndex);
llSetScale(<1,1,1>);
llSetPos(llGetPos() + <0,0,0.5>);
gState = STATE_OBSTACLE;
}
}
listen(integer channel, string name, key id, string s)
{
list message = llCSV2List(s);
string command = llList2String(message, 0);
if(command == "RESET")
{
llDie();
}
else if(command == "EXIT")
{
integer index = llList2Integer(message, 1);
if(index == gIndex)
{
llSetColor(<0,0,0>, ALL_SIDES);
gState = STATE_EXIT;
}
}
else if(command == "ENTRANCE")
{
integer index = llList2Integer(message, 1);
if(index == gIndex)
{
llSetTexture("5748decc-f629-461c-9a36-a35a221fe21f", ALL_SIDES);
gState = STATE_EXIT;
}
}
}
}