# Procedural World Generation

43 replies to this topic

### #1 PlasticineGuy

PlasticineGuy

GMC Member

• New Member
• 2384 posts

Posted 22 December 2009 - 03:37 AM

I'm currently making a Roguelike game, a large part of which is to do with random level generation. I started to look into some ways of generating random worlds, and I found some examples of procedural generation (created in Game Maker):

I looked at his results of map generation and wondered how to do that myself. Reading through the site's article, I decided to try his method. I began by (as the site's suggestion) randomly filling a 128x128 grid with single pixels at increments of 16, and looping through the grid, drawing the pixels as 16x16 blocks. It was nice, but not what I wanted. I made the blocks get progressively smaller until I reached 1 pixel blocks. Unfortunately, what I got was mostly random pixels everywhere. What I did next was find the blocks around it, and increase the chance of a block being the same as an adjacent one. The site also advises this, but gave no indication as to how to go about it. The code looks like this:
```block_size = 1;
land_amount = 50;
g = ds_grid_create(room_width, room_height);
ds_grid_set_region(g, 0, 0, room_width, room_height, 0);

var i, ii, d;
d = 0;
for(i = 0; i < room_width; i += block_size) {
for(ii = 0; ii < room_height; ii += block_size) {
d = ds_grid_get(g, i - block_size, ii);
d += ds_grid_get(g, i - block_size, ii - block_size);
d += ds_grid_get(g, i, ii - block_size);
d += ds_grid_get(g, i + block_size, ii - block_size);
d += ds_grid_get(g, i + block_size, ii);
d += ds_grid_get(g, i + block_size, ii + block_size);
d += ds_grid_get(g, i, ii + block_size);
d += ds_grid_get(g, i - block_size, ii + block_size);
d *= 40;
if(d == 0) d = -50;
ds_grid_set(g, i, ii, (round(random(200 - d)) <= land_amount));
}
}```
land_amount is a variable I use for playing with the amount of land; I set it to 30 to begin with.
After a bit of playing with the values (including the amount to multiply "d" by), I ended up with a result like this:

I experimented a bit more, and found that by increasing the block_size variable, I could make the map have more islands.

So what I thought would be interesting would be to discuss other ways of achieving a similar result, and expanding this idea into other styles of maps.
• 1

### #2 Endorel

Endorel

GMC Member

• Banned Users
• 191 posts

Posted 22 December 2009 - 03:30 PM

I think that it would be better to "form" the land, rather than try to arrange pixels into something that looks like land.

The first version of my growing concept:
fundamental bodies of land + peninsulas = dynamic bodies of land

```islands = 5;
map_width = 100;
map_height = 100;

var this_island, this_peninsula;
for(this_island = 0; this_island < islands; this_island += 1)
{
island_X[this_island] = random(map_width);
island_Y[this_island] = random(map_height);
island_aspect[this_island] = 0.5+random(1);
peninsulas[this_island] = choose(1,2,3,4);
for(this_peninsula = 0; this_peninsula < peninsulas[this_island]; this_peninsula += 1)
{
peninsula_magnitude[this_island,this_peninsula] = 0.5 + random(0.5);
// The "position" is actually an angle between 0 and 360 degrees:
peninsula_position[this_island,this_peninsula] = random(360);
}
}
// Then after the general shape of the islands is decided, use a pixel generator to build an image of the islands.```

I will try to add onto this code, test it, and completely finish it, but I don't want to right now. I could significantly improve it, but I will try it later.

~ SnowCream

Edited by SnowCream, 22 December 2009 - 03:33 PM.

### #3 Tarik

Tarik

GMC Member

• GMC Member
• 2731 posts
• Version:GM:Studio

Posted 23 December 2009 - 09:06 PM

I gave it a shot. Generating a few maps worked out pretty nicely though it can still use lots of work.
Also I generated a map, and used a planet example xot kindly made me to texture a planet with a map (which I just generated, the 1024x512 map took about 60 seconds!)

Here's a link showing the large map, the planet, and 3 smaller maps that take about 5 seconds to render.
SCREENSHOT

