# Random Map Generation

#### Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

•  Subject
• Author
• Posted on
I'm wanting to write a browser based wargame and am going to use PHP
to it.  The game requires a big map and I want to generate this
randomly as it will be a lot of work to do it manually.

My first prototype for doing this doesn't give good results, the map
being far too random, can someone help me out or point me to a good

The map will need to have sea in it and ideally rivers as well as the
usual terrain, cities, forest, hills, plains etc.

Thanks!

## Re: Random Map Generation

i think you should write your how algorithm
like every 10 miles print a lake and close to it a city
put on paper the logic you have to follow and then try to resolve the
problem on it before go on php

## Re: Random Map Generation

Real geography is not random.

First, take a grid, say 1001x1001 is size. Now find the middle square of
it and set it to have a height of 1m above sea level. Now spiral out from
that square, creating a height for each square using an algorithm like this:

1. Look at the adjacent squares, but only the ones that
you've already assigned a height to!
2. Find the average (mean) of height those and call it \$h.
3. Now here's where we add a bit of randomness:

if (rand(1,2)==1)
\$h -= log(rand(1,1000000));
else
\$h += log(rand(1,1000000));
if (rand(1,20)==1) \$h *= 3;

There is a note way down below about step 3. Don't read it yet. Wait until
you get there.

OK. Now you have a 1001x1001 grid of various heights. Anything below 0m in
sea level should be water.

Find the two highest grid squares. Make them and the adjacent 16 squares.

Find the four next highest which aren't already covered with ice. Add
rivers flowing from them. Here's how you chart a river's course from its
origin.

1. You're on a particular grid square.
2. Are you at the sea yet? If so, stop.
3. Look at the 8 adjacent squares. Which has the lowest altitude?
4. The river should flow to that square. Go to step 1.

Now you know where all the water is, find the ten squares furthest from
any rivers, ice and ocean. Make them into desert.

Find areas that are between 12m and 25m above sea level and are not
either ice, river or desert. Make them into forest.

Select a random two of the four rivers. Place a city where they meet the
sea.

Select a random two of the four rivers. Place a city half-way between the
origin and the sea.

Place two cities at any random part of the geography that is not under
water.

You get the idea. For any other geographic feature, you should be able to
think of a method of placing it randomly, but realistically.

Having done all this, you might realise that your map is now either too
boring, or too unrealistic. So here comes my note about step 3. Most of
the randomness that is introduced into the map is introduced here:

if (rand(1,20)==1) \$h *= 3;

If you want to make it more random, then either decrease '20' or increase
'3' (or both!). If you want to make it more boring, then do the reverse.

I'd be interested to see how it pans out, and how much use any of my ideas
are. Please do post here, or drop me an e-mail when you're done.
mail at tobyinkster dot co dot uk.

--
Toby A Inkster BSc (Hons) ARCS
Contact Me ~ http://tobyinkster.co.uk/contact
Geek of ~ HTML/SQL/Perl/PHP/Python*/Apache/Linux

* = I'm getting there!

## Re: Random Map Generation

Toby A Inkster wrote:

Oops! You'll sometimes run into a dead end here. I'll leave you with the
challenge of figuring out how to detect and fix this. Clue: lakes.

--
Toby A Inkster BSc (Hons) ARCS
Contact Me ~ http://tobyinkster.co.uk/contact
Geek of ~ HTML/SQL/Perl/PHP/Python*/Apache/Linux

* = I'm getting there!

## Re: Random Map Generation

Toby A Inkster wrote:

Toby,

Nice algorithm.  For your dead end, might I suggest you make the lowest
square a lake and take the next lowest square as the outlet?  Repeat
until you get an outlet.

--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstucklex@attglobal.net
==================

## Re: Random Map Generation

Jerry Stuckle wrote:

If I understand you correctly, I think you might end up with lakes that go
uphill that way. Consider the following landscape; heights in
metres, co-ordinates as A1, C2, etc:

A    B    C    D    E    F    G
1    800  600  400  500  600  800  800
2    800  550  350  480  550  650  600
3    800  550  200  300  310  300  300
4    880  650  220  400  400  450  500
5    900  700  240  400  450  500  550
6    900  700  280  450  500  550  600
7    900  650  350  500  550  600  650
8       900  650  300  550  600  650  700

