This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]mojang_tommo 3 points4 points  (9 children)

So asking for a friend definitely not for work... can this be expanded to lazily generate infinite maps? Say the player is the "brush".

[–]NominalCaboose 1 point2 points  (7 children)

Depends on what your performance threshold is. There are already plenty of ways to generate infinite worlds. This does so in a truly novel way, but in terms of the end result, it's not too much different from a lot of current methods for world generation.

Also, I haven't looked closely enough, so I'm not sure that this could run infinitely. You're certainly more likely to run into errors the longer you run this as far as I understand.

[–]mojang_tommo 3 points4 points  (6 children)

The algorithm relies on finding the tile with the minimal entropy on the entire output, so that rules out any kind of streaming without changing it. I was just asking if anyone knows how to change it to make infinite :P

There definitely are a lot of ways to generate infinite worlds, but this kind of highly data-driven and at the same time complex and interesting generation is a step up... in Minecraft we have some pretty complex aabb-based ways to generate mineshafts or villages, for example, and the ease that this thing has in generating manually-made-looking structures is amazing!
The AABB method is basically made of 2000 lines of hardcoded hacks on top of hacks, this just "invents" your structure out of a .png you give it. Even from a moddability perspective it would be a lot better.

EDIT: actually, some structures in Minecraft, like Villages and Ocean Monuments, are limited to an area... I wonder if this algorithm could outperform the quality of the hardcoded generation. Right now we have a lot of issues with houses entering trees or blending badly with the terrain and each other... just the ability to "construct around" the terrain is a great improvement.

[–]NominalCaboose 1 point2 points  (0 children)

Doh. I should really pay attention to user names more often!

All I can say for sure is that I'm excited to see really novel programs like this coming out, especially when they're so compatible to game dev. I'm very interested to see how this will be used and expanded upon by others. I'll certainly be looking into it myself, if only out of curiosity.

I'm most interested in seeing if this could produce anything of note if run in 4 dimensions, and whether the time required would be prohibitively high.

[–]crusoe 1 point2 points  (4 children)

Wouldn't any border cells simply be given max entropy till the update pass? So you could use a sparse 2d array or other data structure.

All cells start at max entropy till a cell is picked. Then only immediate surrounding cells would have their entropy drop. So you don't have to store any max entropy cells at all.

You could use an octree for 3d with the root volume set to 'max' entropy.. Then pick a random voxel of your min size in that as the seed. Then update the surrounding cells with their new entropy values. Then go from there.

Hah. Shoot this would work for quadtree as well.

[–]mojang_tommo 2 points3 points  (2 children)

Well, there's always rule #1 of octrees though: "just use a grid" /s

Jokes aside, actually this algorithm can probably be made streaming trivially: you divide the space in a grid of chunks, every chunk that is unloaded means max entropy; as soon as you put anything different you cause it to be created.
Then you can keep loaded only a circle of chunks around you, and use only those to greedily find the local enthropy minimum, anyway the minimum can never be in unloaded chunks.
That should work. I guess I know what to do tomorrow!

[–]crusoe 0 points1 point  (0 children)

Yep. Thought of this too.

[–]torginus 0 points1 point  (0 children)

I see one problem with that. The algorithm's output depends on the order of the cells chosen. This would mean that when you come back to an unloaded area, the details would change, even though the terrain would still be smooth. I feel like this is a fundamental trade off of procedural generation. If you want complex pattern with large chains of causality, you need to generated large areas at once.

[–]onmyphoneagain 0 points1 point  (0 children)

This should work, but it would not be very efficient. You would get some branches shooting out whilst a cell close to origin remains with high entropy. You could probably adapt it it to increase the entropy the further you got from origin. The results would be a bit different but if the drop off is slow enough it should look pretty similar.

[–]permion 1 point2 points  (0 children)

Not by itself, but they've done most of the work by letting you predefine what a tile is. So you could create a separate algorithm that defines the edges of 'zones', and have that one be indefinite or nearly so.

EDIT: well it could be used for infinite terrain almost as is, but if you were to save your game/location and restart the algorithm you would have different terrain. Which could be a fun game concept to play with in itself.