mazejudge.py

import collections
import numpy as np
import scipy.sparse
import scipy.sparse.linalg
import sys
import imageio
import io
import base64

class MazeJudge:
    def __init__(self, width, height):
        """ Creates a maze with given width and height. Coordinate system starts at (0, 0) in the topleft corner. """
        self.width = width
        self.height = height
        self.hwalls = np.zeros((width - 1, height), dtype=np.bool)
        self.vwalls = np.zeros((width, height - 1), dtype=np.bool)
        self.starts = []
        self.exits = []

    def set_start(self, x1, y1, x2, y2):
        """ Sets the two connected starting tiles as (x1, y1) and (x2, y2) along a border. """
        assert abs(x1 - x2) + abs(y1 - y2) == 1
        assert x1 == 0 or x1 == self.width - 1 or y1 == 0 or y1 == self.height - 1
        assert x2 == 0 or x2 == self.width - 1 or y2 == 0 or y2 == self.height - 1
        self.starts = [(x1, y1), (x2, y2)]
        assert not(set(self.starts) & set(self.exits))

    def set_exit(self, x1, y1, x2, y2):
        """ Sets the two connected exit tiles as (x1, y1) and (x2, y2) along a border. """
        assert abs(x1 - x2) + abs(y1 - y2) == 1
        assert x1 == 0 or x1 == self.width - 1 or y1 == 0 or y1 == self.height - 1
        assert x2 == 0 or x2 == self.width - 1 or y2 == 0 or y2 == self.height - 1
        self.exits = [(x1, y1), (x2, y2)]
        assert not(set(self.starts) & set(self.exits))

    def add_horiz_wall(self, x, y):
        """ Adds a horizontal wall between (x, y) and (x+1, y). """
        assert 0 <= x < x+1 < self.width and 0 <= y < self.height
        self.hwalls[x,y] = True

    def add_vert_wall(self, x, y):
        """ Adds a vertical wall between (x, y) and (x, y+1). """
        assert 0 <= x < self.width and 0 <= y < y+1 < self.height
        self.vwalls[x,y] = True

    def save_image(self, filename):
        """ Saves the maze as an image. """
        self._save_image(filename)

    def as_ascii(self):
        """ Returns a pretty ASCII representation of the maze. """
        self._fix_maze()
        lines = ["+" + "---+"*self.width]
        for y in range(self.height):
            lines.append("|" + "".join(" {} {}".format("S" if (x, y) in self.starts else "E" if (x, y) in self.exits else " ",
                                                       " |"[x == self.width - 1 or int(self.hwalls[x,y])])
                                       for x in range(self.width)))
            lines.append("+" + "".join("---+" if y == self.height - 1 or self.vwalls[x,y] else "   +"
                                       for x in range(self.width)))
        return "\n".join(lines)

    def as_compact_string(self):
        """ Returns a compact string for communicating mazes. """
        assert self.starts and self.exits
        self._fix_maze()
        f = io.BytesIO()
        np.savez_compressed(f, [self.width,self.height], self.starts, self.exits, self.hwalls, self.vwalls)
        return base64.b64encode(f.getvalue()).decode("utf-8")

    @classmethod
    def from_compact_string(cls, s):
        """ Constructs a maze from a compact string. """
        data = np.load(io.BytesIO(base64.b64decode(s)), allow_pickle=False)
        [width, height], starts, exits, hwalls, vwalls = data.values()
        self = cls(width, height)
        self.set_start(*(starts.flatten()))
        self.set_exit(*(exits.flatten()))
        self.hwalls = hwalls
        self.vwalls = vwalls
        data.close()
        return self

    def score(self, verbose=True):
        """ Computes the score of this maze. """
        self._fix_maze()
        if verbose: print("Building graph.", file=sys.stderr)
        nodes, edges = self._build_graph()
        non_absorb = [n for n in nodes if n[0] not in self.exits]
        non_absorb_index = {n: i  for i, n in enumerate(non_absorb)}

        if verbose: print("Building transition matrix.", file=sys.stderr)
        data = []; row_idx = []; col_idx = []
        for i, node in enumerate(non_absorb):
            row_idx.append(i)
            col_idx.append(i)
            data.append(1)
            for neighbor in edges[node]:
                try:
                    j = non_absorb_index[neighbor]
                    row_idx.append(i)
                    col_idx.append(j)
                    data.append(-1/len(edges[node]))
                except KeyError:
                    # Edge to absorbing state omitted in I-Q.
                    pass

        Ql = len(non_absorb)
        ImQ = scipy.sparse.coo_matrix((data, (row_idx, col_idx)), shape=(Ql, Ql), dtype=np.float64)
        if verbose: print("Solving for mean exit time.", file=sys.stderr)
        mean_steps = scipy.sparse.linalg.spsolve(ImQ.tocsr(), np.ones((Ql,)))[0]
        return int(round(mean_steps - 1))  # -1 for _virt_start

    def _fix_maze(self):
        # Remove any walls between start/exit pairs.
        if self.starts:
            x1, y1 = self.starts[0]
            x2, y2 = self.starts[1]
            if x1 != x2: self.hwalls[min(x1, x2),y1] = 0
            if y1 != y2: self.vwalls[x1,min(y1,y2)] = 0
        if self.exits:
            x1, y1 = self.exits[0]
            x2, y2 = self.exits[1]
            if x1 != x2: self.hwalls[min(x1, x2),y1] = 0
            if y1 != y2: self.vwalls[x1,min(y1,y2)] = 0

    def _unobstructed_dirs(self, x, y):
        dirs = []
        if x > 0 and not self.hwalls[x-1,y]: dirs.append((-1, 0))
        if x + 1 < self.width and not self.hwalls[x,y]: dirs.append((1, 0))
        if y > 0 and not self.vwalls[x,y-1]: dirs.append((0, -1))
        if y + 1 < self.height and not self.vwalls[x,y]: dirs.append((0, 1))
        return dirs

    def _negdir(self, dir):
        return (-dir[0], -dir[1])

    def _build_graph(self):
        assert len(self.starts) == len(self.exits) == 2

        # Face away from 1 when starting on 0 and vice versa.
        start0dir = (self.starts[0][0] - self.starts[1][0], self.starts[0][1] - self.starts[1][1])
        startnodes = [(self.starts[0], start0dir), (self.starts[1], self._negdir(start0dir))]
        nodes = ["_virt_start"] + startnodes
        nodeset = set(nodes)
        edges = collections.defaultdict(list)
        edges["_virt_start"] = [startnodes[0], startnodes[1]]
        unvisited = startnodes[:]
        exit_found = False
        while unvisited:
            node = unvisited.pop()
            (x, y), dir = node
            negdir = self._negdir(dir)
            moves = set(self._unobstructed_dirs(x, y)) - {negdir} or {negdir}

            for dx, dy in moves:
                neighbor = ((x + dx, y + dy), (dx, dy))
                edges[node].append(neighbor)
                if not neighbor in nodeset:
                    nodes.append(neighbor)
                    nodeset.add(neighbor)
                    unvisited.append(neighbor)
                    if neighbor[0] in self.exits:
                        exit_found = True

        if not exit_found:
            raise RuntimeError("exit unreachable from start")

        return nodes, edges

    def _save_image(self, filename):
        self._fix_maze()
        img = np.zeros((self.height * 2 + (self.height + 1) * 1, self.width * 2 + (self.width + 1) * 1, 3), np.uint8)

        wall = (0, 0, 0)
        start = (255, 0, 0)
        exit = (0, 0, 255)
        floor = (255, 255, 255)

        img[:,:] = floor
        img[0,:] = wall
        img[:,0] = wall

        for x in range(self.width):
            for y in range(self.height):
                cx, cy = 1+3*x, 1+3*y
                if x == self.width - 1 or self.hwalls[x,y]:
                    img[cy,cx+2] = wall
                    img[cy+1,cx+2] = wall
                if y == self.height - 1 or self.vwalls[x,y]:
                    img[cy+2,cx] = wall
                    img[cy+2,cx+1] = wall

        # Fill in corners.
        for x in range(self.width):
            for y in range(self.height):
                cx, cy = 3+3*x, 3+3*y
                fill_corner = False
                for dx in [-1, 0, 1]:
                    for dy in [-1, 0, 1]:
                        if abs(dx) + abs(dy) != 1: continue
                        if not (0 <= cx + dx < img.shape[1]): continue
                        if not (0 <= cy + dy < img.shape[0]): continue
                        fill_corner |= (tuple(img[cy+dy,cx+dx]) == wall)

                if fill_corner:
                    img[cy,cx] = wall

        if self.starts:
            (x1, y1), (x2, y2) = self.starts
            img[1+3*min(y1,y2):1+3*max(y1,y2)+2,1+3*min(x1,x2):1+3*max(x1,x2)+2] = start
        if self.exits:
            (x1, y1), (x2, y2) = self.exits
            img[1+3*min(y1,y2):1+3*max(y1,y2)+2,1+3*min(x1,x2):1+3*max(x1,x2)+2] = exit


        img = np.repeat(img, 2, axis=0)
        img = np.repeat(img, 2, axis=1)
        imageio.imwrite(filename, img)





def example(w, h, num_edges):
    maze = MazeJudge(w, h)
    for i in range(num_edges):
        if np.random.random() < 0.5:
            x, y = np.random.randint(0, maze.width - 1), np.random.randint(0, maze.height)
            maze.add_horiz_wall(x, y)
        else:
            x, y = np.random.randint(0, maze.width), np.random.randint(0, maze.height - 1)
            maze.add_vert_wall(x, y)
    maze.set_start(0, 0, 0, 1)
    maze.set_exit(maze.width-1, maze.height-1, maze.width-1, maze.height-2)

    print(maze.score())
    maze.save_image("maze.png")
    with open("maze.txt", "w") as f:
        f.write(maze.as_compact_string())

No, sorry.