Fettler - the path to random map generation

While the blog has been a bit quiet, I've been working on some new features for Fettler.

The first part was a Python script that will go through the masks directory, load each image, and figure out what parts of each edge are floor and which are wall.  It's actually a little smarter, it looks at the whole image and figures out which openings are connected to the rest of the openings on each tile.  While that last bit of info isn't being used yet, it might come in handy down the road.

The connected-ness is determined by converting the images into a grid of nodes (basically a low-res black & white bitmap) and then doing a flood-fill from each of the edge openings to figure what you can reach from that edge.  The "fingerprint" just a list of each of the edge squares and what it connects is saved as a json file for use by the second part.

The second part attempts to generate random map of tiles, using the fingerprints to make sure the edges of adjacent tiles match up.  First stab at this uses a backtracking algorithm, so it tries all of the tiles in a given spot, and if it can't place any it goes back tot he previous tile placed, switches it for the next one that fits there, then tries move forward again.

The issue is that with nearly a thousand possible tiles in each spot, the backtracking algorithm is really limited to backtracking at most two or three tiles.  Any more than that and the number of iterations is too big -- three steps of backtracking is a billion tile combinations.  So the question then becomes what order to place the tiles.  If we do any sort of scan-line placement (rows across left to right, working top to bottom, for example), then it might become necessary to unwind a whole row, which is too much if the row is more than 2 or 3 tiles.

With a horizontal or diagonal scanline placement, then, the random generation can sometimes get stuck.  There are a few pairs of edge combinations that don't exist in the tileset, which leads to too much unwinding being needed.  I've currently got a timeout set so if it goes a few seconds without completing it just bails out and starts over.  Not elegant, but it works.

This can be mitigated a bit with a snake or spiral placement patter, so at every tile is always next the previous tile that was placed.  I'm going to add this next.

Here's one random map:

Here's a bigger 12x20 tile map (each tile being 6x6 squares):

And here is a 30x30:

Since overall connected-ness isn't factored in, there are a fair number of isolated segments, though if you consider putting "secret doors" in a few walls, it works pretty well.  Its output is a list of tiles, so you can always go tweak the tiles to add/remove/edit individual tiles before making the map.

The other limitation is that some not-quite-aligned-to-corners edges will end up matched to ones that are aligned.

A lot of the time this can be fixed manually by putting in a tile that does align.  Removing this type of tile for the available set would work, too.

My other plan is to make it so that instead of generating the map from textured tiles, the map can be assembled into one large mask, then the mask given the texture and edges as the tiles are.  This will leave the generated shape, but clean up the missing edge lines.

I'm also going to explore something that attempts a bit more random placement but allows for removing of other already-placed tiles when it can't fit stuff next to them.  It wouldn't be guaranteed to find a solution, but it might actually end up more likely to complete the map when the pure backtracking algorithm ends up getting stuck.