Jump to content
  • Advertisement
Sign in to follow this  

Terrain Generation Problem

This topic is 4262 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi all, Now this might seem a little strange so bear with me. I am writing some terrain generation software that features, the hill, diamond square and fault algorithm. What I want to do is define which parts of the terrain is accessable and which parts aren't. For example, given a slope angle, say 30 degrees, a player can travel to a point where the slope is less than 30 degrees but cannot climb a slope that is greater tan 30 degrees. I'm not interested in collision detection, just the rendering of the terrain. I have defined a slopemap which is a multidimensional array of ints the same size as the terrain and I want it so that if an element contains a 1 then that part of the terrain is accessable, if the element is a 2, then that part of the terrain is inaccesable as the slope is too high. I hope i've explained this ok, let me know if you need further clarification. Any ideas/suggestions? Many thanks

Share this post


Link to post
Share on other sites
Advertisement
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]

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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:

11111111111111
11111000000111
11100000001011
10000000011011
10000000001011
11111000000111
11111111111111
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:

11111
10001
10111
10001
11111
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!