PDA

View Full Version : Creating a map generator in Excel



GM.Casper
2010-05-26, 01:16 PM
So I tried my hand in creating a simple map generator in Excel. The principle is simple: first I create a field of random numbers (1-99). Then an average from the given cell and 3 rings of surrounding cells is calculated, value is then deposited in a second field, creating mountains and valleys. Then I have Excel color the cells.

http://img64.imageshack.us/img64/130/mapgen.jpg

It doesn’t do any proper continents or mountain chains. Still thinking how to manage that.

Leecros
2010-05-26, 02:10 PM
looks nice. There's a couple of spots there that look like they could be mountain chains. Not sure how you would set up the oceans, you'd have to set up at least 50% of it being water to get any real sizeable ocean...

GM.Casper
2010-05-26, 03:49 PM
I can easily adjust the water level- but then the valeys would just get flooded. It still would not form proper continents.

RS14
2010-05-26, 04:05 PM
Cool project.

Generating the base numbers as you are, you get uniformly random results. I think it will look better if you give it a heavier (still uniformly random) bias in certain areas. For each of the cells 20-30, for instance, you might give it a higher bias, or a lower bias.

You try instead starting with a very low resoultion and make those pixels very signifigant. Then expand--perhaps twice the resoultion--and create a gradient to fill in the newly created pixels.

Thus

0, 1

becomes

0, 0.3, 0.7, 1.

Then you add further randomness, but with less bias. For instance, between 0 and .5 on each. Continue increasing the resolution.

Pyrian
2010-05-26, 04:15 PM
It doesn’t do any proper continents or mountain chains. Still thinking how to manage that.If you're happy with the patterns, just not the scale, simply create the same thing on a larger scale and then overlay.

For example, you could generate a random number in every tenth cell of every tenth row, average those from the nearest 7x7 as you do normally, smooth those values into all the empty cells between. Finally, average that result into your current results, weighting as you see fit.

