A hill on a plain at sea-level is divided in tiles. The diagram below shows the top-view of the hill, the height of each tile is given. The hill is flooded with rain. Water flows from high tiles to low tiles (only horizontally and vertically), off the hill. Which puddles of water remain? Reload the page to get a new random hill (all cells get random height 1..9), which will be analyzed by the algorithm.
The algorithm computes for each tile the final water level (after all excess water is drained) and to which neighbor the water flows (its "sink"). Note that a sink is a neighbor with the lowest height (if there are more, one is chosen).
The algorithm distinguishes three states for each tile: unknown (water level and sink neighbor is not yet known), to do (water level and sink neighbor are known, but its neighbors are not yet inspected) and done (water level and sink neighbor are known, and its neighbors are also known, that is have state to do or done). Note that in the user interface, the tiles with state done are either colored blue or green (depending on the water height). The diagram below shows the state naming.
The tiles are drawn as top-view squares with their height in big font in the center. It is assumed that the hill (all tiles) are on a plain; the plain is at sea level, so at height 0). Unknown tiles are colored red. Done tiles are colored blue or green: blue when the final water level is above the tile height and green when the final water level equals the tile height. A tile with state to do is yellow. Note that known tiles will also indicate the water level (small font in upper right corner) and the sink neighbor (blue triangle/arrow).
The diagrams below shows the steps taken by the algorithm. Here the hill tiles are drawn from the side. Initially, all tiles are unknown.
The first step of the algorithm is to put all tiles on the border of the hill in the to do state. The water falls off the tiles onto the plain. Remaining water height is the same as the tile height. The first step is presented schematically below: the left-hand side of the arrow (»») the before situation and the right-hand side of the arrow the after situation. Note also the state change from unknown (red) to to do (yellow).
The next diagram shows the iteration steps. It shows how a to do tile (yellow, with know water height) induces a water height on an unknown tile. Again, the left-hand side is the before situation and the right-hand side the after situation.
For example, the top row shows a to do tile with a height of 4, that (due to not drawn tiles on its left) no water is retained, so the water level of that tile is also 4. The neighbor on the right, which has a height of 2, inherits that water level of 4. The second example, a new water level is established, because the unknown tile is higher than the to do one.
The next three are similar, but analyze the cases where the to do tile actually retains water. The five cases look complex, but can be captured by a simple rule: the water level of the unknown tile equals the maximum of the water level of the to do tile and the height of the unknown tile in all five cases.
One final aspect is important: of all to do tiles (the work list), we always take one with the lowest water level of all to do tiles, for the next iteration step.
Observe that once the algorithm is finished, puddles of connected tiles indeed have the same water height.
(end)