tomchuk

a little place for me to write things down so I don't forget them

Solving Mazes with Python

I stumbled across the following ridiculous maze on Reddit. It's been a few years since my last AI class, so I decided to brush of the ol' pathfinding algorithms and take a crack at it. It may look like a gray square, but click it --- you'll see how crazy it really is.

Here's the code. You'll need progressbar and Pillow.

#!/usr/bin/env python

import math
import struct
import sys
from collections import deque
from progressbar import ProgressBar
from PIL import Image

class Maze():

    def __init__(self, image_file):
        self.image = Image.open(image_file)
        self.image = self.image.convert("RGB")
        self.w, self.h = self.image.size
        self.maze = self.image.load()

        self.start = self.end = None
        self._last_was_wall = True
        def check_cell(x,y):
            if any(self.maze[x,y]):
                if self._last_was_wall:
                    if not self.start:
                        self.start = (x,y)
                    elif not self.end:
                        self.end = (x,y)
                    else:
                        raise Exception('More than two openings')
                self._last_was_wall = False
            else:
                self._last_was_wall = True
        for y in range(self.h):        check_cell(0,y) # Left
        for x in range(self.w):        check_cell(x,self.h-1) # Bottom
        for y in range(self.h, 0, -1): check_cell(self.w-1,y-1) # Right
        for x in range(self.w, 0, -1): check_cell(x-1,0) # Top
        del self._last_was_wall

        self.search_depth = self.image.convert("1").histogram()[255]

        self.metadata = {}

    def adjacent(self, xy):
        rv = {}
        x,y = xy
        for x1,y1 in [(x,y-1), (x+1,y), (x,y+1), (x-1,y)]:
            try:
                if any(self.maze[x1,y1]):
                    rv[x1,y1] = self.maze[x1,y1]
            except IndexError:
                pass
        return rv

    def geometric_distance(self, c1, c2):
        return math.sqrt(abs(c1[0]-c2[0])**2 + abs(c1[1]-c2[1])**2)

    def get_heuristic(self, cell):
        h = 0
        try:
            x,y,h = struct.unpack('HHH', self.metadata[cell])
        except:
            pass
        return h

    def get_parents(self, cell):
        rv = []
        try:
            x,y,h = struct.unpack('HHH', self.metadata[cell])
        except (KeyError, struct.error):
            return rv

        while True:
            rv.append((x,y))
            try:
                x,y,h = struct.unpack('HHH', self.metadata[x,y])
            except (KeyError, struct.error):
                return rv
        return rv

    def save(self):
        for xy in self.path:
            self.maze[xy] = (255,0,0)
        self.image.save('solution.png')
        print 'Found path of length: %d' % len(self.path)

    def solve_astar(self):

        search_cell = self.start
        open_set = set()
        open_set.update([search_cell])
        closed_set = set()
        self.astar_done = 0

        pbar = ProgressBar().start()
        while len(open_set) > 0:

            if self.astar_done % 100 == 0:
                pbar.update(100.0*(float(len(closed_set))/float(self.search_depth)))
            self.astar_done += 1

            for cell in self.adjacent(search_cell):
                if cell == self.end:
                    x,y = search_cell
                    self.metadata[cell] = struct.pack('HHH', x, y, 0)
                    self.path = self.get_parents(cell)
                    pbar.finish()
                    self.save()
                    return

                if cell not in closed_set and cell not in open_set:
                    open_set.update([cell])
                    if cell not in self.metadata: self.metadata[cell] = []
                    self.metadata[cell] = struct.pack('HHH', search_cell[0],
                        search_cell[1], len(self.get_parents(cell)) + self.geometric_distance(cell, search_cell))

            closed_set.update([search_cell])
            try:
                open_set.remove(search_cell)
            except KeyError:
                pass
            search_cell = None

            for cell in open_set:
                if search_cell is None:
                    search_cell = cell
                    continue
                if self.get_heuristic(search_cell) > self.get_heuristic(cell):
                    search_cell = cell
        print 'No Solution'

    def _bfs(self):
        queue, enqueued = deque([(None, self.start)]), set([self.start])
        while queue:
            parent, n = queue.popleft()
            self.bfs_done += 1
            yield parent, n
            new = set(self.adjacent(n)) - enqueued
            enqueued |= new
            queue.extend([(n, child) for child in new])

    def solve_bfs(self):
        pbar = ProgressBar().start()
        self.bfs_done = 0
        parents = {}
        for parent, child in self._bfs():
            pbar.update(100.0*(float(self.bfs_done)/float(self.search_depth)))
            parents[child] = parent
            if child == self.end:
                revpath = [self.end]
                while True:
                    parent = parents[child]
                    revpath.append(parent)
                    if parent == self.start:
                        break
                    child = parent
                self.path = list(reversed(revpath))
                pbar.finish()
                self.save()
                return
        print 'No Solution'

if __name__ == '__main__':
    try:
        maze = Maze(sys.argv[1])
    except (IndexError, IOError):
        print "Specify file"
        sys.exit(1)
    else:
        if sys.argv[2] == 'b':
            maze.solve_bfs()
        else:
            maze.solve_astar()

To comment, please sign in with your Google, AOL or Yahoo account.