Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


We're also offering banner ads on our site from just $5! 1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Random Map generator needs improvement


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
7 replies to this topic

#1 Dan Violet Sagmiller   Members   -  Reputation: 896

Like
1Likes
Like

Posted 18 April 2013 - 09:02 AM

I have a random map generator, that essentially uses the X/Y location of the tile as the seed to identify its tile type.  (infinite terrain without needing to save it)

 

However, its too random.  the terrain is peppered with any terrain type.  I would like it to be more splotchy.

 

What I was planning, was to divide it into regions (like x >> 4, y >> 4) of 16x16 to increase the likely hood of a particular type, but then I end up with squares.  any thoughts? 

 

Here is the code I use:  

 

    public static int PickANumber0ThoughN(int seed, int x, int y, int range)
    {
        uint hash = (uint)seed;
        hash ^= (uint)x;
        hash *= 0x51d7348d;
        hash ^= 0x85dbdda2;
        hash = (hash << 16) ^ (hash >> 16);
        hash *= 0x7588f287;
        hash ^= (uint)y;
        hash *= 0x487a5559;
        hash ^= 0x64887219;
        hash = (hash << 16) ^ (hash >> 16);
        hash *= 0x63288691;
        return (int)(hash % range);
    }
int tileTypeId = PickANumber0ThoughN(playerid, tileX, tileY, TileTypes.Length) - returns a seemingly random tile, that is the same every time the method is called.  I'm considering ways. to improve that to make larger blocks of random code, without adding much cost here.  Any ideas? I'm not opposed to using polar coordinates, 

Edited by Dan Violet Sagmiller, 18 April 2013 - 09:04 AM.

Moltar - "Do you even know how to use that?"

Space Ghost - “Moltar, I have a giant brain that is able to reduce any complex machine into a simple yes or no answer."

Dan - "Best Description of AI ever."

My Game(s), Warp Wars is in early development and can be found here: http://blog.WarpWars.Net.


Sponsor:

#2 JTippetts   Moderators   -  Reputation: 8575

Like
3Likes
Like

Posted 18 April 2013 - 09:15 AM

The typical tool used for this sort of thing is continuous noise (aka, Perlin noise and variants). Such functions can be constructed to be infinite (or at least practically infinite, within the limits imposed by data types) and can be layered upon one another to create more complex terrain. Noise is excellent for outdoor/natural areas, but less excellent for artificial terrain constructions (forts, towns, etc...)

Edit:
To illustrate, here is an image of some noise patterns I had generated a couple years ago using my noise library, and posted in my journal...

PIZ19ie.jpg

If you generate a function like one of these (or any of an infinite number of other patterns) and assign values of gray to different tile types, you can end up with some pretty decent looking terrain.

Edited by JTippetts, 18 April 2013 - 09:22 AM.


#3 Norman Barrows   Crossbones+   -  Reputation: 2204

Like
0Likes
Like

Posted 18 April 2013 - 11:56 AM

an interesting challenge.

 

terrain that makes sense, randomly generated, on the fly, no saving to disk or ram.

 

can you lose the "no saving to ram" requirement, and generate sections at a time in ram at least? if so you can apply more sophisticated distributions to your tile patterns, but the algos may not be fast enough to do it from scratch every frame for every tile.

 

essentially, you'd have part of your world map stored in memory, probably the usual 9 regions paging method. but in your case, you don't page, you generate. but since the algos define multiple tiles at once, you have to store the results in ram, and can't just generate one tile at a time if it happens to need drawing. well, you could, but it probably would be too slow.

 

the algos themselves are your typical splotch based stuff. as long as you keep it deterministic, you should be able to generate anything anybody else does. 


Norm Barrows

Rockland Software Productions

"Building PC games since 1988"

 

rocklandsoftware.net

 


#4 Nercury   Crossbones+   -  Reputation: 770

Like
0Likes
Like

Posted 18 April 2013 - 12:15 PM

