Random Map Generation

[skulkrinbait]

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
resource please?

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

Thanks!

[Daniele]

sk**********@googlemail.com wrote:

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
resource please?

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

Thanks!

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

[Toby A Inkster]

sk**********@googlemail.com wrote:

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
resource please?

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!

[Toby A Inkster]

Toby A Inkster wrote:

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.

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!

[Jerry Stuckle]

Toby A Inkster wrote:

Toby A Inkster wrote:

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

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,

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.
js*******@attglobal.net
==================

[skulkrinbait]

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.

:-/

[Toby A Inkster]

Jerry Stuckle wrote:

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.

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!

[Richard Formby]

"Toby A Inkster" wrote

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.

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.

[Toby A Inkster]

Richard Formby wrote:

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

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

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

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!

[Richard Formby]

"Toby A Inkster" <us**********@tobyinkster.co.ukwrote in message
news:9p************@ophelia.g5n.co.uk...

Richard Formby wrote:

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

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

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

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!

[Richard Formby]

"Toby A Inkster"

Richard Formby wrote:

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

The Alice Springs one.

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

For the lesser informed:

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

Cheers
Richard.

[Jerry Stuckle]

Toby A Inkster wrote:

Jerry Stuckle wrote:

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

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.

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.
js*******@attglobal.net
==================

[skulkrinbait]

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 ;-)

[Dikkie Dik]

... Just call me Slartibartfast ;-)
Do you put the "message from the maker" somewhere in your design?

Have fun.

[skulkrinbait]

On Feb 24, 12:48 pm, Dikkie Dik <[e-mail]:

... Just call me Slartibartfast ;-)

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

Have fun.

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