One small problem that keeps occurring is that sometimes (rarely) the maps' distribution ratio of land to water is very lopsided, caused by what you could describe as an avalanche effect, though not in the usual programming sense. The method discussed in this topic bases its choice of land or water on the adjacent cells. Thus if there's land nearby, the cell has a likely chance of also becoming land, which will increase the chance of other cells also being land. Of course when the first distribution is even, there's a small chance that this happens. But when the first distribution is say 65/30, the 65 can quickly become even worse. It's possible to counter this by comparing the observed distribution to the expected distribution, and then use that result to influence the new distribution. (So if we set distribution to 50/50, and we find after the first loop that it's 40/60, then we will artificially increase the chances of the first being chosen in the second loop to get closer to 50/50 again.) Anyway it's not a big problem, just something to look out for.

It's not very interesting to generate land versus water alone though, as terrain and worlds are much more complex than that. The maps I generated are green/blue (with random color variations), so you can consider them as containing information on a completely flat world with either blue or green land, which is inadequately exciting for just about any game!

A next step I'll be looking into are heightmaps, so that it's not just water or land, but a hill or a mountain, and different colors at different heights (ice on very high land). That'd provide more interesting information to render a planet, or 3d terrain. Clouds follow a pretty similar concept, and it's quite possible to have these circular distortions applied to the cloud-surface to mimic storms, pretty cool!

Thanks for the interesting post, procedural content is a very interesting programming & game concept and GM provides a great basis for quickly prototyping basic algorithms.
It'd be interesting to expand terrain generation to something more complex, such as generating infrastructure (bridges, roads) and concentrations of life based on very simplified concepts.

Oh and don't forget you can save GM's random seed, allowing you to generate the exact same map multiple times, and compare algorithms applied to the same random distribution.

Edited by Tarik, 23 December 2009 - 09:07 PM.

• 0

### #4 Atarian

Atarian

GMC Member

• New Member
• 28 posts

Posted 24 December 2009 - 02:03 PM

one thing you should think about is that id you can create (fairly) realistic land/water scenarios you could then use these in a height map generator, it would allow for more realism, on land for example you could create rolling hills where as underwater you could have a much sharper drop off and then some other sort of height map generator, it would also break the process down into a couple of simpler steps which would allow for easier adjustment.
• 0

### #5 Endorel

Endorel

GMC Member

• Banned Users
• 191 posts

Posted 24 December 2009 - 08:13 PM

It's obvious that you could use this for heightmaps. I would also mix it with a little bit of perlin noise if I were to use it for a heightmap. I guess that my original idea was stupid; perpixel procedural generation is the way to go!

~ SnowCream

Edited by SnowCream, 24 December 2009 - 08:21 PM.

### #6 PlasticineGuy

PlasticineGuy

GMC Member

• New Member
• 2384 posts

Posted 24 December 2009 - 11:44 PM

It might be a bit slower, but I feel letting it randomly generate would give the player a better feeling of immersion; it automatically generates quite a few islands, and the small islands just off the coast are very realistic.

I've never worked with heightmaps before; can you explain a little bit, please?
• 0

### #7 Endorel

Endorel

GMC Member

• Banned Users
• 191 posts

Posted 25 December 2009 - 01:51 AM

Height maps are used to generate height fields: 3-Dimensional terrain geometry. Like in Age of Mythology or Age of Empires III, they use procedural generation to build 3D maps with islands and an ocean. We're talking about implementing these specific pixel algorithms into 3D video games, to build random maps.

Checkout Jesper's example: Link to Topic

Edited by SnowCream, 25 December 2009 - 01:59 AM.

### #8 Schreib

Schreib

• GMC Member
• 1458 posts
• Version:Unknown

Posted 25 December 2009 - 11:51 AM

If not mentioned already, look up Midpoint displacement, which is a very effective technique.

The very best world generator (I'm afraid to say much more advanced than any of us Game Makers can ever dream to implement) I've seen so far is in the terrific game of Dwarf Fortress.

Interview on the shallowest world generation concepts of Dwarf Fortress: Gamasutra

A world generated in Dwarf Fortress:

Edited by Schreib, 25 December 2009 - 11:53 AM.

• 0
~ Tiefling | DeviantART gallery See my spacescapes!
GM Obfuscator | Protect your games from prying eyes. Get it now!
Motto: Noli turbare axiomates meos!

### #9 xot

xot

GMC Dismember

• GMC Elder
• 4785 posts
• Version:GM:Studio

Posted 25 December 2009 - 03:28 PM

Midpoint displacement is a powerful and easy to understand technique. It's a shame that Wikipedia doesn't show a very good example of it for the purposes of this topic. In fact Wikipedia seems to go out of its way to make it hard to understand. The main problem with it is that it creates crease-like artifacts along the 2n grid lines. I did find this which at least illustrates the process:
http://en.wikipedia....actal_landscape

This looks like a pretty good explanation of the algorithm:
http://www.gameprogr...om/fractal.html

This might provide some food for thought as well:
http://algorithmicbo...ntains.gi93.pdf

Personally, I'd go with a solid texturing technique, especially if you are attempting to work with a topology other than a flat plane. If you look at Tarik's image, you'll see that the map appears pinched near the poles. This needs to be compensated for which can be very difficult if your generator is based on a Cartesian/grid-like structure. It's a classic mapping problem and is why all flat maps of the globe have some amount of distortion. The mapping Tarik is using is similar to a Mercator projection, the most common projection seen for world maps. In those maps the areas near the poles are extremely distorted. An equirectangular projection is what Tarik is actually using. It is the most common spherical image projection used in CGI, probably because of its simplicity.

http://en.wikipedia....ular_projection

A solid texture can eliminate these distortion problems and Perlin noise is an ideal foundation for a spherical fractal terrain (or any other shape, including a plane). Instead of attempting to map an image to a shape using UV coordinates, a solid texture function is continuous in all dimensions and takes any point in space as an input. That's why they work for any kind of shape. Because the texture exists everywhere in space, if you created a solid texture to look like marble and textured a 3D model with it, the result would be 100% analogous to carving a real statue out of real marble. This link shows how such a texture can be constructed:
http://en.wikipedia....cedural_texture

Typical noise-based fractals have their own problems, namely they tend to be very homogeneous; everything looks the same at all scales and locations. That's the self-similar nature of fractals in general. It leads to unnatural looking valleys and shorelines. F. Kenton Musgrave attempts to address the problem by creating a variant called a multifractal that creates a more heterogeneous result. This is all covered in the book Texturing & Modeling: A Procedural Approach. Here's a preview of the book:

Thanks to the WayBack Machine, the source code is still available. I highly recommend checking it out, although it may be a little difficult to follow without the text.
http://web.archive.o...ndmodeling.com/

The same techniques are discussed briefly here:
http://www.gamasutra...procedural_.php

Edited by xot, 28 November 2015 - 07:31 PM.

• 0

If any of my posts contain broken images or links, I can probably supply them for you. PM with a link to the post.

### #10 Endorel

Endorel

GMC Member

• Banned Users
• 191 posts

Posted 26 December 2009 - 01:04 AM

Very interesting; but suppose you want a specific amount of islands, with a ratio of land and water. Create a bank of the particles you will use. Start the islands by placing the designated amount of them as particles ( onto a coordinate plane ). Loop through each "particle" left in the bank and place it by another randomly selected particle which has already been place onto the plane. You'll have a some-what complex algorithm, but it shouldn't be too hard to program. Eventually the bank of particles will collect into the designated islands!

```// Initialize
islands = 3;
land_percent = 0.8;
width = 100;
height = 100;
area = width * height;
land_particles = round(area * land_percent);
particle_num = 0;
bank_num = land_paritcles;

// Place nodes
for(i = 0; i < islands; i += 1)
{
particle_x[i] = round(random(width-2))+1;
particle_y[i] = round(random(height-2))+1;
// The 8 valid positions (4 sides + 4 corners)
particle_valid[i,0] = true;
particle_valid[i,1] = true;
particle_valid[i,2] = true;
particle_valid[i,3] = true;
particle_valid[i,4] = true;
particle_valid[i,5] = true;
particle_valid[i,6] = true;
particle_valid[i,7] = true;
particle_surrounded[i] = false; /* This is a piece for optimization which tells whether or not it is completely surrounded by other particles */
particle_num += 1;
bank_num -= 1;
}

// Build map
for(i = 0; i < bank_num; i += 1)
{
// TODO: place pixels into collections using two special repeat loops. I explain this more, after the code.
}

// TODO: draw map```

Let me explain the primarily unfinished segment of code:

The REPEAT Loop
I will elaborate the idea of the repeat loops: choose a random place to start at, then circle through until a valid selection has been made. Because the random function is only used once, there's no chance of wasted processing; again, because you're not using it everytime the loop executes the statement (like if you used a while loop).

Why not use a FOR loop?
Because FOR loops cannot have dynamic progression! This unique loop design can begin at any place, and should be capable of circling past the threshold and wrap to 0. I call this design the "circle" loop.

Why do you need to use 2 circle loops?
You have to circle through the placed particles, and also 8 possibly valid positions around the selected particle (4 sides and 4 corners).

~ SnowCream

Edited by SnowCream, 26 December 2009 - 01:11 AM.

### #11 xDanielx

xDanielx

GMC Member

• GMC Member
• 1002 posts
• Version:Unknown

Posted 27 December 2009 - 01:03 AM

This is always a fun topic. I wrote a terrain generator in Java (sorry, I can't stand GML these days), borrowing from some of these ideas. Here are some screenshots:

The algorithm is similar to the one originally described:
• We start with a map comprised of large blocks. The default block size is 64 by 64. The state of each block (land or water) is entirely pseudorandom.
• Repeat until all blocks are 1 by 1 in size:
• Divide each block into four smaller blocks.
• For each derived block, decide on a probability for that block becoming a land block. This probability is based on the state of the block it was derived from, and the land mass of surrounding blocks. The probability computation can be configured in different ways with different weights.
• If a pseudorandom number between 0 and 1 is less than that probability, the derived block becomes a land block. Otherwise, it becomes a water block.
• Darken land blocks which are contiguous with water blocks.
Here is a runnable JAR to play around with. You can also view the source code, although it may be difficult to understand the algorithm from the code alone.

Edited by xDanielx, 27 December 2009 - 06:01 AM.

• 0

### #12 Juju

Juju

GMC Member

• GMC Member
• 1109 posts
• Version:Unknown

Posted 27 December 2009 - 11:32 AM

I wrote this in 2006, written in GM6: http://64digits.com/...i...ame&id=1246
I do have other versions that have height mapping, wrap-around worlds and weather systems et cetera if anyone is interested.
• 1

Try out my open-source 3D globe terrain generator!

How about a fancy-pants text engine?

Adding dialogue boxes to your games is now super easy. Also localisation. Also tweening.

### #13 Endorel

Endorel

GMC Member

• Banned Users
• 191 posts

Posted 31 December 2009 - 08:16 PM

I can't believe my eyes, the source code! This code generates an islands map for Age of Mythology. Apparently the way that they declare islands is as "blobs". Pretty simple concept . . .

Age of Mythology, Islands Map:
View Text File

I hope that this is helpful for those who are making an RTS game.

~ SnowCream

************
Moderator Note:

I removed several posts after this one, which commented how nice Juju's contribution was... but whose authors apparently hadn't downloaded his example:

"I might be interested in this." .... "I would like to take a look at this...."

Look, this is a discussion forum about technical issues. Not a chat room. If you don't have anything substantial to contribute -- or a meaningful question to ask -- then don't post.

Edited by KC LC, 01 January 2010 - 11:36 AM.

### #14 wiiowner

wiiowner

Absolute Zero Team

• New Member
• 685 posts

Posted 01 January 2010 - 10:16 PM

This site has some good theoretical ideas for generating maps that aren't for any language in particular but are more general processes that can be implemented into GM quite easily. In another section they also explain ways to place tiles on the grid.
The method is basically selecting a starting point and then selecting one of the neighboring cells and setting all of the ones around them to the "available" state. You can then either select one of the "available" cells randomly or pick the ones that have to most filled cells around them (or the other way around if you prefer a more scattered approach). It also has some good explanations for having themed zones (ie. forest, desert) and different ways of connecting the zones together.

Edited by wiiowner, 01 January 2010 - 10:21 PM.

• 0
Completed Projects: Eco-Chrome || Conway's Game of Life - Update that triples framerate!
Scripts: Grid Based Lighting (With Dynamic Soft Shadows) || Mud Physics

### #15 Sinaz

Sinaz

MCP Killer

• GMC Elder
• 2751 posts
• Version:GM8

Posted 11 January 2010 - 08:13 PM

One thing I notice in those sorta noise generated terrains is that there are no smooth coastlines.

I'd like to know a bit about how LunarCell by Flaming Pear generates their terrain. I've been trying to find some relevant articles, but just cannot.
• 0
S I N A Z

That's SINAZ... He fights for the Users.

I am retired from providing GML Mentorship, but I am available to answer questions about career and educational goals & strategies to members who are interested in pursuing game development as a life long profession. Just PM me!

### #16 Yourself

Yourself

The Ultimate Pronoun

• GMC Elder
• 7352 posts
• Version:Unknown

Posted 11 January 2010 - 08:39 PM

One thing I notice in those sorta noise generated terrains is that there are no smooth coastlines.

I'd like to know a bit about how LunarCell by Flaming Pear generates their terrain. I've been trying to find some relevant articles, but just cannot.

One thing to look into are erosion algorithms. For the most part, pure noise doesn't make a very good heightmap. You have to do some kind of post-processing which is usually some kind of simulated erosion. Have a look at this paper for more on that:

http://oddlabs.com/d..._generation.pdf

They go over not only erosion algorithms, but also the methods for generating the noise.

I should mention that I couldn't really reproduce their results exactly. My implementation of their final algorithm (which is the same as the pseudocode given) produces a lot of artifacts. These artifacts are single pixels which have a height value considerably higher than their neighbors.

Edited by Yourself, 11 January 2010 - 08:44 PM.

• 0

### #17 xot

xot

GMC Dismember

• GMC Elder
• 4785 posts
• Version:GM:Studio

Posted 11 January 2010 - 09:55 PM

The nicest erosion modelling I've ever seen is in the program World Machine.

http://www.world-machine.com/

The output from that program is beautiful and it's node-based terrain design system is extremely powerful.

In the past, with height maps, I've used a simple median-style filter biased to selected the lowest sample. It works OK and is simple to understand. It might work better if applied at multiple scales and intensities as part of a midpoint displacement system.

The multifractal noise technique I mentioned earlier specifically tries to flatten out valleys which gets you smoother coastlines and what can pass for alluvial plains. A variant called a ridged multifractal attempts to accentuate mountain ridgelines as well. Just having those simple kinds of variation between low altitudes and high altitudes goes a long way towards improving realism.
• 0

If any of my posts contain broken images or links, I can probably supply them for you. PM with a link to the post.

### #18 icuurd12b42

icuurd12b42

Self Formed Sentient

• GMC Elder
• 18181 posts
• Version:GM:Studio

Posted 12 January 2010 - 05:18 AM

I used xot linked site for terrain generation (his other post, not this ^^ one)... Actually, terrain deformation as the terrain need initial data to start with... it's not 100%

Edited by icuurd12b42, 12 January 2010 - 05:22 AM.

• 0

I FRANTICALLY MADE MY 18000 POST TOPIC BEFORE MIKE ANNOUNCED A DELAY...
Now I'm squirming not to hit that reply button

### #19 Aethelwulffe

Aethelwulffe

GMC Member

• GMC Member
• 118 posts

Posted 13 January 2010 - 02:38 PM

I just came up with my first generation isometric random terrain generator myself.
Mind you, I don't really quite know your objectives here. Rogue was a 1983 dungeon game, so for that purpose, I don't get the world gen thing. That being said, I am VERY interested in generating planetary maps, especially if they are of high enough quality to use as planetary textures later on....
For my game, I would also like a planetary map generator. I use isometric terrain in some parts of the game, and 2d in others. Planetary landing scenes, and atmospheric flight would be nice in small scale 2d, as would "maps".
I learned some important things in my 8 hours first gen room generator coding session:
1. Leave room in the code. Breaking it up into scripts will enable you to easily modify multiple levels of arguments.
2. If the maps or sub-maps are supposed to be repeatable, use a map grid system (cartesian whatever) to generate the random seed. That way, if the character is at grid x-4, y10, and you use the product of these two numbers to generate the random seed, then the randomly created map at that location will be the same every time the player visits it.

Edited by Aethelwulffe, 25 February 2010 - 09:33 PM.

• 0

### #20 xot

xot

GMC Dismember

• GMC Elder
• 4785 posts
• Version:GM:Studio

Posted 14 January 2010 - 09:44 PM

I learned some important things in my 8 hours first gen room generator coding session:

3. Find the Enter key because lines of code that are 464 characters long are extremely hard to follow and make your posts difficult to read.
• 0

If any of my posts contain broken images or links, I can probably supply them for you. PM with a link to the post.

### #21 PlasticineGuy

PlasticineGuy

GMC Member

• New Member
• 2384 posts

Posted 15 January 2010 - 02:23 AM

That code hurts my eyes.
• 0

### #22 Schyler

Schyler

Noskcirderf Derf

• GMC Member
• 2680 posts
• Version:GM:Studio

Posted 16 January 2010 - 03:08 AM

That code hurts my eyes.

Agreed. I find irony in the first thing he said

Out of interest, how long does that Jar take to render? I can't test it myself, it dosn't seem to be working for me.

-Schyler-
• 0

### #23 xDanielx

xDanielx

GMC Member

• GMC Member
• 1002 posts
• Version:Unknown

Posted 16 January 2010 - 10:19 AM

Sorry to hear the JAR isn't working for you, can't think of why that might be. For a 512*512 terrain, the generation takes a few hundred milliseconds.

The one thing I don't like about it, and other generators that take a similar approach, is that I can't see a nice generalization into the third dimension.
• 0

### #24 xot

xot

GMC Dismember

• GMC Elder
• 4785 posts
• Version:GM:Studio

Posted 21 January 2010 - 06:14 AM

It can easily be extended to other dimensions, but the result wouldn't make a very good landscape. It'd be more like a hypertexture or isosurface.

http://mrl.nyu.edu/~...c/hypertexture/

Edited by xot, 28 November 2015 - 08:02 PM.

• 0

If any of my posts contain broken images or links, I can probably supply them for you. PM with a link to the post.

### #25 nick1965

nick1965

GMC Member

• New Member
• 88 posts

Posted 24 February 2010 - 01:50 AM

Ok well I got an idea, too busy to actually figure it out, but here's how it works.

First, you randomly place maybe 5 massive blocks, like 48 * 48 blocks.

Then use some kind of grid to randomly add single pixels ONLY around the edges of the 48*48 blocks.

This way you would get several equally sized, randomly placed, random coastline islands.

Hope I helped =)

~Nick
• 0

### #26 freko

freko

The Professional

• GMC Member
• 504 posts
• Version:GM8

Posted 08 March 2010 - 08:44 AM

Out of interest, how long does that Jar take to render? I can't test it myself, it dosn't seem to be working for me.

Pretty fast. Yes a few milliseconds and has good setup as well
• 0
Nemesis | 3D Rts Engine
Shadow RT Engine| Freko Vehicle Engine
_____________________________________________________

Phoenix Artist blog

### #27 vdweller

vdweller

GMC Member

• GMC Member
• 212 posts
• Version:Unknown

Posted 19 March 2010 - 09:25 PM

I managed to put together a planet surface creation script for a project involving random planet creation. Here are some screenies with the results (click on the thumbs for larger size):

Earth-like

http://s114.photobuc...ent=ss58937.jpg
Jungle

http://s114.photobuc...ent=ss58970.jpg
Barren

http://s114.photobuc...ent=ss58757.jpg
Oceanic

http://s114.photobuc...ent=ss58054.jpg
Icy

http://s114.photobuc...ent=ss58542.jpg
Volcanic

If you're interested in the script, let me know.

PS It is quite slow. It takes 4,5 seconds on my Dual Core 2.13MHz to create a 400x300 map. These screens are from a 180x180 map, 2x scaled (takes about 0.88 seconds).

Edited by vdweller, 19 March 2010 - 09:26 PM.

• 0

### #28 varuks

varuks

GMC Member

• New Member
• 982 posts
• Version:Unknown

Posted 20 March 2010 - 01:57 PM

Whell i am gona make an example that shows what is my idea of making random levels! It is probably not as mathematical as optimistic.

The thing is this: First the entire screen is fillen with cubes about (random(32)) pixels wide and long. Then you make some kind of amount of objects that have a random x and y.

then every point or object makes an instance that flies to some other point whilst destroying any block it touches(it can also have a curl)

While they fly they can make small semi objects that also fly in some direction and have a life time(this makes small tunels and dead ends)

when the instances touch some other point they get destroyed!

It neads some improvement but it wourks good for a spelunky type game!
• 0
All human life is equal, true. But not all humans are equal. Some through their stupidity become less superior than others through their wisdom...

### #29 Boreal

Boreal

C++ Wackjob

• GMC Member
• 417 posts
• Version:None

Posted 22 May 2010 - 12:27 PM

I'm making a roguelike for comp06, and I have been trying to find a good way to generate dungeons.
Just now I found this article, which gives a very interesting way to generate a realistic dungeon.

It basically works using a tree to store sub-dungeons, splitting sub-dungeons into further sub-dungeons, and then linking them up to their sisters and parents.
• 0

### #30 YellowAfterlife

YellowAfterlife

GMC Member

• Global Moderators
• 4157 posts
• Version:GM:Studio

Posted 22 May 2010 - 01:07 PM

I'm making a roguelike for comp06, and I have been trying to find a good way to generate dungeons.

Judges don't seem to be keen on roguelike (and\or turnbased) games.

My comp05 comp05 entry had done quite poorly, in fact I don't know if it was even actually played by judges.
I've since posted the dungeon generator code that I've made for it.

• 0
If my posts contain broken links, try looking around my website. I gradually make blog posts for any examples I make.

### #31 xot

xot

GMC Dismember

• GMC Elder
• 4785 posts
• Version:GM:Studio

Posted 22 May 2010 - 09:30 PM

Baloney. If something of the caliber of Spelunky was submitted it would easily win, but yeah, I'd avoid highly traditional rogue-very-much-likes.

Spelunky uses a pretty great method for dungeon generation. It uses 10x8 tile prefabs (called "rooms") that are randomly assembled together in a grid. The rooms are constrained to follow a random path that goes from the start to the exit via their connected/open sides. The prefabs can include blocks that change based on random factors, and they are sometimes further augmented by smaller, randomly selected prefab 5x3 groups of blocks (called "obstacles") inserted within the rooms. This approach makes perfect sense for a platformer since you need tight control over the height of things in order to make them a jumpable height (or a survivable fall). It also allows you to create certain "interesting" situations that will bite the player square in the ass if they're not paying attention.
• 0

If any of my posts contain broken images or links, I can probably supply them for you. PM with a link to the post.

GMC Member

• GMC Member
• 1615 posts

Posted 22 May 2010 - 09:58 PM

I'm making a roguelike for comp06, and I have been trying to find a good way to generate dungeons.
Just now I found this article, which gives a very interesting way to generate a realistic dungeon.

It basically works using a tree to store sub-dungeons, splitting sub-dungeons into further sub-dungeons, and then linking them up to their sisters and parents.

That's actually quite an interesting method. It also eliminates problems caused by "carve" methods when having to check if there's enough space to dig a room. If coupled with a Voronoi diagram, you could get some interesting results - just make sure to use a flood fill algorithm to avoid generating too small of a room.
• 0

#gmc - It's like that treehouse club you always wanted to join

### #33 Rani_sputnik

Rani_sputnik

GMC Member

• GMC Member
• 482 posts
• Version:GM:Studio

Posted 24 November 2010 - 09:06 PM

Ummm it's been a while... but I have an idea (That isn't mine, I just found it haha)

Take a look at this vid. It's a demonstration of the tools the Spore artists used to create their planets. The paper that goes with this is here.

I liked the fact that their method gives a lot of control while also allows complete randomness, so I am going to try to replicate it (in 2d of course). This is what I plan to do.

Define a bunch of parameters for splines.
Create a path that will store the spline generation.
Pick a random point on the map and use this as the starting condition.
Add this point to the path and pick a random direction.
Head in the current direction, placing new points based on the spline settings.
Once the edge of the map is reached either stop, wrap or start a new path.

Now that we have a path, clear the screen black.
Draw grayscale sprites along the path to create a feature along that spline.
Save the screen as a sprite.

This will generate a heightmap very quickly as there is very little math involved. In some preliminary tests I was getting 30fps generating one per frame o.O The next step however will take a while and that is extracting heights from the heightmap though I have seen a little script that speeds up draw_getpixel by about 7 times. If anyone knows of a another way to extract the heightmap please let me know... It takes ages!

The final step would be to adjust visuals based on the created heightmap. I thought for texture mapping, a really quick way would be using gameGod's (I think it was him) meta-ball script (Which is incredibly fast 2800 instances @30fps). It creates surfaces rally effeciently but simply drawing out anything with an opacity that was too low.

Conclusions -> Don't use these math heavy techniques in Game Maker, it is just too slow. Make the graphics do the work.

Hope this helps anyone still interested in this topic, I'll try get a nice example uploaded soon. Cheers.
• 0

My games - In DecemberBoy Goes to Space

Utilities & Extensions - FloxGM

### #34 Zerb Games

Zerb Games

GMC Member

• GMC Member
• 155 posts
• Version:GM:Studio

Posted 04 June 2015 - 03:24 AM

I wrote this in 2006, written in GM6: http://64digits.com/...i...ame&id=1246
I do have other versions that have height mapping, wrap-around worlds and weather systems et cetera if anyone is interested.

Sorry for the 6 year late response but I would be interested in the one with height mapping, wrap-around worlds and weather systems et cetera.  I really liked the one you had on 64 digits except for the fact that the civilizations didn't work.

• 0

-Stay Royal

### #35 Juju

Juju

GMC Member

• GMC Member
• 1109 posts
• Version:Unknown

Posted 04 June 2015 - 01:53 PM

Blimey, quite the necropost! I'll see what I can whip up tonight for you.

• 2

Try out my open-source 3D globe terrain generator!

How about a fancy-pants text engine?

Adding dialogue boxes to your games is now super easy. Also localisation. Also tweening.

### #36 Zerb Games

Zerb Games

GMC Member

• GMC Member
• 155 posts
• Version:GM:Studio

Posted 04 June 2015 - 08:36 PM

Thanks that would be much appreciated.

• 0

-Stay Royal

### #37 Juju

Juju

GMC Member

• GMC Member
• 1109 posts
• Version:Unknown

Posted 04 June 2015 - 11:19 PM

https://www.dropbox.... Model.gmz?dl=0

Use the arrow keys to manually spin left and right.

Doesn't include a weather model because it's gone midnight and I had a long day, but does have a neat pseudo-3D spinning planet to show off the wrap-around part though. It does run a bit slowly despite some trig approximations, it seems like this is down to the vast number of rectangles that I'm drawing rather than the maths. Current map it generates is 180x90, for comparison the largest map that Civ 5 generates is 128x80 (can't remember what size Civ 4 would go up to).

