Pathfinding Algorithm

Hi,

I am looking to buy a pathfinding algo (A* or similar).

Please him me up inworld if you have something

Haden Marshall

I sell access to mine, which is hosted outside of SL, and has an email interface.

L$25/user if you plan to resell it as part of something else (eg a vehicle), sold in minimum bundles of 10 users at a time.

The system uses A* pathfinding against a current database of mainland & island sims, and is undergoing an update at the moment to select prefferentially based on last measured SimFPS.

-Adam

I started messing around with an implementation of Djikstra's algorithm however this IS NOT FINISHED! Maybe it will help you though. Thanks to Francis Chung for pointing out the name Djikstra.

//These three lists go together. I would make them into a 2d array but SL doesn't support that. They define sides
// or walkways. So the first walkway is between points 1 and 2 and has a distance of .215.

 
list gSideA=     [   1,    1,    2,    2,    3,    3,    4,    4,    6,    6,    7,    7,    8,    9,    9,   10,   10,   11,   12,   13,   14];
list gSideB=     [   2,    6,    3,    6,    4,    7,    5,    8,    7,    9,    8,   10,   11,   10,   13,   11,   14,   15,   13,   14,   15];
list gSideLength=[.215, .253, .149, .081, .120, .060, .154, .067, .167, .042, .149, .050, .051, .175, .128, .163, .118, .115, .227, .168, .163];

// This holds the best distance found so far for any given point.
list gPointDistance;
// This shows the optimal point to return to found so far for any given point.
list gPointBack;
//This starts out as "" and turns to "permanent" when we are done with that point.
list gPointFlag;  


// The main routine. It prints out the shortest path at the end by saying the points to go to.
find_shortest_path(integer current_point, integer end_point)
{
    // This is used after everything has been figured out to display the way back.
    list the_way_back;
    
    // Initializations. Set the dietance for all points higher that it can possibly go.        
    gPointDistance = [
1000, 1000, 1000, 1000, 1000, 1000,
1000, 1000, 1000, 1000, 1000,
1000, 1000, 1000, 1000, 1000

];

// This points the way back. 0 means we've gotten to our destination but set them all 
// to 0 for now.
    gPointBack=[
0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0
];

// These show whether the point has been finished with. They change to "permanent" 
// when that is the case.
    gPointFlag=[
"", "", "", "", "", "",
"", "", "", "", "",
"", "", "", "", "",
"", "", "", "", ""
];

// The starting point has a distance of 0.
gPointDistance=ListReplaceList(gPointDistance, [0], current_point);

// And is permanent
gPointFlag = ListReplaceList(gPointFlag, ["Permanent"], current_point);
    
    while(current_point != 0)
    {
        assign_distances(current_point);
        current_point=find_next_point(current_point);
    }
    
    // We have figured everything out now. Let's display it
    current_point=end_point;
    while(llList2Float(gPointDistance, current_point) > 0)
    {
        current_point=llList2Integer(gPointBack, current_point);
        the_way_back = the_way_back + current_point;
    }
    llSay(0, llDumpList2String(the_way_back, " "));
    
}


// This figures out the best distances known so far for points adjoining the current point.
// Also if the current point is the best way back so far it is flagged as such.
assign_distances(integer current_point)
{
    integer current_side; // all the walkways
    integer far_point;    // if one of the ends of the walkway is the current point this is the other
    integer c;            // a counter
    
    // I was hoping not having to recalculate this in the for loop would speed things up
    // but it didn't seem to make much difference.
    c=llGetListLength(gSideA);
    
    for(current_side=0; current_side < c; current_side++)
    {
        
    // Let's first find a walkway with our current point and figure out the other end point
    far_point=0;
     if(llList2Integer(gSideA, current_side) == current_point || llList2Integer(gSideB, current_side) == current_point)
        {
            if(llList2Integer(gSideA, current_side) == current_point)
            {
                far_point=llList2Integer(gSideB, current_side);
            }
        else
            {
                far_point=llList2Integer(gSideA, current_side);
            }
        }
        
        // We found a walkway and it isn't already marked permanent
        if(far_point != 0 && llList2String(gPointFlag, far_point) == "")
        {
        // If we haven't already found a better distance, assign the distance and way back
 
        if(llList2Float(gPointDistance, far_point)  > llList2Float(gPointDistance, current_point) + llList2Float(gSideLength, current_side))
            {
             gPointDistance=ListReplaceList(gPointDistance, [llList2Float(gPointDistance, current_point) + llList2Float(gSideLength, current_side)], far_point);   
                gPointBack=ListReplaceList(gPointBack, [current_point], far_point);

            }
        }
    }
}



integer find_next_point(integer current_point)
{
    integer best_point=0;
    integer c;
    integer d;
    
    d=llGetListLength(gPointDistance);
    
    for(c=1; c<d; c++)
    {
        if(llList2String(gPointFlag, c) == "" && 
llList2Float(gPointDistance, c) > 0)
        {
            if(best_point == 0 || llList2Float(gPointDistance, c) <
llList2Float(gPointDistance, best_point))
            {
                best_point=c;
            }
        }
    }
    if(best_point != 0)
    {
        gPointFlag=ListReplaceList(gPointFlag, ["permanent"], best_point);
    }
    return best_point;
}

// This is code from the wiki to replace an item in a list.
list ListReplaceList(list dest, list src, integer pos) {
    if (pos < 0) pos = llGetListLength(dest) + pos;
    return llListInsertList(llDeleteSubList(dest, pos, pos), src, pos);
}






default
{
    state_entry()
    {
        llSay(0, "Hello, Avatar!");
        find_shortest_path(11, 12);
        llSay(0, "The end");
    }

    touch_start(integer total_number)
    {
        llSay(0, "Touched.");
    }
}

Thanks, I will take a look at that.

Regards,

Haden

You may have speed and memory problems using Djinkstra's algorithm in LSL.

I used to do it in the 1.2 era; around the 92 sim mark, it just refused to work. Before then, it was taking over a minute to do a calculation, with some fairly serious optimisation.

-Adam

That's one of the reasons I put it by the wayside. I didn't have memory problems but as I recall it was taking at least 20 seconds to figure out 15 points.

When I did it locally in Perl it was done before I released the Enter key.

The Djinkstra's algorithm looks pretty easy to implement into php and mysql(which would hold the sim coords)...I made an algorithm that ran off php about the 300 sim mark and found the path to opposite sims on the map in 5 seconds....sadley, I gave up on that algorithm when I forgot to implement the "u" shaped paths and would have made me redo the script all together, ill take a try at this one and see how it works

If you are going to reimplement it in php, here is the link I used (I'm no math wiz so I liked this one) to figure out how to do it in lsl.

Djikstra's algorithm