Alpha's pixel maze solving algorithm

from PIL import Image
import math
import sys
import time
import pickle
import os

class Node():
    def __init__(self, index, pos, paths, distancefromexit):    # Node(index, (x,y), [up,right,down,left])
        self.index = index
        self.pos = pos
        self.paths = paths
        self.distancefromexit = distancefromexit
        self.connections = []
        self.deadend = False

##########

whitepix = (255,255,255)
blackpix = (0,0,0)
redpix = (255,0,0)
greenpix = (0,255,0)

##########

def getIndexOfNodeInNodelistByItsNodeIndex(nodeindex, nodelist):
    for i in range(len(nodelist)):
        if nodelist[i].index == nodeindex:
            return i
    return None

def getDistanceWithCoords(A, B):
    return math.sqrt( math.pow((B[0] - A[0]),2) + math.pow((B[1] - A[1]),2) )


if __name__ == "__main__":

    imagename = input("Enter the maze image name: ")

    maze = Image.open(imagename)
    maze = maze.convert('RGB')
    mazepix = maze.load()
    nodelist = []

    print(maze.size)

    starttime = time.time()

    if os.path.isfile(imagename + ".lnodelist"):
        print("Found lnodelist file for current maze. Loading it!")
        with open(imagename + ".lnodelist", 'rb') as handle:
            nodelist = pickle.load(handle)
            handle.close()
    else:
        print("Generating nodes...")

        # print("Looking for ending node")
        # Locate the ending node
        for i in range(maze.size[0]):
            # print(mazepix[i, maze.size[1]-1])
            if mazepix[i, maze.size[1]-1] == whitepix:
                exitnodecoords = (i, maze.size[1]-1)
                nodelist.append(Node(0, exitnodecoords, [True, False, False, False], 0))
                # print("New node added")
                break


        # Locate the entry node
        # print("Looking for entry node")
        for i in range(maze.size[0]):
            if mazepix[i, 0] == whitepix:
                entrynodecoords = (i, 0)
                nodelist.append(Node(1, entrynodecoords, [False, False, True, False], getDistanceWithCoords( entrynodecoords,exitnodecoords ) ))
                # print("New node added")
                break


        #from there, build a list of all nodes/crossroads

        previouspix = blackpix
        nodecounter = 2
        for b in range(1,maze.size[1]):
            for a in range(maze.size[0]):
                # print("Processing [%d,%d]"%(a,b))
                if mazepix[a,b] == blackpix:
                    previouspix = blackpix
                elif mazepix[a,b] == whitepix:
                    if previouspix == blackpix:
                        if mazepix[a+1,b] == whitepix:
                            newnode = Node(nodecounter, (a,b), [False, True, False, False] , getDistanceWithCoords( (a,b),exitnodecoords ) )
                            nodecounter += 1
                            if mazepix[a,b+1] == whitepix:
                                newnode.paths[2] = True
                            if mazepix[a,b-1] == whitepix:
                                newnode.paths[0] = True
                            nodelist.append(newnode)
                            # print("New node added")

                    elif previouspix == whitepix:
                        cangoUp = False
                        cangoDown = False
                        cangoRight = False
                        if mazepix[a,b-1] == whitepix:
                            cangoUp = True
                        if mazepix[a,b+1] == whitepix:
                            cangoDown = True
                        if mazepix[a+1,b] == whitepix:
                            cangoRight = True
                        if cangoUp or cangoDown:
                            newnode = Node(nodecounter, (a,b), [cangoUp, cangoRight, cangoDown, True], getDistanceWithCoords( (a,b),exitnodecoords ))
                            nodecounter += 1
                            nodelist.append(newnode)
                            # print("New node added")
                    previouspix = whitepix

        # for node in nodelist:
            # print("Creating node %d, at %s : %s"%( node.index, str(node.pos), str(node.paths) ) )
            # print("  %f pixels from exit"%node.distancefromexit)
            # mazepix[node.pos[0], node.pos[1]] = redpix
        # maze.save('solved.png')

        # ^ Draws the nodes (not useful) (ugly) ^



        nbrofnodes = len(nodelist)
        print("%d nodes generated"%nbrofnodes)

        print("")
        print("Linking nodes...")
        # Alright, we got our nodes list... Now it's time to connect them.

        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.")
        print("Saving current linked nodelist as %s"%imagename + ".lnodelist")
        with open(imagename + ".lnodelist", 'wb') as handle:
            pickle.dump(nodelist, handle, protocol=pickle.HIGHEST_PROTOCOL)
            handle.close()
        print("Done.")

    print("")
    print("Pathfinding...")

    # We've got our nodes and our connections.
    # Time to A* .


    startnode = nodelist[1]
    endnode = nodelist[0]

    currentpath = []
    currentpath.append(startnode)

    currentnode = startnode
    while True:
        totaldistance = 0
        for i in range(len(currentpath)):
            node1 = currentpath[i]
            try:
                node2 = currentpath[i+1]
                totaldistance += getDistanceWithCoords( node1.pos,node2.pos )
            except:
                pass
        queuelist = []
        for connection in currentnode.connections:
            nodeindex = getIndexOfNodeInNodelistByItsNodeIndex(connection, nodelist)
            if not nodelist[nodeindex].deadend == True:
                score = nodelist[nodeindex].distancefromexit + getDistanceWithCoords( currentnode.pos,nodelist[nodeindex].pos ) + totaldistance
                queuelist.append( (connection, score, nodelist[nodeindex].deadend) )

        queuelist.sort(key=lambda x: x[1])
        nextnode = nodelist[queuelist[0][0]]
        if nextnode in currentpath:
            try:
                nextnode = nodelist[queuelist[1][0]]
            except:
                # print("ARGL! Node %d is a dead end! Restarting calculations..."%currentnode.index)

                currentnode.deadend = True
                currentnode = currentpath[-2]
                del currentpath[-1]
                continue


        # print(totaldistance)
        # print(str(queuelist))
        # print("Going from node %d to node %d.."%(currentnode.index, nextnode.index))
        currentpath.append(currentnode)
        currentnode = nextnode
        if currentnode.pos == endnode.pos:
            break

    print("Calculations completed. Shortest path is:")
    disppath = ""
    for node in currentpath:
        if not node == endnode:
            disppath += str(node.index) + "->"
        else:
            disppath += str(node.index)
    print(disppath)
    totaldistance = 0
    for i in range(len(currentpath)):
        node1 = currentpath[i]
        try:
            node2 = currentpath[i+1]
            totaldistance += getDistanceWithCoords( node1.pos,node2.pos )
        except:
            pass
    print("\n%s nodes used, with a total travel distance of %d pixels."%(len(currentpath),totaldistance))

    stoptime = time.time()
    print(stoptime-starttime)





    # Draw the path
    for i in range(len(currentpath)):
        currentnode = currentpath[i]
        try:
            nextnode = currentpath[i+1]
            totaldistance += getDistanceWithCoords( currentnode.pos,nextnode.pos )
            x = currentnode.pos[0] - nextnode.pos[0]
            y = currentnode.pos[1] - nextnode.pos[1]

            if x != 0:
                direction = "horizontal"
                if currentnode.pos[0] < nextnode.pos[0]:
                    jump = 1
                else:
                    jump = -1
            elif y != 0:
                direction = "vertical"
                if currentnode.pos[1] < nextnode.pos[1]:
                    jump = 1
                else:
                    jump = -1

            if direction == "horizontal":
                for i in range(currentnode.pos[0],nextnode.pos[0],jump):
                    mazepix[i, currentnode.pos[1]] = greenpix
            elif direction == "vertical":
                for i in range(currentnode.pos[1],nextnode.pos[1],jump):
                    mazepix[currentnode.pos[0], i] = greenpix



        except:
            pass

    ##

maze.save('solved.png')