There are many ways of doing pathfinding; most of them too complex for my pedestrian intellect so I’m quite pleased to have rediscovered one which is relatively simple to understand, implement and finds the optimal solution to most problems. It should work in any number of dimentions although I have stuck to 2D space for the sake of simplicity.
It’s probably quite expensive compared to some methods, but for the time being I’m not concerned with that. It works on the basic principle of starting at the finish and then working backwards in every direction, valueing each position with the number of steps it took to get there untill every position is marked with how close it is to the finnish. The route finder then merely has to look at the value of the cells around it and move to the one with the lowest value. Repeating this sequence untill it arives at the target destination.
The above picture was rendered by pygame and shows a simple maze which the path finder has completed. The bottom right square is the exit and the top left is the entrance. White squares are walls, greenish squares are close to the exit and reddish ones are far away or unreachable. The small black squares are located on cells which are on the path finders chosen route.
This is a slightly altered version of the first maze. As you can see one of the routes has been blocked off and cells that were previously considered close to the exit (were green) are now far away (red). The path finder has of course chosen a new route which avoids the dead end.
I must warn you that the implementation code may seem incomprehensible. I have just the right amount of knowledge and ignorance to confuse anyone who isn’t familiar with python and maybe functional programming. At any rate I’ll let you be the judge of that.
I generally just run this code from inside IDLE, you will have to add an event loop to mazeView.py if you don’t want to and you also need to have pygame installed regardless.
Pathfinder.py
class Maze:
defaultMap = [[1,1,0,1,0,1,0]
,[1,1,0,1,0,1,1]
,[0,1,1,1,1,1,1]
,[1,0,0,1,0,0,1]
,[0,0,1,1,1,0,1]]
def __init__(self):
self.map = self.defaultMap
def inMaze(self, xy):
x, y = xy
return x < len(self.map) and y = 0 and y >=0
def getCell(self, xy):
if self.inMaze(xy):
x, y = xy
return self.map[x][y]
else:
return -1
def setCell(self, xy, value):
if self.inMaze(xy):
x, y = xy
self.map[x][y] = value
def getMoves(self, xy, validator):
"""Returns a list of all possible moves from the cell at xy. The validator decides what moves are possible"""
x, y = xy
left = (x - 1, y)
right = (x + 1, y)
up = (x, y - 1)
down = (x, y + 1)
moves = [left, right, up, down]
return filter(validator, moves)
def scentTarget(self, startxy):
"""Casts out ascending cell values from the chosen position.
The lower the cell value the closer (as the mouse crawls) it is to the target.
It's like a bad smell creeping through the maze. The quickest route to the source
will be kicking off the worst wiff, thus finding the optimal route is easy."""
def creep(xy, dist):
def validator(m):
cv = self.getCell(m)
return cv == 1 or (cv > 2 and (cv - dist) > 1)
dist += 1
self.setCell(xy, dist)
for m in self.getMoves(xy, validator):
creep(m, dist)
creep(startxy, 1)
def findRoute(self, startxy):
"""Trace a route towards the scented target (select target with scentTarget())."""
route = [startxy]
def step(xy, pxy):
"""Take a step in the direction with the lowest value and add the cell to the route."""
def validator(m):
return self.getCell(m) >= 2
moves = self.getMoves(xy, validator)
if len(moves) < 1:
return
lowest, lowestm = self.getCell(moves[0]), moves[0]
for m in moves:
if self.getCell(m) < lowest:
lowest, lowestm = self.getCell(m), m
route.append(lowestm)
if lowest == 2 or lowestm == pxy:
return
step(lowestm, xy)
step(startxy, startxy)
return route
if __name__ == "__main__":
maze = Maze()
maze.scentTarget((4, 6))
for r in maze.map:
print r
r = maze.findRoute((0, 0))
m = maze.map
print
for x, y in r:
m[x][y] = 'X'
for mr in m:
print mr
mazeView.py
from pathfinder import Maze
from pygame import *
BLACK = (0, 0, 0)
WHITE = (255, 255, 255)
RED = (255, 0, 0)
BLUE = (0, 0, 255)
def createMaze():
m = Maze()
m.scentTarget((4, 3))
return m
def drawMaze(m, screen):
wsquare = Surface((50, 50))
wsquare.fill(WHITE)
csquare = Surface((50, 50))
row = 1
for r in m.map:
cell = 1
for c in r:
if c == 0:
screen.blit(wsquare, (50 * cell, 50 * row))
else:
if c == 1 or c * 20 > 255:
csquare.fill(RED)
elif c > 1:
csquare.fill((c * 20, 255 - (c * 20), 0))
screen.blit(csquare, (50 * cell, 50 * row))
cell += 1
row += 1
def drawRoute(r, screen):
marker = Surface((25, 25))
marker.fill(BLACK)
for x, y in r:
screen.blit(marker, (50 * (y + 1) + 12, 50 * (x + 1) + 12))
if __name__ == "__main__":
init()
screen = display.set_mode((640, 480))
m = Maze()
m.scentTarget((4, 6))
drawMaze(m, screen)
drawRoute(m.findRoute((0,0)), screen)
display.flip()
