class Node:
	"""
	Override me to provide node specific behaviour.
 	
	You'll probably need to implement __hash__ and __eq__, which should probably be those respective functions of your coordinate type. Maybe.
	"""
	parent = None
	
	def GetAdjacent(self):
		pass
	
	def __hash__(self):
		pass
	
	def __eq__(self):
		pass

class SquareNode(Node):
	"""
	Example implementation of a Node which has adjacent nodes on four sides.
	Use me or override me.
	"""
	# each of these steps should have the same dimensionality as as the base coord type
	w = 128
	h = 128
	adj = [(0,  +1), (+1,  0), (0,  -1), (-1,  0), (+1, -1), (+1, +1), (-1, +1), (-1, -1)]
	
	def __init__(self, coord):
		self.coord = coord
	
	def __hash__(self):
		return self.coord.__hash__()
	
	def __eq__(self, other):
		return self.coord.__eq__(other.coord)
	
	def TestValid(self, c):
		return True
	
	def GetAdjacent(self):
		return [self.__class__((self.coord[0] + x, self.coord[1] + y)) for x, y in self.adj if (self.TestValid((self.coord[0] + x, self.coord[1] + y)) and self.coord[0] + x >= 0 and self.coord[0] + x < self.w and self.coord[1] + y >= 0 and self.coord[1] + y < self.h)]

class PathFinder:
	def FindRoute(self, start_node, dest_node):
		visited = set()
		open_nodes = [start_node]
		
		while open_nodes:
			node = open_nodes.pop(0)
			
			if node == dest_node:
				path = []
				while node != start_node:
					path.append(node)
					node = node.parent
				return path[::-1]
		     	
			for adj in node.GetAdjacent():
				if adj not in visited:
					visited.add(adj)
					adj.parent = node
					open_nodes.append(adj)
		
		return []