Welcome to the Second Life Forums Archive

These forums are CLOSED. Please visit the new forums HERE

Pathfinder

Karl Longwell
Junior Member
Join date: 23 Jul 2003
Posts: 5
08-09-2003 18:18
Here's my sim 'pathfinder' script that should be easily modified into a cross-sim auotmated flying script. (Ie: Global Taxi). It's a lil messy as I was playing with a few things (I think this is the 3rd script I wrote in SL ;)


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!
Jack Skallagrimson
バナナの電話!
Join date: 17 Jul 2003
Posts: 63
01-03-2004 16:24
I know I ask this in a bunch of scripts... but, I have tried and tried to get this script to do something, but it hasn't done a thing. Can someone help?
_____________________
hi
Azelda Garcia
Azelda Garcia
Join date: 3 Nov 2003
Posts: 819
01-06-2004 17:51
This is a very cool script. If this was really this guy's third script, this guy is a genius! He doesn't exist in the game any more.

To use it, add the two scripts to an object and type "dest: kissling" followed by "go". It will stack-heap if you attempt to add the entirety of SL mainland to the database, but it's quite easy to fix.

The algo in this script is very good and is the basis for my Navigational Computer which I use in my Satellite System. It's really useful to have, it opens a lot of doors. You'll want to combine it with my ChangeSim module (in the Alternative Scripting Library) and then the world is your oyster!

Does anyone know what happened to Karl Longwell? This is one of the best scripts in the library, arguably THE best script.

Azelda
Beau Perkins
Second Life Resident.
Join date: 25 Dec 2003
Posts: 1,061
02-06-2004 13:15
excuse my lack of scripting skill here. To get this to work do I put all three parts in one script? or do i make 3 different scripts and drop them all in the same object?
Kedamono Onizuka
Member
Join date: 27 Jan 2004
Posts: 16
02-19-2004 16:28
From: someone
Originally posted by Beau Perkins
excuse my lack of scripting skill here. To get this to work do I put all three parts in one script? or do i make 3 different scripts and drop them all in the same object?


Looking at the instructions, you create one notecard with the database information listed at the beginning of the post, and then you create two scripts for the second and third code block.
Michael Small
Addicted To Counseling
Join date: 22 Sep 2003
Posts: 123
03-14-2004 12:23
I have tried this code, and being that it's his 3rd script, I will be gentle...


1. there are no usage instructions
2. its poorly commented
3. its terribly slow
4. its not scalable (cant add more sims)
5. it is very unoptimized. (multiple calls to the same llGetListLength function in one statement, this should have been called once and the result cached for multiple uses)

and the biggie:
6. the algorithim in general is flawed. it wont find a path from stinson to brilliant, because the path is shaped in a U. -- correct me if im wrong.

A valiant effort neverless.

Michael
_____________________
I don't play, but I still read the forums.

The new layout sucks.
Adam Zaius
Deus
Join date: 9 Jan 2004
Posts: 1,483
03-14-2004 23:27
This is why I keep saying if you want a pathfinder, dont write it around the one on the forums, if you want to write one, you need to rewrite from the ground up.

Guzar Fonzarelli wrote a better one for me a while back, and I have since then rewritten my own.

-Adam
Michael Small
Addicted To Counseling
Join date: 22 Sep 2003
Posts: 123
03-18-2004 07:18
I wrote mine using Dijkstra's algorithm. It's working now, but the source needs cleaned before I can release it.

Yes, I will post it to the library. :)
_____________________
I don't play, but I still read the forums.

The new layout sucks.
Huns Valen
Don't PM me here.
Join date: 3 May 2003
Posts: 2,749
03-23-2004 05:14
I wrote a parallel terraced scan-based pathfinder last year. It cleans up the found path with a raycaster to eliminate redundant travel. Maybe I'll post it here sometime before the end of the year. :)

edit: I'm rewriting it to be able to handle extremely large maps.
Ming Chen
Here since 0.4.1!
Join date: 3 Sep 2003
Posts: 524
08-10-2004 08:56
<-- Is Developing A faster way to do this, except for lsl doing all the calculatis with its amazing 14k memory per script, Im doing it off a web server with 8 megs a script and a sql database :) Able to handle with larger maps.
_____________________
xiopher Keegan
SL Packrat
Join date: 17 Jun 2004
Posts: 9
08-13-2004 10:21
I was wondering if anyone ever created a scrtipt to follow the linden land. I would use it mainly to follow a road from point a to b.