Pathfinder from image file

Question

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

• Dair: That is a small png.
• user2635139: 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
• I'll add comments tomorrow: 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.
• Dan Oberlam: 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
• user2635139: Bit late now, sorry. But this is more for learning's sake, otherwise I would have just used A* pathfinding.

Answer 1

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.

• user2635139: 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?
• Dan Oberlam: Iirc it does, but catching it and doing things with it would be a pretty big code smell to any python developer
• user2635139: If I've updated the code and added new features, do I modify this question or ask a new one?
• Dan Oberlam: Please ask a new question @user2635139