sprite-optimizer/sprite-optimizer.py

#!/usr/bin/env python3

### Readme ###################################################################
# name: sprite-optimizer
# version: 1.1
# author: Dark-Storm
# license: CeCILL v2.1
#
# comments:
# lines are stored as arrays of pixels
##############################################################################


from argparse import ArgumentParser
from bresenham import bresenham
from PIL import Image, ImageDraw
from random import randint
import sys
from time import time

rand = lambda: randint(0,200)
progress = False


def print_stats(img):
	"""Print number and percentage of black pixels"""
	pixels = img.getdata()
	count = sum([1 for i in pixels if i == 0])
	if progress:
		print("{} black pixels over {} ({:.1%})".format(count, len(pixels), count/len(pixels)))


def get_lines(img):
	"""Generate all potential lines the image contains"""
	lines = set()
	lines_uniq = set()
	pixels = {(x, y) for x in range(img.width) for y in range(img.height) if img.getpixel((x, y)) == 0}

	i, n = 0, len(pixels) * len(pixels)

	if progress:
		print("Get lines:", end = "")
	# for each pair of pixels, get the line
	for a in pixels:
		for b in pixels:
			line = tuple(bresenham(*a, *b))
			line_uniq = tuple(sorted(line))

			# if image contains the line, put it on the array
			if set(line).issubset(pixels) and line_uniq not in lines_uniq:
				lines.add(line)
				lines_uniq.add(line_uniq)
			i += 1
			if progress:
				print("\rGet lines: {:.1%}".format(i / n), end = "")

	if progress:
		print("\rGet lines: complete")
		print("{} lines found".format(len(lines)))
	return list(lines)


def removing_useless(lines):
	"""Remove lines that are sub-lines of other ones"""
	results = []
	n = len(lines)

	if progress:
		print("Remove useless lines:", end = "")
	# for each line, see if there is a line that contains every pixel of it
	lines_set = [ set(l) for l in lines ]

	for i, l in enumerate(lines_set):
		inclusions = 0
		# others are all lines that are not l
		for j, k in enumerate(lines_set):
			if i == j: continue
			if l.issubset(k):
				inclusions += 1
				break
		# or len(l) == 1 : we keep single pixels to complete the image if necessary
		# TODO: do some tests to see if it's worth or not
		if inclusions == 0 or len(l) == 1:
			results.append((len(l), lines[i], l))
		if progress:
			print("\rRemove useless lines: {:.1%}".format(i / n), end = "")
	if progress:
		print("\rRemove useless lines: complete")

	if progress:
		print("{} lines kept".format(len(results)))
	return results


def get_best_solution(img, lines):
	"""Compute an optimized solution. The magic part of the algorithm"""
	px_left = {(x, y) for x in range(img.width) for y in range(img.height)
	           if img.getpixel((x, y)) == 0}
	results = []
	n = len(px_left)

	if progress:
		print("Draw:", end = "")
	# while the entier image has not been drown
	while px_left:
		# define the length of lines
		lines = [(len(l_set.intersection(px_left)) - len(l)/(2*max(img.size)),
			      l, l_set) for n, l, l_set in lines]
		# sort them by length
		lines = sorted(lines)
		# pop the longest
		(p, line, line_set) = lines.pop()
		# define the pixels that are not covered by any lines
		px_left = px_left.difference(line_set)
		results.append((line[0], line[-1]))
		if progress:
			print("\rDraw: {:.0%}".format(1 - len(px_left)/n), end="")
	if progress:
		print("\rDraw: complete")

	if progress:
		print("Solution found in {} lines".format(len(results)))
	return results


def generate_code(lines, args):
	"""Generate Basic Casio code"""
	str_x, str_y = "{", "{"

	# Casio's bresenham is reversed compared to classic ones
	# so we need to reverse the ends of the lines
	for (x_end, y_end), (x_start, y_start) in lines:
		x_start, y_start = x_start + int(args.offset[0]), y_start + int(args.offset[1])
		x_end, y_end = x_end + int(args.offset[0]), y_end + int(args.offset[1])
		str_x += "{}, ".format(get_coord(x_start, x_end))
		str_y += "{}, ".format(get_coord(y_start, y_end))

	str_x = str_x[:-2] + "}"
	str_y = str_y[:-2] + "}"
	code = "Graph(X,Y)=({}, {})".format(str_x, str_y)
	return code


def generate_raw(lines, args):
	"""Generate raw line coordinates"""
	ox, oy = int(args.offset[0]), int(args.offset[1])
	code = ""

	for (x_end, y_end), (x_start, y_start) in lines:
		code += f"{x_start} {y_start} {x_end} {y_end}\n"

	return code


# From Zezeombye's BIDE
def get_coord(start, end):
	"""Convert a pair of coordonates to the appropriate x+yT  Multi DrawStat output"""
	result = "";
	if start != 0:
		result += str(start)
	delta = end - start
	if delta != 0:
		if delta > 0 and start != 0:
			result += "+";
		if delta < 0:
			result += "-";
		if delta != 1 and delta != -1:
			result += str(abs(delta))
		result += "T";
	if len(result) == 0:
		result = "0"
	return result;



if __name__ == "__main__":
	start = time()

	parser = ArgumentParser(description='Generate the Multi DrawStat code for an image.')
	parser.add_argument('path', type=str, help='path of the image to process')
	parser.add_argument('-e', '--export', nargs=1, help='export the code into <EXPORT>')
	parser.add_argument('-o', '--offset', nargs=2, default=(0, 0), help='offset for viewwindow. Default: (0, 0)')
	parser.add_argument('-f', '--flip', action='store_true', help='flip image vertically (for inverted ViewWindow)')
	parser.add_argument('-i', '--info', action='store_true', help='print informative stats')
	parser.add_argument('-p', '--progress', action='store_true', help='print progress info')
	parser.add_argument('-s', '--show', action='store_true', help='show the result')
	parser.add_argument('-d', '--draw', action='store_true', help='draw the result into a new file')
	parser.add_argument('-r', '--raw', action='store_true', help='print raw line coordinates')

	args = parser.parse_args()

	progress = args.progress

	try:
		image = Image.open(args.path)
	except:
		sys.exit("Error! Unable to open file.")

	try:
		image = image.convert('1')
	except:
		sys.exit("Error! Unable to convert to 1bit")

	if args.flip:
		image = image.transpose(Image.FLIP_TOP_BOTTOM)

	if args.info:
		print_stats(image)

	lines = get_lines(image)
	lines = removing_useless(lines)
	lines = get_best_solution(image, lines)

	if args.raw:
		code = generate_raw(lines, args)
	else:
		code = generate_code(lines, args)

	if args.draw or args.show:
		export = Image.new('RGB', image.size, 'white')
		drawer = ImageDraw.Draw(export)
		for ((a, b), (c, d)) in reversed(lines):
			drawer.line((a, b, c, d), fill=(rand(), rand(), rand()))
		export = export.resize((export.width * 8, export.height * 8))
		if args.draw:
			export.save(args.path[:-4] + "_gen.png")
		if args.show:
			export.show()

	if args.info:
		print("{} processed in {} lines ({:.3}s)".format(args.path, len(lines), time() - start))
	if args.export:
		try:
			f = open(args.export[0], 'w')
			f.write(code)
			f.close()
			print("Code saved into", args.export[0])
		except Exception as e:
			sys.exit("Error: " + str(e))
	print(code)