Implementing A* pathfinding: call stack issues and overall code quality

Started by LostTrainDude, Thu 28/06/2018 06:24:09

Previous topic - Next topic

LostTrainDude

I have been struggling for about a week to convert this pseudocode (and its C++ implementation) in AGS.

After quite some time I was able to shrink down the script to just integers and bools, which made everything more easy to manage and edit. I made some progress but I'm not there yet.

I am using a grid of nodes, 8px distant from each other. Each Node has an x and a y that can be used to calculate their node number within a global array of Nodes.
Code: ags
#define NCOLS 8
#define NROWS 8

int GetNodeAtRowCol(int row, int col)
{
   return row*NCOLS+col;
}

int GetNodeAtYX(int y, int x)
{
   return GetNodeAtRowCol((y - 8) / 8 , (x - 8) / 8);
}

I started with a 24x24 grid, but 576 nodes were too much for the search algorithm, who started running those pesky loops running "150001 times" and more. So, for testing purposes, I scaled down, up to 8x8, so 64 nodes. Things went better but as soon as I started moving from a less complex algorithm, such as the Breadth First search, towards the A* I started getting those again.

I tried my best to make the code as simple as possible, splitting much of it into separate functions, also having to write my own versions of push(), pop(), insert(), etc. Still, it returns such "infinite loop" errors: 90% of the time it won't work from the very start, 10% of the time it would crash after a few moments.

Of course, I do not exclude that I may have made some mess.
Can you make sense of it? I tried my best to comment it and I hope it is understandable.

Most of all I'd like to know if it's me just pushing this too far or if there is something wrong with what I have coded.

I have marked with an asterisk (*) the lines that trigger the error, but I suppose it was quite obvious.

Code: ags
// BigBang.ash
struct Node
{
   int x, y;
   int neighbours[8];  
   bool isFree;
   int cost;
}

(cost at the moment is either 1 or 2, depending on whether there is a planet on there or not)

Code: ags
// Pathfinding.asc
int frontier[TOTAL_NODES];
int frontier_priority[TOTAL_NODES];
int came_from[TOTAL_NODES];
int cost_so_far[TOTAL_NODES];

int heuristic(int node_a, int node_b)
{   
   float n1x = IntToFloat(g_Nodes[node_a].x);
   float n1y = IntToFloat(g_Nodes[node_a].y);
   float n2x = IntToFloat(g_Nodes[node_b].x);
   float n2y = IntToFloat(g_Nodes[node_b].y);
   
   return FloatToInt(Maths.Ceil(Maths.Abs(n1x - n2x) + Maths.Abs(n1y - n2y)));
}

// Initialize all of the arrays for the search function
function InitializeArrays()
{
   for (int i = 0; i < TOTAL_NODES; i++)
   {
      frontier[i] = -1;
      came_from[i] = -1;
      cost_so_far[i] = -1;
      frontier_priority[i] = -1;
   }   
}

// Check if there is at least one valid element in the array
bool IsFrontierEmpty()
{
   for (int i = 0; i < TOTAL_NODES; i++)
   {
      if (frontier[i] != -1)
      {
         return false;
      }
   }
   return true;
}

// "Remove" the first valid element in the array and return its value
int Frontier_GetFirstNode()
{
   int i, ret;
   for (i = 0; i < TOTAL_NODES; i++)
   {
      // if something different than -1 is encountered
      if (frontier[i] != -1)
      {
         // break the loop
         break;
      }
   }
   // store the value at the position
   ret = frontier[i];
   
   // "nullify" the element
   frontier[i] = -1;
   frontier_priority[i] = -1;
   
   // return the stored value;
   return ret;
}

// Insert 
function Frontier_Insert(int node, int priority)
{
   int cur;
   
   // From the back of the array, copy each element to the following index, until desired position is reached
   for (cur = TOTAL_NODES-2; cur >= 0; cur--)
   {
      frontier[cur+1] = frontier[cur];
      frontier_priority[cur+1] = frontier_priority[cur];
   }
      
   // Fill the element at the desired position with the desired node's values
   frontier[0] = node;
   frontier_priority[0] = priority;
} 

// Insert an element at the front of the array
function CameFrom_Insert(int node)
{
   int cur;
   
   // Copy each element to the slot next to them, until desired position is reached
   for (cur = TOTAL_NODES-2; cur >= 0; cur--)
   {
      came_from[cur+1] = came_from[cur];
   }
      
   // Fill the element at the desired position with the desired node's values
   came_from[0] = node;   
}

// Return the first valid element from the back of the array
int CostSoFar_GetLastNode()
{
   for (int j = TOTAL_NODES-1; j > 0; j--)
   {
      if (cost_so_far[j] != -1)
      {
         return cost_so_far[j];
      }
   }
}

