Last active
November 29, 2023 12:43
-
-
Save BoldBigflank/5803651 to your computer and use it in GitHub Desktop.
Convert an image of a map into its generated tile-set.Command line args: tileWidth, tileHeight, fileexample:python Image2Map.py 16 16 map.png
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Filename : Image2Map.py | |
# Authors : Alex Swan, Georg Muntingh and Bjorn Lindeijer | |
# Version : 1.3 | |
# Date : June 17, 2013 | |
# Copyright : Public Domain | |
import os, sys, networkx | |
from PIL import Image | |
class TileMap: | |
""" This class represents a map of tiles. | |
""" | |
def __init__(self, file, tileX, tileY): | |
# For initialization, map image with filename file should be specified, together with the | |
# tile size (tile X, tileY). First we set the tile sizes. | |
self.TileX, self.TileY = tileX, tileY | |
# Open the map and find its attributes. | |
print "Opening the map image file: " + file | |
self.MapImage = Image.open(file) | |
self.MapImageWidth, self.MapImageHeight = self.MapImage.size | |
self.Width, self.Height = self.MapImageWidth / self.TileX, self.MapImageHeight / self.TileY | |
# Store the unique tiles in a list and a hash, and the map in a list. | |
self.MapList, self.TileList, self.TileDict = self.parseMap() | |
# Create a graph that contains the information that is relevant for the article. | |
self.graphFromList() | |
# We create a dictionary self.FullTileMap whose keys will be the coordinates | |
# for the image of unique tiles, and the values are the unique tile numbers. | |
self.FullTileMap = {} | |
# Extract maximal components from G into the dictionary TileMap, and combine them | |
# into self.FullTileMap using a method that places them as close to each other as | |
# possible. | |
while self.G.nodes() != []: | |
v = self.G.nodes()[0] | |
TileMap, K = self.growTileMap({(0, 0): v}, self.G, 0, 0, v) | |
self.FullTileMap = self.composeDictionaries(self.FullTileMap, TileMap) | |
self.G.remove_nodes_from(TileMap.values()) | |
# Create an image file from our map of unique tiles. | |
self.TileImage = self.getTileImage() | |
def parseMap(self): | |
""" This function takes the map image, and obtains | |
* a list TList of unique tiles. | |
* a hash TDict of unique tiles. | |
* a double list self.MapList of where an entry equals i if | |
self.TileList[i] is the corresponding picture on the map image. | |
""" | |
MList = [[-1 for i in range(self.Width)] for j in range(self.Height)] # TODO: Make this a single list | |
TList = [] | |
TDict = {} | |
progress = -1 | |
print "Parsing the Map: " | |
# Jump through the map image in 8 x 8-tile steps. In each step: | |
# * If the string of the tile is in the dictionary, place its value in map list MList[y][x]. | |
# * Otherwise, add this tile to the list, and add its string to the dictionary with value "the | |
# number of elements in the list". Also place this value in MList[y][x]. | |
for y in range(self.Height): | |
for x in range(self.Width): | |
box = self.TileX * x, self.TileY * y, self.TileX * (x+1), self.TileY * (y+1) | |
tile = self.MapImage.crop(box) | |
s = tile.tostring() | |
if TDict.has_key(s): | |
MList[y][x] = TDict[s] | |
else: | |
TList.append(tile) | |
TDict[s] = len(TList) | |
MList[y][x] = len(TList) | |
# Calculate the progress, and print it to the screen. | |
p = ((x + y * self.Width) * 100) / (self.Width * self.Height) | |
if progress != p: | |
progress = p | |
self.printProgress(progress) | |
self.printProgress(100) | |
print "Done!" | |
return MList, TList, TDict | |
def printProgress(self, percentage): | |
""" This function prints the percentage on the current row after erasing what is already there. | |
""" | |
print '%s\r' % ' '*20, # clean up row | |
print '%3d%% ' % percentage, # ending with comma prevents newline from being appended | |
sys.stdout.flush() | |
def getTileImage(self): | |
""" This function takes the hash of unique tiles self.FullTileMap and | |
creates a tileset image from it. | |
""" | |
H = self.FullTileMap | |
Xmin = min([ h[1] for h in H.keys() ]) | |
Xmax = max([ h[1] for h in H.keys() ]) | |
Ymin = min([ h[0] for h in H.keys() ]) | |
Ymax = max([ h[0] for h in H.keys() ]) | |
TileImage = Image.new("RGB", (self.TileX * (Xmax - Xmin + 1), self.TileY * (Ymax - Ymin + 1) ) ) | |
for i in range(Ymin, Ymax + 1): | |
for j in range(Xmin, Xmax + 1): | |
if (i,j) in H: | |
box = ( self.TileX * (j - Xmin) , self.TileY * (i - Ymin), \ | |
self.TileX * (j - Xmin + 1), self.TileY * (i - Ymin + 1) ) | |
TileImage.paste(self.TileList[H[(i,j)] - 1].convert("RGB"), box) | |
return TileImage | |
def printHash(self, H): | |
""" This function nicely aligns dictionaries with elements of the form | |
"(y, x): n" in a table, in which row y, column x has entry n. | |
In this specific case (x, y) will be the tile coordinates at which | |
tile n will be placed in the tile image. | |
""" | |
Xmin = min([ h[1] for h in H.keys() ]) | |
Xmax = max([ h[1] for h in H.keys() ]) | |
Ymin = min([ h[0] for h in H.keys() ]) | |
Ymax = max([ h[0] for h in H.keys() ]) | |
# Find the number of symbols we need to write down the tile numbers. | |
D = len(str(max(H.values()))) | |
st = "" | |
for i in range(Ymin, Ymax + 1): | |
for j in range(Xmin, Xmax + 1): | |
if not (i,j) in H: | |
st = st + "|" | |
for k in range(D): | |
st = st + "." | |
else: | |
h = H[(i,j)] | |
d = len(str(h)) | |
st = st + "|" | |
for k in range(D-d): | |
st = st + "." | |
st = st + str(h) | |
st = st + "|\n" | |
print st | |
def addEdge(self, s, t, dir): | |
""" This function increases abs(value) of an edge st in a graph G, taking the | |
'direction' of st into account. | |
s: a start vertex | |
t: an end vertex | |
dir: a value depicting the st-direction, | |
+1 for left -> right | |
-1 for up -> down | |
""" | |
if self.G.has_edge(s, t): | |
values = [ value for value in self.G.get_edge_data(s, t) if (dir * value) > 0 ] | |
else: | |
values = [] | |
if values: | |
self.G.remove_edge(s, t, values[0]) # increase the value by 1 | |
self.G.add_edge(s, t, values[0] + dir) | |
else: | |
self.G.add_edge(s, t, dir) # create a dir-valued edge | |
def graphFromList(self): | |
""" This function constructs a weighted directed graph from the | |
list that depicts the map using the following scheme: | |
Left A, Right B -> add (A, B, 1) | |
Left B, Right A -> add (B, A, 1) | |
Up A, Down B -> add (A, B,-1) | |
Up B, Down A -> add (B, A,-1) | |
We then add all similar edges together, so for instance | |
(A, B, 1) and (A, B, 1) -> (A, B, 2) | |
but *NOT* | |
(A, B, 1) and (A, B, -1) -> (A, B, 0) | |
""" | |
self.G = networkx.MultiDiGraph(selfloops = False, multiedges = True) | |
L = self.MapList | |
progress = -1 | |
print "Generating the graph: " | |
# Now add for every Cartesian crossing an edge (or a value) in G | |
for i in range(len(L) - 1): | |
for j in range(len(L[0]) - 1): | |
self.addEdge(L[i][j], L[i][j + 1], 1) # L-R, +1 | |
self.addEdge(L[i][j], L[i + 1][j], -1) # U-D, -1 | |
# Calculate the progress, and print it to the screen. | |
p = ((j + i * len(L)) * 100) / (len(L) * len(L[0])) | |
if progress != p: | |
progress = p | |
self.printProgress(progress) | |
# What remains is the bottom and right line of edges: | |
for j in range(len(L[0]) - 1): | |
self.addEdge(L[len(L) - 1][j], L[len(L) - 1][j + 1], 1) | |
for i in range(len(L) - 1): | |
self.addEdge(L[i][len(L[0]) - 1], L[i + 1][len(L[0]) - 1], -1) | |
# Now show 100% progress and say we're done. | |
self.printProgress(100) | |
print "Done!" | |
def growTileMap(self, TileMap, G, posX, posY, curV): | |
""" This is a recursive function that arranges a map of unique tiles. | |
""" | |
# For each of the directions, make a possible edge-list to choose from, | |
# and combine them into one list Edges such that Edges[i] stands | |
# for the edges with direction code i, where | |
# 0 <-> up | |
# 1 <-> right | |
# 2 <-> down | |
# 3 <-> left | |
LL = [e for e in G.in_edges(curV, keys=True, data=True) if e[2] > 0] | |
LU = [e for e in G.in_edges(curV, keys=True, data=True) if e[2] < 0] | |
LR = [e for e in G.out_edges(curV, keys=True, data=True) if e[2] > 0] | |
LD = [e for e in G.out_edges(curV, keys=True, data=True) if e[2] < 0] | |
Edges = [LU, LR, LD, LL] | |
# We want to visit all directions such that we visit the direction with | |
# the smallest amount of possible tiles first. This is because these tiles | |
# will have the smallest probability to fit in at a later stage. It will | |
# also embed blocks of tiles that appear only in one configuration | |
# (pictures chopped up in tiles). | |
dir = [ [ Edges[i], i ] for i in range(4)] | |
dir.sort(cmp = lambda L1, L2: len(L1[0]) - len(L2[0])) | |
dir = [ x[1] for x in dir] | |
while dir != []: | |
direction = dir[0] | |
if Edges[direction] != []: | |
E = Edges[direction] | |
# Now order E with respect to the values of its edges. This will | |
# make the algorithm start with a combination that appears most | |
# often in the graph, which is a measure for how much two tiles | |
# "belong together". | |
E.sort(cmp = lambda e, f: abs(e[2]) - abs(f[2]), reverse = True) | |
# Now walk through E until you find an edge that fits with | |
# the previously placed tiles in TileMap | |
isPlaced = False | |
while E != [] and isPlaced == False: | |
e = E[0] | |
# We need to know the end vertex and the new position. | |
if direction == 0: | |
endV = e[0] | |
NX, NY = posX, posY - 1 | |
elif direction == 1: | |
endV = e[1] | |
NX, NY = posX + 1, posY | |
elif direction == 2: | |
endV = e[1] | |
NX, NY = posX, posY + 1 | |
elif direction == 3: | |
endV = e[0] | |
NX, NY = posX - 1, posY | |
# Now in case position NX, NY is not already taken and endV is | |
# compatible with "surrounding edges" in our graph, then we can | |
# add endV to our TileMap. | |
if (not (NY, NX) in TileMap) and (TileMap.values().count(endV) == 0) and \ | |
( (not (NY-1, NX) in TileMap) or G.has_edge(TileMap[(NY-1, NX)], endV) ) and \ | |
( (not (NY, NX+1) in TileMap) or G.has_edge(endV, TileMap[(NY, NX+1)]) ) and \ | |
( (not (NY+1, NX) in TileMap) or G.has_edge(endV, TileMap[(NY+1), NX]) ) and \ | |
( (not (NY, NX-1) in TileMap) or G.has_edge(TileMap[(NY, NX-1)], endV) ): | |
# Add this node to our TileMap and delete the edge we just processed. | |
TileMap[(NY, NX)] = endV | |
isPlaced = True | |
G.remove_edge(e[0], e[1]) | |
# Call the procedure recursively with this new node. | |
TileMap, G = self.growTileMap(TileMap, G, NX, NY, endV) | |
E = E[1:len(E)] # Chop of the first edge | |
dir = dir[1:len(dir)] # Chop of the first direction | |
return TileMap, G | |
def centerOfDictionary(self, H): | |
""" Returns the center of the dictionary, that is, the average of all keys. | |
""" | |
L = H.keys() | |
return [ int(round( sum([l[1] for l in L]) / (len(L) + 0.0) )), \ | |
int(round( sum([l[0] for l in L]) / (len(L) + 0.0) )) ] | |
def composeDictionaries(self, H1, H2): | |
""" This method takes two dictionaries H1, H2 that represent pieces of the | |
maps of unique tiles, and pastes the second into the first, as close to | |
their centers -- as close together -- as possible. | |
""" | |
# In the first step H1 will be empty, and we return just H2. | |
if H1 == {}: | |
return H2 | |
CX1, CY1 = self.centerOfDictionary(H1) | |
CX2, CY2 = self.centerOfDictionary(H2) | |
# To make sure we fit H2 in as central as possible in H1, we walk in a spiral | |
# around the center of H1, the offset being X, Y. | |
# |.4|.5|.6| | |
# |.3|.0|.7| | |
# |.2|.1|.8| | |
# ...|.9| | |
X, Y = 0, 0 | |
foundFit = False | |
while foundFit == False: | |
# We check if H2 can be placed at location (CX1 + X, CY1 + Y) | |
isFit = True | |
keys = H2.keys() | |
# As long as there are keys in H2 left and we found no counter example: | |
while keys != [] and isFit: | |
(y, x) = keys.pop() | |
x1, y1 = x - CX2 + CX1 + X, y - CY2 + CY1 + Y | |
if H1.has_key((y1, x1)) or H1.has_key((y1 - 1, x1)) or H1.has_key((y1, x1 + 1)) or \ | |
H1.has_key((y1 + 1, x1)) or H1.has_key((y1, x1 - 1)): | |
isFit = False | |
# If we found a fit, embed H2 into H1 accordingly. | |
if isFit: | |
for (y, x) in H2.keys(): | |
x1, y1 = x - CX2 + CX1 + X, y - CY2 + CY1 + Y | |
H1[(y1, x1)] = H2[(y, x)] | |
foundFit = True | |
# Update the offset (X, Y) from the center of H1, by spiraling away. | |
if X == 0 and Y == 0: | |
Y += 1 # The first direction away from (0,0) | |
elif Y < 0 and X < -Y and X >= Y: | |
X += 1 | |
elif X > 0 and Y <= X and Y >= -X: | |
Y += 1 | |
elif Y > 0 and X > -Y and X < Y: | |
X -= 1 | |
elif X < 0 and Y > X and Y <= -X: | |
Y -= 1 | |
return H1 | |
if sys.argv[1] == "--help": | |
print "Usage : python Image2Map.py [tileX] [tileY] files..." | |
print "Example: python Image2Map.py 8 8 Sewers.png Caves.png" | |
elif len(sys.argv) < 4: | |
print "Error : You specified too few arguments!\n" | |
print "Usage : python Image2Map.py [tileX] [tileY] files..." | |
print "Example: python Image2Map.py 8 8 Sewers.png Caves.png" | |
else: | |
tileX, tileY = int(sys.argv[1]), int(sys.argv[2]) | |
for file in sys.argv[3:]: | |
map = TileMap(file, tileX, tileY) | |
tilefile = os.path.splitext(file)[0] + "-Tileset" + ".png" | |
print "Saving the tileset image into the file: " + tilefile | |
map.TileImage.save( tilefile, "PNG" ) | |
print "Pretty-printing the tileset:" + "\n" | |
map.printHash(map.FullTileMap) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
In lines 108 and 115, I think it would be better to use "RGBA" instead of "RGB", so it would be possible to use maps with transparencies.