Elevation propagation is incorrect

[vjackson725]

Hi,

I have recently been attempting to implement this map generator algorithm, using the blog post and this code as reference.

I noticed that the propagation code for elevation updates does not match what is described in the blog post. The part that differs from the actual implementation is:

As with any flood fill, since any particular section may be processed multiple times because of its neighboring sections, there is a race condition where the last one to be processed “wins” by having its elevation override everything that came before. My simple solution to this was to set it to only add a neighboring section to the queue if its newly desired elevation is greater than its existing elevation.

I believe this 'race condition' does not occur in the code as written.

The particular piece of the code is VoronoiDiagram, Line 480. Here, the neighboring cells are added if they are not already queued

bool alreadyQueued = false;
queuedSites.TryGetValue(neighborSite, out alreadyQueued);
if (!alreadyQueued) {

    // calculate a new neighborHeight

    if (newElevation > elevationCutoff) {
        updateSites.Enqueue(neighborSite);
        elevations.Enqueue(neighborHeight);
        queuedSites.Add(neighborSite, true);
    }
}

but the insertion code adds the neighbour to the queuedSites. This results in every cell only being processed once, which ends up creating 'swirls' of decreasing elevation, which can loop back around until very low elevation cells sit next to very high elevation cells.

Here's an example from my implementation I believe the observation I've made from the output of my code is consistent with the behaviour of your code, as I followed it fairly closely (bar minor changes due to differences in the language). Furthermore, looking at the 'basic' no-density result from your blogpost, I believe these features can be attributed to this problem.

To correct this problem, I believe the solution is to compute the elevation in layers. This gets rid of the problem of infinite updates, as it prevents cells decided after the current cell from affecting the elevation of the current cell.