// Check if the given node is already included in the array
bool CostSoFar_CheckNode(int node)
{
   for (int i = 0; i < TOTAL_NODES; i++)
   {
      if (cost_so_far[i] == node)
      {
         return true;
      }
   }
   return false;
}

// Foresee the cost of the next step in the search algorithm
int CostSoFar_NextStepCost(int node)
{
   for (int i = 0; i < TOTAL_NODES; i++)
   {
      if (g_Nodes[i] == g_Nodes[node])
      {
         return g_Nodes[i].cost;
      }
   }
}

// Insert an element after the last valid one in the array
function CostSoFar_InsertToBack(int cost)
{
   for (int i = TOTAL_NODES-1; i > 0; i--)
   {
      if (cost_so_far[i] != -1)
      {
         cost_so_far[i+1] = cost;
      }
   }
}

String a_star_search(int nStart, int nGoal)
{
   // Initialize all arrays elements to -1
   InitializeArrays();
   
   // INIT start_location
   int start_location = nStart;
   int start_location_nbs[8];
   for (int i = 0; i < 8; i++) start_location_nbs[i] = g_Nodes[nStart].neighbours[i];
   
   // Add start_location to frontier
   frontier[0] = nStart;
   frontier_priority[0] = 0;
   
   // Add start_location to frontier
   came_from[0] = nStart;
   
   // Add current cost of 0;
   cost_so_far[0] = 0;
   
   // As long as there is something different than -1 in frontier[]
   while (!IsFrontierEmpty())
   {
      // Get the first element in frontier[]
      int f_node = Frontier_GetFirstNode();
      
      // INIT current_location
      int current_location = f_node;
      int current_location_nbs[8]; // neighbours
      for (int i = 0; i < 8; i++)
      {
         current_location_nbs[i] = g_Nodes[f_node].neighbours[i];
      }
      
      // Stop searching once arrived to the destination
      if (f_node == nGoal)
      {
         break;
      }
     
      
      // Scan the neighbours to see if they have been visited
      for (int i = 0; i < 8; i++)
      {
         // Store the node
         int neighbour_node = current_location_nbs[i];
         
         // If the node is within the bounds
         if (neighbour_node != -1)
         {
            // Calculate: last cost + the cost from the last location to the current one
            int new_cost = CostSoFar_GetLastNode() + (CostSoFar_GetLastNode()+g_Nodes[neighbour_node].cost);
            
            // Test the next iteration in advance to check whether it's valid or not
            if (i+1 < 8 && current_location_nbs[i+1] != -1)
            {
               // If it's valid calculate the cost of the next location
               int next_cost = CostSoFar_NextStepCost(current_location_nbs[i+1]);
               
               // If we didn't visit this node yet OR if it is less expensive
               if (!CostSoFar_CheckNode(current_location_nbs[i+1]) || new_cost < next_cost)
               {
                  // Add the cost to the cost_so_far array
                  CostSoFar_InsertToBack(new_cost);
                  
                  // Establish the priority
                  int priority = new_cost + heuristic(nGoal, current_location_nbs[i+1]);
                  
                  // Insert the next neighbour at the top of the frontier array;
                  Frontier_Insert(current_location_nbs[i+1], new_cost); // *
                  
                  // Insert the next neighbour at the top of the came_from array;
                  CameFrom_Insert(current_location_nbs[i+1]); // *
               }
            }
         }
      }
   }
   
   
   // Store the path into a string, separating values with comma
   String s = "";
   for (int i = TOTAL_NODES-1; i > 0; i--)
   {
      if (came_from[i] != -1)
      {
         String ss = String.Format("%d,", came_from[i]);
         s = s.Append(ss);
      }
   }
   return s;
}

export a_star_search;


It is also worth noticing that the frontier_priority array, theoretically to be used "side by side" with the frontier one, is still not used in any kind of sorting (which at this stage I'm not really sure how to tackle).

Thanks a lot in advance to anyone who spends some time on this. Also thanks again to Crimson Wizard, Gurok* and vga256 who have helped a lot already.
I wonder if this can be turned into a module, once (and if) it will be figured out. :)

*Gurok: if you're reading this, the last code you shared with me helped me a great bunch, although I was not able to figure out the circular queue, yet :(
"We do not stop playing because we grow old, we grow old because we stop playing."

Snarky

