Terrain generation algorithm? Please?
Sidath Jayawardena
For a programming project I have to generate a map like
Civilization. Well, it's not as easy as I thought. I've been
scratching my head for quite sometime trying to figure it out. Could
anyone suggest any algorithms which would generate a world like this?
Any replies will be greatly appreciated and the replier worshipped for
the rest of his or her life. Thanks,
Jaliya
Joan E Krochko
: Hi all,
: Jaliya
Nothings as easy as we think it is :)
For terrain I download Terrain Maker from x2ftp.oulu.fi
/pub/msdos/programming/utils. I think its tm.zip. This is a fabulous
program if you don't need wraparound terrain. It will generate a 512x512
bitmap then it allows you to edit it and save it in gif format. It was
originnally intended for Povray but I just take the gif file, resize it
and convert it to a pcx file.
Andrew,
Stephen Bowman
Sidath Jayawardena <jal...@cs.brandeis.edu> wrote:
>Hi all,
> For a programming project I have to generate a map like
>Civilization. Well, it's not as easy as I thought. I've been
>scratching my head for quite sometime trying to figure it out. Could
>anyone suggest any algorithms which would generate a world like this?
>Any replies will be greatly appreciated and the replier worshipped for
>the rest of his or her life. Thanks,
>
a believable map:
This would basically work if you are using a square grid map. First
determain the heights randomly for points equally spaced(how far
apart is up to you). then fill in the spaces between these points
with the average height of the original adding either a very small
randomly generated positive or negative number so that there aren't
straight angles between the original points. Now choose a height
for the water level on your landscape and put all squares under
this height underwater. This should give you a fairly good
representation of a landscape
hope this helps!!
>
Steven Miller
On 14 Apr 1995, Sidath Jayawardena wrote:
> For a programming project I have to generate a map like
> Civilization. Well, it's not as easy as I thought. I've been
> scratching my head for quite sometime trying to figure it out. Could
> anyone suggest any algorithms which would generate a world like this?
> Any replies will be greatly appreciated and the replier worshipped for
> the rest of his or her life. Thanks,
Here is a way to make decent land masses stored in a 2-D array:
First, create a 2-D array, each dimension the size of the width and
height of the map (a map of 10 spaces by 15 spaces would be land[10][15].)
Initialize each element to 0. In this example, 0 is assumed to represent
water in the map and 1 is assumed to represent land.
Next, generate a number of random coordinates and an equal number
of radius's. Each one of these will be the center point of a land mass.
Finally, for every coordinate and radius pair, create a circle of
1's (land) the size and position determined on the map array. To make the
circle, you would need to use the sine and cosine functions (commonly
referred to as SIN and COS) to create the circle. Remember to fill the
circle in with 1's, and not just make a border.
To add more variety, you could make a random ratio for each
circle, making some circles fat and some circles thin.
To make gulfs, lakes, and bays, you could reverse this process,
and make circles of water on the map that overlap, or partially cover the
land masses.
I hope this helps. If you need more details with creating the
code or adding other details, e-mail me at the address below.
Jonathan T. Moore
sketch for you. Start with a 2-dimensional array representing your surface
area. Initialize each cell to 0. The numbers stored in these cells are
interpreted as follows:
0 water
1 plains
2 mountains
Of course, you can add other numbers to get a finer granularity for height.
Now, select a number of "volcanoes" -- random locations on the map. At each
volcano, increment the cell count (raise that point). Then, for each of the
8 surrounding cells, assign a probability (which can either be constant or
can increase in proportion to the volcano height) of activating a volcano
there, and recurse.
This actually mimics somewhat the way islands are built (e.g. the Hawaiian
islands). However, if you have enough initial volcanoes, you can build up
pretty sizable land masses, and by varying the probability of "proximity
volcanoes", you can control how long mountain ranges are, etc.
Note: although this will let you get lakes, any "rivers" which might appear
would be purely coincidental, in contrast with Civilization.
Hope that helps.
-------------------------------------
Jon Moore (jmo...@cmu.edu)
-------------------------------------
Torben AEgidius Mogensen
This is not a particular good way of making realistic-looking maps. A
recursive subdivision metod is better (and faster). A description of
one is included below. The description shows how to find the altitude
of a single point. If you want to find all points, you just subdivide
both triangles, and record the values in the appropriate array (or
screen) cells when you reach the desired resolution.
Torben Mogensen (tor...@diku.dk)
=========================8<---------------------------
>Does anyone have a fractal landscape equation or routine I can use, I need
>a routine that takes in two co-ords, a x and a y and returns a height,
>similar to a mandelbrot but to create realistic(ish) landscapes.
>We already have both !Land and !Fractal but they are not what is wanted..
I have a simple algorithm that works quite well. I have also a 3D
version, which generates a planet (that is, a spherical map). I don't
have code handy for the 2D version, but it is quite simple, so I'll
describe it below.
You start with an right-angled isosceles triangle, like this (AB and
AC are supposed to be of equal length):
B
|\
| \
| \
| \
A----C
At each vertex you have an altitude and a seed for a random number
generator. To find the altitude of a point inside the triangle, divide
the triangle in two by finding the midpoint P of the line BC:
B
|\
| \P
| /\
|/ \
A----C
This creates two right-angled isosceles triangles, PAB and PAC. You
find a new seed and altitude for P the following way:
1) Use the two seeds in B and C to produce a seed for P. The random
number generator must be symmetric in the two seeds, that is
ran2(b_seed,c_seed) = ran2(c_seed,b_seed). You can use a normal
single-seed RNG and XOR or add the two seeds before using them as
argument.
2) Use the new seed to generate an offset scaled by the recursion
level of the subdivision (see below) and add this to the mean of
the altitudes in B and C to obtain an altitude in P.
Now find out if the desired point is in the triangle PAB or PAC, and
then apply the algorithm recursively on that triangle until the
desired resolution is obtained, then use the altitude of A as the
final altitude.
The reason the RNG must be symmetrical is that you can generate the
same point on several routes. The point midway between A and P will be
reached both by subdividing PAB twice and by subdividing PAC twice.
The scaling of the altitude offset can be varied depending on how
"rough" a landscape you want. The initial value determines the range
of altitudes in the scene, and the amount it is reduced by determines
the roughness. If the scale is multiplied by 0.7 at every recursive
call, you get a very smooth landscape. If it is multiplied by 0.8, you
get a very rough landscape. Experiment to see which suits you best.
Since you (probably) don't want a triangular map, you can get a square
map by putting two triangles together:
B----D
|\ |
| \ |
| \ |
| \|
A----C
There are several optimizations you can make to this general idea:
1) Make specialized procedures for every orientation of the triangle.
There are 8 orientations, and you will always know the orientation
of the recursive call from the orientation of the caller. Knowing
the orientation helps you find the midpoint easier and, more
importantly, makes it easier to determine in which half the
desired point is.
2) If the next point you want the altitude of is likely to be close
to the previous point, you can keep the values of the intermediate
triangles from the previous call in an array, and (starting from
the bottom of the array) find the first triangle that encloses the
new point, and subdivide from there. You will need 16 recursive
calls to get a resolution of 256x256, and if the next point is a
neighbour of the previous point, you will on average have to go
two levels up (and do two subdivisions from there), so this will
save you a lot. Of course, there is some overhead in keeping the
array, but that is relatively small.
Torben Mogensen (tor...@diku.dk)
Eddie Edwards
>Civilization. Well, it's not as easy as I thought. I've been
>scratching my head for quite sometime trying to figure it out. Could
>anyone suggest any algorithms which would generate a world like this?
>Any replies will be greatly appreciated and the replier worshipped for
>the rest of his or her life. Thanks,
One way of generating landscapes on a grid, which I mention because no-one
else has, is a 'seismic disturbance' model.
Start off with, say, a 32x32 grid of heights - initialize each one to zero.
Then choose a random line through the grid (many ways to do this - e.g. pick
two cells on different sides of the grid). Pick a random shift value. For
all cells to the left of the line, move the height up by this shift value, and
for all cells to the right of the line, move the height down by this shift
value.
After several iterations, mountains and lakes soon become apparent. As
suggested by virtually all the previous posts, set a 'water level' and set
any cell with a height below this to 'water' and any other cell to 'ground'.
Not particularly 'better' than any of the other suggested methods, but it
works well and is easy to understand. (IMHO)
--
Eddie xxx
------- Powerslave Software, PO Box 175, Enfield, Middlesex EN2 6RD -------
---------------- For all your Acorn game conversion needs -----------------
Dion Kurczek
writes:
I've employed a sililar, but simpler method for generating 2d maps
which was pretty effective. At each random center point, generate a
number of random "snakes" that radiate outward. Each snake has a
random direction, 1-4 (N,S,E,W), and turns left or right after each
movement. The alforithm then looks something like this:
function Mass( nMasses, nSnakes, nRadius: integer )
for i := 1 to nMasses do;
begin
startx := random( Width );
starty := random( Height );
for j := 1 to nSnakes do
begin
snakex := startx;
snakey := starty;
direction := Random( 4 );
for k := 1 to nRadius do
begin
FillTerrain( snakex, snakey );
if Random < 0.5 then
turn direction left
else
turn direction right;
advance snakex, snakey based on direction;
end;
end;
end;
end;
By varying the number of masses, snakes, and radius, you can achieve
many different effects, from huge continents to sparse islands. This
will get you a pretty good land/water map. From there, you'd want to
go into some more specific algorithms for forests, mountains, rivers,
swamps, desert, etc.
Amit Patel
Eddie Edwards <e...@datcon.co.uk> wrote:
>Sidath Jayawardena <jal...@cs.brandeis.edu> wrote:
>>Hi all,
>
>else has, is a 'seismic disturbance' model.
[shift on one side of a randomly picked line]
Add to this a volcano/meteor phase:
Pick a random circle on the grid.
Push things up or down by something that looks like the
top 10% of a sphere.
To make things smooth, instead of a sphere, I used a function like
HF/(F+x^2+y^2). H is +/- distance moved at the center and F is a
smoothness factor. A small F gives a very pointy mountain/depression
and a large F gives a large smooth area.
Of course you don't want everything to look like circular areas, so
you need to use the technique Eddie mentioned to jumble things up
again. Alternating seismic disturbances and volcano/meteors can
produce a nice terrain.
- Amit
P.S. I haven't tried this but it seems like a mountain range might be
created if you use fixed circles for volcanos and lines for shifts.
It would be like Hawaii -- a tectonic plate moving over a fixed hot
spot under the surface.
Amit Patel
Do any games actively modify terrain after it's been generated?
What I would like to do is have rivers FLOW, not just exist like in
Civilization. Water levels could vary from season to season -- rivers
would dry up at times and flood the player's cities at other times.
Snow would accumulate during the winter and melt in the spring.
Erosion (accelerated by farming?) could be interesting too. The
player could build dams, which would create lakes. Earthquakes or
player-built structures might alter the flow of a river.
I am having trouble making rivers flow on a grid map (like Civ). I am
storing an altitude level and a water level, and making water flow
downhill, but it seems to spread out over a large area instead of
forming a river. Has anyone had success making a realistic river flow
model?
Amit
Robert Cassidy
Patel) wrote:
I wrote some terrain modeling software some years back that handled rivers
- it was not easy, I can tell you. I can recall storing altitude and water
level - then adding water at regular intervals (simulate rain) and then
determining flow - much as you seem to do. To do the rivers you need to
realize that a river will pick out the subtle changes in altitude and
magnify them by eroding a channel - decrease the altitude based on ground
density, flow rate (function of slope), and volume. The problem is that
sediment is also deposited in places - function of flow rate and sediment
carried. Rivers often originate from a spring - so what seems to work ok
is to model your terrain to determine rivers, then work up the river to
the origins and simply place springs there - then you can pretty much drop
the rainfall model (which is pretty time consuming - at least was on the
fastest 386 of the day!). You need to throw in all sorts of corrections to
the model to account for things you don't think of - to prevent rivers
from simply cutting your map in half, evaporation, etc. As you can see,
there is a lot more work involved than the generation of terrain. I found
that the maps were far better if you did some kind of 3D ground density
modeling - this will allow for waterfalls and other cool things. It took
me about a year of tinkering to get it the way that I wanted - I wish I
knew what I did with the code, though! I never tried snowfall other than
to say that over a particular altitude it snowed. Dams, etc. would've fit
in really well, wish I had thought of it at the time. I did find that if
the 3D density model was right, by hacking up some of my parameters that
caves could also be modeled but they were few and far between - the
density model wasn't the best - I'll have to think of a new one.
I've thought about rewriting the project on my nice fast PowerMac - should
be a lot more fun to watch - maybe this summer.
--
Bob Cassidy
UC Irvine
Olson Kevin
: In article <3n91af$q...@nntp.Stanford.EDU>, am...@Xenon.Stanford.EDU (Amit
: Patel) wrote:
: > I've seen a lot of terrain generation ideas posted here.
: >
: > Do any games actively modify terrain after it's been generated?
: >
: > What I would like to do is have rivers FLOW, not just exist like in
: > Civilization. Water levels could vary from season to season -- rivers
: > would dry up at times and flood the player's cities at other times.
: > Snow would accumulate during the winter and melt in the spring.
: > Erosion (accelerated by farming?) could be interesting too. The
: > player could build dams, which would create lakes. Earthquakes or
: > player-built structures might alter the flow of a river.
: >
I don't know if this is a viable option for you or not, but there is a
program called GRASS which is in the public domain. The Army Corp of
Engineers wrote it. GRASS will take various maps and handle altitudes,
etc. It is possible to hook it with another program called HEC-5 which
does river flows, including sediments, reservoirs (also lakes), variations
by seasons, etc. I know that they have PC versions of the stuff, but I
personally have only seen the workstation stuff. I was working on a larger
water modeling project, but the stuff could be adapted. What's best is
that all the routines already exist (some of it is in Fortan though I
think), and is the public domain, so all you have to do is adopt the
sections you want.
Just a thought -- perhaps not a helpful one.
Kevin Olson
Tim Drozinski
This is pretty interesting. I've been thinking of ways to generate maps for a
Civ/Colonization-type game I've been thinking about (I think a lot about these
things...), and this pretty much sums up all of the ways I've considered into one
big lump. The only thing I have to say I haven't liked about the above mentioned
games is that you CAN'T sail boats up rivers. That kind of makes rivers a
pointless feature in the game, with the exception that you get a production
bonus on river squares. I think it would make the game more interesting if you
had real rivers (one whole square of water, like an ocean sqaure) traversing
the land masses. You could add directionality to the river, so that you could
increase movement points required to sail upstream, and reduce the number
needed to go downstream. I know this is making a simple concept incredibly
complex, but think of all the cities in the world that are landlocked, but,
because of access to a major river, were important manufacturing and shipping
areas.
One way to do this could be to pick a starting point (I'd like to say the original
"volcanoes" since these areas are most likely to be the highest mountain areas)
and call that the river's source. Randomly generate a path from there to the
ocean, giving each segment a higher counter number (to assign directionality),
and you can even assign weights to different terrain, so that you don't have a river
running back up over mountains, only running down through mountains and into the
plains. Additionally, you could make the river broaden into a lake, especially if
it dead-ends in some mountains, or if it the river is on an exceptionally large
continent.
Another way is to generate some random river courses and overlay them on the
terrain map. If the river squares overlay ocean, then they just become ocean;
but if they are over land, the land becomes a river square.. The big problem I see
here is that you'd have to check to be sure that a piece of land on the corner of a
continent doesn't get turned into a river when the river doesn't go inland, just
clips the corner off the island. You'd want that square to remain ocean, or land.
Just my take on the idea. I'd love to have comments, so maybe I can add them into
my game concept, which I'll get around to coding one of these days.
Tim
Larry Smith USG
>I am having trouble making rivers flow on a grid map (like Civ). I am
>[...] but it seems to spread out over a large area instead of
At a guess, from the description, you don't have a river
channel. River flow that way because they are moving to
the next lowest square. In terms of your map, you need
a channel for the core of the river, to confine it, and
only allow the fanning out during flood times.
What I think
you have:
-------- <- all at same level
\ \
\.......\ <- intended path
\ \
---------
What I think you
need:
--------
\-------\
|_ _____|_ <- need a channel
\ \
---------
--
Larry Smith --- My opinions only. lar...@zk3.dec.com/lar...@io.com.
"It is not the function of the government to keep the citizen from falling into
error; it is the function of the citizen to keep the government from falling
into error." - U.S. Supreme Court. And we are doing a damned poor job of it.
Tim Drozinski
>I've seen a lot of terrain generation ideas posted here.
>
>Do any games actively modify terrain after it's been generated?
>
>What I would like to do is have rivers FLOW, not just exist like in
>Civilization. Water levels could vary from season to season -- rivers
>would dry up at times and flood the player's cities at other times.
>Snow would accumulate during the winter and melt in the spring.
>Erosion (accelerated by farming?) could be interesting too. The
>player could build dams, which would create lakes. Earthquakes or
>player-built structures might alter the flow of a river.
>
of ability to use boats on the rivers in games such as Civ and Colonization.
I posted earlier about a concept I had....
>I am having trouble making rivers flow on a grid map (like Civ). I am
>storing an altitude level and a water level, and making water flow
>downhill, but it seems to spread out over a large area instead of
>forming a river. Has anyone had success making a realistic river flow
>model?
Well, if you start at a mountain square, and pick a random direction, create
a river square with an index/count of 1. Pick another square in that same
general direction (you'll have to have an algorithm that keeps track of what the
last direction was, then only allow movement in 3 of the 8 possible directions, in
the general direction of the flow. This should stop the river from spreading out
too much), make THAT square a river with an index/count of 2. Continue until
you hit an ocean square. You can then say that as you move along a watercourse,
if the index or count is decreasing, you are travelling upstream, and vice-versa.
I'm sure there are some problems, like a river turning back on itself. You might
counter that by letting any river that completely encircles a piece of land just
become a lake, which has no river counter (no flow). The odds of a river creating a
perfect loop would be (1/3)^7 = 0.000457..... (Assuming you have a 1 in 3 shot of
picking the same direction to turn the river each time, eventually creating an
octagon). The good news is that by limiting yourself to 3 directions in each
decision, you can't ever immediately double back or "widen" the river. The down
side is that rivers may often turn out as either straight lines or incredibly squiggly
ones. I guess a case could be made that a) there are rivers like both of those cases,
and b) the odds are that the river will be sufficiently irregular to be realistic.
Hope it gives you some good ideas! Give me some feedback, I'm thinking of using
the concept myself.
Droz