@Locomule and I have been playing with tiled worlds recently - he's been doing clever tricks with tiling images, and I've been trying to generate infinite play fields procedurally.

I'm now at the stage where I understand what needs to be done, but it turns out that doing it is not as simple as it looks.

Here's how a procedural world generator works: for each tile position (x, y) you evaluate a function f(x,y) that returns a tile number.

Let's say you have 16 tile shapes, then a simple generator would return values in the range 0..15

So f is really f(x, y, n) with n being the number of different values that can be returned.

Every time that f is called with the same x,y,n parameters, it should return the same result in the range 0..n-1.

That would be enough to make this work - as long as it didn't lead to repetitive patterns in the tiles. You would think it would be an easy function to write, but you should try it and see what happens…

Now to do a really good map generator, the situation is a bit more complex than this. You don't just pick a random tile number, because you want tiles to join up with their neighbors, for example if the tileset is a railway, and you have a track exiting the tile on the East side, then the tile to the right of it had better have a track entering from the West side so that they join up.

The way we make this work is by first deciding what happens at the boundaries between tiles, and then choosing the tile that fits those edge cases.

Lets say the tiles are simple and either have a path that crosses any edge or no path. There's no third option such as a river or something else that crosses between tiles. It's either a path or nothing (ie ground).

So we assign a 0 to an edge for ‘no path’ and a 1 to an edge for ‘path’. Since there are four edges, each tile can be defined by four random numbers in the range 0..1. For instance a tile with a path North, a path East, and a path South but none to the West would have edge codes 1,1,1,0. This is the same as choosing tile no 14 (binary 1110).

So our procedural generator evaluates 4 function calls of f(x, y, 2). One for the West side of square x,y; one for the South side of square x,y, and one for the East side of square x,y which is identical to the West side of square x+1,y; and one for the North side of square x,y which is identical to the South side of square x,y+1.

Again, seems like a simple specification, right?

But did you notice that the parameters of f for the west edge are the same as for the south edge? If we do a simple function, it will always return the same result for both the west edge and the south edge, which means that the world will have a weird diagonal bias. So our function has to be slightly more complex again, with an extra parameter which says if the edge we're asking for is horizontal or vertical,

ie f(x, y, orientation, range)

I have created a test bed that uses this definition - can you write the function ‘f’ that makes it look good and doesn't repeat patterns?

https://scratch.mit.edu/projects/127872959/

Thanks!

Not sure I'm quite getting your explanation.

Not sure it will be possible to have no repeat patterns but might be able to get it so the repeats are far enough apart.

One idea, don't know if it helps. Use a different function for vertical intersections and horizontal ones. The values can obviously be combined into a single function.

So if h(x,y,n) is the horizontal function then for square X,Y the south edge is actually h(X,Y-1,n) and the north edge is h(X,Y,n) which means the edges will join up. Similarly for a vertical function v(x,y,n) with the west edge for X,Y being v(X-1,Y,n) and the east edge being v(X,Y,n).

Hopefully this simplifies things a little. With prime numbers and mod values you can perhaps come up with something along the lines of

h(X,Y,n) = [(X mod 7) + (X mod 17) + (Y mod 37)} mod n

and something along similar lines for a vertical function?

OK perhaps that idea doesn't work.

An alternative might be to generate two random string of 0s and 1s at the start of the project which you then use to select the costume - so for square x you use the 0 or 1 in the letter x position of the x-string and for square y you use the value in the y position of the y string. Then use what I suggested above to ensure the edges match.

Edit - not really thought through and doesn't work but I think there's a grain of an idea in there!

@gtoal are you talking about totally random procedural generation or procedural as in a grassy world map with areas of more or less trees, water, lava, etc? My dumb version of our project does the first already and I think I have an idea on how to do the second.
My current map generation is basically the same function I would use if I added the ability to scroll downward. It works like @deck26 suspected, by generating the first tile (top left corner, map stamped book-wise) randomly, then each tile afterwards is based on the tiles West and North of it with its other two edges randomized. To scroll in a different direction, I would just need to sample and randomize a different set of edges.
By the way, at @gtoal's suggestion I made the map edges tile so my code contains some extra procedures to handle the edge rows and columns of tile generation. Likewise, the first row has no previous row to read, so it randomizes all North edges. Just mentioning this in case someone takes a peak because these exceptions cause the procedural generation code to look more complicated than just using two previous edges. The map edge tiling function would be removed for procedural scrolling anyway.

deck26 wrote:

One idea, don't know if it helps. Use a different function for vertical intersections and horizontal ones. The values can obviously be combined into a single function.

