Basic A-Star Pathfinder

From Second Life Wiki
Jump to: navigation, search

Integer based node-grid sized at 20x32.

Tile <lsl> // 2009, Nexii Malthus // Public Domain

integer Obstacle = FALSE; default {

   touch_start(integer total_number)
   {
       if(llDetectedKey(0) != llGetOwner()) return;
       
       if(!Obstacle){
           llRegionSay(9999,llGetSubString(llGetScriptName(),4,-1));
           llSetScale(<1.0,1.0,1.0>);
           llSetColor(<0.25,0.25,0.25>,0);
           Obstacle = TRUE;
       } else {
           llRegionSay(9999,llGetSubString(llGetScriptName(),4,-1));
           llSetScale(<1.0,1.0,0.01>);
           llSetColor(<1.00,1.00,1.00>,0);
           Obstacle = FALSE;
       }
   }

} </lsl>

A* Unit <lsl> // 2009, Nexii Malthus // Public Domain

list Rows = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]; list Nodes = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]; list Cost = [14,10,14,

             10,   10,
             14,10,14];

list Directions = [< 1, 1,0>,< 0, 1,0>,<-1, 1,0>,

                  < 1, 0,0>,          <-1, 0,0>,
                  < 1,-1,0>,< 0,-1,0>,<-1,-1,0>];

list aPath; vector Dest; integer Tock;

integer Change; vector Ref = <15.5,67.0,22.0>;

integer GetState(list Src,integer X,integer Y){

   return llList2Integer(Src,Y) & X;}

list SetState(list Src,integer X,integer Y){

   return llListReplaceList(Rows,[llList2Integer(Src,Y) ^ X],Y,Y);}

integer Dist(integer X1,integer Y1,integer X2,integer Y2){

   return (X1 - X2) + (Y1 - Y2);}

list A_Path(vector GPos,vector TPos){

   if(!Change) return;
   list Path = [];
   vector gPos = GPos - Ref;
   vector tPos = TPos - Ref;
   integer X1 = (integer)gPos.x;integer Y1 = (integer)gPos.y;
   integer Xt = (integer)tPos.x;integer Yt = (integer)tPos.y;
   integer Tick = 150;//Failsafe...
   
   @Loop;
       --Tick;
       integer Dir = -1;integer H = 999;
       
       if(!GetState(Rows,X1+1,Y1+1) && !GetState(Nodes,X1+1,Y1+1)){ if(H < 14 + Dist(X1+1,Y1+1,Xt,Yt)){ Dir = 0; } }
       if(!GetState(Rows,X1  ,Y1+1) && !GetState(Nodes,X1  ,Y1+1)){ if(H < 10 + Dist(X1  ,Y1+1,Xt,Yt)){ Dir = 1; } }
       if(!GetState(Rows,X1-1,Y1+1) && !GetState(Nodes,X1-1,Y1+1)){ if(H < 14 + Dist(X1-1,Y1+1,Xt,Yt)){ Dir = 2; } }
       if(!GetState(Rows,X1+1,Y1  ) && !GetState(Nodes,X1+1,Y1  )){ if(H < 10 + Dist(X1+1,Y1  ,Xt,Yt)){ Dir = 3; } }
       if(!GetState(Rows,X1-1,Y1  ) && !GetState(Nodes,X1-1,Y1  )){ if(H < 10 + Dist(X1-1,Y1  ,Xt,Yt)){ Dir = 4; } }
       if(!GetState(Rows,X1+1,Y1-1) && !GetState(Nodes,X1+1,Y1-1)){ if(H < 14 + Dist(X1+1,Y1-1,Xt,Yt)){ Dir = 5; } }
       if(!GetState(Rows,X1  ,Y1-1) && !GetState(Nodes,X1  ,Y1-1)){ if(H < 10 + Dist(X1  ,Y1-1,Xt,Yt)){ Dir = 6; } }
       if(!GetState(Rows,X1-1,Y1-1) && !GetState(Nodes,X1-1,Y1-1)){ if(H < 14 + Dist(X1-1,Y1-1,Xt,Yt)){ Dir = 7; } }
       
       Path += Dir;
       Nodes = SetState(Nodes,X1,Y1);
   if((X1 != Xt)||(Y1 != Yt)||(!Tick)||(Dir+1)) jump Loop;
   Nodes = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];
   return Path;

}


default {

   state_entry(){
       llListen(9999,"","","");
   }
   
   listen(integer ch,string nm,key id,string msg){
       integer Y = (integer)msg;integer X = (integer)nm;
       Rows = SetState(Rows,X,Y);
       Change = TRUE;
   }
   
   touch_start(integer dnum){
       if(llDetectedKey(0) != llGetOwner())return;
       llSensor("Target","",PASSIVE,30.0,TWO_PI);
   }
   
   sensor(integer dnum){
       Dest = llDetectedPos(0);
       aPath = A_Path(llGetPos(),Dest);
       llSetTimerEvent(1.0);
   }
   
   timer(){
       if(Change){aPath = A_Path(llGetPos(),Dest);Tock = 0;}
       llSetPos(llGetPos() + llList2Vector(Directions,llList2Integer(aPath,Tock)));
       ++Tock;if(Tock >= llGetListLength(aPath) || llVecDist(llGetPos(),Dest) < 0.1) llSetTimerEvent(FALSE);
   }

} </lsl>