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

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

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?

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
• As I understand he wants the pools to be random, this approach would no be random, so why not place the water manually in the first place? Without complicating it with sea levels and stuff. – justanotherhobbyist Jul 17 '12 at 21:06
• @hustlerinc the heightfield would be random, if it is generated with perlin noise. The "sea level" just determines how much of the world is covered in water. If you assume [0,1] as output of perlin noise and set the "sea level" to 0.1f there would be almost no water, where as with a value 0.9f almost all would be covered. – thalador Jul 17 '12 at 21:11
• The question doesn't state whether a heightmap will be used. Maybe it's a simple 2D map where height isn't necessary. – ChrisC Jul 17 '12 at 22:20
• @CCRicers true, the heightmap is only temporary construction aid to create the pools. After that it can be deleted. The game/map remains 2D all the time. – thalador Jul 17 '12 at 22:29
• I like this approach a lot; the only problem with it is that it makes explicit placement (e.g., 'I want a puddle here of roughly this radius') kind of tricky; the water goes where it wants to go. – Steven Stadnicki Jul 17 '12 at 23:58

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

• Sorry if I didn't was clear. When I step in spiral sequence I set randomly some tiles as Water, not all. – RawArkanis Jul 18 '12 at 11:40
• @LuizdePrá You were clear that you were doing it, you list it in step 4 of your process. The reason you were doing it was a little unclear, though I suppose you were doing it in the hope of making the shape more random. – fnord Jul 18 '12 at 17:24

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:

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.

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++ ) {
phase[idx] = rand[0, 2*pi];
}
for (float theta = 0; theta < 2*pi; theta += SMALL_STE) {
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);
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.

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. :)

• Good approach too. Giving a try! – RawArkanis Jul 18 '12 at 11:44

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.