So if h(x,y,n) is the horizontal function then for square X,Y the south edge is actually h(X,Y-1,n) and the north edge is h(X,Y,n) which means the edges will join up. Similarly for a vertical function v(x,y,n) with the west edge for X,Y being v(X-1,Y,n) and the east edge being v(X,Y,n).

The horizontal/vertical distinction is there as a parameter set to 0 or 1. It's f(x,y,axis,n)

So we agree, you're on the right track.

I encourage everyone interested in this problem to actually try their solution in the project - it's short and simple code that does exactly what I described in the top post above, and the function is supplied as a dummy that should be a 1-liner to modify.

It's really surprising how easily patterns develop when you think you have a handle on the randomisation.

Locomule wrote:

@gtoal are you talking about totally random procedural generation or procedural as in a grassy world map with areas of more or less trees, water, lava, etc? My dumb version of our project does the first already and I think I have an idea on how to do the second.
My current map generation is basically the same function I would use if I added the ability to scroll downward. It works like @deck26 suspected, by generating the first tile (top left corner, map stamped book-wise) randomly, then each tile afterwards is based on the tiles West and North of it with its other two edges randomized. To scroll in a different direction, I would just need to sample and randomize a different set of edges.
By the way, at @gtoal's suggestion I made the map edges tile so my code contains some extra procedures to handle the edge rows and columns of tile generation. Likewise, the first row has no previous row to read, so it randomizes all North edges. Just mentioning this in case someone takes a peak because these exceptions cause the procedural generation code to look more complicated than just using two previous edges. The map edge tiling function would be removed for procedural scrolling anyway.

I know - we both have solutions that sort of work, but I'm asking for help here to create a perfect solution that is trivial to code and behaves optimally. Your solution is too complex (pretty sure it doesn't allow scrolling back over a large area without keeping an array of state or regenerating the entire large area on every move back) and my solution led to unexpected repeating patterns that I had not realised until today, because it is just really difficult to create an idempotent random-like function from those 4 inputs that doesn't repeat.

I'm looking forward to seeing what the folks here can come up with. What we need is someone who understands PRNGs really well. I have some ideas but I'm still thinking about the details. What I'm venturing towards is using an actual PRNG procedure - setting the seed from the ‘x’ parameter and selecting a random value according to the ‘y’ parameter. Somewhere in there we also need to throw in the orientation parameter - probably combining it with the seed. (This may be useful)

deck26 wrote:

Not sure it will be possible to have no repeat patterns but might be able to get it so the repeats are far enough apart.

Yes, if the repeating were say 16K apart, that would be good enough.

Also note that it needs to be resistant to patterns on a micro scale as well. A lot of my earlier attempts would be sequences of 01010101 broken up by a few odd bits now and then. That was why I initially added an array of randoms from the Scratch RNG that was pre-filled at startup and ‘whitened’ the results of the function by doing a lookup into that array before returning the bit. I removed that from the demo project to simplify it but if we crack the large-scale repeat problem we may need to reintroduce whitening to solve the local-scale oscillation problem.

gtoal wrote:

I know - we both have solutions that sort of work, but I'm asking for help here to create a perfect solution that is trivial to code and behaves optimally. Your solution is too complex (pretty sure it doesn't allow scrolling back over a large area without keeping an array of state or regenerating the entire large area on every move back) and my solution led to unexpected repeating patterns that I had not realised until today, because it is just really difficult to create an idempotent random-like function from those 4 inputs that doesn't repeat.

I'm looking forward to seeing what the folks here can come up with. What we need is someone who understands PRNGs really well. I have some ideas but I'm still thinking about the details. What I'm venturing towards is using an actual PRNG procedure - setting the seed from the ‘x’ parameter and selecting a random value according to the ‘y’ parameter. Somewhere in there we also need to throw in the orientation parameter - probably combining it with the seed.

Ah, now I understand. Your solution is the only one I see at the moment, biasing each randomization according to previous states which is basically what we are already doing with the two repeated edges. Too bad the 2-edge set of Wang Tiles has such a limited number of matching edge sets out of the entire 16 tiles. That is going to produce the visual effect of repetition even with randomization ala small closed loops, etc. I experimented with generating maps with reduced tile sets, as per the page you shared, to produce loopier maps more conducive to travel by vehicles, etc, but what you gain in inter-tile movement access you lose in map complexity aesthetics.

deck26 wrote:

An alternative might be to generate two random string of 0s and 1s at the start of the project which you then use to select the costume - so for square x you use the 0 or 1 in the letter x position of the x-string and for square y you use the value in the y position of the y string. Then use what I suggested above to ensure the edges match.