UglyPanda
2010-05-26, 04:45 PM
If you want something random but geographically sound, you could just download Dwarf Fortress (http://www.bay12games.com/dwarves/) and have it spend an hour making a world.

Hobs
2010-05-26, 04:52 PM
If you're happy with the patterns, just not the scale, simply create the same thing on a larger scale and then overlay.

For example, you could generate a random number in every tenth cell of every tenth row, average those from the nearest 7x7 as you do normally, smooth those values into all the empty cells between. Finally, average that result into your current results, weighting as you see fit.

yeah, that should work. just smooth over larger areas.

looks like a neat project.

I could imagine using VB scripts to add in forests and deserts, with rules like forests have to be above a certain elevation and deserts below a certain level. or have a 2nd worksheet, that creates a temperature gradient map, and have that depend on both the latitude but also the elevation. and then terrain types could depend on temperature as well.

lesser_minion
2010-05-26, 06:31 PM
Rogue basin (http://roguebasin.roguelikedevelopment.org/index.php?title=Main_Page) is pretty much dedicated to developing roguelikes - it has quite a bit of information on procedurally-generated maps as a result.

Leecros
2010-05-26, 07:33 PM
If you want something random but geographically sound, you could just download Dwarf Fortress (http://www.bay12games.com/dwarves/) and have it spend an hour making a world.

the only problem with that idea is that if he downloads Dwarf Fortress he may spend the next month or two learning how to/playing the game than working on his generator.

UglyPanda
2010-05-26, 09:13 PM
Of course, the point of that suggestion was so that he wouldn't have to work on his generator.

Je dit Viola
2010-05-27, 01:21 AM
Wow, that's really really cool.

One way that I can think of to get oceans and lakes would be to, on every tenth square or so in both directions [(J, 10) and (J, 20) and (T, 10) and so on], and have them go a random number between -50 and 50, then average them out between each of these points between the two. Then it'll make large sections of higher ground and large sections of lower ground also.

Unfortunately, I don't know how to make that work in Excel very well, so I can't help you with the mechanics of it.

lesser_minion
2010-05-27, 03:26 AM
Of course, the point of that suggestion was so that he wouldn't have to work on his generator.

I think procedural generation is interesting enough as a programming exercise in its own right that it's worth learning to do yourself as opposed to linking against someone else's library.

GM.Casper
2010-05-28, 10:07 AM
Making this myself is part of the fun. Besides I can fully control how it is being created and in what form the output is. Even if DF source code is available, I only know Pascal.

Now, I had an idea: I create first field with random numbers:
1 3 6 5 3 9 2
9 4 1 4 7 5 6
6 2 7 3 5 2 6

Second field would show landmasses:
5 5 5 5 5 5 5
5 5 5 1 1 1 1
5 5 1 1 1 5 1
5 1 1 1 1 5 5

Those would be combined and then “smoothed out” by calculating averages.
Now I just need to find out how to do the landmasses part.

RS14
2010-05-28, 10:17 AM
Here's an idea for the landmasses. Pick N random points. Make them land.

For k iterations,

For each water point, count the number of times, l, it is adjacent to a land point. Make it land with probability P(a*l^2+l*b).


Tweak N, k, a, b as necessary.



Also, if you know Pascal, why do this in Excel? It seems that Pascal would be far more flexable and easier to use. Is it just the difficulty of rendering it as an image?


Edit:
I wrote a little C++ program to do the above. It's not very user friendly. You'll need to set a few constants at the start, compile, and run it, redirecting output to an appropriate file.


#include <time.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=10; //Number of random points to start as land
const int k=40; //Iterations
const int x=100; // X dimensions of map
const int y=100; // Y ...
const double a=-0.02; // Coefficient for probability function (see bool P(double l))
const double b=0.16; // Coefficient for probability function...

int* field;
pair<int,int> dims;

pair<int,int> rand_pair(){
return pair<int,int>(rand() % dims.first,
rand() % dims.second);

}

bool P(double l){
int limit = max(0.0,min(1.0,(l*l*a+l*b)))*RAND_MAX;
return (rand() < limit);
}

int field_deref(const pair<int,int>& trg){
return trg.first+dims.first*trg.second;
}

bool is_land(const pair<int,int>& trg){
if ( ((trg.first < dims.first) && (0 <= trg.first)) &&
((trg.second < dims.second) && (0 <= trg.second))){
return (1==field[field_deref(trg)]);
}
else{
return false;
}
}

int adjacent(const pair<int,int>& trg){
int count = 0;
for(int idx = -1; idx <= 1; ++idx){
for(int jdx = -1; jdx <= 1; ++jdx){
if((idx==0)&&(jdx==0)){
continue;
}
else{
if(is_land(pair<int,int>(trg.first+idx,trg.second+jdx))){
++count;
}
}
}
}
return count;
}

void survey(){
int* new_field = new int[dims.first*dims.second];
pair<int,int> trg(0,0);
for(; trg.first < dims.first; ++trg.first){
for(; trg.second < dims.second; ++trg.second){
{
int count = adjacent(trg);
if( (is_land(trg)) ||
( ( 0 < count) && P((double) count))){
new_field[field_deref(trg)]=1;
}
else{
new_field[field_deref(trg)]=0;
}
}
}
trg.second=0;
}
delete [] field;
field=new_field;
}

void setup(const pair<int,int>& new_dims){
dims=new_dims;
field=new int[dims.first*dims.second];
pair<int,int> trg(0,0);
for(; trg.first < dims.first; ++trg.first){
for(; trg.second < dims.second; ++trg.second){
field[field_deref(trg)]=0;
}
trg.second=0;
}

pair<int,int> extra;
for(int i=0; i < N; ++i){
// At most N starting land points--I don't want to do the extra checking to ensure it is exactly N.
extra = rand_pair();
field[field_deref(extra)]=1;
}

}

void print(){
pair<int,int> trg(0,dims.second-1);
for(; 0 <= trg.second ; --trg.second){
for(;trg.first < dims.first; ++trg.first){
cout << field[field_deref(trg)];
}
trg.first=0;
cout << '\n';
}
}


int main(){
srand (time(NULL));
setup(pair<int,int>(x,y));
for(int i=0; i < k; ++i){
survey();
}
print();
delete [] field;
}

Tulio d Bard
2010-05-28, 12:33 PM
So, does it print 0s and 1s to represent land and water (NNITO) or should I put that in some kind of Excel file?

(I know nothing of Excel)


If the 0s are land pieces (and I believe they are), you could do something to remove some of the single ones. There are too many small islands.

And also creating something to define mountains and valleys. Maybe if the 0s were water you could randomize land numbers from 1 to 9.

But that would be asking too much. :smalltongue:

GM.Casper
2010-05-28, 04:49 PM
Thanks, RS14. Your formula works nicely. Seting a=-1 reduces the number of inland lakes. At N=8 and k=15 it creates one or several large continents.
At N=25 and k=5 it creates an arhipelago.


Also, if you know Pascal, why do this in Excel?
In Excel it is easy to quickly try out the basic concept and see results. Since Excel cant do iterations (maybe custom macros can, but I havent learned that yet), I will now move to Pascal. Ill try to combine this with the random mountains/valley patern and see what I get.

If anyone is interested in RS14`s code in Free Pascal version, it is here, ready to run:

uses crt;
var m1:array[1..80,1..80] of integer;
i,x,y,a,b,D,P,N,k:integer;



begin
clrscr;
randomize;
a:=-1;
b:=16;
N:=8;
k:=15;

{Set basic Grid}
for y:=1 to 60 do
begin
for x:=1 to 79 do
begin
m1[x,y]:=0;
end;
end;

{starting land}
for i:=1 to N do m1[random(60)+1,random(79)+1]:=1;




for i:=1 to k do begin


for y:=2 to 60 do
begin
for x:=2 to 79 do
begin
if m1[x,y]=0 then begin D:=m1[x-1,y-1]+m1[x+1,y+1]+m1[x-1,y+1]+m1[x+1,y-1]+
m1[x-1,y]+m1[x,y-1]+m1[x+1,y]+m1[x,y+1];


P:=a*(D*D)+D*b; if (random(100)+1)<P then m1[x,y]:=1;
end;
end;
end;


end;


{draw map}
for y:=1 to 60 do
begin
for x:=1 to 79 do
begin
write(m1[x,y]);
end;
writeln;
end;



readln;readln;
end.

lesser_minion
2010-05-28, 04:53 PM
If you put it in
tags, then the indentation will be preserved. That would make it a little easier to read.

Also, shouldn't there be a program or a procedure statement somewhere in there?

Tulio d Bard
2010-05-28, 05:57 PM
Thanks, RS14. Your formula works nicely. Seting a=-1 reduces the number of inland lakes. At N=8 and k=15 it creates one or several large continents.
At N=25 and k=5 it creates an arhipelago.

:smalleek::smallredface: I hadn't checked the code before, just directed the printing into a .txt file. Now I see that 0s are water. -.-

RS14
2010-05-28, 06:17 PM
:smalleek::smallredface: I hadn't checked the code before, just directed the printing into a .txt file. Now I see that 0s are water. -.-

Oh, I didn't really say anything about what was what. Sorry about that. I thought of it as elevation, with 0 being sea-level and 1 above sea-level.

Sorry, more generally, for the lack of comments in the code. I'm usually better about that, but I was hurrying, and I figured the basic outline of the algorithm was already printed.

Tulio d Bard
2010-05-28, 07:25 PM
Oh, I didn't really say anything about what was what. Sorry about that. I thought of it as elevation, with 0 being sea-level and 1 above sea-level.

Sorry, more generally, for the lack of comments in the code. I'm usually better about that, but I was hurrying, and I figured the basic outline of the algorithm was already printed.

I set your N=0 (Number of random points to start as land), and then the map was all zeros. So, it wasn't impossible to find out. (I guess there are other ways, but I was too lazy to read the code) :smallbiggrin:

Don't matter about the comments (or lack of them), I think the important thing (showing how your formula works) was done with no troubles.

Leecros
2010-05-28, 07:37 PM
Of course, the point of that suggestion was so that he wouldn't have to work on his generator.

Of course, The drawback of your suggestion is that he'd be busy playing Dwarf Fortress instead of doing...whatever he wants to do with the map.

valadil
2010-05-28, 07:44 PM
Here's an idea for mountains and rivers. Choose a pair of points at opposite edges of the map. Draw a line through that. All cells touching the line get +50. Neighboring cells get +25. That raises a mountain range while preserving the randomness you already have. Change the values for dropping a river.

Obviously you'll have to do some math that's a little more interesting than just drawing a line. I'm guessing instead you'll go through each cell in the table (or maybe each cell in the rectangle determined by the two points you pick plus some edge cells around those) and measure the closest distance to the line determined by the two initial points. If that's within a certain tolerance, the cell is on the line and gets a big bump. If it's within a lower tolerance it gets a little bump.

To make it more interesting you could also pick a midway point in the middle of the map. The first point would connect to that and then that would go on to connect to the farther away point. You might have to check the angle, but it would otherwise be a neat way to make bending mountain ranges. A river OTOH could bend in any direction, so that wouldn't need the angle check.

RS14
2010-05-28, 08:52 PM
Obviously you'll have to do some math that's a little more interesting than just drawing a line. I'm guessing instead you'll go through each cell in the table (or maybe each cell in the rectangle determined by the two points you pick plus some edge cells around those) and measure the closest distance to the line determined by the two initial points. If that's within a certain tolerance, the cell is on the line and gets a big bump. If it's within a lower tolerance it gets a little bump.
Take a look at Bresenham's line algorithm (http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm). Just offset it to get the smaller, adjacent deviations.

You might also get good results by picking three points: one center and two end-points. Draw an eliptical arc through them, as above. Probably here it would be best to target each point along the arc and raise them each as:

0 1 2 1 0
1 2 3 2 1
2 3 6 3 2
1 2 3 2 1
0 1 2 1 0

so that the "brush" is softer.

It might be best if you can put both arc endpoints on the same contenent, perhaps near the edge (try picking at random until you can find a land route between them). This way you keep the mountains mostly along a plausible plate boundary. By all means, experiment with more intelligent algorithms. It might be best to just pick this by hand.

I would just draw rivers by hand, if you need them. They're so narrow that they shouldn't really show up at this resolution. If you must have them automatically, I would:

for every point, assign a quantity of rainfall, 1.0. Furthermore, track the throughput of each point, defined as the amount of water passing through it. Thus the throughput starts at 1.0.

For every point, find the lowest point in its neighborhood, and pass .9 of the water present into that point. Repeat until satisfied. Tiles with high throughputs contain either rivers (if water flows out) or lakes (otherwise).

valadil
2010-05-28, 10:37 PM
Take a look at Bresenham's line algorithm (http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm). Just offset it to get the smaller, adjacent deviations.


Nice. I've seen that before, but it's been 6 or 7 years and there was no way I was going to remember its name.

GM.Casper
2010-05-29, 11:03 AM
Ah,.yes, we covered Bresenham's algorithm in university a couple months ago. That would be one good way to create mountain ranges…
As for rivers, when terrain relief is known, and climate map has been generated as well (rain shadows and such), rivers could be calculated. Just dropping them on the map would look weird.

So I combined random map with continental map using RS14 code, and got rather good results:

http://img175.imageshack.us/img175/7033/mpgen.jpg

Code is here:


uses crt;
var m :array[1..90,1..90] of integer;
m1:array[1..90,1..90] of integer;
m2:array[1..90,1..90] of integer;
i,x,y,a,b,D,P,N,k,r:integer;




procedure Continent;
begin
{Set basic Grid}
for y:=1 to 60 do
begin
for x:=1 to 80 do
begin
m[x,y]:=0;
end;
end;

{starting land}
for i:=1 to N do m[random(60)+1,random(79)+1]:=1;

for i:=1 to k do
begin
for y:=2 to 60 do
begin
for x:=2 to 79 do
begin
if m[x,y]=0 then begin D:=m[x-1,y-1]+m[x+1,y+1]+m[x-1,y+1]+m[x+1,y-1]+
m[x-1,y]+m[x,y-1]+m[x+1,y]+m[x,y+1];
P:=a*(D*D)+D*b;
if (random(100)+1)<P then m[x,y]:=1;
end;
end;
end;
end;


for y:=1 to 60 do
begin
for x:=1 to 80 do
begin
if m[x,y]=0 then m[x,y]:=-450;
end;
end;


end;



procedure Rndm; begin
randomize;
r:=100;
{create random m1}
for y:=1 to 80 do
begin
for x:=1 to 80 do m1[x,y]:=random(r)*10;
end;

{calculate m2}
for y:=3 to 79 do
begin
for x:=3 to 79 do begin m2[x,y]:=Trunc((

m1[x-1,y-1]+m1[x,y-1] +m1[x+1,y-1]+
m1[x-1,y] +m1[x,y] +m1[x+1,y]+
m1[x-1,y+1]+m1[x,y+1] +m1[x+1,y+1]+

m1[x-2,y-2]+m1[x-1,y-2]+m1[x,y-2]+m1[x+1,y-2]+m1[x+2,y-2]+

m1[x-2,y-1]+m1[x-2,y]+m1[x-2,y+1]+
m1[x+2,y-1]+m1[x+2,y]+m1[x+2,y+1]+

m1[x-2,y+2]+m1[x-1,y+2]+m1[x,y+2]+m1[x+1,y+2]+m1[x+2,y+2] )/25);

end;
end; end;



procedure Combine; begin

for y:=1 to 60 do
begin
for x:=1 to 80 do
begin
m1[x,y]:=m[x,y]+m2[x,y];
end;
end; end;



begin clrscr; randomize;
a:=-1;
b:=16;
N:=8;
k:=14;

Continent; Rndm; Combine;

{draw map}
for y:=3 to 60 do
begin
for x:=3 to 79 do
begin

if m1[x,y]>580 then begin TextColor(15); write('M');end else
if m1[x,y]>530 then begin TextColor(4); write('m');end else
if m1[x,y]>470 then begin TextColor(6); write('n');end else
if m1[x,y]>110 then begin TextColor(green); write('#')end else
begin TextColor(1); write('*'); end;

end;
writeln;
end;



readln;readln;
end.

YPU
2010-05-29, 11:12 AM
Impressive work, tough its starting to feel rather DF to me, but then that game has such a cult following that it cant be a bad thing.

Athaniar
2010-05-29, 01:05 PM
On a similar topic, does anyone here know how to create a random generator similar to the Video Game Name Generator?

Lord Herman
2010-05-29, 01:09 PM
On a similar topic, does anyone here know how to create a random generator similar to the Video Game Name Generator?

I take it that's an app that makes random names? You can use Inspiration Pad (http://www.nbos.com/products/ipad/ipad.htm) for that. It can also make all kinds of other generators like random treasure generators, random towns, random stats for NPCs, or whatever else you can come up with as long as it's text-based.