"""An implementation of the A* searching algorithm.
dyoo@hkn.eecs.berkeley.edu
I got so disgusted at my previous attempt at A*, so here I go again.
Hopefully this version will be easier on the eyes.
A* is a search algorithm that's similar to Dijkstra's algorithm: given
a graph, a start node, and a goal, A* will search for the shortest
path toward the goal.
To help it get there faster, we can provide a heuristic that evaluates
how far we are from that goal. With a good heuristic, finding an
optimal solution takes MUCH less time.
The main function that one would use is aStar(). Take a look at
_testAStar() to see how it's used.
jackdied@yahoo.com
* Re-jiggered to use generators
* unrolled Child func
* hooked it up to a C priority queue
"""
from __future__ import generators
import ICFP
__version__ = "$Revision: 1.15 $"
class AStar:
def __init__(self, start, goal, CBoard):
self.solution = None
self.gen = self.main_loop(start, goal, CBoard.neighbors, CBoard.get_danger)
self.danger = CBoard.get_danger
return
def cdist(self, x, y):
ans = (self.danger(x) + self.danger(y) + 1)
return ans
def done(self):
"""IF YOU DONT CALL DONE, OUR CIRCULAR REFERENCE
(THROUGH THE GENERATOR) WILL EAT THE WORLD"""
del self.gen
return
def main_loop(self, start, goal, nfunc, dfunc):
seen = {}
g_costs = {start : 1}
parents = {start : start}
heur = ICFP.heuristic1
dist = ICFP.distance1
neig = nfunc
pqueue = ICFP.PQueue()
d_calc = lambda x,y: self.cdist(x,y)
start_cost = heur(start, goal)
pqueue.push((start_cost, start))
seen[start] = start_cost
while (len(pqueue)):
next_cost, next_node = pqueue.pop()
g_costs[next_node] = g_costs[parents[next_node]] + d_calc(next_node, parents[next_node])
if next_node == goal:
self.solution = getPathToGoal(start, goal, parents)
return
children = neig(next_node)
for child in children:
if g_costs.has_key(child): continue
f = g_costs[next_node] + d_calc(next_node, child) + heur(child, goal)
if (not seen.has_key(child) or seen[child] > f):
seen[child] = f
pqueue.push((f, child))
parents[child] = next_node
yield None
self.solution = getPathToGoal(start, goal, parents)
return
def getPathToGoal(start, goal, parents):
"""Given the hash of parental links, follow back and return the
chain of ancestors."""
try:
results = []
while (goal != start):
results.append(goal)
goal = parents[goal]
results.append(start)
results.reverse()
return results
except KeyError: return []