Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
add comment

5 Answers 5

up vote 13 down vote accepted

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
share|improve this answer
1  
+1, this is really the best solution –  Hannesh Jul 17 '12 at 21:03
    
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. –  hustlerinc 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
1  
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
show 3 more comments

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

share|improve this answer
    
Good approach too. Giving a try! –  RawArkanis Jul 18 '12 at 11:44
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.