4
\$\begingroup\$

I've created a simple pathfinder programme that receives its input from a very small .png file.

Example file here: enter image description here

Here's a link to the file (note that the green pixel represents the start, the red pixel represents the end and black pixels represent walls). Also, the file needs to be saved as map.png, in the same folder that the programme is running, for it to be recognised as the input.

Although the programme generally works, it often fails to find a path to the exit in more complicated mazes. I'm certain there are many improvements that could be made to make it work in a more efficient way.

from PIL import Image
import sys, numpy

class Node(object):
    distance = 0
    end = False
    start = False
    pathItem = False


    def __init__(self, color, position):
        self.color = color;
        self.position = position
        if color == "0, 0, 0":
            self.passable = False
        else:
            self.passable = True


    def updateDistance(self, end):
        diffX = abs(end[0]-self.position[0])
        diffY = abs(end[1]-self.position[1])
        self.distance = diffX+diffY
        if self.distance < 10:
            self.distance = "0"+str(self.distance)
        else:
            self.distance = str(self.distance)


    def checkAround(self):
        #returns how many available nodes are passable around self. Excluding diagonal
        counter = []
        x = self.position[0]
        y = self.position[1]
        if x < width-1:
            if map[y][x+1].passable:
                counter.append("r")
        if x > 0:
            if map[y][x-1].passable:
                counter.append("l")
        if y < height-1:
            if map[y+1][x].passable:
                counter.append("d")
        if y > 0:
            if map[y-1][x].passable:
                counter.append("u")

        return counter



def printMap(show="all"):#just a pretty for loop, used for debugging
    offset=" "*2 #
    print("\n" + offset, end="")
    for i in range(width):
        print(str(i) + "  ", end="")

    print("\n" + offset, end="")
    print("_"*width*3)


    for y in range(height):
        print(str(y) + "|", end="")
        for x in range(width):
            if show == "start":
                if map[y][x].start:
                    print("S  ", end="")
                else:
                    print("   ", end="")
            elif show == "end":
                if map[y][x].end:
                    print("E  ", end="")
                else:
                    print("   ", end="")
            elif show == "passable":
                if not map[y][x].passable:
                    print("■  ", end="")
                else:
                    print("   ", end="")
            else:
                if map[y][x].color == "255, 255, 255":
                    if show == "distance":
                        print(map[y][x].distance + " ", end="")
                    else:
                        print("   ", end="")

                elif map[y][x].color == "0, 0, 0":
                    print("■  ", end="")
                elif map[y][x].color == "0, 255, 0":
                    print("S  ", end="")
                elif map[y][x].color  == "255, 0, 0":
                    print("E  ", end="")
                elif map[y][x].color  == "0, 0, 255":
                    print("*  ", end="")
        print("")


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]



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

#now start and end are found, update Node 
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)

#################################
#FIND PATH
foundFinish = False

lowestDistance = width+height
path = []
currentNode = map[start[1]][start[0]]
nextNode = "unknown"

while not foundFinish:
    path.append(currentNode)
    if currentNode.checkAround() == []:
        currentNode = map[start[1]][start[0]]
        for i in path:
            map[i.y][i.x].passable = True
        map[path[len(path)-1].y][path[len(path)-1].x].passable = False


        path = []



    for i in currentNode.checkAround():

        if currentNode.x < width-1:
            if i == 'r':
                if int( map[currentNode.y][currentNode.x+1].distance ) < lowestDistance:
                    lowestDistance = int(map[currentNode.y][currentNode.x+1].distance)
                    nextNode = map[currentNode.y][currentNode.x+1]


        if currentNode.x > 0:
            if i == 'l':
                if int( map[currentNode.y][currentNode.x-1].distance ) < lowestDistance:
                    lowestDistance = int(map[currentNode.y][currentNode.x-1].distance)
                    nextNode = map[currentNode.y][currentNode.x-1]

        if currentNode.y < height-1:    
            if i == 'd':
                if int( map[currentNode.y+1][currentNode.x].distance ) < lowestDistance:
                    lowestDistance = int(map[currentNode.y+1][currentNode.x].distance)
                    nextNode = map[currentNode.y+1][currentNode.x]

        if currentNode.y > 0:
            if i == 'u':
                if int( map[currentNode.y-1][currentNode.x].distance ) < lowestDistance:
                    lowestDistance = int(map[currentNode.y-1][currentNode.x].distance)
                    nextNode = map[currentNode.y-1][currentNode.x]


    if currentNode.checkAround() == [] and path == []:
        print("Could not find path!")
        break   


    currentNode.passable = False
    currentNode = nextNode
    lowestDistance = width+height

    if currentNode.distance == "00":
        foundFinish = True

#output found path
for i in path:
    map[i.y][i.x].color = "0, 0, 255"


printMap()

The way the algorithm works is by assigning each pixel on the map a distance from the exit, regardless if walls are blocking the way or not. Then, starting from the start point, the programme evaluates which pixels are available to move the current position to, and it then moves to the pixel that has the smallest distance from the exit. If the current position has nowhere else to go, i.e. it is blocked off on all 4 sides, the current position is set to:

Node.passable = False

The current position is then set back to the start and the programme runs again. If the start position is blocked off on all 4 sides, the programme exits.

Any hints or tips to make the code better or to help me become a better programmer would be massively appreciated (I'm still a newbie).

\$\endgroup\$
  • 3
    \$\begingroup\$ That is a small png. \$\endgroup\$ – Dair Aug 22 '16 at 3:14
  • \$\begingroup\$ Don't over-estimate how well it works. If the file gets too big, it generally can't figure out the right path. It can only do very simple obstacles \$\endgroup\$ – user2635139 Aug 22 '16 at 3:22
  • \$\begingroup\$ From your description it sounds like you are trying something similar to A* (A star) algorithm. This algorithm (or any of its variants) is pretty much the standard solution to path planning problems based on graphs (like yours). It will always find the solution if one exists. Instead of reinventing the wheel by creating your own algorithm, maybe try a standard one first. If that fails, you know that it's either the input data that has a problem or your implementation of the algorithm that's wrong, but not the algorithm itself. \$\endgroup\$ – I'll add comments tomorrow Aug 22 '16 at 8:14
  • \$\begingroup\$ Working on an answer for this now - are you interested in leveraging 3rd party libraries to help solve the problem? Or is this more of a learning for learning's sake thing? either way I'll try to include both, but it would help to know what to focus on \$\endgroup\$ – Dannnno Aug 23 '16 at 3:50
  • \$\begingroup\$ Bit late now, sorry. But this is more for learning's sake, otherwise I would have just used A* pathfinding. \$\endgroup\$ – user2635139 Aug 26 '16 at 14:35
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Only one thing, I thought that sys.exit() did raise anexception that could be caught on outer levels. If I remember right, "sys.exit()" is the same as "raise SystemExit()", right? \$\endgroup\$ – user2635139 Aug 26 '16 at 14:07
  • 1
    \$\begingroup\$ Iirc it does, but catching it and doing things with it would be a pretty big code smell to any python developer \$\endgroup\$ – Dannnno Aug 26 '16 at 15:22
  • \$\begingroup\$ If I've updated the code and added new features, do I modify this question or ask a new one? \$\endgroup\$ – user2635139 Aug 28 '16 at 19:55
  • \$\begingroup\$ Please ask a new question @user2635139 \$\endgroup\$ – Dannnno Aug 28 '16 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.