
First part is the DB (on a notecard)
CODE
### Zone,X,Y,North,West,South,East ###
47
^gibson,996,1000,bonifacio,NILL,NILL,oak grove
^bonifacio,996,1001,dore,NILL,gibson,morris
^dore,996,1002,darkwood,NILL,bonifacio,ahern
^darkwood,996,1003,NILL,NILL,dore,NILL
^oak grove,997,1000,morris,gibson,NILL,NILL
^morris,997,1001,ahern,bonifacio,oak grove,rizal
^ahern,997,1002,NILL,dore,morris,lusk
^brown,997,1007,NILL,NILL,NILL,green
^rizal,998,1001,lusk,morris,NILL,tehama
^lusk,998,1002,NILL,ahern,rizal,perry
^aqua,998,1006,green,NILL,NILL,blue
^green,998,1007,NILL,brown,aqua,NILL
^tehama,999,1001,perry,rizal,NILL,freelon
^perry,999,1002,kissling,lusk,tehama,clara
^kissling,999,1003,NILL,NILL,perry,boardman
^gray,999,1005,blue,NILL,NILL,plum
^blue,999,1006,NILL,aqua,gray,lime
^da boom,1000,1000,freelon,NILL,NILL,ritch
^freelon,1000,1001,clara,tehama,da boom,minna
^clara,1000,1002,boardman,perry,freelon,varney
^boardman,1000,1003,tan,kissling,clara,deharo
^tan,1000,1004,plum,NILL,boardman,NILL
^plum,1000,1005,lime,gray,tan,sage
^lime,1000,1006,mocha,blue,plum,rose
^mocha,1000,1007,NILL,NILL,lime,olive
^immaculate,1001,999,ritch,NILL,NILL,NILL
^ritch,1001,1000,minna,da boom,immaculate,zoe
^minna,1001,1001,varney,freelon,ritch,natoma
^varney,1001,1002,deharo,clara,minna,stillman
^deharo,1001,1003,NILL,boardman,varney,NILL
^sage,1001,1005,rose,plum,NILL,NILL
^rose,1001,1006,olive,lime,sage,teal
^olive,1001,1007,NILL,mocha,rose,slate
^zoe,1002,1000,natoma,ritch,NILL,clementina
^natoma,1002,1001,stillman,minna,zoe,taber
^stillman,1002,1002,NILL,varney,natoma,NILL
^teal,1002,1006,slate,rose,NILL,NILL
^slate,1002,1007,NILL,olive,teal,NILL
^clementina,1003,1000,taber,zoe,NILL,NILL
^taber,1003,1001,NILL,natoma,clementina,welsh
^welsh,1004,1001,NILL,taber,NILL,clyde
^jessie,1005,1000,clyde,NILL,NILL,stanford
^clyde,1005,1001,NILL,welsh,jessie,hawthorne
^stanford,1006,1000,hawthorne,jessie,NILL,federal
^hawthorne,1006,1001,NILL,clyde,stanford,shipley
^federal,1007,1000,shipley,stanford,NILL,NILL
^shipley,1007,1001,NILL,hawthorne,federal,NILL
The second part is the DB script (I had to split them up due to memory limitations)
CODE
// Pathfinder DB
// Created by Karl Longwell
// July 30th, 2003
//
// This used to be a lot prettier, but uh, need more memory!
integer numEntries = 0;
integer currentEntry = 0;
list zoneData;
key entryRequest;
key dataRequest;
integer getSimIndex(string name)
{
integer rval = -1;
if (name == "")
{
vector simCorner = llGetRegionCorner() / 256;
rval = llListFindList(zoneData, [(string)((integer)simCorner.x), (string)((integer)simCorner.y)]);
rval --;
}
else
{
string tName = "^" + name;
rval = llListFindList(zoneData, [tName]);
}
return rval;
}
default
{
state_entry()
{
if (zoneData == []) // don't have zone data yet so..
entryRequest = llGetNotecardLine("World Data", 1);
}
touch_start(integer num)
{
if (zoneData != [])
llMessageLinked(0, 0, "loaded", "");
}
link_message(integer sender_num, integer num, string str, key id)
{
if (num == 666) // special data request
{
integer index = getSimIndex(llToLower(str)); // get the index of requested zone
if (index >= 0)
{
list sendList = llList2List(zoneData, index, index + 6); // grab a list
// llWhisper(0, "Sending: " + llList2CSV(sendList));
llMessageLinked(0, 555, llList2CSV(sendList), ""); // send it back
}
}
}
dataserver(key queryid, string data)
{
if (data != EOF)
{
if (queryid == entryRequest) // number of entries
{
numEntries = (integer)data; // easy enough
entryRequest = ""; // free up memory?
currentEntry = 1; // set ourselves to the first entry for the load
llWhisper(0, (string)currentEntry); // debug
dataRequest = llGetNotecardLine("World Data",1 + currentEntry); // do a datarequest on the first entry
}
else if (queryid == dataRequest) // loading data here
{
list current; // current line
current = llCSV2List(data); // convert the notecard data to a list (csv)
if (llGetListLength(current) == 7) // make sure it matches our number of columns
zoneData = zoneData + current; // add it to the current list
current = []; // free up memory?
if (currentEntry == numEntries) // loaded them all
{
dataRequest = ""; // free up memory?
llWhisper(0, "sending loaded?");
llMessageLinked(0, 0, "loaded", "");
}
else
{
currentEntry++; // get ready for the next entry
llWhisper(0, (string)currentEntry); // debug
dataRequest = llGetNotecardLine("World Data",1 + currentEntry); // do a datarequest for the next entry
}
}
}
}
}
Here's the actual pathfinding code
CODE
list currSim;
list destSim;
list visited;
list path;
vector destVector;
string dest;
// Flags for figuring out direction, S ones mean strongest
integer NORTH = 1;
integer WEST = 2;
integer SOUTH = 4;
integer EAST = 8;
integer getFlightPath(list current)
{
integer rval = -1;
vector start = <0,0,0>;
integer flags = 0;
integer hDirection;
integer vDirection;
integer vFirst = -1;
integer vFlipped = 0;
float hDistance = 0;
float vDistance = 0;
string nextSim = "";
start.x = llList2Float(current, 1);
start.y = llList2Float(current, 2);
if (start.x > destVector.x)
flags = flags | WEST;
else if (start.x < destVector.x)
flags = flags | EAST;
if (start.y > destVector.y)
flags = flags | SOUTH;
else if (start.y < destVector.y)
flags = flags | NORTH;
// ok, now we should have an idea which direction to go.. so let's figure out which to take first (first heuristic)
if (flags & WEST)
{
hDirection = WEST;
hDistance = start.x - destVector.x;
}
else if (flags & EAST)
{
hDirection = EAST;
hDistance = destVector.x - start.x;
}
if (flags & SOUTH)
{
vDirection = SOUTH;
vDistance = start.y - destVector.y;
}
else if (flags & NORTH)
{
vDirection = NORTH;
vDistance = destVector.y - start.y;
}
if (hDistance > vDistance)
vFirst = 0;
else
vFirst = 1;
string north = llList2String(current, 3);
string west = llList2String(current, 4);
string south = llList2String(current, 5);
string east = llList2String(current, 6);
while (vFirst != -1)
{
if (vFirst == 1 && vDirection == NORTH && north != "NILL" && llListFindList(visited, [north]) == -1)
{
nextSim = north;
vFirst = -1;
}
else if (vFirst == 1 && vDirection == SOUTH && south != "NILL" && llListFindList(visited, [south]) == -1)
{
nextSim = south;
vFirst = -1;
}
else if (vFirst == 0 && hDirection == WEST && west != "NILL" && llListFindList(visited, [west]) == -1)
{
nextSim = west;
vFirst = -1;
}
else if (vFirst == 0 && hDirection == EAST && east != "NILL" && llListFindList(visited, [east]) == -1)
{
nextSim = east;
vFirst = -1;
}
if (nextSim == "")
{
if (vFlipped == 1)
vFirst = -1;
else
{
if (vFirst == 0)
vFirst = 1;
else
vFirst = 0;
vFlipped = 1;
}
}
}
if (nextSim == "")
{
// second heuristic, makes use of the 'tan' choke point
if (east != "NILL" && llListFindList(visited, [east]) == -1)
nextSim = east;
else if (west != "NILL" && llListFindList(visited, [west]) == -1)
nextSim = west;
else if (north != "NILL" && llListFindList(visited, [north]) == -1)
nextSim = north;
else if (south != "NILL" && llListFindList(visited, [south]) == -1)
nextSim = south;
else
{
nextSim = llList2String(path, llGetListLength(path) - 2);
path = llDeleteSubList(path, llGetListLength(path) - 2, llGetListLength(path) - 1);
}
}
if (nextSim != "")
llMessageLinked(0, 666, nextSim, "");
return rval;
}
default
{
state_entry()
{
llWhisper(0, "Pathfinder loaded.");
llListen(0, "", llGetOwner(), "");
}
link_message(integer sender, integer num, string str, key id)
{
if (num == 555)
{
if (currSim == []) // get current sim
{
currSim = llCSV2List(str);
visited = [llGetSubString(llList2String(currSim, 0), 1, llStringLength(llList2String(currSim, 0)) - 1)];
llWhisper(0, "Source: " + llGetSubString(llList2String(currSim, 0), 1, llStringLength(llList2String(currSim, 0)) - 1));
}
else if (destSim == [])
{
destSim = llCSV2List(str);
if (llGetListLength(destSim) <= 0)
llWhisper(0, "Unable to find destination in database!");
else
llWhisper(0, "Dest: " + llGetSubString(llList2String(destSim, 0), 1, llStringLength(llList2String(destSim, 0)) - 1));
}
else
{
list tmpSim = llCSV2List(str);
if (llToLower(dest) == llGetSubString(llList2String(tmpSim, 0), 1, llStringLength(llList2String(tmpSim, 0)) - 1))
{
path += [llGetSubString(llList2String(tmpSim, 0), 1, llStringLength(llList2String(tmpSim, 0)) - 1)];
llWhisper(0, "Path is: " + llList2CSV(path));
}
else
{
llWhisper(0, "Current: " + llGetSubString(llList2String(tmpSim, 0), 1, llStringLength(llList2String(tmpSim, 0)) - 1));
visited += [llGetSubString(llList2String(tmpSim, 0), 1, llStringLength(llList2String(tmpSim, 0)) - 1)];
path += [llGetSubString(llList2String(tmpSim, 0), 1, llStringLength(llList2String(tmpSim, 0)) - 1)];
getFlightPath(tmpSim);
}
}
}
}
listen(integer channel, string name, key id, string message)
{
list command = llParseString2List(message, [" "], []);
if (llGetListLength(command) == 2)
{
if (llList2String(command, 0) == "dest")
{
currSim = [];
destSim = [];
llMessageLinked(0, 666, "", "");
llMessageLinked(0, 666, llList2String(command, 1), "");
}
}
else if (llGetListLength(command) == 3)
{
if (llList2String(command, 0) == "dest")
{
currSim = [];
destSim = [];
llMessageLinked(0, 666, "", "");
llMessageLinked(0, 666, llList2String(command, 1) + " " + llList2String(command, 2), "");
}
}
else if (message == "go")
{
path = [];
visited = [];
destVector = <0,0,0>;
destVector.x = llList2Integer(destSim, 1);
destVector.y = llList2Integer(destSim, 2);
dest = llGetSubString(llList2String(destSim, 0), 1, llStringLength(llList2String(destSim, 0)) - 1);
getFlightPath(currSim)
}
}
}
Have fun!