5 ms·

Procedural Worlds from Simple Tiles

218 points by airstrike 5y ago

lostdog 5y ago
Very cool idea, and the results look great. If I were using this practically, I would add a "fuzzer" to find intractable situations and add new tiles to fit them. You could even add a high cost to make certain tiles undesirable, so that the generator tries not to place them but can still use them to get unstuck.
isoprophlex 5y ago
Very nice writeup, i find it always a pleasure to read stories from people explaining their journey towards designing an algo. TLDR: This is basically "wave function collapse" that was posted here as well some days ago, only it does local probability updates instead of global during tile resolving steps. This makes it run faster without sacrificing ability to halt, apparently. Very nice.
mysterydip 5y ago
They look complex, but are they interesting? That seems to be the more difficult trick for any procedural algorithm I've seen to pull off. Although inherently subjective, anything that repeats too similarly too often, or doesn't logically make sense or have smooth transitions feels computer generated. The best procedural creation should feel hand-made IMHO.
- pfortuny 5y ago
  Yes. They have no global design, so in essence they are meaningless because the only function of each tile is “to fill space”, albeit in a “coherent” way.
etherealmachine 5y ago
This is a great write up of the problem space. I've also tried an approach here that converted the tile dependencies into a Boolean constraint satisfaction problem and then used the Open Source clasp (https://potassco.org/clasp/ https://potassco.org/clasp/) answer set solver to return valid tilings. The inspiration was from the paper "Answer Set Programming for Procedural Content Generation: A Design Space Approach" (https://adamsmith.as/papers/tciaig-asp4pcg.pdf https://adamsmith.as/papers/tciaig-asp4pcg.pdf) which is also a good read. Using an answer set solver was nice because it was so easy, I just had to encode the tile constraints and then the solver did all the work, backtracking, etc, but it could be slow, and it could also fail to return (infinite loop). I gave up because it seemed like WFC and similar could return results fast enough for "online" generation, like generating chunks in Minecraft and also because it seemed hard to encode tile probabilities (from some initial example map) like WFC does.
rendall 5y ago
Interesting. His follow up blog post The Constrained Tile Placement Algorithm behind Generate Worlds (2019) seems like a refinement of the idea, and I found its explanation to be clearer https://ijdykeman.github.io/procedural_generation/2019/11/08/generate-worlds-algorithm.html https://ijdykeman.github.io/procedural_generation/2019/11/08...
ijdykeman 5y ago
Author here. It's awesome to see my post on hn! Happy to answer questions.
- movedx 5y ago
  Amazing work. I'm not a very visually creative person. I want to be able to make virtual worlds but the assets are the problem for me. I think this will help alleviate that issue so thank you. Bought a copy. (I really want a little RPG about exploring.)
  - programd 5y ago
    Don’ let that stop you! There are a ton of free assets both for Unity and Unreal. Check out e.g. the free category in the Unreal marketplace. https://www.unrealengine.com/marketplace/ https://www.unrealengine.com/marketplace/ Search for the RPG category. There are whole RPG systems you can plug into Unreal which you can buy for laughably little money. (No affiliation, I just like what Epic is doing with the engine)
    - movedx 5y ago
      Oh, I know! I have a tonne of assets already. They just all feel disjointed and I'm bad at lighting :P
  - abetusk 5y ago
    OpenGameArt.org (OGA) has a lot of assets available for gaming [0]. In particular Kenney has loads of 2d and 3d assets that can be used as the basis for a wide array of games [1] [2] [3]. OGA has many Zelda-like tilesets. Some of my favorites: [4], [5], [6], [7], [8], [9], [10] Also note that there's a FOSS Zelda game engine called Solarus [11]. [0] https://opengameart.org/ https://opengameart.org/ [1] https://opengameart.org/users/kenney https://opengameart.org/users/kenney [2] https://www.kenney.nl/ https://www.kenney.nl/ [3] https://twitter.com/KenneyNL https://twitter.com/KenneyNL [4] https://opengameart.org/content/overhead-action-rpg-forest https://opengameart.org/content/overhead-action-rpg-forest [5] https://opengameart.org/content/zelda-like-tilesets-and-sprites https://opengameart.org/content/zelda-like-tilesets-and-spri... [6] https://opengameart.org/content/16x16-game-assets https://opengameart.org/content/16x16-game-assets [7] https://opengameart.org/content/rp-destiny-sprites-and-tilesets https://opengameart.org/content/rp-destiny-sprites-and-tiles... [8] https://opengameart.org/content/zoria-tileset https://opengameart.org/content/zoria-tileset [9] https://opengameart.org/content/gameboy-tileset https://opengameart.org/content/gameboy-tileset [10] https://opengameart.org/content/forest-tileset-new-and-old https://opengameart.org/content/forest-tileset-new-and-old [11] https://www.solarus-games.org/ https://www.solarus-games.org/
