How to generate water pools on a 2D tile grid?

Question

I'm coding a algorithm that generate a map, fixed size 2D matrix of tiles (32x32, 64x64, ...), for a game. The game map contains 2 elements, ground and water tiles. I'm trying to flood some water pools on the map, but I don't come to any ideal conclusion.

I can do it with this steps:

1. Fill the map with Ground
2. Get a random position (x,y)
3. Set (x,y) as Water
4. Walk on, in spiral sequence, from the (x,y) point to a limit of N random steps, setting randomly tiles as Water
5. Jump to step 2, making K more random water pools

This is a good approach? I think not! That algorithm will make pools with ground on the inside, with irregular borders and square shape. But I desire random shaped lakes.

Anyone can give me a idea of a better solution?

Answer 1

I would give it a try like that:

1. Generate a heightfield for your map (e.g. with perlin noise)
2. Determine a height which represents sea level
3. Fill all tiles below sea level with your water pool tile

Answer 2

I'm not sure why you would be setting the tiles randomly to water in your spiral sequence, since that would (as you point out) leave ground on the inside of the pools. If you changed all of the tiles you spiral on into water, then you would have a whole pool, but it would always turn out to be square-shaped.

Instead of a spiral from your selected point, you could do a Random Walk.

1. From the current tile, pick one of the four directions to move (up, down, left, right)
2. Move to that tile and mark it as a water tile.
3. Repeat until you've taken enough steps.

You could also limit the tiles you can walk to by only stepping towards ground tiles. In that case, you also want to have an exit from that loop for when you no longer have any valid directions to pick.

The downside to this method would be that (as seen in pictures on the link above) the walk could be very oddly shaped.

To smooth over that odd shape, you could then run something similar to the Rules in Conway's Game of Life. Replace the words "live neighbor" with "water", and adjust how many neighbors are needed to create water, and that should smooth out the larger irregularities made by a Random Walk.

Edited to add: I added this answer as an alternative to going through the more natural looking but more complex to code answer of Perlin Noise. That does produce much more interesting and natural-looking landscapes, I thought to suggest something similar in scope to what the original poster was doing already and that would give something a little different/better than their original algorithm

Answer 3

While I would recommend the heightmap answers, they may be more trouble than they're worth if you really don't want islands. In such cases in the past I have used a 'random floodfill'. The basic algorithm is:

1. Start with a point and a desired area.
2. Change the current point to water.
3. Add all of the current point's neighbors to a list
4. Sort the list by each entry's number of water neighbors.
5. Grab a (weighted) random item in the list as 'the current point'.
6. Return to step 2, unless the desired area has been covered.

This is easy to grasp and implement, except for step 5. How that is implemented changes the output considerably. One option is to use a geometric or exponential distribution, weighing the odds towards points with lots of (or fewer) water neighbors. Another option is to automatically fill in any points with 3 or 4 water neighbors, eliminating islands but flattening the coastline a bit.

//set up the pile of points
std::vector<Point> pile;
int covered_area = 0;

//push on the starting point
pile.push_back(points.get(start_x, start_y));

//keep adding water until we hit our desired area (or the whole map is filled)
while (pile.size() > 0 && covered_area < desired_area)
{
    //if there are any points with three or four neighbors, we should prioritize those by skipping this step
    if (pile.back().water_neighbors < 3)
    { 
        //pick a point in the pile based on some distribution
        //int position = pile.size() - 1 - std::binomial_distribution<int>(pile.size() - 1, 0.5)(rng);
        std::uniform_int_distribution<> distribution(0, pile.size() - 1);
        int position = distribution(rng);

        //swap that point with the back
        std::iter_swap(pile.begin() + position, pile.rbegin());
    }

    //now pull off the top of the pile
    Point p = pile.back();
    pile.pop_back();

    //set it to water, update the area variable
    points.set(p.x, p.y, 1);
    ++covered_area;

    //now go through the list and remove any points that neighbor this cell (we'll re-add them below with updated neighbor counts)
    for (int i = 0; i < (int)pile.size(); ++i)
    {
        //if the manhattan distance bewteen the two points is 1...
        if (std::abs(pile[i].x - p.x) + std::abs(pile[i].y - p.y) == 1)
        {
            //remove the element
            pile[i] = pile.back();//the most efficient way to do this in a vector (where order doesn't matter) is by swapping with the back and then popping
            pile.pop_back();
            --i;
        }
    }

    //now add in this cell's land neighbors
    Point pw = points.get(p.x - 1, p.y);
    Point pn = points.get(p.x, p.y - 1);
    Point pe = points.get(p.x + 1, p.y);
    Point ps = points.get(p.x, p.y + 1);

    if (pw.valid && !pw.water)
        pile.push_back(pw);
    if (pn.valid && !pn.water)
        pile.push_back(pn);
    if (pe.valid && !pe.water)
        pile.push_back(pe);
    if (ps.valid && !ps.water)
        pile.push_back(ps);

    //then sort the pile by water-neighbor count (so the highest are at the end)
    //std::shuffle(pile.begin(), pile.end(), rng); //if using a non-uniform distribution, shuffle first to reduce blockiness
    std::sort(pile.begin(), pile.end());
}

