Creating a 2D circle with a flood approach

Question

I'm trying to generate topographical contour lines looking something like this:

My eventual goal is to generate contour lines based on a few user-defined points (ex: this hill is at 100m elevation, and has a slope of X).

For now, my algorithm for generating a heightmap is a kind of radial flood fill, where each point sets its current height, then enqueues its 8 neighbours (including diagonals) to have their height set to the current height - the value of the slope. heightmap is a 2D array of doubles representing the height at each x/y point on the map. sqrt_2 is the value of square root of 2, which we multiply the slope value of diagonal neighbours to represent their true distance from the current point. Each point also propagates outwards its slope (the rate at which the height moves towards the default height. EnqueueIfValidPoint simply adds a point to the points_to_assign queue. The idea is to start at certain points that we KNOW the height of, and slowly slope/gradient towards a default height (0 in this case). points_to_assign is a regular FIFO Queue.

This code is written in C# in Unity, but the language does not change the logic behind it.

// Continue the flood fill until we're out of points to assign
while (points_to_assign.Count > 0)
{

    PointToAssign p = points_to_assign.Dequeue();

    // Check if we have already assigned a height to this point
    if (heightmap[p.x_pos, p.y_pos] == unassigned_height)
    {
        assigned_points++;
        // Assign a height to this point
        heightmap[p.x_pos, p.y_pos] = p.height;


        // Height to assign neighbours to, moved towards default floor value
        double slope = p.slope;//GetRandomSlope(p.x_pos, p.y_pos, p.slope);

        double orthogonal_heights = 0;
        if (p.height >= 0)
            orthogonal_heights = Math.Max(0, p.height - (slope));
        else
            orthogonal_heights = Math.Min(0, p.height + (slope));
        // Enqueue neighbours of this point to assign a new height to
        // Below
        EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos - 1, p.y_pos, orthogonal_heights, p.slope);
        // Above
        EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos + 1, p.y_pos, orthogonal_heights, p.slope);
        // Left
        EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos, p.y_pos - 1, orthogonal_heights, p.slope);
        // Right
        EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos, p.y_pos + 1, orthogonal_heights, p.slope);

        double diagonal_heights = 0;
        if (p.height >= 0)
            diagonal_heights = Math.Max(0, p.height - (slope * sqrt_2));
        else
            diagonal_heights = Math.Min(0, p.height + (slope * sqrt_2));
        // Below and left
        EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos - 1, p.y_pos - 1, diagonal_heights, p.slope);
        // Below and right
        EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos + 1, p.y_pos - 1, diagonal_heights, p.slope);
        // Above and left
        EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos - 1, p.y_pos + 1, diagonal_heights, p.slope);
        // Above and right
        EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos + 1, p.y_pos + 1, diagonal_heights, p.slope);
    }
}

Height values are then passed to a colour function that assigns a colour, ex: if the height is between 0 and 1, assign it white, if it's between 1 and 2, assign it light green, etc.

Unfortunately this code doesn't quite produce circle, and instead produces a octagon. I imagine the problem has to do with encoding the diagonal neighbour values

Does anyone have any idea how to produce a circle, instead of an octagon using my flood fill strategy?

Answer 1

The problem is that you are getting wrong distances when you mix your two step types (diagonal and orthogonal). E.g., an orthogonal step + a diagonal step result in an actual distance of sqrt(5) ~ 2.24. But your algorithm gives you 1 + sqrt(2) ~ 2.41. That's why the circle is cut off.

What you need to do is calculate the actual distance from the seed point. Simply store the seed point with the items in the queue (or if there is only one, then use this one) and calculate the height from the distance. Something along:

heightmap[p.x_pos, p.y_pos] = distance(p.seedPoint, p) * p.slope + p.seedPoint.height;

You could also store the seed point and its slope externally and just reference it in the queue to save some memory.

It is also possible to incrementally calculate the Euclidean distance by accumulating the x-difference and the y-difference and then just calculate sqrt(x-difference^2 + y-difference^2). But this is probably not worth the effort.