Most Efficient way to implement a flood algorithm in parallel job?

So I have a grid represented in a NativeArray<byte>, starting at point (x,y) I want this job to flood all adjacent cells of a matching value, essentially a flood tool like you'd see in a paint program.
For a while I've just been doing this on a single thread, but it's always been nagging at the back of my brain, wondering if there's a way to queue more "check locations" as each job iteration completes.

I know I could add new flooded locations to a nativeQueue, then sync back on the main thread with a .complete(), then push this queue to a native array, and IJobparallelFor over these new locations, repeat until there's no new items in the queue, but then the cost of halting, waiting, resuming on the main thread over and over is going to add up.

Is there a better way to do this? In which the job continues in parallel until each run stops producing new check locations? I wasn't sure if IJobForProduce was for a situation like this, but can't find any code examples for it.

 

Is there a reason you want this to be parallel?

 

SPEED, and theoretical curiosity, but mostly SPEED.

these cells are attached to physics objects the player is walking around on (breaking apart on flooding), so hitches/delays are going to be noticeable. Also while I do a fill I have to pause other systems that modify these grids. I want this job to complete as fast as possibly, and in theory it's a task that should be able to be parallelized, but I'm just not sure what the best way to implement it using jobs would be.

 

So flood fill is one of those algorithms that is much more efficient single-threaded than multi-threaded. So definitely profile and see if you can get some other CPU work to run in parallel with a single-threaded flood-fill.

But if you are really having latency problems, you can try this. It is not amazing by any means, but gives you a starting point:
1) Extend from the start point along both directions in the column. (Up to two threads)
2) Flood fill the rows from the cells in the column in step 1. (Parallel)
3) Search all cells filled in 1 and 2 that have an unfilled neighbor and add those neighbors to a NativeHashMap. (Parallel)
4) Single-thread flood-fill the rest or use some quick guess to pick a new start point and repeat steps 1-3 for a fixed number of iterations before resorting to single-threaded flood-fill.