Image2Map.py

# Filename  : Image2Map.py
# Authors   : Georg Muntingh and Bjorn Lindeijer
# Version   : 1.2
# Date      : June 16, 2010
# Copyright : Public Domain

import os, sys, Image, networkx

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, dirr):
        """ 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.edge[s][t] if (dirr * 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] + dirr)
        else:
            self.G.add_edge(s, t, dirr)             # 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)  if e[1] > 0]
        LU = [e for e in G.in_edges(curV)  if e[1] < 0]
        LR = [e for e in G.out_edges(curV) if e[1] > 0]
        LD = [e for e in G.out_edges(curV) if e[1] < 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[1]) - abs(f[1]), 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)

                        # 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)

MapWriter.py

# Filename  : MapWriter.py
# Authors   : Bjorn Lindeijer and Georg Muntingh
# Version   : 1.1
# Date      : April 29, 2008
# Copyright : Public Domain

import os, sys, Image, math
import struct, base64, zlib

from xml.dom.minidom import Document

class Tileset:
    """ This class represents a set of tiles.
    """

    def __init__(self, tileImageFile, tileWidth, tileHeight):
        self.TileWidth = tileWidth
        self.TileHeight = tileHeight
        self.Filename = tileImageFile
        self.Name = os.path.splitext(tileImageFile)[0]
        self.List = []
        self.TileDict = {}
        self.readTiles()

    def readTiles(self):
        """ This method reads the tiles from the tileset and also fills up the tile dictionary.
        """
        TileImage = Image.open(self.Filename).convert("RGB")
        TileIW, TileIH = TileImage.size
        TilesetW, TilesetH = TileIW / self.TileWidth, TileIH / self.TileHeight

        for y in range(TilesetH):
            for x in range(TilesetW):
                box = self.TileWidth * x, self.TileHeight * y, self.TileWidth * (x+1), self.TileHeight * (y+1)
                tile = TileImage.crop(box)
                self.List.append(tile)

                str = tile.tostring()
                if not self.TileDict.has_key(str):
                    self.TileDict[str] = len(self.List) - 1

    def findTile(self, tileImage):
        """ This method returns the tile index for the given tile image if it is part of this tileset,
            and returns 0 if the tile could not be found. Constant complexity due to dictionary lookup.
        """
        str = tileImage.tostring()
        if self.TileDict.has_key(str):
            return self.TileDict[str] + 1
        else:
            return 0

class TileMap:
    """ This class represents a tile map.
    """

    def __init__(self, mapImageFile, tileSet, tileWidth, tileHeight):
        self.TileWidth = tileWidth
        self.TileHeight = tileHeight
        self.TileSet = tileSet
        self.List = []
        self.readMap()

    def readMap(self):
        """ This function takes the map image, and obtains a list self.List, where
            an entry equals i if self.TileSet.List[i-1] is the corresponding picture on the map
            image. If a matching tile is not found, i is set to 0.
        """
        MapImage = Image.open(mapImageFile).convert("RGB")
        MapImageWidth, MapImageHeight = MapImage.size
        self.Width, self.Height = MapImageWidth / self.TileWidth, MapImageHeight / self.TileHeight
        progress = -1

        for y in range(self.Height):
            for x in range(self.Width):
                box = self.TileWidth * x, self.TileHeight * y, self.TileWidth * (x+1), self.TileHeight * (y+1)
                tile = MapImage.crop(box)
                self.List.append(self.TileSet.findTile(tile))

                # 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)

    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 write(self, fileName):
        doc = Document()
        map = doc.createElement("map")
        map.setAttribute("version", "0.99b")
        map.setAttribute("orientation", "orthogonal")
        map.setAttribute("width", str(self.Width))
        map.setAttribute("height", str(self.Height))
        map.setAttribute("tilewidth", str(self.TileWidth))
        map.setAttribute("tileheight", str(self.TileHeight))
        tileset = doc.createElement("tileset")
        tileset.setAttribute("name", self.TileSet.Name)
        tileset.setAttribute("firstgid", str(1))
        tileset.setAttribute("tilewidth", str(self.TileSet.TileWidth))
        tileset.setAttribute("tileheight", str(self.TileSet.TileHeight))
        image = doc.createElement("image")
        image.setAttribute("source", self.TileSet.Filename)
        tileset.appendChild(image)
        map.appendChild(tileset)
        layer = doc.createElement("layer")
        layer.setAttribute("name", "Ground")
        layer.setAttribute("width", str(self.Width))
        layer.setAttribute("height", str(self.Height))
        data = doc.createElement("data")

        data.setAttribute("encoding", "base64")
        TileData = ""
        for tileId in self.List:
            TileData = TileData + struct.pack("<l", tileId)  # pack the tileId into a long
        b64data = doc.createTextNode(base64.b64encode(TileData))
        data.appendChild(b64data)

        layer.appendChild(data)
        map.appendChild(layer)
        doc.appendChild(map)
        file = open(fileName, "w")
        file.write(doc.toprettyxml(indent = " "))
        file.close()

if sys.argv[1] == "--help":
    print "Usage  : python Image2Map.py [tileX] [tileY] <map image file> <tileset file>"
    print "Example: python MapWriter.py 8 8 JansHouse.png JansHouse-Tileset.png"
elif len(sys.argv) < 5:
    print "Error  : You specified too few arguments!\n"
    print "Usage  : python Image2Map.py [tileX] [tileY] <map image file> <tileset file>"
    print "Example: python MapWriter.py 8 8 JansHouse.png JansHouse-Tileset.png"
else:
    tileX, tileY = int(sys.argv[1]), int(sys.argv[2])
    mapImageFile, tileImageFile = sys.argv[3], sys.argv[4]
    map = TileMap(mapImageFile, Tileset(tileImageFile, tileX, tileY), tileX, tileY)
    map.write(os.path.splitext(mapImageFile)[0] + ".tmx")

Got it. Just had to change the "RGB" to "RGBA" in getTileImage

Two small changes to make this work with the latest libraries:

change the import to:

import os, sys, networkx
from PIL import Image

and change the call tile.tostring() to tile.tobytes() on line 69

Parsing the Map: 100% Done! Generating the graph: 100% Done! Traceback (most recent call last): File "C:\Users\ryans\Desktop\Mother 4\Image2Map2.py", line 378, in <module> map = TileMap(file, tileX, tileY) File "C:\Users\ryans\Desktop\Mother 4\Image2Map2.py", line 39, in __init__ v = self.G.nodes()[0] File "C:\Python27\lib\site-packages\networkx\classes\reportviews.py", line 178, in __getitem__ return self._nodes[n] KeyError: 0

Not sure why, but I'm getting this after it seems like it's finished and then no map gets produced.

Just in case anyone else stumbles here.

@ShrineFox : Downgrade networkx to v.1.X,

2.X returns a dictionary from nodes()

https://pypi.org/project/networkx/1.11/#files

Anybody has a version of this that runs on python3? I can't get it to work with any combination of old libraries.
@ACatThatPrograms I think networkx 1.9 doesn't work with python3 anymore since it tries to use cgi.escape which is deprecated (sigh)