You can copy the initial permutation idea from the Perlin noise: basically, you have a permanent 256-sized array which points to a numbers from 0 to 255, call it "permutations". Then your "random" hash number at a specific integer point would be:

 

int X = (int)Math.floor(x) & 255;
int Y = (int)Math.floor(y) & 255;
int Z = (int)Math.floor(z) & 255;

int hash = permutations[X];
hash = permutations[hash + Y];
hash = permutations[hash + Z];

 

 

Also the trick is to expand the 256-sized array and clone the copy of the same numbers to the second half, so you don't need to check for array overflow when adding the coordinates.

 

You get more variations by interpolating between these values and blending more noises at different scales.

 

Perlin noise is here: http://mrl.nyu.edu/~perlin/noise/. 3D Perlin noise additionally interpolates between 12 points, plus 4 point simplex shape.

Although you would want to use improved Perlin noise, which uses 4 point simplex for 3D and 3 point triangle for 2D, which is aptly called Simplex Noise.


Edited by Nercury, 18 April 2013 - 12:21 PM.


#5 Dan Violet Sagmiller   Members   -  Reputation: 896

Like
0Likes
Like

Posted 18 April 2013 - 12:21 PM

@Norman

Here is the reason I'm trying to avoid saving chunks of data.  When the server needs to know something, like if a building can go in a particular spot, it needs to check all the tiles that it will be on to make sure they are buildable.  As in not water for instance.  If I did chunks, then for each check, it has to build that entire chunk, Suppose a building is 2x2 tiles, and that is right on a division between four chunks.  Then it has to build up all 4 chunks of data just to check 4 tile ids.  

 

So it is for the server's sake that I am trying to avoid this. 

 

also, @JTippetts

Some of what that produced was awesome.  exactly the types of layouts I would like to see.  But it also looks like its building in large chunks, not so much pixel by pixel.  (as in a function/pattern will adjust many pixels at a time, so if you didn't preprocess that, how much work would it take to implement something like that per pixel for checking.  

 

 

*Possible Idea...

(PreviousRandom = where the current code leaves off and was about to return)

X>>3&7&previousRandom = obtaining bits 0 1 2 3 4 5 (giving blocks of 8*8 the same base randomizers), as 0 through 7.  It increases the odds for the value to be 0, then 1,2 or 4, then 3,5,6 then 7 from highest to lowest order.

I can repeat the same pattern on the Y side. 

Each value can link to something that will alter the odds of particular tile types, for instance, I could make

: 0 grass, just all grass.  No more mods.

: 1,2,4 Grass mostly, but with water as an alternative.

: 3 = grass at edges, another tile type massed through the center

: 5 = additional rock focus.

: 6 = additional forrest focus.

: 7 = Forest.

 

That would be the X effect, and Y could have its own modifying alterations.  Perhaps the top corner pieces, can even look up its 2 neighbors to modify its likely hood of a particular type.

 

I think this gives me some more tweaking room without particularly expanding on the processing level too much.


Edited by Dan Violet Sagmiller, 18 April 2013 - 01:45 PM.

Moltar - "Do you even know how to use that?"

Space Ghost - “Moltar, I have a giant brain that is able to reduce any complex machine into a simple yes or no answer."

Dan - "Best Description of AI ever."

My Game(s), Warp Wars is in early development and can be found here: http://blog.WarpWars.Net.


#6 JTippetts   Moderators   -  Reputation: 8575

Like
3Likes
Like

Posted 18 April 2013 - 05:59 PM

also, @JTippetts
Some of what that produced was awesome.  exactly the types of layouts I would like to see.  But it also looks like its building in large chunks, not so much pixel by pixel.  (as in a function/pattern will adjust many pixels at a time, so if you didn't preprocess that, how much work would it take to implement something like that per pixel for checking.

Every single pattern in the image I posted was the result of a mathematical function composed of noise layers plus various transforms and modifiers. Every single one was callable on the single-pixel level, and not generated as a chunk, and thus would be suitable for a streaming infinite world generated on-the-fly.

Edit:

For further clarification, here is an old journal post detailing the beginnings of the generator I use for generating islands in Goblinson Crusoe. A sample:

WD5BvgH.jpg

The island is constructed from pure math functions:

1) A sphere forms the basic island shape
2) 2 layers of Perlin noise distort the sphere to give the sphere a cool island-y shape
3) Various layers of noise are blended together to delineate areas of mountain or lowland
4) Various layers of noise are blended together to delineate areas of forest or open
5) Various layers of noise are blended together to delineate areas of wet or dry
6) Additional layers are used to composite all the selected types together.

