[Deedolith]

Hello,

For a video game project using tile-mapping, I wrote a script checking that every tile (16x16) in a picture are unique (let's call this picture "tileset").

But I have a problem:
My script seems unable to detect if 2 tiles are equal when there are transparent areas, it even can't detect that 2 empty tiles are equals.

I did the following:

#!/usr/bin/env python

from gimpfu import *

import pygtk
pygtk.require("2.0")
import gtk

        # messBox function, not from me
def messBox(message, GTKtype, modal):
	if modal == 0:      
		flag = gtk.DIALOG_DESTROY_WITH_PARENT    
	else:   
		flag = gtk.DIALOG_MODAL|gtk.DIALOG_DESTROY_WITH_PARENT
		msgBox = gtk.MessageDialog(None, flag, GTKtype, gtk.BUTTONS_OK, message)
		ret = msgBox.run()
		msgBox.destroy()

def python_tileChk(calque):
	msg = ""
		# retrieve 1st tile to check with the others
	for x in range(0, calque.width, 16):
		for y in range(0, calque.height, 16):
				tile1 = calque.get_pixel_rgn(x,y,16,16)[x : x+16, y : y+16]
					# retrieve 2nd tile to check with the 1st
				for a in range(0, calque.width, 16):      
					for b in range(0, calque.height, 16):
							# discard tile checking with itself
						if ((x != a) and (y != B)/>):
							tile2 = calque.get_pixel_rgn(a,b,16,16)[a : a+16, b : b+16]
								# check if the 2 tiles are equals
							if(tile1 == tile2):
								msg = msg + "Warning: Tile(" + str(x) + ", " + str(y) + ") and (" + str(a) + ", " + str(B)/> + ") are equal !"
	if msg == (""):
		msg = "All tiles ok"
	messBox(msg, gtk.MESSAGE_INFO, 1)
	return

No clue what's wrong here, I'll apreciate any help.

PS: I'm not used to develop with python much, and even less under gimp environment.

This post has been edited by Deedolith: 21 March 2012 - 07:35 PM

[ofnuts]

Can't tell what is wrong form a cursory look, but your algorithm is quadratic with the number of tiles, and so is the 4th power of your image size in pixels. So it won't be practical on big image. May I suggest instead:
- Create a a "signature" string from each tile (pr[0:16,0:16] may be enough
- add them one by one with the coordinates of the tile in a dictionary, using the signature as the key.
- if you have a collision when you insert a new tile "signature" then check if the two tiles are really equal (some signatures may imply that the pictures are equal).

This algorithm is linear over the tiles and so only quadratic over the image size.

[Deedolith]

If I understood correctly, my python_tileChk function should now look like this:

def python_tileChk(calque):
	msg = ""
	list = dict()
		# retrieve a tile
	for x in range(0, calque.width, 16):
		for y in range(0, calque.height, 16):
				tile = calque.get_pixel_rgn(x,y,16,16)[x : x+16, y : y+16]
					# turn it into string
				key = str(tile)
					# attempt to store it in dictionary
				if(key not in list):
					list[key] = tile
				else:
					msg = msg + "Warning: Tile(" + str(x) + ", " + str(y) + ") is duplicate\n"
	list.clear()
	if msg == (""):
		msg = "All tiles ok"
	messBox(msg, gtk.MESSAGE_INFO, 1)
	return

Well, that work a lot faster, alas the duplicate tiles issue remain ....

[ofnuts]

I think you have to use a "canonical" representation of your transparent areas... you can have a fully transparent pixel which is white (RGBA:255,255,255,0) or just red (RGBA:255,0,0,0). They are visually identical but still different (if you edit the layer mask you won't obtain the same picture). To make a canonical form where all fully transparent pixels are replaced by a fully transparent black pixel, copy the characters 4 by 4 from the raw form to the canonical form, while testing if the 4th character is 0, if so replace the 4 characters with (0,0,0,0).

Btw, come to think of it, this algorithm is a lot faster, but it ends up storing the whole layer as keys in the dictionary. But unless you process very large images I don't think it matters much.

[Deedolith]

I'm afraid I don't follow you there.
Do you mean that I'll need to test each RGBA pixels for each tiles ?

As for memory usage, there is a maximum of 256 tiles in a picture, so it isn't that much.

[ofnuts]

Deedolith, on 21 March 2012 - 11:31 AM, said:

I'm afraid I don't follow you there.
Do you mean that I'll need to test each RGBA pixels for each tiles ?

Yes, but only once... or you find a way, before calling your algorithm, to "blacken" (or whiten) all fully transparent pixels (maybe by getting a selection by thresholding the alpha channel for values <1).

Deedolith, on 21 March 2012 - 11:31 AM, said:

As for memory usage, there is a maximum of 256 tiles in a picture, so it isn't that much.

The things the algorithm uses as keys are the bitmaps of the 16x16 tiles you check (which are exactly one K each: 16x16x4). If you have a 512x512 pic, you'll have 32x32 = 1024 tiles, 1K each: 1M.

[Deedolith]

Well, finally I'll work without alpha channel to avoid more coding, from my tests, pixel access is slow.

Thanks for the replies tho, it helped a lot.

On the other hand, I also wrote a tile extractor script, wich look like this:

def tilesExtractor(calque):
	liste = dict()
	img = calque.image
		# create a new layer
	layer = gimp.Layer(img, calque.name + " tileset", img.width, img.height, calque.type, 100, NORMAL_MODE)
		# look for each unique tile, store it in a dictionary
	for x in range(0, calque.width, 16):
		for y in range(0, calque.height, 16):
			tile = calque.get_pixel_rgn(x,y,16,16)[x : x+16, y : y+16]
			key = str(tile)
			if(key not in liste):
				liste[key] = tile
	x = 0
	y = 0
		# write each tile in the new layer
	for key in liste.keys():
		if(x >= img.width):
			x = 0
			y = y + 16
		layer.get_pixel_rgn(x, y, 16, 16)[x: x+16, y: y+16] = liste[key]
		x = x + 16
	img.add_layer(layer, 0)
	liste.clear()
	return

[cloudes]

I think you have to use a "canonical" representation of your transparent areas..