Decoding the autotile pattern

Talk about things that are not making games here. But you should also make games!

Moderators: Bob the Hamster, marionline, SDHawk

Post Reply
lennyhome
Slime Knight
Posts: 115
Joined: Fri Feb 14, 2020 6:07 am

Decoding the autotile pattern

Post by lennyhome »

Described here:
http://www.cr31.co.uk/stagecast/wang/blob.html

I use the 8x6 shape here. The only tricky part is to consider that a side covers two corners, so their bits should be set to zero if the side is present.

I check the corners first, then the sides, then with the the bitmask I do a search into the the array I've set up at the beginning.

Code: Select all

plotscript, auto tile, par
	variable(base, zone, layer, x, y, z, bm)

	base = 256

	write global (base + 0, 0)
	write global (base + 1, 4)
	write global (base + 2, 92)
	write global (base + 3, 112)
	write global (base + 4, 28)
	write global (base + 5, 124)
	write global (base + 6, 116)
	write global (base + 7, 64)

	write global (base + 8, 20)
	write global (base + 9, 84)
	write global (base + 10, 87)
	write global (base + 11, 221)
	write global (base + 12, 127)
	write global (base + 13, 255)
	write global (base + 14, 245)
	write global (base + 15, 80)

	write global (base + 16, 29)
	write global (base + 17, 117)
	write global (base + 18, 85)
	write global (base + 19, 95)
	write global (base + 20, 247)
	write global (base + 21, 215)
	write global (base + 22, 209)
	write global (base + 23, 1)

	write global (base + 24, 23)
	write global (base + 25, 213)
	write global (base + 26, 81)
	write global (base + 27, 31)
	write global (base + 28, 253)
	write global (base + 29, 125)
	write global (base + 30, 113)
	write global (base + 31, 16)

	write global (base + 32, 21)
	write global (base + 33, 69)
	write global (base + 34, 93)
	write global (base + 35, 119)
	write global (base + 36, 223)
	write global (base + 37, 255)
	write global (base + 38, 241)
	write global (base + 39, 17)

	write global (base + 40, 5)
	write global (base + 41, 68)
	write global (base + 42, 71)
	write global (base + 43, 193)
	write global (base + 44, 7)
	write global (base + 45, 199)
	write global (base + 46, 197)
	write global (base + 47, 65)

	zone = 10
	layer = 3

	for (y, 1, map height () - 2) do (
		for (x, 1, map width () - 2) do (
			
			bm = 0
			
			if (not(read zone (zone, x, y))) then (
				continue
			)

			if (read zone (zone, x + 1, y - 1)) then (
				bm = bm | 0b00000010
			)
			if (read zone (zone, x + 1, y + 1)) then (
				bm = bm | 0b00001000
			)
			if (read zone (zone, x - 1, y + 1)) then (
				bm = bm | 0b00100000
			)
			if (read zone (zone, x - 1, y - 1)) then (
				bm = bm | 0b10000000
			)

			if (read zone (zone, x + 0, y - 1)) then (
				bm = bm | 0b00000001
			) else (
				bm = bm & 0b01111101
			)
			if (read zone (zone, x + 1, y + 0)) then (
				bm = bm | 0b00000100
			) else (
				bm = bm & 0b11110101
			)
			if (read zone (zone, x + 0, y + 1)) then (
				bm = bm | 0b00010000
			) else (
				bm = bm & 0b11010111
			)
			if (read zone (zone, x - 1, y + 0)) then (
				bm = bm | 0b01000000
			) else (
				bm = bm & 0b01011111
			)

			for (z, 0, 47) do (
				if (read global(base + z) == bm) then (
					break
				)
			)
			
			write map block (x, y, (z / 8 + 4) * 16 + z % 8, layer)
		)
	)
end
TMC
Metal King Slime
Posts: 4308
Joined: Sun Apr 10, 2011 9:19 am

Re: Decoding the autotile pattern

Post by TMC »