Now imagine our river comes onto this map from the North at C1. Using my
algorithm it flows to C2 and then C3. Here it reaches a local minimum, so
should form a lake.

Using your algorithm, it will look to C4 as an outlet. Assuming we can't
go back to C3 as this would result in an infinite loop, we are again at a
local minimum, so we look to C5 as an outlet, and so on, eventually
expanding the lake into C5, C6 and C7 and then finally finding a way
downhill at C8.

In real life, although C3, C4, C5 and C6 would fill up as a lake, C7 would
not; D3 would become part of the lake, and the outlet would be through E3,
F3 and G3.

It's a rather contrived map -- a valley with two possible outlets for the
river: one that initially seems less favourable, but ultimately should
prove the chosen outlet. I'm sure it would crop up from time to time
though.

It *can* be dealt with computationally, but it's rather hard.

Personally I'd be tempted to not give the lake an outlet and explain it
away by saying that the water flows into an underground stream from there.
This might be a realistic explanation for one or two lakes on a map, but
not for hundreds though -- having not run the algorithm myself, I'm not
sure how often they would crop up.

--
Toby A Inkster BSc (Hons) ARCS
Contact Me ~ http://tobyinkster.co.uk/contact
Geek of ~ HTML/SQL/Perl/PHP/Python*/Apache/Linux

* = I'm getting there!

## Re: Random Map Generation

"Toby A Inkster" wrote

Most of the "lakes" in the centre .au don't have outlets. The water flows
into them and then just dries up.

Similar, the rivers. They flow (sometimes) from here where it is raining go
over there --> where it isn't. Then they stop.

Quick quiz: Name the only yacht regatta in the world that takes out
insurance against rain. Hint: it takes place in a "river".

Cheers
Richard.

## Re: Random Map Generation

Richard Formby wrote:

Indeed. Causing great mystery to early explorers searching for an
"inland sea".

The Alice Springs one.

--
Toby A Inkster BSc (Hons) ARCS, passport-carrying Australian :-)
Contact Me ~ http://tobyinkster.co.uk/contact
Geek of ~ HTML/SQL/Perl/PHP/Python*/Apache/Linux

* = I'm getting there!

## Re: Random Map Generation

"Toby A Inkster"

Indeed, my learned friend. The Henley-on-Todd.

For the lesser informed:

http://www.henleyontodd.com.au/

Cheers
Richard.

## Re: Random Map Generation

Toby A Inkster wrote:

Tony,

Yep, that's just what I'm saying.  And if the lake gets too big, you
could adjust the elevation a little to bring it down.

The underground stream is also a possibility.  Not sure how it would go
over, though.  It does seem a bit contrived.  Besides, rivers are a good
source of transportation, food, etc.

Another way I thought about doing this is to make it more realistic.
Instead of having just a single elevation for each square (which isn't
realistic in most places), have a minimum and maximum elevation.  That
range could increase as the minimum elevation increases (i.e
foothills/mountains) and decrease as the elevation decreases (plains,
etc).  It might give a more realistic pattern, and more possible outlets
for the lake.

And small changes to the algorithms could have large effects on the outcome.

--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstucklex@attglobal.net
==================

## Re: Random Map Generation

Just a quick update, I've got a very simple prototype of this working,
once I've refined it a bit more I will let you see the code, it needs
some tidying up!

Thanks again!

The "randomness" will need tweaking a fair amount I think, but overall
I'm confident it has potential!  Just call me Slartibartfast ;-)

## Re: Random Map Generation

Do you put the "message from the maker" somewhere in your design?

Have fun.

## Re: Random Map Generation

Well there certainly are a lot of "crinkly bits around the edges!"

## Re: Random Map Generation

Thanks, of course, height is the key!  Hadn't thought of that, the
code I'd written before just decided if the terrain was going to be
plains, hills, mountains etc but your method is much better and I will
use it.

Will post updates when I get some results, but I'm working on another
game first.

:-/