Flood fill algorithm

Comments and questions to John Rowe.

We are looking to identify "islands" of groups of people surrounded by empty seats.

• NB a "neighbour" is somebody seating in a seat immediately next to you, ie behind, in front or beside you but excluding diagonally, with no empty seats in between. (Most definitions of a neighbour would include diagonals but this makes the islands smaller and so the process is a bit quicker.)

Simple algorithm: with people!

Counting version

When a neighbour ("the original neighbour" ) gives you a letter:

• If you already have a letter immediately reply "zero" and do nothing else.

• Otherwise:
  1. You now have a letter.
  2. Working clockwise from the original neighbour, tell each neighbour the letter, waiting for them to reply before going onto the next one, keeping track of the running total of the replies.
     • Do not try to be clever by saying "I don't need to tell that person because somebody else has already done so": we are simulating a computer blindly following an algorithm without any thought. (And we will want to see what happens when the algorithm goes wrong!)
  3. When you have told each neighbour, tell the original neighbour the total of replies you received plus one.
     • Example: if you had two neighbours and one replied "two" and the other replied "one" you would reply with the single word "four".

Parallel, non-counting algorithm

This is the same as the algorithm above but there is no numerical reply:

When a neighbour ("the original neighbour" ) gives you a letter:

• If you already have a letter do nothing.

• Otherwise:
  • You now have a letter.
  • Working clockwise from the original neighbour, tell each neighbour the letter, without waiting for them to reply before going onto the next one (because they won't reply!).

Algorithm with depth debugging

When a neighbour ("the original neighbour" ) gives you a letter and a number:

• If you already have a letter, or you have no other neighbours, do nothing.

• Otherwise:
  • You now have a letter.
  • Working clockwise from the original neighbour, tell each neighbour the letter plus the number one greater than the one you were given. (E.g. if you were told "B3" you would tell each neighbour "B4". Note that you tell each neighbour the same thing.)

Completely broken algorithm

Use the parallel algorithm but tell your neighbours their new letter and number even if you already have one. (NB this would break the non-parallel algorithm too but somewhat less noisily!)

Preventing recursive loops

The key here is that if an algorithm has to do something to a thing to prevent it being processed twice (and hence three times and four times...) that must be done before the recursive function call, not after it or, as in this case, not at all.

Another completely broken algorithm

When a neighbour ("the original neighbour" ) gives you a letter and a number:

• If you already have a letter, or you have no other neighbours, do nothing.
• You now have a letter.
• If you do not nowhave a letter (irrespective of whether or not you had one before), then working clockwise from the original neighbour, tell each neighbour the letter you were given.