Edit - not really thought through and doesn't work but I think there's a grain of an idea in there!

Yep, that's exactly what I had. It doesn't affect long-range repeating patterns but it does stop the problems caused by the last bit of X or Y increasing by 1 on every call, and the generator returning values modulo 2, with the result that you get sequences of 101010 repeating a lot.

I did take that out to make problems more visible in the demo code, but once we have a viable solution, we can add that white noise back in.

Locomule wrote:

Too bad the 2-edge set of Wang Tiles has such a limited number of matching edge sets out of the entire 16 tiles. That is going to produce the effect of repetition. I experimented with generating maps with reduced tile sets, as per the page you shared, to produce loopier maps more conducive to travel by vehicles, etc.

Ah, but once we have a good Wang-2 solution, the code generalises to any Wang-N just by changing the ‘n’ parameter and adding more tiles!

Explanation of ‘Wang-2’ - that means tilable tiles whose edges can be one of two choices, eg land or road. A Wang-3 tile might support land, roads, and rivers. Wang-4 would allow land, roads, rivers and railways. Etc. Unfortunately we need 4 * 2^N different tile designs for any N, although many of them are rotations and reflections and could theoretically be calculated by the program from whatever basic set is supplied by the artist.

Also, something Locomule and I haven't discussed yet is how to do larger-scale map features, eg large areas of land and sea with roads over the land areas, for example. This can be done by having a multi-level generator where one master function defines land/sea - when an X,Y is looked up it evaluates if it is featureless sea and returns tile 0000 for that, otherwise it calls the land-generator function which returns land with roads, houses etc,

I'd suggest just trying something that multiplies the parameters by largish primes (5 or 6 digits), adds together to create a number. Then extract something from that number based on each parameter (maybe a digit?), and add those digits (and then mod n).

Perhaps something like:
h = leftright*237137 + a*842993 + b*640027
h = round( h/(a mod 17 + 7) + h/(b mod 31 + 17) + h/(leftright*10+3) ) mod n