The actual chain used is posted as a snippet of Lua code at the end of that article. Every building block of the function is either a) Some form of signal generator (noise, pattern, etc...), b) Some sort of combiner that combines the results of a number of functions (add, multiply, select, blend, etc...) c) Some sort of modifier that modifies the output of a function (like pow, sin, curve, etc...) or d) Some sort of transformation that modifies the input coordinates of functions above it in the chain. By combining these basic, simple blocks some pretty complex patterns are formed.

The result is a function that you can call at any point in the domain -1<x<1 and -1<y<1 to obtain the type of terrain at that location. In a similar fashion, you could construct such a layered system to build your large streaming world. (To make it truly infinite, you would probably eliminate the sphere and just use another fractal layer to select between land and ocean instead.) Give the function chain a different seed and an entirely different world is generated, with near-infinite possibilities. (Near infinite due to the seed being unsigned int type, and thus limited to a huge number of variations).

To generate the greyscale images I posted earlier, I constructed a Lua script that would recursively construct a function tree using randomly selected function pieces, then map a segment of it to an image and save the image to a folder. I turned the script loose when I went to work and when I returned home, I had a whole folder full of cool patterns (and a veritable mass of not-so-cool ones) to select from. In later variations of the theme, I also stored a Lua table describing the structure of the function so that I could have the patterns in a library to choose from. In the absence of any sort of visual exploration tool, this is really the only way to generate cool patterns without spending hours trying different combinations, but it really does pay off if you need a lot of different and cool patterns.

Edited by JTippetts, 18 April 2013 - 06:19 PM.


#7 FLeBlanc   Crossbones+   -  Reputation: 3109

Like
1Likes
Like

Posted 19 April 2013 - 03:54 PM

I've done this sort of thing before, and I always used Perlin noise as JTippetts suggested.

Note that some things are pretty difficult to do with purely math methods, such as erosion. There are some tricks you can do with a Perlin function, such as using the derivative of the function at the given point, to sort of fake erosion but it's just never going to look as good as an explicit pass across a buffer of data using Navier-Stokes or some other approximation. Of course, if you're doing a tile game, then good looking erosion probably isn't a necessity. biggrin.png

If you have to do any after-the-fact modification to the terrain, or if you want to add things like roads, then again you will probably need to be able to work with chunks of data. Pure mathematical procedural roads are a BEAST to implement, and only rarely to they look good, but you can make them look okay if done as a post-processing pass after chunk generation.

#8 JTippetts   Moderators   -  Reputation: 8575

Like
2Likes
Like

Posted 20 April 2013 - 05:25 AM

Yeah, erosion and roads can be tricky. I do use erosion on the maps in Goblinson Crusoe to help with river and lake placement, but it's a lot easier in my case since I'm not streaming a continuous world. There are a couple of noise variants described here that use the derivative of preceding noise layers to affect latter noise layers (some of the "tricks" that FLeBlanc may have been talking about). The Swiss variant described at that link, especially, gives the appearance of an eroded terrain. It still doesn't really help with rivers, though. I still haven't found what I would consider a good technique for procedural rivers on procedural terrain that doesn't involve simulating a process over an entire chunk.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS