Pathfinder from image file

My first annoyance with this is that your printMap function doesn't display it nearly as nicely as I would like it to - I get something like this

  0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  
  ________________________________________________________________________
0|S  *  *  *  *  *  *  *  *  *           ■  ■  ■  ■  ■  ■                 
1|■  ■  ■     ■  ■  ■  ■  ■  *  ■  ■     ■              ■     ■  ■  ■     
2|               ■  *  *  *  *  ■        ■     ■  ■     ■     ■  ■        
3|   ■     ■  ■  ■  *  ■  ■  ■  ■     ■  ■     ■        ■     ■        ■  
4|   ■     ■        *  *  *     ■     ■  ■     ■     ■  ■     ■  ■  ■  ■  
5|   ■  ■  ■  ■  ■  ■  ■  *  ■  ■     ■        ■     ■  *  *  *  *  *  *  
6|                  ■  *  *  ■        ■     ■  ■     ■  *  ■  ■  ■  ■  *  
7|■  ■  ■  ■  ■  ■  ■  *  ■  ■     ■  ■     ■        ■  *  ■        ■  *  
8|*  *  *  *  *  *  *  *  ■        ■        ■  ■  *  *  *  ■        ■  *  
9|*  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  *  ■  ■  ■     ■  ■  *  
10|*  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *              ■  E  *  

Without appropriate spacing it makes it much harder to understand what's going on. If you just add some padding it should be manageable (as long as we don't get massive images). Ideally it would end up like this

   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  
   _____________________________________________________________________________________________
 0|S   *   *   *   *   *   *   *   *   *               ■   ■   ■   ■   ■   ■                      
 1|■   ■   ■       ■   ■   ■   ■   ■   *   ■   ■       ■                   ■       ■   ■   ■      
 2|                    ■   *   *   *   *   ■           ■       ■   ■       ■       ■   ■          
 3|    ■       ■   ■   ■   *   ■   ■   ■   ■       ■   ■       ■           ■       ■           ■  
 4|    ■       ■           *   *   *       ■       ■   ■       ■       ■   ■       ■   ■   ■   ■  
 5|    ■   ■   ■   ■   ■   ■   ■   *   ■   ■       ■           ■       ■   *   *   *   *   *   *  
 6|                        ■   *   *   ■           ■       ■   ■       ■   *   ■   ■   ■   ■   *  
 7|■   ■   ■   ■   ■   ■   ■   *   ■   ■       ■   ■       ■           ■   *   ■           ■   *  
 8|*   *   *   *   *   *   *   *   ■           ■           ■   ■   *   *   *   ■           ■   *  
 9|*   ■   ■   ■   ■   ■   ■   ■   ■   ■   ■   ■   ■   ■   ■   ■   *   ■   ■   ■       ■   ■   *  
10|*   *   *   *   *   *   *   *   *   *   *   *   *   *   *   *   *                   ■   E   *  

My second annoyance is how much stuff you have going on in the body of your module. Typically you would do

if __name__ == '__main__':
    # stuff

This makes your module import-safe, i.e. if you (or someone else) tries to import your module it won't execute a bunch of code that would be surprising. Generally all you want to do in the body of your module is declare important constants and globals, functions, classes, etc. We can address this by doing two things:

1. Move a lot of that code into functions to make it more generic
2. Move the remaining code into such a block.

Lets start with this code

image = Image.open("map1.png")
width, height = image.size
image_data = list(image.getdata())

for i in range(len(image_data)):#make data easier to handle
    image_data[i] = Node(str(image_data[i]).replace("(", "").replace(")", ""), [0, 0])#create Node objects

map = []
for i in range(width):#change image_data into matrix of Nodes with correct width
    map.append(image_data[i*width:width*(i+1)])#object can be accessed by map[y][x]

There are two primary things I'm going to suggest here:

1. Use list comprehensions.
2. Don't override the builtin function map.

We can greatly simplify this code and put it into a function like so:

def create_image_graph(image_name):
    image = Image.open(image_name)
    width, height = image.size

    image_data = [Node(str(datum).replace("(", "").replace(")", ""), [0, 0]) for datum in image.getdata()]
    image_graph = [image_data[i*width:(i+1)*width] for i in range(width)]
    return image_graph, width, height

image_map, width, height = create_image_graph("map1.png")

Next we can look at this chunk

start = end = []
for y in range(height):
    for x in range(width):
        if map[y][x].color == '0, 255, 0':#set start position
            if start == []:
                start = [x, y]
                map[y][x].start = True
            else:
                print("Error: Cannot have more than one start")
                sys.exit()
        elif map[y][x].color == '255, 0, 0':#set end position
            if end == []:
                end = [x, y]
                map[y][x].end = True
            else:
                print("Error: Cannot have more than one end")
                sys.exit()      
if start == []:
    print("Error: Could not find start")
    sys.exit()
elif end == []:
    print("Error: Could not find end")
    sys.exit()

for y in range(height):
    for x in range(width):
        map[y][x].position = [x, y]
        map[y][x].x = x
        map[y][x].y = y
        map[y][x].updateDistance(end)

First of all, it's kind of weird to do start = end = []. This is a red flag to most experienced Python programmers as that would lead to bugs due to mutability. If someone were to do start.append(1), then both start and end would be equal to [1], which is not desirable. You also use sys.exit() - this is really weird. Instead you should raise an exception. Then whatever is using your function can handle it (if they know how) or let it continue, which will eventually end the program anyway.

It's also a bit weird how you have to keep track of the start and the end separately, when really those belong on your map. I'd use a different data structure to hold your map (more on this later) where those are data members. I'd also give a Node a cell_type attribute that can have one of a few enum values - START, END, WALL, EMPTY, PATH for example. Also, all of this information should be available as soon at time of construction. These values should either be set when you initialize the Node (with the exception of updateDistance) or made into properties of the Node (or both). I'd do something like this

from enum import Enum

CellType = Enum("CellType", "START END PATH WALL EMPTY")

class Node(object):

    _cell_types = {
        (0, 0, 0): CellType.WALL,
        (255, 255, 255): CellType.EMPTY,
        (0, 255, 0): CellType.START,
        (255, 0, 0): CellType.END,
        (0, 0, 255): CellType.PATH,
        CellType.WALL: (0, 0, 0),
        CellType.EMPTY: (255, 255, 255),
        CellType.START: (0, 255, 0),
        CellType.END: (255, 0, 0),
        CellType.PATH: (0, 0, 255)
    }

    @property
    def passable(self):
        return self.color != CellType.WALL

    @property
    def cell_type(self):
        return Node._cell_types[self.color]

    @cell_type.setter
    def cell_type(self, value):
        self.color = Node._cell_types[value]    

    @property
    def x(self):
        return self.position[0]

    @property
    def y(self):
        return self.position[1]

    def __init__(self, color, position):
        self.color = color;
        self.position = position
        self.neighbors = []

    def distance_to_node(self, node):
        return sum(map(lambda x, y: abs(x - y), zip(node.position, self.position)))

You'll notice that I've put a bidirectional mapping into Node._cell_types - that was more out of convenience than anything, and if I were writing this myself I probably would, but for the sake of this review I just jammed them all in there. I've also stopped treating the color as strings - they work just fine as tuples, and converting them back and forth is silly. This means that we can change create_image_graph to skip all of the str() and .replace() calls. Lastly, I've removed the updateDistance and the checkAround functions - those are really functions that should live on whatever is managing all of your nodes (coming soon, I promise). They both require knowledge that the node itself shouldn't have about the topography of the system as a whole. I did make a distance_to_node function that essentially replaces the updateDistance function - it should accomplish the same thing, although I got a little fancier to make it a one-liner. I'm not sure how I feel about how you calculate your distance, however. You should really be doing something like this (assuming you mean distance in the traditional sense)

    def distance_to_node(self, node):
        return sum(map(lambda x, y: pow(x - y, 2), zip(node.position, self.position)))

With this we've gotten rid of looping over all of your nodes to set values and do calculations after they've been created. This gets rid of two loops that could take quite a long time for larger images. We'll still need to do error handling for an invalid number of start/end points, but that'll all be handled by the container class, which I'll talk about now.

This problem is a graph problem, specifically one about path finding. There are libraries that can handle a lot of this for you (I'll talk about that at the end) but first let's understand what we need in a graph:

• Nodes, or the actual points in the graph
• Edges, or connections between nodes

There are a bunch of other things you may want for a specific domain or application of a graph (such as start/end points, color, etc) but those two things are all you really need. I started with this structure

from collections import defaultdict

class InvalidGraphException(Exception): pass  

class Graph:

    @classmethod
    def from_file(cls, image_name):
        return Graph(Image.open(image_name))

    @property
    def width(self):
        return self.image.width

    @property
    def height(self):
        return self.image.height

    _start = None
    @property
    def start(self):
        return self._start    
    @start.setter
    def start(self, value):
        if self._start:
           raise InvalidGraphException("Graph can only have one start point")
        self._start = value

    _end = None
    @property
    def end(self):
        return self._end
    @end.setter
    def end(self, value):
        if self._end:
           raise InvalidGraphException("Graph can only have one end point")
        self._end = value

    def _calculate_position(self, index):
        return index // self.width, index % self.width

    def __init__(self, image):
        self.image = image
        self.nodes = {}
        self.edges = defaultdict(set)
        for i, datum in enumerate(image.getdata()):
            position = self._calculate_position(i)
            self.add_node(datum, position)

        if not self.start:
           raise InvalidGraphException("Graph must have a start point")                
        if not self.end:
           raise InvalidGraphException("Graph must have an end point")

    def add_node(self, datum, position):
        self.nodes[position] = Node(datum, position)
        if self.nodes[position].cell_type is CellType.START:
            self.start = position
        elif self.nodes[position].cell_type is CellType.END:
            self.end = position

This takes a lot of your existing code, but again uses properties to make things cleaner and makes sure that everything is owned by the right thing - the topography of our image owns the collection as a whole, while our nodes own themselves.

The next thing we want to do is make our edges - edges should go between adjacent nodes that are passable. We can do that like so

def __init__(self, image):
    # same as before up until this point

    for position, node in filter(lambda node: node[1].passable, self.nodes.items()):
        for neighbor in self._neighbors_of_node(node):
            self.add_edge(node, neighbor)

def _neighbors_of_node(self, node):
    if not node.neighbors:
        x, y = node.position
        neighbor_coords = (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)
        for coordinates in neighbor_coords:
            neighbor = self.nodes.get(coordinates, None)
            if neighbor is not None and neighbor.passable:
                node.neighbors.append(neighbor)

    return node.neighbors

def add_edge(self, start, end):
    if start.position not in self.nodes:
        raise ValueError("{} not in the graph".format(start))
    if end.position not in self.nodes:
        raise ValueError("{} not in the graph".format(end))

    self.edges[start.position].add(end)
    self.edges[end.position].add(start)

Next we want to actually figure out the distance between them. I've modified your algorithm a bit (I'm not actually sure if it works or not, as it times out for me). I've gotten rid of a lot of the weird string transformations you did as they are no longer necessary, and I've also removed a bunch of code that was unnecessary with the improvements we've made elsewhere.