Trying above gives something that looks pretty random (though I wouldn't be surprised if it does repeat after a few thousand).

It could be mixed up further by having three different numbers divided in the second expression, rather than always dividing h (i.e. have three different functions of a,b,leftright, and use each for the division).

As long as a, b and leftright are smaller than ~10 digits, nothing should overflow the precision limit, so that allows a & b up to ~ten billion.

You could easily add a seed to above, using the same idea:
h = leftright*237137 + a*842993 + b*640027 + seed*13
h = round( h/(a mod 17 + 7) + h/(b mod 31 + 17) + h/(leftright*10+3) + h/(seed mod 23 + 13) ) mod n


Thinking about it, I guess at a=640027, b=-842993 (and ignoring seed), the value of h from first expression is 0 or 237137 (for leftright=0 or 1 respectively). And it'll also give the same for all a,b such that a/b=-640027/842993. So there's gotta be a pattern at some point – but I can't look into it further right now…

Anyway, I'd be interesting to know if anyone else has some insight into how to analyse above expression for patterns.

DadOfMrLog wrote:

Perhaps something like:
h = leftright*237137 + a*842993 + b*640027
h = round( h/(a mod 17 + 7) + h/(b mod 31 + 17) + h/(leftright*10+3) ) mod n

Trying above gives something that looks pretty random (though I wouldn't be surprised if it does repeat after a few thousand).

That looks plausible - I added the code to https://scratch.mit.edu/projects/127872959/ - no obvious visible problems :-)

Now, to make it a little faster? Unfortunately the randomisation is called quite often and a lengthy function is sufficient to slow down the scrolling enough to be noticeable.

I guess we really only ever need to calculate the edges when we scroll - the rest can be cached in a 2D cyclic buffer array. That would probably be enough to make it fast, but it does raise the complexity level a lot. It would have been nice to keep it simple.

Last word on this thread for tonight. I've added pixel scrolling (rather than jumping a tile at a time) but it's very slow. And I've added the ability to define the width and height of the generated map, rather than forcing the user to accept an infinite world.

https://scratch.mit.edu/projects/129232814/

Unfortunately all these tweaks have made the code a little more complex, but I'm leaving the original simpler version online as it is easier to understand for anyone who wants to learn about procedural map generation using Wang tiles (and indeed the method generalises to pretty much any kind of procedural generator).

gtoal wrote:

Now, to make it a little faster? Unfortunately the randomisation is called quite often and a lengthy function is sufficient to slow down the scrolling enough to be noticeable.

The main slowdown is from costume switching, not the hash calculation.

You can easily see that if you drag a “set color effect” block into the project – Stage3D makes costume pixel calculation way quicker, so you'll see everything speed up a lot.

It's possible Stage3D could have some detrimental side-effects under some situations, and it'd mean anyone with a computer that cannot use Stage3D would be stuck in slow-mo, so it'd be better to cache the costumes as separate clones, and have each clone stamp wherever its costume is used.

DadOfMrLog wrote:

gtoal wrote:

Now, to make it a little faster? Unfortunately the randomisation is called quite often and a lengthy function is sufficient to slow down the scrolling enough to be noticeable.

The main slowdown is from costume switching, not the hash calculation.

You can easily see that if you drag a “set color effect” block into the project – Stage3D makes costume pixel calculation way quicker, so you'll see everything speed up a lot.

It's possible Stage3D could have some detrimental side-effects under some situations, and it'd mean anyone with a computer that cannot use Stage3D would be stuck in slow-mo, so it'd be better to cache the costumes as separate clones, and have each clone stamp wherever its costume is used.

There are 16 costumes. Would it be fast enough just to cycle through each costume then stamp it at each of the locations it occurs? Currently it is doing (480/32) * (360/32) costume changes. If I use clones, don't I need to communicate to the clones via 16 broadcasts which would be slower than what we have now?

Hold on a minute - I'll go do a version that doesn't change costume at all, that should tell me the maximum speedup we'll get from costume switching optimisations….

OK… I literally removed the ‘switch costume’ block and it was no faster. There's a bottleneck elsewhere before we have to worry about costume switching…

The ‘set colour effect’ trick did have a noticable impact. Ah! set colour effect *and* removing the costume switch does make it acceptably fast. OK, I'll see what I can do to optimise those costumes…

G

gtoal wrote:

There are 16 costumes. Would it be fast enough just to cycle through each costume then stamp it at each of the locations it occurs?

Yeah, that's one way, if the choice of costumes is not too high.

What I would probably do, if the number of possible costumes becomes higher, would be to have a clone for each possible costume, with each clone fixed on a costume. (You're limited to 300 possible tile costumes, of course, assuming you're not taking up even more clones on more things…)

And then have a list for each possible costume, and append the X,Y positions onto the appropriate list. Then send a single broadcast and have the clones check the list that corresponds to its costume. This is much easier with hacked list blocks, but if you want to avoid that then you could use a single longer list which is split into ‘bins’ where you replace instead of append. You could make sure the bins are large enough to hold the possibility that all costumes are the same (which would be a huge waste of unused list items), or you could make the bins ‘extendible’ (so it'd be just the same as the way bincredisort does it).

I tried doing <= 16 separate passes over the display with a costume change between passes, but it was way slower. :-(

DadOfMrLog's recommendation using clones will work, but I _really_ want to keep the code simple… so, I've resorted to an old video game programmer's trick of using larger step sizes to get faster scrolling speeds - except I've tried to make it adaptive so that it's a lot less obvious that we're jumping whole tiles at a time.

When you first hold down an arrow key, it scrolls 1 pixel at a time and then speeds up exponentially. When you let go of the key, it takes a few frames to slow down and stop. Overall the effect suggests that the scrolling is smoother than it actually is.

Hopefully the final result is such that it's really not obvious that this is even a tiled system:

https://scratch.mit.edu/projects/129324720/

The only remaining thing I'm not happy with is the need for a border around the tiles because of the Scratch “50% off-screen” design flaw. I know how to fix that but it involves a lot of costume editing and I'm not sure I have the patience for that at the moment! It would be nice to have a full-screen scroller though…

G

Hi, i'm unable to help you but i want to say that your acelerated scroll trick looks nice.
What about to stop not suddenly but decelerated at short time prior to stop scrolling?
For a borders' solution perhaps you could implement https://scratch.mit.edu/discuss/topic/224332/

asivi wrote:

Hi, i'm unable to help you but i want to say that your acelerated scroll trick looks nice.
What about to stop not suddenly but decelerated at short time prior to stop scrolling?

That's what I'm doing already. It's a fine balance between taking too long to slow down and appearing instant. And may depend on your computer speed.

asivi wrote:

For a borders' solution perhaps you could implement https://scratch.mit.edu/discuss/topic/224332/

I'd forgotten about that trick- I was thinking instead of the transparent pixel off to one side.

It will work, but given how many costume changes I need, it's likely to slow it down a lot… I do about 200 changes per frame, This would make it 400.