Quote from: LostTrainDude on Thu 28/06/2018 06:24:09I was not able to figure out the circular queue, yet :(

I always imagine a circular queue like the game Snake, played on a screen that wraps around (and always moving in one direction/dimension). The snake is the queue, which can grow longer and shorter. Crucially, the snake is moving around, so that the head and tail are in different positions, but as long as it doesn't grow longer than the screen, it's not a problem, you just have to keep track of it.

It's not a perfect analogy: the queue doesn't move by itself, only by growing or shrinking, and this means it moves in the opposite direction of Snake, shrinking from the head (when someone leaves the queue at the front) and growing backwards (when someone joins it at the end) â€" this is assuming it's being used as a queue rather than a stack, since I don't think there's any reason to treat a stack as a circular structure. Still, it helps me visualize it.

Basically, you just need to keep track of the indexes for the head and the tail (it also helps to keep the current queue length as a separate variable): when someone joins the queue, increment the tail index (and the length) and write to that slot, and when someone leaves it, increment the head index (and decrement the length) - you don't have to wipe the slot, it will be overwritten the next time the queue gets to that point. Make sure they wrap around, using modulo with the size of your array. Use the queue length to determine whether the queue is empty or full, and deal with those cases accordingly.

Snarky

Having had a bit more of look at it, this stands out to me:

Quote from: LostTrainDude on Thu 28/06/2018 06:24:09
It is also worth noticing that the frontier_priority array, theoretically to be used "side by side" with the frontier one, is still not used in any kind of sorting (which at this stage I'm not really sure how to tackle).

Without a sorted priority queue, you're not actually using any of these algorithms: it's all just some version of breadth-first, and so it's no wonder that the loop check goes out of bounds. You must have this in place before you can proceed. The easiest/most efficient way to implement a priority queue is usually as a binary (min) heap.

In general, this sort of thing is better to work out as a prototype (a separate AGS project) using small test cases at first: that way you can follow it by eye/manually to see where it breaks. Once you do scale it up, there is a noloopcheck keyword that allows a loop to run as long as it needs: obviously you don't want that if you do in fact have an infinite loop, since the game will then freeze with no emergency stop.

Snarky

Because it's heaps of fun, I went ahead and coded up a priority queue (binary min-heap). All untested, but it at least demonstrates the basic idea:

Code: ags
// PriorityQueue.ash
#define QUEUE_SIZE_MAX 1000

managed struct PriorityNode
{
  int node;
  int priority;
};

// LOWEST priority is first
struct PriorityQueue
{
  protected PriorityNode* queue[QUEUE_SIZE_MAX+1];
  protected int size;

  import readonly attribute int Size;
  import bool Enqueue(PriorityNode* node);
  import PriorityNode* Dequeue();
};


Code: ags
// PriorityQueue.asc

int get_Size(this* PriorityQueue)
{
  return this.size;
}

int parent(int i)
{
  return i/2;
}

int leftChild(int)
{
  return 2*i;
}

int rightChild(int)
{
  return 2*i+1;
}

// cf. https://www.cs.cmu.edu/~adamchik/15-121/lectures/Binary%20Heaps/heaps.html
bool PriorityQueue::Enqueue(PriorityNode* node)
{
  if(this.size==QUEUE_SIZE_MAX)
    return false;
  this.size++;
  int i=this.size;
  for(; i>1 && node.priority < this.queue[parent(i)].priority; i=parent(i))
  {
    this.queue[i] = this.queue[parent(i)];
  }
  this.queue[i] = node;

  return true;
}

// Restores the min-heap property on a subtree of the heap
// cf. https://en.wikipedia.org/wiki/Binary_heap#Extract
MinHeapify(this* PriorityQueue, int index)
{
  int l = leftChild(index);
  int r = rightChild(index);
  int min = index;
  
  if(l <= this.size && this.queue[l].priority < this.queue[min].priority)
    min = l;
  if(r <= this.size && this.queue[r].priority < this.queue[min].priority)
    min = r;

  if(min != index)
  {
    PriorityNode* n = this.queue[index];
    this.queue[index] = this.queue[min];
    this.queue[min] = n;
    this.MinHeapify(min);
  }
}

PriorityNode* PriorityQueue::Dequeue()
{
  if(this.size==0)
    return null;
  PriorityNode* root = this.queue[1];    // We'll return the root
  this.queue[1] = this.queue[this.size]; // ... and overwrite it with the last value
  this.size--;
  this.MinHeapify(1); // ... then restore the heap property
  return root;
}


Edit: Fixed some errors

LostTrainDude

Thanks a lot for this, Snarky :)

Although I think I will spend some time figuring out how to use it for my own purposes, I think I understand the concept behind it.
Those links you included in the comments are very useful!
"We do not stop playing because we grow old, we grow old because we stop playing."

SMF spam blocked by CleanTalk