(For those not following along, you need to layout your tileset like the examples here and either use Lenny's variant-HamsterSpeak compiler or else do some search-replaces on the scripts to convert to standard HS.)

Neat. Huh, a bit more complicated than I was expecting, but I get it. The loop over all the possible tile might be a bit slow, could build a size-256 lookup table to speed it up dramatically.

I had wondered why you were omitting tile 0 from all your tilesets but I see it suggested on that page, "each tile has a central 'blob' of land or carpet, although tile_0 is often depicted without for artistic reasons." I only see that being useful if you generate a map by placing tiles (zones) randomly and want to clean it up a bit.

Does anyone else use "blob tileset" to identify this 47 wang tile tileset? It's far more common than the full 256 tile version (I have seen OHR games that use it), and I also definitely want to add an option to my halftile autotiler to disable the diagonally-adjacent corner pieces, to use this instead.
lennyhome
Slime Knight
Posts: 115
Joined: Fri Feb 14, 2020 6:07 am

Re: Decoding the autotile pattern

Post by lennyhome »

Image

The pattern at the top is the one that has to be drawn manually and it's the same RpgMaker uses. The pattern at the bottom is derived automatically. It's a logistical nightmare because it requires an off-line script. I can publish it but I doubt anybody would be able to use it. I still hope this gives an idea of how the half-tile re-arragnement business works.

I'm also experimenting with a couple other automapping features from RpgMaker. There are "tape" areas which can be stretched, both horizontal and vertical and also vertical tapes with a 45° splice, which are used for cliffs. Very interesting.

The example RpgMaker ChipSets I'm looking at come from here:
https://github.com/EasyRPG/RTP
diagonally-adjacent corner pieces
This particular scheme has no support for diagonal pieces. RpgMaker doesn't support them. I think.

But the point is to be able to handle most of the cases by drawing as little as possible. Special pieces and adjustments will still need to be made. One very cool thing is that OHRPGCE supports multiple layers with a transparent color. That opens up some interesting possibilities compared to RpgMaker where there is only one background layer.
TMC
Metal King Slime
Posts: 4308
Joined: Sun Apr 10, 2011 9:19 am

Re: Decoding the autotile pattern

Post by TMC »

Hmm. The "decompressing" script could be written as a HS script that draws the tileset using a lot of clipping slices, so any OHR user could run (and export by taking a screenshot). But that's a lot of work and I'm not suggesting you do that (and it would be more useful to have builtin autotiling anyway.) Although, I had the idea for years that it would be nice if you could run scripts in Custom, and the biggest usecase I've always had in mind was autotiling and other map generation tools. The question is whether HS or a better language should be embedded, and my answer is that ideally HS should be made into a better language and then embedded.

Yes, looking at the RPGMaker tilesets you posted it looked like it didn't do diagonally-adjacent corners, but I decided to implement them anyway.

I couldn't find anything about "tape" tiles. Is there some other name for that?
But that reminds me of 9-slice scaling which is something I want to implement. I think probably as a Rectangle slice setting rather than a Sprite slice one, because it's mainly useful for box backgrounds, and the sprite scaling settings are already really complicated.
compared to RpgMaker where there is only one background layer.
Really? Even the more recent versions?
lennyhome
Slime Knight
Posts: 115
Joined: Fri Feb 14, 2020 6:07 am

Re: Decoding the autotile pattern

Post by lennyhome »

The 2000 version has only one background layer, one foreground layer and some sprites. Generally the same as the SNES hardware limitations.

But that doesn't prevent crazy people from doing stuff like this:
https://yume2kki.fandom.com/wiki/Ancient_Aeropolis

I don't believe there's much else which is technically relevant beyond what we've explored so far. I think the "tapes" and 9-slice scaling are just simplified cases of the autotile pattern. In the EasyRPG source code they're called A through D blocks, but I haven't completely figured out which is which yet. The only slight exception are the vertical tapes meant for diagonal cliffs.

Being able to run scripts in the editor could be an appealing idea but in my opinion it should be much simpler. Ideally there should be only one pre-defined way to do the setup for autotiling.
TMC
Metal King Slime
Posts: 4308
Joined: Sun Apr 10, 2011 9:19 am

Re: Decoding the autotile pattern

Post by TMC »

Yes I'm worried about having too many different autotiling methods, since I've now got that half-tile one in addition to whatever else.
But I strongly feel that autotiling should support people's existing tilesets rather than only being applicable to new tilesets drawn to conform to a pattern (and hence new maps).
It's really ambitious, but a fun project would be to automatically determine which tiles fit together either by analysing the pixels along the boundaries (I have experience with this), or looking at which tile combinations the user has already placed on their maps. I would call it autoautotiling.
lennyhome
Slime Knight
Posts: 115
Joined: Fri Feb 14, 2020 6:07 am

Re: Decoding the autotile pattern

Post by lennyhome »

Some tool made specifically to grab regions from images, sort, organize and resize tiles into tile sheets would be useful.

I was checking Tiled's manual and I've noticed they've added support for the 47 tiles "mixed set" relatively recently:
https://doc.mapeditor.org/en/stable/manual/terrain/
They also have special "input" layers where preferred associations can be specified and then used for validation or auto-correction. There's scripting but it has no pixel or sub-tile level access, so it can't be used for advanced analysis.

My main problem with Tiled is that it expects some already-made, already-organized tile sheet which the user must provide in advance to be able to do anything. That's why I started looking into RpgMaker instead. I wanted to understand what needs to happen before one can start working with some tool like Tiled.

For some of my recent experiments I've been using pixel access in Python/PySDL2.

Code: Select all

from sdl2 import *
from ctypes import *
...
    screen = SDL_CreateRGBSurface(
            0, 320, 200, 32, 0, 0, 0, 0
        )[0]

    pixels = cast(screen.pixels, POINTER(c_uint))

    for i in range(320 * 200):
        pixels[i] = SDL_MapRGB(screen.format, 0, 128, 0)
...
SDL2 and ctypes are both a little bit annoying but it works. Other useful functions include SDL_LoadBMP, SDL_SaveBMP and SDL_BlitSurface, which is how I move sub-tiles around.
automatically determine which tiles fit together either by analysing the pixels along the boundaries
Concepts from JPEG compression such as cosine transforms could be used but in general a tile resolution is so low, an algorithm (or a human) is not able to tell what a tile represents if the context around it is unknown. Like... Is that gray-ish noise a wall or some lunar soil?
looking at which tile combinations the user has already placed
I don't remember if this has already been mentioned:
https://github.com/mxgmn/WaveFunctionCollapse
They'll probably implement it in Tiled and other engines at some point. At its core it's just Sudoku solver.
TMC
Metal King Slime
Posts: 4308
Joined: Sun Apr 10, 2011 9:19 am

Re: Decoding the autotile pattern

Post by TMC »

Thanks for linking that Tiled documentation. Actually, that's great, and I'm tempted to first just copy how they do it.
And I see that they have even more advanced autotiling: https://doc.mapeditor.org/en/stable/manual/automapping/
And that automapping has the sort of power I hoped for (e.g. placing tiles on multiple layers). But the problem is that you have to write the rules in a text file, which is definitely not what I had in mind.

That said, Tiled just keeps getting better to the point that I feel like just implementing import/export from/to Tiled would be the most time-effective way to improve mapping in the OHR. It's been requested a number of times, I just haven't gotten around to it.
I don't remember if this has already been mentioned:
https://github.com/mxgmn/WaveFunctionCollapse
They'll probably implement it in Tiled and other engines at some point. At its core it's just Sudoku solver.
I actually helped Seilburg port this library to GDscript (ie for use in Godot), but we ended up not using it, partially because it was too slow (WFC is slow, and porting to gdscript made it far slower) but also because we didn't need it. ...And also we didn't fully debug it. (At that point neither of us had experience using C# in Godot). But I'm not a fan of its inference algorithm and think it's not suitable for autotiling anyway, because every time you place a tile only tiles within a small radius (adjustable, normally 1-3 tiles) would be candidates for changing, so the search space is small. So I would use a simple optimiser (the goal is to minimise number of incompatible adjacent tiles) like annealing or branch-and-bound backtracking rather than WFC's really complicated mean-field inference (which isn't a particularly good algorithm anyway). So I think I can do better, but yes, constraint solvers are what I had in mind.
Concepts from JPEG compression such as cosine transforms could be used but in general a tile resolution is so low, an algorithm (or a human) is not able to tell what a tile represents if the context around it is unknown.
I don't think Fourier basis functions are suitable; small wavelets would be far better. And other small filters/local feature detectors. The low resolution shouldn't be a problem, as all that's needed is to judge whether the edges of two tiles are similar: colour, edges, texture. Would only want to look at the strip about 2-4 pixels along each edge.
lennyhome
Slime Knight
Posts: 115
Joined: Fri Feb 14, 2020 6:07 am

Re: Decoding the autotile pattern

Post by lennyhome »

you have to write the rules in a text file
That's nasty and I have mixed feelings about Tiled because it's one of those open source programs that calls home every time you open it. It's a drama waiting to happen.
implementing import/export
I would try to have an OHRRPGCE export plugin accepted by them for publicity. I suspect it may not be very practical because I don't think they have an API to tell the user which features are available in the target engine and which aren't.

In the Quake level editor world, a big chunk of the complexity comes from trying to determine if a particular monster is available in the particular variation of the Quake engine the user decided to target. There are special comments that must be placed in the source code of the game to announce the availability of a feature to the editor.

To my knowledge, Tiled makes no attempt at anything like that. I'm sure they will at some point.
small wavelets would be far better
Although my math skills aren't the best, I'm always interested in fringe stuff.
TMC
Metal King Slime
Posts: 4308
Joined: Sun Apr 10, 2011 9:19 am

Re: Decoding the autotile pattern

Post by TMC »

Yes, I thought of the publicity aspect. But I'd rather delau that until after the OHR's map and tileset file formats are replaced, which will make import/export of map data far more practical. I'm not familiar enough with Tiled to even know what features it has that we wouldn't support, but I think a few more of them would get OHR equivalents over time. I have considered supporting flipped/rotated tiles too, though I didn't like the idea at first.

Wavelets are very mainstream in image processing, even if JPEG2000 never caught on. But even CNNs use wavelets on the lowest convolutional level automatically.
lennyhome
Slime Knight
Posts: 115
Joined: Fri Feb 14, 2020 6:07 am

Re: Decoding the autotile pattern

Post by lennyhome »

Tiled has way too many features. When you'll see them you'll make sense of my criticism in my previous post.

I didn't mean to say that wavelets are fringe. I meant that I like challenging computer stuff in general.

Years ago I found this:
https://en.wikipedia.org/wiki/Hadamard_transform
and it inspired me to write some audio/video processing stuff. I have a folder full of code (Java unfortunately), however one day I lost interest in it and then I never bothered to document it.

EDIT:
Image
This is what I had in mind. I can paint the terrain in GIMP at double the resolution on the left side and then a script automatically halves it and re-arranges it.

The script is nothing special. It's just a bunch of Python/PySDL2 blit operations but the concept is interesting. Initially I thought that I had to write some special resizing algorithm. It could still be done for some slight improvement in quality. But then I realized that as long as the scale factor is an interger, then shrinkSurface from sdl_gfx will not cause bleeding edges.

I've added rulers to help set up GIMP guides and the special tile marker.

Also before I permanently forget:
The loop over all the possible tile might be a bit slow, could build a size-256 lookup table to speed it up dramatically.
I wanted to show the mechanics because something similar is relevant for collision detection as well. I'm aware that I'm doing a linear reverse-lookup on an array per tile but if I didn't do it that way it would have been just a table with 256 mysterious numbers in it.
I have considered supporting flipped/rotated tiles
The SNES hardware had support for mirroring but in practice it's almost useless because any pseudo-3d shading will break the symmetries. I wouldn't bother.
even if JPEG2000 never caught on
A lot of "submarine patents" were discovered. Just like with anything remotely related to OpenCV. You have to be ready to receive a tight package of lawsuits and pure hate if you ever succeed in making any money with it.
Post Reply