def find_path(self):
    min_distance = self.width + self.height
    path = []
    current_node = self.nodes[self.start]
    next_node = None

    while True:
        path.append(current_node)
        if not current_node.neighbors:
            current_node = start
            path = []
        else:
            for neighbor in current_node.neighbors:
                if neighbor not in path:
                    new_distance = current_node.distance_to_node(neighbor)
                    if new_distance < min_distance:
                        min_distance = new_distance
                        next_node = neighbor

        if not (current_node.neighbors or path):
            print("Could not find path!")
            break   

        current_node = next_node
        min_distance = self.width + self.height

        if current_node == self.nodes[self.end]:
            break

    for node in path:
        node.color = (0, 0, 255)

    return path

Then to wrap up your module, you'd just do this

if __name__ == '__main__':
    g = Graph.from_file("map1.png")
    print(g.find_path)

Now that we've gone through your manual implementation I have good news and bad news. The good news is that you hopefully have a pretty good feel for why we're using a graph, and how it works. The bad news is that there are libraries to do this work for you. From here on out I'm going to show how we could solve this with NetworkX, a really cool graph library for Python. We're actually going to reuse a lot of our existing code, except with a NetworkX backend, like so

import networkx as nx

class InvalidNxGraphException(InvalidGraphException): pass

_cell_types = {
    (0, 0, 0): CellType.WALL,
    (255, 255, 255): CellType.EMPTY,
    (0, 255, 0): CellType.START,
    (255, 0, 0): CellType.END,
    (0, 0, 255): CellType.PATH,
    CellType.WALL: (0, 0, 0),
    CellType.EMPTY: (255, 255, 255),
    CellType.START: (0, 255, 0),
    CellType.END: (255, 0, 0),
    CellType.PATH: (0, 0, 255)
}

class NxGraph:    
    @classmethod
    def from_file(cls, image_name):
        return NxGraph(Image.open(image_name))

    @property
    def width(self):
        return self.image.width

    @property
    def height(self):
        return self.image.height

    _start = None
    @property
    def start(self):
        return self._start    
    @start.setter
    def start(self, value):
        if self._start:
           raise InvalidNxGraphException("NxGraph can only have one start point")
        self._start = value

    _end = None
    @property
    def end(self):
        return self._end
    @end.setter
    def end(self, value):
        if self._end:
           raise InvalidNxGraphException("NxGraph can only have one end point")
        self._end = value

    def _calculate_position(self, index):
        return index // self.width, index % self.width

    def __init__(self, image):
        self.image = image
        self.graph = nx.Graph()
        for i, color in enumerate(self.image.getdata()):
            position = self._calculate_position(i)
            self.add_node(color, position)

        if not self.start:
           raise InvalidNxGraphException("Graph must have a start point")                
        if not self.end:
           raise InvalidNxGraphException("Graph must have an end point")


        for node in self.graph.nodes():
            if self.graph.node[node]['passable']:
                x, y = node
                for position in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
                    if position in self.graph.node and self.graph.node[position]['passable']:
                        self.graph.add_edge(position, node)

    def add_node(self, color, position):
        cell_type = _cell_types[color]
        passable = cell_type != CellType.WALL
        self.graph.add_node(position, color=color, type=cell_type, passable=passable)
        if cell_type is CellType.START:
            self.start = position
        if cell_type is CellType.END:
            self.end = position

    def find_path(self):
        return nx.astar_path(self.graph, self.start, self.end)

You'll notice that a lot of our code has been saved, except we cleand up a few spots, and we don't use our Node class anymore because NetworkX lets us put arbitrary attributes on our nodes (each node is a dictionary). Then we use the builtin A* search algorithm instead of your home-grown one, and it'll give us the shortest path. If you wanted you could implement A* search on your own with the old system (it isn't that hard) and avoid the external dependency.

It's also relatively easy to add the ability to draw a graph or arbitrary points if you use matplotlib, but I've spent enough hours writing this review so I'll leave that as an exercise for the reader.