Change FloodFill-Algorithm to get Voronoi Territory for two data points?

Question

I got a grid with two points. I want to calculate the amount squares each point can reach before the other. Currently I implement a FloodFill-Algoritm, which can calculate the amount of squares one point can reach.

How can I change that algorithm to do the "flooding" for both points simaltaneuosly or at least one after another?

Subternatural

Greetings, Google AI contestant :) – Brouhaha

Thanks, did you already implement such thing or is your strategy different? – Subternatural

I did, just using kind of a simultaneous BFS from two points - similar to IVlad's answer. – Brouhaha

Answer 1

What do you mean by "each point can reach before the other"?

It looks to me like you need a BF search. Use a FIFO queue like so:

Let p1 and p2 be the positions of the two points.

let f be the first element in the queue and l the last. Initially f = 0, l = 1. Let Q be the queue.

Q[f] = p1
Q[l] = p2
while ( f <= l )
{
   poz = Q[f];
   ++f;

   for each neighbour poz' of poz
      if poz' hasn't been marked yet
      {
         mark poz'
         add poz' to Q: Q[++l] = poz
      }
}

Q will need to be the size of your grid (rows x cols). You can use two matrices: one with the positions p1 can reach and the other with the positions p2 can reach, or you can use one matrix and mark the squares p1 reaches with positive numbers and the squares p2 reaches with negative numbers. If you are interested where they meet, you just need to check if you are about to mark a positive value from a negative value (poz negative and poz' positive) or the other way around. This will basically do your flooding in turns: flood one square from p1, then from p2, then from p1, then from p2 and so on.

Cartierbresson