If people are running different version of GM (this is for Studio) then I can post the source manually - it's only four mid-length scripts.

Edited by Juju, 04 June 2015 - 11:20 PM.

• 3

Try out my open-source 3D globe terrain generator!

How about a fancy-pants text engine?

Adding dialogue boxes to your games is now super easy. Also localisation. Also tweening.

### #38 Zerb Games

Zerb Games

GMC Member

• GMC Member
• 155 posts
• Version:GM:Studio

Posted 04 June 2015 - 11:30 PM

Dude you are the best I freaking love you (no homo whatever I don't care I said it)!  Another thing, if I may ask how would I be able to replace sprites with objects?  Or place objects where there are sprites I know it would have something to do with this variable: global.terrain_grid right? Oh and why a .gmz I use gm 8.1 so do you have a gmk?

If people are running different version of GM (this is for Studio) then I can post the source manually - it's only four mid-length scripts.

Edited by Zerb Games, 04 June 2015 - 11:40 PM.

• 0

-Stay Royal

### #39 Juju

Juju

GMC Member

• GMC Member
• 1109 posts
• Version:Unknown

Posted 05 June 2015 - 07:35 AM

Alright, here we go. You only need one object and one room, though the room should be at least be 800 x 800. This is a lot more basic than the 64D example but you can apply the same techniques to get a suitable solution.

Create event

```globalvar deltatime; //Deltatime functionality is game-wide, might as well be a globalvar
deltatime = 1;

x = room_width/2;
y = room_height/3; //Centre point of the planet "model"

res = 2; //Angular resolution of the longitude (x) coordinates, in degrees. This should probably be a number that divides 180 into a whole number
disk_size = 20; //Circle size used during generation
rotation_speed = 2; //Degrees per turn to spin

var rad_res = degtorad( res ); //Multiplier that turns tile index into radians, makes things a bit quicker

long_res = ceil( 360 / res ); //Number of tiles around the waist of the planet, all the way round
lat_res = ceil( 180 / res ); //Number of tiles from top to bottom, only halfway round though (planet model is basically a squeezed cyclinder)
scale = radius * sin( rad_res ) / 2; //Drawing scale of the tiles on the planet

rotation = 0; //Rotation of the planet model, in degrees
auto_rotate = true; //Automatically spin the planet at the start of the game

for( var deg = 0; deg < long_res + 1; deg++ ) {

var real_deg = deg * rad_res;

sin_of_deg[ deg ] = sin( real_deg ); //Generate two trig look up tables
cos_of_deg[ deg ] = cos( real_deg );

}

height_grid = ds_grid_create( long_res, lat_res ); //Our height map
colour_grid = ds_grid_create( long_res, lat_res ); //Our colour map for different "terrain" types
var wrap_grid = ds_grid_create( long_res + disk_size * 2, lat_res ); //Our height map with extra allowance for overspill from the circle-based generator

ds_grid_clear( height_grid, 0 ); //Make sure it's a clean slate
ds_grid_clear( wrap_grid, 0 );

for( var long = 0; long < long_res; long++ ) { //Actual generation. Super simple
for( var lat = 0; lat < lat_res; lat++ ) {
ds_grid_add_disk( wrap_grid, long + disk_size, lat, disk_size, 1 - random( 2 ) ); //Note "+ disk_size" horizontal offset
}
}

for( var long = 0; long < disk_size; long++ ) {
for( var lat = 0; lat < lat_res; lat++ ) {

var val = ds_grid_get( wrap_grid, long, lat );
ds_grid_add( wrap_grid, long_res + long, lat, val ); //Wrap left-most overflow onto the right hand side

var val = ds_grid_get( wrap_grid, long_res + disk_size + long, lat );
ds_grid_add( wrap_grid, disk_size + long, lat, val ); //Wrap right-most overflow onto the left hand side

}
}

for( var long = 0; long < long_res; long++ ) {
for( var lat = 0; lat < lat_res; lat++ ) {

var val = ds_grid_get( wrap_grid, long + disk_size, lat );
ds_grid_set( height_grid, long, lat, val ); //Copy across from one grid to another (yes, I know there's an in-built function to do it)

}
}

var mini = ds_grid_get_min( height_grid, 0, 0, long_res - 1, lat_res - 1         );
ds_grid_add_region( height_grid, 0, 0, long_res - 1, lat_res - 1,  -mini );
var maxi = ds_grid_get_max( height_grid, 0, 0, long_res - 1, lat_res - 1         );
ds_grid_multiply_region( height_grid, 0, 0, long_res - 1, lat_res - 1, 1/maxi ); //Normalise the height map

for( var long = 0; long < long_res; long++ ) {
for( var lat = 0; lat < lat_res; lat++ ) {

var val = ds_grid_get( height_grid, long, lat );
val = colour_continuum( val ); //Turn the height value into a colour
ds_grid_set( colour_grid, long, lat, val ); //Generate colour map

}
}

surface_sur = surface_create( long_res, lat_res ); //Create the 2D map

surface_set_target( surface_sur );
draw_clear( c_fuchsia ); //Silly colour to help detect bugs

for( var long = 0; long < long_res; long++ ) {
for( var lat = 0; lat < lat_res; lat++ ) {

draw_set_color( ds_grid_get( colour_grid, long, lat ) );
draw_point( long, lat ); //Draw the colour map with 1x1 pixel resolution to save memory - we'll be scaling this up later

}
}

surface_reset_target();

ds_grid_destroy( height_grid );
ds_grid_destroy( wrap_grid ); //Free up some memory
```

Step event

```deltatime = min( 4, room_speed / ( 1000000 / delta_time ) ); //delta_time is measured in microseconds. I'm not sure GM is actually accurate down this far but whatever

if ( auto_rotate ) rotation += rotation_speed * deltatime; //This stuff is all kinda obvious

if ( keyboard_check( vk_left ) ) {
auto_rotate = false;
rotation -= rotation_speed * deltatime;
}

if ( keyboard_check( vk_right ) ) {
auto_rotate = false;
rotation += rotation_speed * deltatime;
}

rotation = ( rotation + 360 ) mod 360; //Make sure we don't get a negative rotation - causes bugs otherwise
```

Draw event

```texture_set_interpolation( false );
draw_surface_ext( surface_sur, x - long_res, ( room_height - (y+radius) ) / 2 + (y+radius) - lat_res, 2, 2, 0, c_white, 1); //Draw the 2D map
texture_set_interpolation( true );

d3d_transform_set_identity();
d3d_transform_add_translation( x, y, 0 ); //Neat little hack to offset further draw calls

for( var long = 0; long < long_res; long++ ) {

var real_long = ( long * res + rotation ) mod 360; //Spins the planet round, making sure we're offseting tiles appropriately

if ( real_long > 180 ) { //...though obviously everything behind the planet we want to skip drawing (fancier people would call this "backface culling")

ipart = floor( real_long / res ); //Turn the rotation angle back into a tile coordinate as a estimate for the trig look up table
fpart = frac( real_long / res );

var sin_of_real_long = lerp( sin_of_deg[ ipart ], sin_of_deg[ ipart+1 ], fpart ); //Do an estimate on a trig value by interpolating between two known values
var cos_of_real_long = lerp( cos_of_deg[ ipart ], cos_of_deg[ ipart+1 ], fpart );

var real_x_scale = scale * sin_of_real_long; //This shrinks the x-axis scale to give the illusion of perspective. It's crude

for( var lat = 0; lat < lat_res; lat++ ) {

var colour = ds_grid_get( colour_grid, long, lat ); //Get the colour of the tile
draw_set_color( colour ); //...and set it

var sin_of_real_lat = sin_of_deg[ lat ]; //Look up trig values for this latitude
var cos_of_real_lat = cos_of_deg[ lat ];

var xx = cos_of_real_long * sin_of_real_lat; //Turn the spherical coordinates into (unit length) cartesian coordinates
var yy = -cos_of_real_lat;
var real_y_scale = scale * sin_of_real_lat; //This time, shrink the y-axis scale to give the illusion of perspective

var xxx = xx * radius; //Turn the unit coordinates (radius of length 1) into actual coordinates for display
var yyy = yy * radius;

draw_rectangle( xxx - real_x_scale, yyy - real_y_scale, xxx + real_x_scale, yyy + real_y_scale, false ); //Actually draw the damn tile

}

}
}

d3d_transform_set_identity();
draw_set_color( c_white );

draw_text( 10, 10, string( fps ) );
draw_text( 10, 30, string( long_res ) + " x " + string( lat_res ) );
```

Script, named colour_continuum

```var val = argument0;
var colour = c_fuchsia;

var div_a = 0.5; //start of plains
var div_b = 0.7; //start of forest
var div_c = 0.8; //start of mountains

if ( val < div_a ) {
colour = merge_color( c_blue, c_aqua, val / div_a );
} else if ( val < div_b ) {
colour = merge_color( c_lime, c_green, ( val - div_a ) / ( div_b - div_a ) );
} else if ( val < div_c ) {
colour = merge_color( c_green, c_maroon, ( val - div_b ) / ( div_c - div_b ) );
} else {
colour = merge_color( c_maroon, c_white, ( val - div_c ) / ( 1 - div_c ) );
}

return colour;
```

Regarding objects versus sprites, be very careful about creating too many objects in your game. I can't remember what size map that program produces but even at 50x50 you're creating 2'500 objects.

Edited by Juju, 05 June 2015 - 07:40 AM.

• 1

Try out my open-source 3D globe terrain generator!

How about a fancy-pants text engine?

Adding dialogue boxes to your games is now super easy. Also localisation. Also tweening.

### #40 Juju

Juju

GMC Member

• GMC Member
• 1109 posts
• Version:Unknown

Posted 23 June 2015 - 03:30 PM

Quick bump with a proc gen engine that works in 3D on a geodesic grid: https://www.dropbox....distro.zip?dl=0

Screenshot here: http://imgur.com/vCenQdU

• 3

Try out my open-source 3D globe terrain generator!

How about a fancy-pants text engine?

Adding dialogue boxes to your games is now super easy. Also localisation. Also tweening.

### #41 RujiK

RujiK

GMC Member

• GMC Member
• 841 posts
• Version:GM:Studio

Posted 23 June 2015 - 06:59 PM

Juju you are the man. I didn't realize how much my life was missing until I downloaded that example.

Have all the upvotes I can give today.

EDIT: I'm surprised/impressed you gave source. If I made that I would show off screenshots and yell "ALL MINE PEASANTS! Ha ha ha!"

Edited by RujiK, 23 June 2015 - 07:01 PM.

• 0

### #42 Juju

Juju

GMC Member

• GMC Member
• 1109 posts
• Version:Unknown

Posted 23 June 2015 - 11:33 PM

Eh, I've been doing this long enough that I don't have much personal stake.

It's not perfect, still working on things...

• 0

Try out my open-source 3D globe terrain generator!

How about a fancy-pants text engine?

Adding dialogue boxes to your games is now super easy. Also localisation. Also tweening.

### #43 slayer 64

slayer 64

Slayer of gingers

• GMC Member
• 4301 posts
• Version:GM:Studio

Posted 24 June 2015 - 12:00 AM

Eh, I've been doing this long enough that I don't have much personal stake.

It's not perfect, still working on things...

that's really good. i've done similar things http://gamejolt.com/...-duffers/23917/
• 0

### #44 Juju

Juju

GMC Member

• GMC Member
• 1109 posts
• Version:Unknown

Posted 24 June 2015 - 07:48 AM

At the minute, I'm using un-textured polygons because I'm terrified of GM's draw speed. How far were you able to push your engine until it started creaking?

• 0