Comment by ajuc | Hacker News Reader

Comment by ajuc | Hacker News Reader

So, does this algorithm need to remember all already decided tiles forever to be consistent? Or to recalculate everything from the start each time you teleport?

I've been working on similar (but much simpler and 2d) algorithm, and the gist of it was:

- divide infinite world into 2d chunks of constant size that easily fit in memory

- when player is nearby - deterministicaly generate edges of the visible chunks basing on perlin/simplex noise and random number generator seeded with the world coordinates of the chunk

- fill the chunks basing on 2d markov chains trained on hand-crafted map, starting with the edges going inwards

It needed a lot of training data to produce something that makes sense with even small number of possible tiles, so in the end I just generated everything with simplex/perlin noise and some heuristics.

I guess instead of markov chains I could use explicit rules to fill the chunks, like this seems to do.

But it had the advantage that it was very fast - because you didn't need to remember everything from the starting place of the player. You could teleport 1000 screens left, and then back, and everything worked fast and regenerated everything the exact same way.

My implementation keeps the entire world in memory, forever. This is obviously not desirable, but I didn't figure out a way around it. You can't generate a place again that you have been to because the result would be different.

If you do chunks and generate the edges first, you could run into a situation where it's impossible to fill the chunk based on it's edges.

For generating terrain, using noise functions makes a lot of sense since they are local (= don't need to know nearby values to evaluate) and deterministic.

> If you do chunks and generate the edges first, you could run into a situation where it's impossible to fill the chunk based on it's edges.

Yes, to solve that I generated world in 2 stages - first decided which tiles are solid (using simplex noise so it was consistent), then decided "decorations" (what exact thing is in each solid tile - tree, building part, roof, stairs, etc). Most tiles were empty, tiles with nothing beneath were platforms, tiles with nothing above and something below were roofs or tree tops, etc. Where there were decisions to be made I sampled random number generator in constant order for given chunk. That, combined with seeding the generator basing on chunk coordinates meant it always generated same stuff for a given chunk, no matter which path you took to arrive to this chunk.

The problem was - there were a lot of such rules to specify, and if I only specified the few rules that were needed for consistent world - then the generated worlds were very repetative. When I added more tiles specifying rules for all combinations were too much, so I wanted it to learn rules by itself by analysing handmade maps and then tryign to use that in 2d markov chains, but I never got it to work well, and it was my master's thesis, so I just wanted to be done with it at this point ;)

You'd use something like Perlin noise to seed whatever makes the decision about which tile to pick. Perlin noise is deterministic, so it's perfect to generate from the (x,y,z) of the tile & you can be certain that the location will resolve to the same tile if you recalculated the area from scratch. Divide up your world into areas, and force the centre of the area you're in and adjacent areas before filling out the area the player is in.

If you have two adjacent chunks, collapsing one will impose constraints on the other one. Even if the RNG part is deterministic, as you suggested, the result will be different depending on which chunk you collapse first.

I don’t get it. If you have some location between two regions, and you fill it in starting from some regular point (say, centre of the south-west region), you will get the same tiling every time.

If you randomly choose a point to start at (like the player avatar’s current position), then I see that you might get different tilings when regenerating the location.

If you divide world into chunks and specify order of collapsing inside each chunk, and use deterministic random number generator seeded with the same thing for given chunk - then the result will be the same each time.

Reply on news.ycombinator.com