Have you profiled your code to determine what is the slowest part?
I don't quite understand what your code is doing. Do you call Flow
once for each tile, or do you call it once, and it runs over all tiles? If I were to guess, I'd say that allocating a new list each tile is going to be pretty slow. But the best way to know is to profile.
The thing that originally led me to write http://www.redblobgames.com/grids/hexagons was a top-down hex game that was all about water flow. I wrote that game in 1995, and I recently ported it to run on the web here. The algorithm I started with is simple. For each hex, traversed in random order:
- calculate the water level W + elevation H
- calculate the same for each neighbor
- make up to half the water flow to the neighbor with the lowest W + H
The random order is so that the loop doesn't cause water to flow many hexes to the right but not many hexes to the left, or other such direction artifacts. Even cleaner would be to use a double buffer for this: write all the new values to a separate array, and then copy them back to the first array at the end (or swap the arrays).
Beyond that, there are tons of heuristics I used for erosion and other features of the (unfinished) game. The code is old and awful but if you want to take a look, you can download it here (ZIP file). See water.cpp
. I avoided memory allocations in the water flow loop.