Improvement of performance for a maze solving program in Python
fellow programmers. I need help with one of my projects. I'm making a maze solving program. It reads an image file, which has to be black and white (black pixels are walls, white pixels are paths), have only one pixel at the top which is the entrance to the maze, and only one white pixel at the bottom which is the exit.
There're three main parts to the code:
1) The program first create nodes in the maze, respecting a set of rules. For exemple here's a simple maze:
and here're all the nodes drawn in red:
The nodes are like the corners, the crossroads, every point where you can change direction. The distance between each node and the exit of the maze is also measured. While it's generating all the nodes, it places them in a list.
2) As soon as all the nodes are generated, the program will iterate through all the nodes in the list, and try to search in every direction possible for other nodes, to "link" them, establish the possible paths. For exemple, if it detects that there is a path above a node, it'll search each and every pixel in a line from the coordinate of the node, and going up, iterating through ALL of the node list again to see if another node match these coordinates. If it finds one at some point, it links them, and start searching to the right (if there's a path to the right of course), and etc for every direction.
3) Once all of the nodes are linked together and every possible paths established, it's gonna start from the entry node of the maze, and run my implementation of the A* algorithm to figure out the right path, and go back if it's in a dead end. As you can see, it solves mazes without difficulty.
So my program works. What's the problem then? The problem is the node linking part. On small mazes, it takes like half a second. But make the maze somewhat bigger, then the number of nodes will drastically increase. And since it iterates through the node list A LOT of time (one time for every pixel it searches for every node), you can imagine if I have 600 000 nodes... It's gonna take ages.
So that's what I'm asking help for: a better, faster way to link the nodes together. I've posted the entire code on pastebin (https://pastebin.com/xtmTm7wb, sorry if it's a little messy, it was VERY late when I programmed this). The node linking part starts at line 133 and ends at line 196.
Here's the node linking code:
counter = 0
last = 0
for node in nodelist:
a = node.pos[0]
b = node.pos[1]
if node.paths[0]:
for i in range(b-1,0,-1):
if mazepix[a,i] == blackpix:
break
if any(x.pos == (a,i) for x in nodelist):
for iteration in nodelist:
if iteration.pos == (a,i):
indexofnodetolinkto = iteration.index
break
node.connections.append(indexofnodetolinkto)
# print("Linking node %d and node %d..."%(node.index, indexofnodetolinkto))
break
if node.paths[1]:
for i in range(a+1,maze.size[0]):
if mazepix[i,b] == blackpix:
break
if any(x.pos == (i,b) for x in nodelist):
for iteration in nodelist:
if iteration.pos == (i,b):
indexofnodetolinkto = iteration.index
break
node.connections.append(indexofnodetolinkto)
# print("Linking node %d and node %d..."%(node.index, indexofnodetolinkto))
break
if node.paths[2]:
for i in range(b+1,maze.size[1]):
if mazepix[a,i] == blackpix:
break
if any(x.pos == (a,i) for x in nodelist):
for iteration in nodelist:
if iteration.pos == (a,i):
indexofnodetolinkto = iteration.index
break
node.connections.append(indexofnodetolinkto)
# print("Linking node %d and node %d..."%(node.index, indexofnodetolinkto))
break
if node.paths[3]:
for i in range(a-1,0,-1):
if mazepix[i,b] == blackpix:
break
if any(x.pos == (i,b) for x in nodelist):
for iteration in nodelist:
if iteration.pos == (i,b):
indexofnodetolinkto = iteration.index
break
node.connections.append(indexofnodetolinkto)
# print("Linking node %d and node %d..."%(node.index, indexofnodetolinkto))
break
counter += 1
percent = (counter/nbrofnodes)*100
if int(percent)%10 == 0 and int(percent) != last:
print("Linking %d%% done..."%percent)
last = int(percent)
print("All node linked.")
Thank you if you read all of this, I know it's not a very precise question, but I've spend so much time trying to make this work, now that it does I'm really stuck on the ways I could improve it ^^'.
Your program is super slow, because this part takes a long time and you do it many times for every node:
for iteration in nodelist:
if iteration.pos == (i,b):
indexofnodetolinkto = iteration.index
break
There are a lot of ways to make it a lot faster.
You could put the nodes into a dictionary using the position as a key, so you can just do a lookup for a position to find the node there.
Even better, you could put the nodes into row lists and column lists, sorted by position, and then only try to connect adjacent nodes in the lists.
But the best thing to do is to forget about these nodes altogether and just do a BFS search directly on the bitmap.
Since this is a fun problem, I wrote a fast version with a simple BFS. I don't want to ruin all your fun, so here's just the BFS part so that you can see what I mean by doing BFS directly on the image:
#Breadth-first search over the graph
#We use special colored pixels in the image to mark visited locations and their distance
nextlevel=[(entrypos,0)]
nextdist=0
mazepix[entrypos,0] = markerPixel(nextdist)
exitpos = -1
while exitpos<0:
if len(nextlevel) < 1:
print("Could not find exit!")
return
prevlevel = nextlevel
nextdist += 1
nextlevel = []
nextpix = markerPixel(nextdist)
for prevpos in prevlevel:
for dir in [(-1,0),(0,1),(1,0),(0,-1)]:
x = prevpos[0]+dir[0]
y = prevpos[1]+dir[1]
if x>=0 and y>=0 and x<W and y<H and mazepix[x,y]==whitepix:
nextlevel.append((x,y))
#mark it used and distance mod 3
mazepix[x,y]=nextpix
if y>=H-1:
exitpos=x
Instead of using a separate set with objects and links to remember the path, we mark pixels as visited directly in the image. Instead of using actual links of any kind to link one pixel to another, we just check all 4 directions looking for adjacent white pixels whenever we need to.
This does a level-by-level BFS so we always know how far new pixels are from the entrance, and the color we mark a visited pixel indicates its distance from the entrance (mod 3). This allows us to reconstruct the shortest path when we find the exit.
EDIT: It's been a long time and the OP has had his fun, so here's the complete python solver:
from PIL import Image
import math
import sys
import time
import pickle
import os
whitepix = (255,255,255)
blackpix = (0,0,0)
redpix = (255,0,0)
greenpix = (0,255,0)
def markerPixel(distance):
val=120+(distance%3)*40
return (val,val,0)
def smallerMarker(pixel):
return markerPixel(pixel[0]-1)
def isMarker(pixel):
return pixel[2]==0 and pixel[0]==pixel[1] and pixel[0]>=120
def solve(imagename, outputname, showmarkers):
maze = Image.open(imagename)
maze = maze.convert('RGB')
mazepix = maze.load()
nodelist = []
print(maze.size)
starttime = time.time()
W = maze.size[0]
H = maze.size[1]
entrypos = -1
# Find the entry
for i in range(0,W):
if mazepix[i, 0] == whitepix:
entrypos=i
break
if entrypos < 0:
print("No entry!")
return
#Breadth-first search over the graph
#We use special colored pixels in the image to mark visited locations and their distance
nextlevel=[(entrypos,0)]
nextdist=0
mazepix[entrypos,0] = markerPixel(nextdist)
exitpos = -1
while exitpos<0:
if len(nextlevel) < 1:
print("Could not find exit!")
return
prevlevel = nextlevel
nextdist += 1
nextlevel = []
nextpix = markerPixel(nextdist)
for prevpos in prevlevel:
for dir in [(-1,0),(0,1),(1,0),(0,-1)]:
x = prevpos[0]+dir[0]
y = prevpos[1]+dir[1]
if x>=0 and y>=0 and x<W and y<H and mazepix[x,y]==whitepix:
nextlevel.append((x,y))
#mark it used and distance mod 3
mazepix[x,y]=nextpix
if y>=H-1:
exitpos=x
#found the exit -- color the path green
nextpos = (exitpos,H-1)
while nextpos != None:
nextpix = smallerMarker(mazepix[nextpos[0],nextpos[1]])
prevpos = nextpos
mazepix[nextpos[0],nextpos[1]] = greenpix
nextpos = None
#find the next closest position -- all adjacent positions are either
#1 closer, 1 farther, or the same distance, so distance%3 is enough
#to distinguish them
for dir in [(-1,0),(0,1),(1,0),(0,-1)]:
x = prevpos[0]+dir[0]
y = prevpos[1]+dir[1]
if x>=0 and y>=0 and x<W and y<H and mazepix[x,y]==nextpix:
nextpos=(x,y)
break
#Erase the marker pixels if desired
if not showmarkers:
for y in range(0,H):
for x in range(0,W):
if isMarker(mazepix[x,y]):
mazepix[x,y]=whitepix
maze.save(outputname)
solve("maze.gif", "solved.png", False)