This produces output similar to this:

Here's a link to a full implementation of it: Gist. Please note that this was written for clarity, not efficiency, and could be optimized considerably.

Answer 4

Another approach that ought to work is based on turning a 1d 'noise' function (Brownian motion or something like) into a closed path. Imagine that you wanted a perfectly circular pool; then a simple way of imagining that would be to express it in polar coordinates (r,θ) : r=C for some constant C. If you wanted to put a little wobble into the boundary, you could introduce a bit of a sine wave to it: something like r=C0+C1*sin(θ), tracked for 0 <= θ <= 2*π, where C1 is much less than C0 (you don't want to have too much wobble, after all!). But that's only a bit of low-frequency noise, and you want a little more wobble — and you want your wobbles to be out of phase with each other — so add more terms representing higher frequencies:

for (int idx=1; idx < NUM_COEFFICIENTS; idx++ ) {
  C[idx] = BASE_RADIUS*WOBBLE_FACTOR*rand[-1,1]/(idx*idx);
  phase[idx] = rand[0, 2*pi];
}
for (float theta = 0; theta < 2*pi; theta += SMALL_STE) {
  r = BASE_RADIUS;
  for (int idx = 1; idx < NUM_COEFFICIENTS; idx++) {
    r += C[idx] * sin(idx*theta+phase[idx]);
  }
  plot(r,theta);
}

Obviously there are a lot of constants to be fiddled with here (I would start with WOBBLE_FACTOR around .2 or so and NUM_COEFFICIENTS about 20), and you can look at producing bigger wobble (e.g., replacing the divide by (idx*idx) with a divide by just idx so that the higher-frequency terms aren't as damped), but for the resolutions of pools you're talking about most of that will just vanish.

Note that this will (basically) produce the outline of a lake by drawing 'around' it; if you wanted to 'scanline' your lakes you could do it by just deciding whether the center of each cell in your grid is within the lake's outline - that is, whether its radius is less than the frequency sum at that point:

for ( int y = -MAX_LAKE_RADIUS; y <= MAX_LAKE_RADIUS; y++ ) {
  for ( int x = -MAX_LAKE_RADIUS; x <= MAX_LAKE_RADIUS; x++ ) {
    r = sqrt(x^2+y^2);
    theta = atan2(y,x);
    test_r = BASE_RADIUS;
    for (int idx = 1; idx < NUM_COEFFICIENTS; idx++) {
      test_r += C[idx] * sin(idx*theta+phase[idx]);
    }
    if ( r <= test_r ) {
      fill_lake(x,y);
    }
  }
}

This is somewhat similar to thalador's perlin-noise approach, except that we're building our noise function explicitly here (via its fourier transform, essentially) and using it to 'wobble' a 1d line (circle) rather than taking a level set.

Answer 5

One possibility is to use perlin noise as noted in the other answers, but just to share an alternative, I've also implemented this using probabilities before.

Coose the center and the maxRadius of the lake, and for each tile within that radius, use the following probability to determine whether it should be a water tile:

probability = 1 - (distanceFromCenter / maxRadius)

In other words, the probability of a tile being water increases the closest it is to the center. You can measure the distance either in a straight line, or using a manhattan distance. This gives the lake an overall round shape, but with enough variation because of the randomness involved.

To ensure that the lake is contiguous, start from the center which is guaranteed to be water, and call the function recursively for all neighbours, but only when the current tile is also water. This is enough to ensure that all the water is connected to each other.

Finally, to remove any ground tiles that remain on the inside of the lake, check this topic. In retrospective it might have been easier to use perlin noise though. :)

Answer 6

You might find this question & answer for creating random tea leaves offers an approach that could work...

How can I generate a texture that looks like left-over tea leaves?

Instead of sprites of tea leaves, create sprites of different size and shape water puddles that can be overlapped to create a larger water puddle.