Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

AppGameKit Classic Chat / Help with fractal terrain generation!

Author
Message
Plotinus
15
Years of Service
User Offline
Joined: 28th Mar 2009
Location:
Posted: 30th Nov 2017 20:51
Hi there,

I've been playing around with terrain generation and had a go at writing a version of the much-utilised diamond-square algorithm (which is described all over the place, such as here). I've looked at various threads on this here and elsewhere - the best implementation I could find for my purposes is Green Gandalf's, here. It's basically amazing but doesn't quite match what I want, which is something that will generate a smooth-looking terrain over a rectangular area (roughly twice as wide as high) that wraps from left to right (but not top to bottom). I'm not adept enough at unravelling his code to adapt it.

So I've had a go at writing one of my own. As far as I can tell this really ought to work. And it does, after a fashion. But the generated terrain doesn't quite reach to the edges of the array and it doesn't wrap from east to west, although I'm sure it should. And it's got very obvious artefacts which make it unusable. It's quite pretty in its own way but not the smooth effect that I'm after... Can anyone cast their eyes over this code and spot what I'm doing wrong? Many thanks for any help anyone can give...

Plotinus
15
Years of Service
User Offline
Joined: 28th Mar 2009
Location:
Posted: 4th Dec 2017 13:51 Edited at: 4th Dec 2017 14:53
Well, looks like that either defeated everyone or failed to interest anyone!

Luckily I managed to work it out on my own. Here's the code if it helps anyone. This will generate a fractal landscape which wraps from east to west but not north to south. It does it on an array of 1025*513 and on my computer takes two seconds. You can fiddle with the map size, though it is temperamental. You can also play with the "grain" and "valuemod#" values to change the scale and roughness of the terrain.

Markus
Valued Member
19
Years of Service
User Offline
Joined: 10th Apr 2004
Location: Germany
Posted: 4th Dec 2017 22:12
Quote: "Well, looks like that either defeated everyone or failed to interest anyone!"

thanks for sharing your source code.
i don't know what to do with a generated relief map.
a random map of this kind i can also create in my paint tool, named cloud there.
i think this map is only usable for flying over in 3d. i guess that was your goal.
useless in level design as normal terrain, maybe good as template.
AGK (Steam) V2017.09.25 : Windows 10 Pro 64 Bit : AMD (17.11.4) Radeon R7 265 : Mac mini OS High Sierra (10.13)
Harlequin
14
Years of Service
User Offline
Joined: 22nd Mar 2010
Location: Melbourne (AU)
Posted: 5th Dec 2017 02:57 Edited at: 5th Dec 2017 02:59
Thank you for sharing the example, I have been attempting to do it on an off for a while, most examples I find use languages that do not seem to translate well to AppGameKit (at least with my limited skills).
So I am very interested in going through your code to understand where I was going wrong.

I have been using this site https://www.redblobgames.com/maps/terrain-from-noise/ to help me understand terrain generation better, and you code sample is kind of the missing piece (a noise source)!!

I wonder if an inbuilt Perlin noise like function would be a good thing to add to the core of AppGameKit?

Thanks

It\'s late, I\'m tired, out of coffee and now I\'m wet.
puzzler2018
User Banned
Posted: 5th Dec 2017 07:09
Thanks for sharing, I will certainly be having a look at this one when I next get chance to

Cheers

D
Phaelax
DBPro Master
20
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 5th Dec 2017 12:27
Only kind of terrain generation I've done was the fault line algorithm. Very simple. Just a few iterations and finalized with a smoothing (like neighbor averaging) and you get a decent terrain.

"I like offending people, because I think people who get offended should be offended." - Linus Torvalds
Plotinus
15
Years of Service
User Offline
Joined: 28th Mar 2009
Location:
Posted: 6th Dec 2017 21:07
Thanks for the comments, I'm glad there's interest in it!

Quote: "i don't know what to do with a generated relief map.
a random map of this kind i can also create in my paint tool, named cloud there.
i think this map is only usable for flying over in 3d. i guess that was your goal.
useless in level design as normal terrain, maybe good as template."


There are lots of things you could do with this, if you were interested in procedural generation. Dwarf Fortress uses an algorithm like this to generate its worlds. It generates not only the basic heightmap but also other global features such as drainage using the same technique. Put those together and you get a load of different biomes.

You can then use it as a base for deeper worldbuilding. I agree it's not really suitable for "level" design, but that's not the only interesting thing you can do with maps.

