79
edits
Changes
Algorithm update: queue based flood fill - for shortest path single destination
Line 1:
Line 1:
−
+
+
+
+
+
+[CODE]
−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);
− }+
+
− }+[/CODE]+
=== Flood Fill Algorithm ==
+= Algorithm =
−I have tried changing hte algorithm as the one previously used doesnt take walls into account.
+== 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
+**#Is current grad value bigger that the one I'm trying to give it
+**#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.
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.
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.
−==Algorithm==
+== 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...
For those wondering the algorithm I am using to get the gradient can be defined as such...