Faster, Stronger, Wetter
I spent today looking at the performance issue with the erosion algorithm. This constitutes a break of sorts for me as I do love a bit of optimising.
The existing algorithm was very naive, so there was plenty of scope for improvement. The calculation of the flow of water on all cells of the map is an operation which takes a couple of seconds for a 10,000 cell map and the existing erode algorithm was doing this inside a loop which was finding and lowering only the highest blocked cells on each iteration. As it could take thousands of iterations to remove all blocks, the erode operation could take a seriously long time — far too long to be practical for the 1,000,000 cell maps I want as a starting goal.
The solution I’ve implemented is to replace the complete recalculation of the flows as follows:
First, I generate a list of all cells that have potentially had their flow characteristics changed by a block being removed. This list includes the blocked cell, the cell lowered by the unblocking, and all the cells neighbouring the lowered cell (as they now flow more into the lowered cell).
I take each cell in this list and recurse down the cells it flows into (and those they flow into etc.) placing them onto a list of visited cells until I hit sea-level or a cell that has already been visited. Then, as the recursion unwinds, I subtract the existing outgoing flows from the neighbouring cells. This effectively wipes the cumulative flow from the cells that have been changed by the unblocking process.
Finally, I recalculate all the flow proportions (i.e. the proportion of water that flows across each cell edge) for the cells surrounding the unblocking, and then the flows are recalculated for the affected cell list only, again recursing down adding the new flows back into the overall flow map.
The result is that the erode now “only” takes around 10-20 seconds for a 10,000 cell map on my 1.6GHz Pentium M laptop, so a 1,000,000 cell map is doable in about 20 minutes. Definitely something I need to revisit, and perhaps a reason to move to C++ at some point, but it’s a speed that is at least bordering on practical as long as I’m in no rush.