Also you'll notice that the newfractalinit function seeds the map with a series of random heights. You could rewrite this to use a series of predetermined heights. This would allow you to use this routine to "expand" small maps, or small parts of large maps. So suppose you had a world map and you wanted to zoom in on a small area. Instead of storing all that detail in some gigantic array, you just run it through this routine and get a massively zoomed-in map. Make sure you seed the random number generator with the same seed every time, and you'll always get the same zoomed-in region without ever having to store it when you're not looking at it.

Quote: "Thank you for sharing the example, I have been attempting to do it on an off for a while, most examples I find use languages that do not seem to translate well to AppGameKit (at least with my limited skills).
So I am very interested in going through your code to understand where I was going wrong."


Glad to help! I had been struggling with this for a long time too, even though diamond-square is always described as incredibly simple to implement, so I was really glad actually to crack it. Hopefully you can adapt this code for your purposes.

Quote: "I have been using this site https://www.redblobgames.com/maps/terrain-from-noise/ to help me understand terrain generation better, and you code sample is kind of the missing piece (a noise source)!!"


That site gets linked to a lot! It's really interesting but I agree, he doesn't explain how to generate the noise itself at all, and it is rather frustrating. I've tried to understand Perlin noise too and I haven't found any explanation or code example anywhere that I can understand well enough to even begin writing something. Diamond-square is not Perlin noise but you can obviously use it for similar purposes.

Quote: "I wonder if an inbuilt Perlin noise like function would be a good thing to add to the core of AppGameKit?"


I'd like it but I don't know how popular it would be... The closest I've seen to doing Perlin noise actually in AppGameKit is here, but this is DBPro rather than AppGameKit and I wasn't able to understand it well enough to convert!

Quote: "Only kind of terrain generation I've done was the fault line algorithm. Very simple. Just a few iterations and finalized with a smoothing (like neighbor averaging) and you get a decent terrain."


I've never been able to get it to work very well, at least not quickly!

The most effective terrain generation, though, is where you use different methods and then combine them. This is especially so if you're trying to create a large-scale map, like for an entire world, because at the global scale you get different kinds of terrains in different places. So you do something like this:

(1) Create map 1, using (say) my diamond-square method.
(2) Create map 2, using (say) Phaelax's fault-line method.
(3) Create a template map, using (say) the diamond-square method again.
(4) - the clever bit. Create the final map by averaging together maps 1 and 2 - BUT use the template map to skew it towards one or the other. E.g. where the template map has a low value, skew the corresponding point in the final map towards map 1. Where the template map has a high value, skew the corresponding point in the final map towards map 2.

The result is a map that is more like one terrain generation method in some places and more like the other in others, which gives a more natural-seeming varied effect. Of course you could combine lots of methods like this if you wanted to.

I'm doing something like this, so the map created by the code I've posted isn't the final map, it's just one of the methods I'm blending together to get the final thing.
Phaelax
DBPro Master
20
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 6th Dec 2017 22:21
Quote: "I'd like it but I don't know how popular it would be... The closest I've seen to doing Perlin noise actually in AppGameKit is here, but this is DBPro rather than AppGameKit and I wasn't able to understand it well enough to convert!"

I should be able to convert it.

Quote: "The most effective terrain generation, though, is where you use different methods and then combine them"

Totally agree!

"I like offending people, because I think people who get offended should be offended." - Linus Torvalds
nz0
AGK Developer
16
Years of Service
User Offline
Joined: 13th Jun 2007
Location: Cheshire,UK
Posted: 10th Dec 2017 02:40
I adapted Green Gandalf's diamond square to AppGameKit long ago in AGK1 !
Is that any use? I actually wanted it to edge loop, so diamond square was perfect.

I used it to generate (height) maps and even had something to detect and generate sea ports for some game I was doing.

After some scratching around I see I still have the source code from 2014

Here's a screen shot of a random generated map

Attachments

Login to view attachments
MikeMax
AGK Academic Backer
12
Years of Service
User Offline
Joined: 13th Dec 2011
Location: Paris
Posted: 10th Dec 2017 11:18
Great result nz0 !
Plotinus
15
Years of Service
User Offline
Joined: 28th Mar 2009
Location:
Posted: 10th Dec 2017 20:33
Looks good, nz0! I dont need it myself as I did my own conversion of Green Gandalf’s code for my own purposes, before managing to produce my own version of diamond-square instead to replace it, which does exactly what I need it to. But I’m sure other people might find it useful.

Login to post a reply

Server time is: 2024-03-28 21:16:40
Your offset time is: 2024-03-28 21:16:40