1) Is it possible that the algorithm will fail to find a suitable tile and needs to restart?
2) I don't understand, why or how you get those rectangular ponds and lava areas in the first youtube video. I expected them to be far more organic or am I missing something?
3) How would do you ensure connectivity of areas or points of interest? Any ideas? Would you path a way before or after running the algorithm?
> Is it possible that the algorithm will fail to find a suitable tile and needs to restart?
Yes, the algorithm can fail. Since it considers only local areas when making decisions, it can easily make a placement that dooms progress later on. The best way to guarantee success in a given amount of compute time is to make tile sets easier to solve, for example by making it possible to transition from any tile to any other in a few hops. But this limits the amount of structure in the output.
> I don't understand, why or how you get those rectangular ponds and lava areas in the first youtube video. I expected them to be far more organic or am I missing something?
It's possible to restrict the tile set so that only rectangular regions are allowed. You do this by creating only convex corners. Here's an example:
Imagine you only have 10 tiles. They are made up of Ground (#) and water (~), and you want rectangular areas of water.
There are no dead ends because no road dead end tiles exist. Eliminating loops in the road while allowing any direction of travel is more complicated but possible.
Came across the post on Google when searching (out of sheer curiosity) for algorithms for generating tiled wallpaper-like patterns (as in real world wallpapers and upholstery).
This was a truly enjoyable read and such a well written article that I immediately thought others here would appreciate it, so thanks for writing it!
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.
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].
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)
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.
I think you could layer this approach to get some global structure.
Currently the probability of each tile is local * sphere.
A simple approach would be to add some perlin noise on top to dictate different biomes, with each biome having their own tile probability distributions. Then the new tile probability becomes local * sphere * biome.
So in the ocean biome you might be less likely to get houses and other large structures. But islands and grass huts are ok. And obviously water tiles get a large probability boost.
Or… what if we took the tile approach further and have various scales of tile. Perhaps biomes are larger tiles (8x8) which also follow the same algorithm so that biomes have relationships to one another.
The larger worlds wouldn't even have to use larger tiles. Imagine you first create a "world" of tiles that describe biome. The tiles in this "world" set would be things like "plains", "mountain", "water", and obviously some transitions between these. Then for each pixel in the "world" you select the tileset probabilities by the kind of terrain that pixel represents, maybe with some influence from nearby pixels. This could of course be repeated as few or as many times as seems reasonable. For each level you go down the resolution would increase. If we stick to the 3x3 tiles from the original article we can then first generate a global "world" with 3x3 tiles, then populate each pixel in the "world" with a new 3x3 tile from the new set. So for each time you go up in resolution you 3x the size in each dimension.
I disagree with this. Theres nothing about this system which requires the world to be infinite. As an example, check out https://www.badnorth.com/ which uses wave function collapse to generate the islands.
The worlds are carefully tuned and aspects of them are controlled, but the algorithm is the same and I do think this creates worlds or at least aspects of gameplay with great interest.
He supports different probabilities for the tiles. Though he doesn't, you could vary those probabilities spatially. You could even apply the algorithm with one tileset to get Image #1, then scale up Image #1 and use its colors to determine the probabilities for a second application of the algorithm for Image #2, possibly with a different tileset. Recurse as desired.
On the other hand, it might turn out that when you do things that way, you don't need the edge-matching rule at all; you can just say which colors can correspond to which tiles at the next level of resolution down, maybe with probability, and rely on the high-level tiles to guarantee continuity.
But you can run it at different resolutions. Create areas of different biomes, then generate within them, allowing you to move between distinctive regions.
The question is how much do you have to elaborate at each step.
The impressive thing with Minecraft's generation, to me, is that it's incremental, and that you get the same chunks no matter what order they're explored in.
Tile-based solving doesn't lend itself well to that. Minecraft does tile-based solving as well, as I understand it, for structures such as mineshafts and strongholds, and still manages to make them generate the same each time regardless of how you approach it. But it does so by elaborates the whole, bounded structure when you first encounter it. It can only work because the structure is finite.
It's hard to build in relations spanning large areas in incremental generation, even something as simple as a river flowing downhill on an incrementally generated map.
But if there was a clever way to do it, it could go far beyond physical geography. Imagine a world like Dwarf Fortress, but where all the history wasn't pregenerated, but generated incrementally as you met people, read books, explored the world - and still turned out consistently with the same seed, just like you get the same stronghold in a given Minecraft world no matter what order you explore the chunks.
A solution would be to generate a world from an user-generated tilemap, to "guide" the algorithm, and the user configure some aspect of the procedural generation. The goal of procedural generation is to save the time of 3D artists, but procedural generation can't do 100% of the task.
To make a game world interesting, it's more about scenario/mission generation, which isn't so difficult.
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.
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.
Indeed. Check out the stellar work Joe Garth is doing with Brushify.io [1] for the Unreal engine. His procedural landscape placement tools let you create beautiful game terrains very quickly. Watch the videos on the site for what you can do - triple AAA visuals for very little effort.
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...
> 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.
The issue is not that it's randomly generated, but that to get really interesting you need more advanced rule sets. Minecraft, for example, has a lot of rules to alter the distribution of blocks in different ways. First of all biomes. Then lots of rules that alter the probability of different things based on biome, or based on proximity to something else. Then multiple levels of generation. E.g. huts are not randomly placed - huts are placed in a village - but the village itself is randomly placed.
That's not to complain about the linked article - it's awesome work, and the idea of using the tile borders is great. I think he could level up that generators quite easily to do even better as well - people have suggested things like applying it at different resolutions to e.g. first use the same simple rules to generate a biome map for example. It'd be really interesting to see how far the method could be taken while retaining a focus on really simple rules to specify how to connect things.
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/) 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) 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.
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.
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.
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
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.
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.
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.
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.
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.
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.
