ZoriaRPG

ZScript A* (Path Finding for NPCs)

Mar 11th, 2018
82
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Credits to Lejes for making the A* algorithm actually work in ZC! I probably wouldn't have ended up making my version (which is older than this) work without the assistance!
  2.  
  3. ffc script Astar5FFC
  4. {
  5.     void run()
  6.     {
  7.         while (true)
  8.         {
  9.             if (Link->PressEx1)
  10.             {
  11.                 Astar5(this, ComboAt(Link->X + 8, Link->Y + 8));
  12.             }
  13.            
  14.             Waitframe();
  15.         }
  16.     }
  17. }
  18.  
  19. void Astar5(ffc Pathfinder, int Dest)
  20. {
  21.     int PathfinderLoc = ComboAt(CenterX(Pathfinder), CenterY(Pathfinder));
  22.     int current = PathfinderLoc;
  23.    
  24.     int ClosedSet[176]; // The set of nodes already evaluated.
  25.     int OpenSet[176]; // The set of tentative nodes to be evaluated, initially containing the start node
  26.     int Came_From[176]; // The map of navigated nodes.
  27.     int total_path[176];
  28.  
  29.     int g_score[176]; // Cost from start along best known path.
  30.  
  31.     // Estimated total cost from start to goal through y.
  32.     int f_score[176];
  33.    
  34.     //Astar5ArrayInit(OpenSet, ClosedSet, Came_From, g_score, f_score);
  35.     for (int i = 0; i < 176; i++)
  36.     {
  37.         OpenSet[i] = -1;
  38.     }
  39.     for (int i = 0; i < 176; i++)
  40.     {
  41.         ClosedSet[i] = -1;
  42.     }
  43.     for (int i = 0; i < 176; i++)
  44.     {
  45.         Came_From[i] = -1;
  46.     }
  47.     for (int i = 0; i < 176; i++)
  48.     {
  49.         total_path[i] = -1;
  50.     }
  51.     for (int i = 0; i < 176; i++)
  52.     {
  53.         g_score[i] = 9999;
  54.     }
  55.     for (int i = 0; i < 176; i++)
  56.     {
  57.         f_score[i] = 9999;
  58.     }
  59.    
  60.     OpenSet[0] = PathfinderLoc;
  61.     g_score[current] = 0;
  62.     f_score[current] = ManhattanDist(PathfinderLoc, Dest);
  63.    
  64.     while(!ListIsEmpty(OpenSet))//while OpenSet is not empty
  65.     {
  66.         current = FindNode(OpenSet);
  67.         for (int i = 0; i < SizeOfArray(OpenSet); i++)
  68.         {
  69.             if (OpenSet[i] > -1 && current > -1)
  70.             {
  71.                 if (f_score[OpenSet[i]] < f_score[current] || (f_score[OpenSet[i]] == f_score[current] && ManhattanDist(OpenSet[i], Dest) < ManhattanDist(current, Dest)))
  72.                 {
  73.                     current = OpenSet[i];
  74.                 }
  75.             }
  76.         }
  77.  
  78.         if(current == Dest)
  79.         {
  80.             reconstruct_path(total_path, Came_From, current, PathfinderLoc);
  81.             for (int i = 175; i >= 0; i--)
  82.             {
  83.                 Trace(total_path[i]);
  84.                 if (total_path[i] > -1)
  85.                 {
  86.                     //Pathfinder->X = ComboX(total_path[i]);
  87.                     //Pathfinder->Y = ComboY(total_path[i]);
  88.                    
  89.                     // Correct vvv
  90.                     Screen->ComboD[total_path[i]] = 897;
  91.                     Screen->ComboC[total_path[i]] = 7;
  92.                     Waitframes(15);
  93.                    
  94.                     // int walkVar = i + 1;
  95.                     // while(walkVar <= -1)
  96.                     // {
  97.                         // walkVar += 1;
  98.                     // }
  99.                    
  100.                     // if(total_path[walkVar] == PathfinderLoc - 16)
  101.                     // {
  102.                         // for(int i2 = 0; i2 < 16; i2 += 1)
  103.                         // {
  104.                             // Pathfinder->Y -= 1;
  105.                            
  106.                             // Waitframe();
  107.                         // }
  108.                     // }
  109.                     // else if(total_path[walkVar] == PathfinderLoc + 16)
  110.                     // {
  111.                         // for(int i2 = 0; i2 < 16; i2 += 1)
  112.                         // {
  113.                             // Pathfinder->Y += 1;
  114.                            
  115.                             // Waitframe();
  116.                         // }
  117.                     // }
  118.                     // else if(total_path[walkVar] == PathfinderLoc - 1)
  119.                     // {
  120.                         // for(int i2 = 0; i2 < 16; i2 += 1)
  121.                         // {
  122.                             // Pathfinder->X -= 1;
  123.                            
  124.                             // Waitframe();
  125.                         // }
  126.                     // }
  127.                     // else if(total_path[walkVar] == PathfinderLoc + 1)
  128.                     // {
  129.                         // for(int i2 = 0; i2 < 16; i2 += 1)
  130.                         // {
  131.                             // Pathfinder->X += 1;
  132.                            
  133.                             // Waitframe();
  134.                         // }
  135.                     // }
  136.                    
  137.                     // break;
  138.                 }
  139.             }
  140.            
  141.             break;
  142.         }
  143.  
  144.         RemoveNode(OpenSet, current);//OpenSet.Remove(current)
  145.         AddNode(ClosedSet, current);//ClosedSet.Add(current)
  146.        
  147.         for(int i = 1; i <= 4; i += 1)
  148.         {
  149.             int neighbor;// = current + i;
  150.             if(i == 1)              {neighbor = current - 16;}
  151.             else if(i == 2) {neighbor = current + 16;}
  152.             else if(i == 3) {neighbor = current - 1;}
  153.             else if(i == 4) {neighbor = current + 1;}
  154.            
  155.             if (!ValInRange(0, 175, neighbor))
  156.             {
  157.                 continue;
  158.             }
  159.             if(NumInArray(ClosedSet, neighbor) || Screen->ComboS[neighbor] != 0) // neighbor in ClosedSet
  160.             {
  161.                     continue; // Ignore the neighbor which is already evaluated.
  162.             }
  163.  
  164.             int tentative_g_score = g_score[current] + ManhattanDist(current, neighbor);
  165.             if (tentative_g_score < g_score[neighbor] || !NumInArray(OpenSet, neighbor))      // Discover a new node
  166.             {
  167.                 Came_From[neighbor] = current;
  168.                 g_score[neighbor] = tentative_g_score;
  169.                 f_score[neighbor] = g_score[neighbor] + ManhattanDist(neighbor, Dest);
  170.                 if (!NumInArray(OpenSet, neighbor))
  171.                 {
  172.                     AddNode(OpenSet, neighbor);
  173.                 }
  174.             }
  175.            
  176.             // Game->PlaySound(2);
  177.         }
  178.        
  179.         for(int i = 0; i < 176; i += 1)
  180.         {
  181.             if(OpenSet[i] > -1)
  182.             {
  183.                 Screen->ComboD[OpenSet[i]] = 896;
  184.                 Screen->ComboC[OpenSet[i]] = 5;
  185.             }
  186.            
  187.             if(ClosedSet[i] > -1)
  188.             {
  189.                 Screen->ComboD[ClosedSet[i]] = 898;
  190.                 Screen->ComboC[ClosedSet[i]] = 8;
  191.             }
  192.            
  193.             if (g_score[i] < 9999)
  194.             {
  195.                 Screen->DrawInteger(6, ComboX(i), ComboY(i) + 10, FONT_SP, 0x06, 0x07, 0, 0, g_score[i], 0, OP_OPAQUE);
  196.             }
  197.             if (f_score[i] < 9999)
  198.             {
  199.                 Screen->DrawInteger(6, ComboX(i), ComboY(i), FONT_SP, 0x01, 0x07, 0, 0, f_score[i], 0, OP_OPAQUE);
  200.             }
  201.             Screen->DrawInteger(6, 0, 0, FONT_Z1, 0x01, 0x07, 0, 0, current, 0, OP_OPAQUE);
  202.             Screen->DrawInteger(6, 0, 16, FONT_Z1, 0x01, 0x07, 0, 0, OpenSet[0], 0, OP_OPAQUE);
  203.         }
  204.        
  205.         Waitframe();
  206.     }
  207.  
  208.     //return failure
  209. }
  210.  
  211. void reconstruct_path(int total_path, int Came_From, int current, int PathfinderLoc)
  212. {
  213.     total_path[0] = current;
  214.    
  215.     for (int i = 1; i < 176; i++)
  216.     {
  217.         total_path[i] = Came_From[current];
  218.         current = Came_From[current];
  219.         if (current == PathfinderLoc)
  220.         {
  221.             break;
  222.         }
  223.     }
  224. }
  225.  
  226. int ManhattanDist(int loc1, int loc2)
  227. {
  228.         return (Abs(ComboX(loc2) - ComboX(loc1)) + Abs(ComboY(loc2) - ComboY(loc1)));
  229. }
  230.  
  231. // Returns if an array is "empty". Returns true if all elements of an array equal -1. Overloaded to check a specific indice.
  232. bool ListIsEmpty(float list_arr)
  233. {
  234.         for(int i = 0; i < SizeOfArray(list_arr); i += 1)
  235.         {
  236.                 if(list_arr[i] > -1)
  237.                 {
  238.                         return false;
  239.                 }
  240.         }
  241.        
  242.         return true;
  243. }
  244.  
  245. // Returns if an indice on a list array is "empty".
  246. bool ListIsEmpty(float list_arr, int indice)
  247. {
  248.         if(list_arr[indice] <= -1)
  249.         {
  250.                 return true;
  251.         }
  252.         else
  253.         {
  254.                 return false;
  255.         }
  256. }
  257.  
  258. // returns the size of an array "list"
  259. int ListSize(float list_arr)
  260. {
  261.         int size = 0;
  262.        
  263.         for(int i = 0; i < SizeOfArray(list_arr); i += 1)
  264.         {
  265.                 if(!ListIsEmpty(list_arr, i))
  266.                 {
  267.                         size += 1;
  268.                 }
  269.         }
  270.        
  271.         return size;
  272. }
  273.  
  274. // Adds a 'node' to an array 'list'
  275. int AddNode(int list_arr, int locToAdd)
  276. {
  277.         for(int i = 0; i < SizeOfArray(list_arr); i += 1)
  278.         {
  279.                 // if(ListIsEmpty(list_arr, i))
  280.                 if(list_arr[i] <= -1)
  281.                 {
  282.                         list_arr[i] = locToAdd;
  283.                         return i;
  284.                         break;
  285.                 }
  286.         }
  287. }
  288.  
  289. // Adds a 'node' to an array 'list'
  290. int AddNode(int locToAdd, int val_gCost, int val_hCost, int val_Parent, int list_arr, int list_gCost, int list_hCost, int list_Parent)
  291. {
  292.         for(int i = 0; i < SizeOfArray(list_arr); i += 1)
  293.         {
  294.                 if(list_arr[i] <= -1)
  295.                 {
  296.                         list_arr[i] = locToAdd;
  297.                         list_gCost[i] = val_gCost;
  298.                         list_hCost[i] = val_hCost;
  299.                         list_Parent[i] = val_Parent;
  300.                        
  301.                         return i;
  302.                        
  303.                         break;
  304.                 }
  305.         }
  306. }
  307.  
  308. // Removes a 'node' from an array 'list'
  309. void RemoveNode(int list_arr, int node)
  310. {
  311.     // if(!ListIsEmpty(list_arr, indice))
  312.     for (int i = 0; i < SizeOfArray(list_arr); i++)
  313.     {
  314.         if (list_arr[i] == node)
  315.         {
  316.             list_arr[i] = -1;
  317.         }
  318.     }
  319. }
  320.  
  321. // Returns if a variable is in an array.
  322. bool NumInArray(float arr, float num)
  323. {
  324.         for(int i = 0; i < SizeOfArray(arr); i += 1)
  325.         {
  326.                 if(arr[i] == num)
  327.                 {
  328.                         return true;
  329.                 }
  330.         }
  331.        
  332.         return false;
  333. }
  334.  
  335. // Returns the lowest number in array 'arr'.
  336. // Set checkForValid to true if you want to make sure the returned value is "valid" (ie. above -1).
  337. float LowestVal(float arr, bool checkForValid)
  338. {
  339.         float smallest = arr[0] ;
  340.         for(int i = 1; i < SizeOfArray(arr); i += 1)
  341.         {
  342.                 if(checkForValid)
  343.                 {
  344.                         if(arr[i] > -1 && arr[i] < smallest)
  345.                         {
  346.                                 smallest = arr[i];
  347.                         }
  348.                 }
  349.                 else if(arr[i] < smallest)
  350.                 {
  351.                         smallest = arr[i];
  352.                 }
  353.         }
  354.         return smallest;
  355. }
  356.  
  357. float LowestIndice(float arr, bool checkForValid)
  358. {
  359.         int smallestVal = arr[0];
  360.         int smallestIndice = 0;
  361.         for(int i = 1; i < SizeOfArray(arr); i += 1)
  362.         {
  363.                 if(checkForValid)
  364.                 {
  365.                         if(arr[i] < smallestVal && arr[i] > -1)
  366.                         {
  367.                                 smallestVal = arr[i];
  368.                                 smallestIndice = i;
  369.                         }
  370.                 }
  371.                 else if(arr[i] < smallestVal)
  372.                 {
  373.                         smallestVal = arr[i];
  374.                         smallestIndice = i;
  375.                 }
  376.         }
  377.         return smallestIndice;
  378. }
  379.  
  380. // Returns if a number is in range of range_min (inclusive) and range_max (inclusive).
  381. bool ValInRange(float min, float max, float num)
  382. {
  383.         if(min <= max)
  384.         {
  385.                 if(num >= min && num <= max)
  386.                 {
  387.                         return true;
  388.                 }
  389.         }
  390.         else
  391.         {
  392.                 if(num >= max && num <= min)
  393.                 {
  394.                         return true;
  395.                 }
  396.         }
  397.        
  398. }
  399.  
  400. void Astar5ArrayInit(int OpenSet, int ClosedSet, int Came_From, int g_score, int f_score)
  401. {
  402.     for (int i = 0; i < 176; i++)
  403.     {
  404.         OpenSet[i] = -1;
  405.     }
  406.     for (int i = 0; i < 176; i++)
  407.     {
  408.         ClosedSet[i] = -1;
  409.     }
  410.     for (int i = 0; i < 176; i++)
  411.     {
  412.         Came_From[i] = -1;
  413.     }
  414.     for (int i = 0; i < 176; i++)
  415.     {
  416.         g_score[i] = 9999;
  417.     }
  418.     for (int i = 0; i < 176; i++)
  419.     {
  420.         f_score[i] = 9999;
  421.     }
  422. }
  423.  
  424. int FindNode(int list_arr)
  425. {
  426.     for (int i = 0; i < SizeOfArray(list_arr); i++)
  427.     {
  428.         if (list_arr[i] > 0)
  429.         {
  430.             return list_arr[i];
  431.         }
  432.     }
  433.     return -1;
  434. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×