hypertele-Xii 5y ago
The problem with this kind of algorithm is that it doesn't generate worlds; It generates infinitely tiling neighborhoods of the smallest unit of space. It's principally impossible to make a locally-infinite world globally interesting. There is no structure. It's just structured noise. Fine for a bit of generative art, not so much for interactive game worlds.
- asiachick 5y ago
  I agree with this so much. You're not likely going to get a God of War, Zelda, Uncharted, Last of US, or even GTA, Red Dead Redemption experience with a randomly generated world. On the other hand some games the game play itself is enough that randomly generated worlds are good enough? Rogue, Minecraft, Valheim, are a few that I've played.
  - bhaak 5y ago
    Why not both? Use a procedurally generated map as a template and enhance it with manually designed parts. Or mix and match manually designed tiles with procgen stuff. This is similar to to what OP's newer link describes. Another option is to develop a DSL that let's you describe the map in various degrees. "Put a random city there" vs "Put a city with these types of buildings there" vs "Put a city with a pawn shop at the northeast corner, an armor shop somewhere south, [...]". AAA games often use parts of this. For example for plants, many aren't put there manually by the designer but by randomized code and the designer just selects the area in which they should grow.
    - k__ 5y ago
      The Diablo series follows a hybrid approach.
    - all2 5y ago
      The advantage of this kind of tile-set, is the tiles don't have to be some fixed basic size. If you have a 2D Cartesian grid to fill, you could add arbitrary sized tiles (1x2, 2x4, etc) and they don't all have to be rectangles... So you could have variable sized features in your tile-set. You could also allow the user to "paint" the grid with probability modifiers to adjust what populates. You could combine... uhh... layer generative methods together. Start with a 2D grid. Adjust land elevation probabilities with underlying shapes (pick your generative method). Let this algorithm generate based on the "continental plates" from the previous step. Then apply a wind/water erosion algorithm. Permute possible underlying algorithms in each layer...
