Liqwiid Wars/Algorithm

Algorithm

4-way Queue based Flood Fill Algorithm

The Recursive Flood Fill worked OK on small maps (really small 10x10px), but on anything reaching the size I wanted (300x300px) stack dumps were aplenty. In order to remove the stack as such I implemented a queue of "gradient points". The code is just for player 1 at the moment, but adding extra players is just a case of using the "team" variable, and as this was done at 2 in the morning I was more looking at going to bed than functional and elegant code. Saying that, for player 1 it works a treat. Although there is quite a chunk of code (as well as the overhead of a function call) I dont think there is a huge difference in speed between this and the first "algorithm" I tried.

void gradient_fill(int team, int x, int y, int value)
{
  std::queue<gradient> gradient_queue;
  gradient temp_grad;
  temp_grad.x = x;
  temp_grad.y = y;
  temp_grad.value = value;
  gradient_queue.push(temp_grad);	
  do
  {		
     //look at the front element then throw first element away...
     temp_grad = gradient_queue.front();
     gradient_queue.pop();      
     x = temp_grad.x;
     y = temp_grad.y;
     temp_grad.value++;
     if(x<map_x-2)
     {
       if(grad_grid[0][temp_grad.x+1][temp_grad.y] > temp_grad.value || grad_grid[0][temp_grad.x+1][temp_grad.y] ==0)
       {
         temp_grad.x = x+1;
         grad_grid[0][temp_grad.x][temp_grad.y] = temp_grad.value;
         gradient_queue.push(temp_grad);
         temp_grad.x = x;
       }
     }
     if(x>0)
     {
       if(grad_grid[0][temp_grad.x-1][temp_grad.y] > temp_grad.value || grad_grid[0][temp_grad.x-1][temp_grad.y] ==0)
       {
         temp_grad.x = x-1;
         grad_grid[0][temp_grad.x][temp_grad.y] = temp_grad.value;
         gradient_queue.push(temp_grad);
         temp_grad.x = x;
       }
     }
     if(y<map_y-2)
     {
       if(grad_grid[0][temp_grad.x][temp_grad.y+1] > temp_grad.value || grad_grid[0][temp_grad.x][temp_grad.y+1] ==0)
       {
         temp_grad.y = y+1;
         grad_grid[0][temp_grad.x][temp_grad.y] = temp_grad.value;
         gradient_queue.push(temp_grad);
         temp_grad.y = y;
       }
     }
     if(y>0)
     {
       if(grad_grid[0][temp_grad.x][temp_grad.y-1] > temp_grad.value || grad_grid[0][temp_grad.x][temp_grad.y-1] ==0)
       {
         temp_grad.y = y-1;
         grad_grid[0][temp_grad.x][temp_grad.y] = temp_grad.value;
         gradient_queue.push(temp_grad);
         temp_grad.y = y;
       }
     }
   }while(!gradient_queue.empty());
}

Basically it...

• Puts the wiimote IR position on the queue
• Is the queue empty
  • Get the first member of the queue
  • Increment the value we want to put in the cell (this is the key change - as we want a path finding algorithm)
  • Check the four directions seeing if a gradient potential calculation is relevant
    1. Is current grad value bigger that the one I'm trying to give it
    2. OR is there not a gradient potential there at all
  • Add the directions to the queue
  • Check if the queue is empty.... rinse and repeat

A side note, before I call this algorithm I had to clear the grad_grid array, as otherwise the gradient is not updated properly.

Recursive Flood Fill Algorithm

I have tried changing the algorithm as the one previously used doesnt take walls into account. I am now trying different algorithms including a modified flood(/seed/bucket) fill.

void bucket_fill(int x, int y, int value)
{            
  if (grid[x, y] == 0 || (grid[x,y]-value) > 0)
  {
    grid[x, y] = value;
    if (x < map_size-1)
      bucket_fill(x + 1, y, value+1);
    if(x>0)
      bucket_fill(x - 1, y, value+1);
    if (y < map_size-1)
      bucket_fill(x, y+1, value+1);
    if(y>0)
      bucket_fill(x, y-1, value+1);
   }
           
 }

This is gives the right result when used on a small map, but larger maps give stack overflows. I will try and use a queue instead, as this should be smaller.

Basic Algorithm

Anyone looking at this thinking "that is rubbish" this was just an algorithm placeholder for more advanced algorithms. It populates the algorithm grid and allowed me to concentrate on fighter movement etc without worrying about the actual algorithm. Plus it was quite a quick foolproof method. For those wondering the algorithm I am using to get the gradient can be defined as such...

new_grid[x, y] = abs(position[0] - x) + abs(position[1] - y);

4 3 2 3 4 5

3 2 1 2 w 4

2 1 X 1 w 3

3 2 1 2 w 4

4 3 2 3 4 5

However if a wall exists, any fighters on the right of the wall cant "escape" due to them ALWAYS going to an area of equal or lower potential.

Using...

new_grid[x, y] = max(abs(position[0] - x), abs(position[1] - y));

would give

2 2 2 2 2 3

2 1 1 1 w 3

2 1 X 1 w 3

2 1 1 1 w 3

2 2 2 2 2 3

With the wall in the same position the problem no longer arises. However "max" gives additional overheads, and the second option will give rise to this situation

2 2 2 w 2 3

2 1 1 1 w 3

2 1 X 1 2 w

2 1 1 1 2 3

2 2 2 2 2 3

where any army trapped in the "2" space above the wall is trapped there, until the cursor moves.

Either I am worrying about it too much, as the cursor wont stay in the same position for an amount of time (especially given the fact the IR will shake) added to the fact this will not affect a huge amount of fighters

-or-

I need to program some disobedience into the fighters such that very occasionally they will disregard orders and go in the wrong direction