Terrain Generation Problem

It might be a good idea to actually ask a question, since suggestion/ideas can range from "well, do it" to "I'd be you, I'll use a 60° slope limit".[smile]

What is your exact problem?

It's kind of hard to explain. Basically after I have generated some terrain, I calculate the slope of each polygon based on the normal, all the polygons that have a slope value of less than 30 degrees are coloured green and all the polygons that have a slope value that is higher than 30 degrees are coloured red. So assuming that a player cannot travel up slopes greater than 30 degrees, the player can traverse green polygons and not red polygons.

Now using a slopemap, I want to define a path across some terrain from a start point to an end point, i.e.

end
0 0 0 0 0 1 0
0 0 0 0 1 1 0
0 0 0 0 1 0 0
0 0 0 1 0 0 0
0 0 0 1 0 0 0
0 0 0 1 1 0 0
0 0 0 0 1 0 0
start

So a player can only walk on sections with a 1 but cannot reach sections with a 0 as it is too steep. I hope this is clearer. Imagine a game where terrain is created completely randomly during runtime, and there has to be a mechanism to define a path between points that a player can travel down. I think this best sums up the problem.

cheers

[Edited by - Jamiernmd on September 18, 2006 10:12:21 AM]

I'm not convinced that a 'slopemap' will do the trick. In order to calculate the directional derivative of the surface at the point where the player is, you need a signed gradient for each degree of freedom. Hence a scalar map just can't store enough information.

To calculate the directional derivative, i.e. the gradient of the surface in an arbitrary direction (so not necessarily axis-aligned), take the dot product of the normalised projected direction vector with the grad of the surface at that point:

Assuming cartesian (x, y, z) with 'y up', let v = (v1, v2, v3) be the direction the player is facing. Project it onto the x-z axis:

vp = v . (1, 0, 1) = (v1, 0, v3)

and normalise:

vn = vp / sqrt(v1² + v3²)

Now calculate the vector gradient of the surface:

vg = (dy/dx, 1, dy/dz)

using whatever method you feel is appropriate for the partial derivative. There are many ways to do this, taking various accounts for accuracy by interpolation. I guess you are already doing this to create the existing slope map, so I won't go into detail. If not, there are plenty of resources on the web.

From here, take the dot product:

m = vn . vg

m is now the signed gradient of the slope in the direction of the player. It will be positive if he is climbing; negative descending. To stop him climbing cliffs, cull motion if m is above a certain threshold, m_max = tan(angle_max).

Regards
Admiral

Thanks for the response Admiral, but thats not quite what I meant, sorry I probably didn't explain it very well.

The player I mentioned is theorectical, all I'm trying to do is alter the terrain. Imagine a hedge maze, where you have floors that you can walk on, and walls that define where you can walk. That is what I am trying to do with the terrain, where the floor are all polygons with a slope of less than 30 degrees, and walls where the slope is greater than 30 degrees.

Another example is what I have working now. My slopemap can be used to define sections that should remain completely flat. However I don't want them to be flat, I want some hills, but they cant be so steep that a theorectical player couldn't climb, I also want to define sections that are too steep to be climbed to act as a wall or boundary to the level.

Thanks again

I understand. So you're not looking to determine the slope from the terrain, but to build a terrain from a walkability map.

Unless the slope of the tiles is boundless, such a terrain will not always exist. Or at least it won't look anything like a real terrain. Consider the following map:

11111111111111111110000001111110000000101110000000011011100000000010111111100000011111111111111111

The long run of 0s to the west of the plateau will need to be quite an incline (respectively decline) if each 0 tile must be above a certain steepness. Also the lowland (resp. highland) on the border to the left of the hill (crater) must be approximately the same height as that to the right. This leaves the narrow boundary to the right of the plateau being very steep. Of course, this example can be extended to make that cliff arbitrarily steep.

A smaller example:

1111110001101111000111111

Here, the central 1 must be roughly the same height as the leftmost land (as a path of 1s exists connecting them), yet they are separated by a single 0 tile, and hence must be at rather different heights. If the resolution of the slopemap is sufficiently high, this cannot occur.

Of course, if you design the maps carefully, you won't have to deal with such idiosyncracies. My point is that finding an algorithm to do all the dirty work for you won't be too easy, as the problem isn't necessarily solvable.
Just something to think about.

Regards
Admiral

Thats what I was worried about, if I can't guarantee that it will work every time for every possible terrain layout then it wouldn't be very helpful. I'll keep playing around with it and hopefully find a suitable work-around. Thanks again for your help Admiral.

Jamie