everyone 5y ago
This looks like Wave Function Collapse https://github.com/mxgmn/WaveFunctionCollapse https://github.com/mxgmn/WaveFunctionCollapse It's cool, but I agree with some other commenters that it's not a very good way to generate an entire world, but it is a cool way to generate part of a world like a maze or something.
TruePath 5y ago
I don't get the worry about the NP complete problem of tiling a finite area. Yes, of course, if you allow arbitrary adjacency rules then tiling is going to be NP complete but the goal here is to generate realistic tilings then it's reasonable to assume that if you have a compact connected region that obeys the tiling rules and any square there is some tile that is allowed to be placed in that square. I mean this is how the real world works. You don't have holes in reality so if it's possible to have a part of the world that looks like such-and-such there must be a valid description of the stuff next to it.
- TruePath 5y ago
  Damn't I didn't mean compact connected. I meant that if you have a convex region you can extend it. Obviously, non-convex regions can raise problems (e.g. maybe tropical rainforest can't transition to tundra in the space of a single tile). But it should work with convex regions.
- ijdykeman 5y ago
  I think it’s important to point out that it’s NP hard, because if you don’t know that, who’s to say that some efficient, exact algorithm does not exist? Given that because the problem is NP hard, no fast and exact algorithm exists, so we can try to explore possible tradeoffs. This post explores one point in the design space where you trade away exactness for speed. You’re suggesting trading away generality for exactness and speed by restricting the classes of possible inputs and putting in extra work to make the classes you do support very fast to process. A totally valid option.
fho 5y ago
Every time something like this comes up I feel obligated to show my little Zelda map generator I wrote some time ago: https://imgur.com/a/R1OleXp https://imgur.com/a/R1OleXp Sadly I never quite figured out how to complete even the small "maps" ... the LttP map has hundreds of unique tiles making back-tracking somewhat infeasible. You see that in the end of the first example, every time the algorithm notices that it messed up it back-tracks, but with many tiles to try it quickly grinds to a hold.

218 points by airstrike 5y ago

Very cool idea, and the results look great. If I were using this practically, I would add a "fuzzer" to find intractable situations and add new tiles to fit them. You could even add a high cost to make certain tiles undesirable, so that the generator tries not to place them but can still use them to get unstuck.

isoprophlex 5y ago

Very nice writeup, i find it always a pleasure to read stories from people explaining their journey towards designing an algo. TLDR: This is basically "wave function collapse" that was posted here as well some days ago, only it does local probability updates instead of global during tile resolving steps. This makes it run faster without sacrificing ability to halt, apparently. Very nice.

mysterydip 5y ago

They look complex, but are they interesting? That seems to be the more difficult trick for any procedural algorithm I've seen to pull off. Although inherently subjective, anything that repeats too similarly too often, or doesn't logically make sense or have smooth transitions feels computer generated. The best procedural creation should feel hand-made IMHO.

pfortuny 5y ago
Yes. They have no global design, so in essence they are meaningless because the only function of each tile is “to fill space”, albeit in a “coherent” way.

etherealmachine 5y ago

This is a great write up of the problem space. I've also tried an approach here that converted the tile dependencies into a Boolean constraint satisfaction problem and then used the Open Source clasp (https://potassco.org/clasp/ https://potassco.org/clasp/) answer set solver to return valid tilings. The inspiration was from the paper "Answer Set Programming for Procedural Content Generation: A Design Space Approach" (https://adamsmith.as/papers/tciaig-asp4pcg.pdf https://adamsmith.as/papers/tciaig-asp4pcg.pdf) which is also a good read. Using an answer set solver was nice because it was so easy, I just had to encode the tile constraints and then the solver did all the work, backtracking, etc, but it could be slow, and it could also fail to return (infinite loop). I gave up because it seemed like WFC and similar could return results fast enough for "online" generation, like generating chunks in Minecraft and also because it seemed hard to encode tile probabilities (from some initial example map) like WFC does.

rendall 5y ago

Interesting. His follow up blog post The Constrained Tile Placement Algorithm behind Generate Worlds (2019) seems like a refinement of the idea, and I found its explanation to be clearer https://ijdykeman.github.io/procedural_generation/2019/11/08/generate-worlds-algorithm.html https://ijdykeman.github.io/procedural_generation/2019/11/08...

ijdykeman 5y ago

Author here. It's awesome to see my post on hn! Happy to answer questions.

movedx 5y ago
Amazing work. I'm not a very visually creative person. I want to be able to make virtual worlds but the assets are the problem for me. I think this will help alleviate that issue so thank you. Bought a copy. (I really want a little RPG about exploring.)
- programd 5y ago
  Don’ let that stop you! There are a ton of free assets both for Unity and Unreal. Check out e.g. the free category in the Unreal marketplace. https://www.unrealengine.com/marketplace/ https://www.unrealengine.com/marketplace/ Search for the RPG category. There are whole RPG systems you can plug into Unreal which you can buy for laughably little money. (No affiliation, I just like what Epic is doing with the engine)
  - movedx 5y ago
    Oh, I know! I have a tonne of assets already. They just all feel disjointed and I'm bad at lighting :P
- abetusk 5y ago
  OpenGameArt.org (OGA) has a lot of assets available for gaming [0]. In particular Kenney has loads of 2d and 3d assets that can be used as the basis for a wide array of games [1] [2] [3]. OGA has many Zelda-like tilesets. Some of my favorites: [4], [5], [6], [7], [8], [9], [10] Also note that there's a FOSS Zelda game engine called Solarus [11]. [0] https://opengameart.org/ https://opengameart.org/ [1] https://opengameart.org/users/kenney https://opengameart.org/users/kenney [2] https://www.kenney.nl/ https://www.kenney.nl/ [3] https://twitter.com/KenneyNL https://twitter.com/KenneyNL [4] https://opengameart.org/content/overhead-action-rpg-forest https://opengameart.org/content/overhead-action-rpg-forest [5] https://opengameart.org/content/zelda-like-tilesets-and-sprites https://opengameart.org/content/zelda-like-tilesets-and-spri... [6] https://opengameart.org/content/16x16-game-assets https://opengameart.org/content/16x16-game-assets [7] https://opengameart.org/content/rp-destiny-sprites-and-tilesets https://opengameart.org/content/rp-destiny-sprites-and-tiles... [8] https://opengameart.org/content/zoria-tileset https://opengameart.org/content/zoria-tileset [9] https://opengameart.org/content/gameboy-tileset https://opengameart.org/content/gameboy-tileset [10] https://opengameart.org/content/forest-tileset-new-and-old https://opengameart.org/content/forest-tileset-new-and-old [11] https://www.solarus-games.org/ https://www.solarus-games.org/

hypertele-Xii 5y ago

The problem with this kind of algorithm is that it doesn't generate worlds; It generates infinitely tiling neighborhoods of the smallest unit of space. It's principally impossible to make a locally-infinite world globally interesting. There is no structure. It's just structured noise. Fine for a bit of generative art, not so much for interactive game worlds.

asiachick 5y ago
I agree with this so much. You're not likely going to get a God of War, Zelda, Uncharted, Last of US, or even GTA, Red Dead Redemption experience with a randomly generated world. On the other hand some games the game play itself is enough that randomly generated worlds are good enough? Rogue, Minecraft, Valheim, are a few that I've played.
- bhaak 5y ago
  Why not both? Use a procedurally generated map as a template and enhance it with manually designed parts. Or mix and match manually designed tiles with procgen stuff. This is similar to to what OP's newer link describes. Another option is to develop a DSL that let's you describe the map in various degrees. "Put a random city there" vs "Put a city with these types of buildings there" vs "Put a city with a pawn shop at the northeast corner, an armor shop somewhere south, [...]". AAA games often use parts of this. For example for plants, many aren't put there manually by the designer but by randomized code and the designer just selects the area in which they should grow.
  - k__ 5y ago
    The Diablo series follows a hybrid approach.
  - all2 5y ago
    The advantage of this kind of tile-set, is the tiles don't have to be some fixed basic size. If you have a 2D Cartesian grid to fill, you could add arbitrary sized tiles (1x2, 2x4, etc) and they don't all have to be rectangles... So you could have variable sized features in your tile-set. You could also allow the user to "paint" the grid with probability modifiers to adjust what populates. You could combine... uhh... layer generative methods together. Start with a 2D grid. Adjust land elevation probabilities with underlying shapes (pick your generative method). Let this algorithm generate based on the "continental plates" from the previous step. Then apply a wind/water erosion algorithm. Permute possible underlying algorithms in each layer...

everyone 5y ago

This looks like Wave Function Collapse https://github.com/mxgmn/WaveFunctionCollapse https://github.com/mxgmn/WaveFunctionCollapse It's cool, but I agree with some other commenters that it's not a very good way to generate an entire world, but it is a cool way to generate part of a world like a maze or something.

TruePath 5y ago

I don't get the worry about the NP complete problem of tiling a finite area. Yes, of course, if you allow arbitrary adjacency rules then tiling is going to be NP complete but the goal here is to generate realistic tilings then it's reasonable to assume that if you have a compact connected region that obeys the tiling rules and any square there is some tile that is allowed to be placed in that square. I mean this is how the real world works. You don't have holes in reality so if it's possible to have a part of the world that looks like such-and-such there must be a valid description of the stuff next to it.

TruePath 5y ago
Damn't I didn't mean compact connected. I meant that if you have a convex region you can extend it. Obviously, non-convex regions can raise problems (e.g. maybe tropical rainforest can't transition to tundra in the space of a single tile). But it should work with convex regions.
ijdykeman 5y ago
I think it’s important to point out that it’s NP hard, because if you don’t know that, who’s to say that some efficient, exact algorithm does not exist? Given that because the problem is NP hard, no fast and exact algorithm exists, so we can try to explore possible tradeoffs. This post explores one point in the design space where you trade away exactness for speed. You’re suggesting trading away generality for exactness and speed by restricting the classes of possible inputs and putting in extra work to make the classes you do support very fast to process. A totally valid option.

fho 5y ago

Every time something like this comes up I feel obligated to show my little Zelda map generator I wrote some time ago: https://imgur.com/a/R1OleXp https://imgur.com/a/R1OleXp Sadly I never quite figured out how to complete even the small "maps" ... the LttP map has hundreds of unique tiles making back-tracking somewhat infeasible. You see that in the end of the first example, every time the algorithm notices that it messed up it back-tracks, but with many tiles to try it quickly grinds to a hold.