Pathfinder

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)

### 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)

// 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

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!

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?

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

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.

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

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

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 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.

<-- 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.

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.