Commits

Lars Yencken committed daf8a05

Parent field optimisation for A* search.

Comments (0)

Files changed (1)

         "Slow but exact pathfinding."
         t = time.time()
         p = self.find_path(loc, dest)
+        assert self.game.components[loc] == self.game.components[dest]
         if p:
-            logging.debug('finding a path from %s to %s (%.0fms, OK)' % (
-                loc, dest, 1000*(time.time() - t)))
-            new_loc = p[0]
-            d, = self.ants.direction(loc, new_loc)
-            if self.do_move_direction(loc, d):
-                for i, l in enumerate(p):
-                    self.plans[i + 1].add(l)
-                self.targets[dest] = loc
-                return True
-            else:
-                logging.debug('but an ant was in the way')
+            assert len(p) == len(set(p))
+            if settings.DEBUG:
+                logging.debug('finding path %s to %s (%.0fms, %d, OK)' % (
+                        loc, dest, 1000*(time.time() - t), loc.distance(dest),
+                    ))
+            new_loc = p[1]
+            ds = self.ants.direction(loc, new_loc)
+            for d in ds:
+                if self.do_move_direction(loc, d):
+                    for i, l in enumerate(p):
+                        self.plans[i + 1].add(l)
+                    self.targets[dest] = loc
+                    return True
+                else:
+                    settings.DEBUG and logging.debug(
+                            'but an ant was in the way')
 
-        logging.debug('finding a path from %s to %s (%.0fms, FAIL)' % (
-            loc, dest, 1000*(time.time() - t)))
+        if settings.DEBUG:
+            logging.debug('finding path %s to %s (%.0fms, %d, OK)' % (
+                    loc, dest, 1000*(time.time() - t), loc.distance(dest),
+                ))
         return False
     
     def do_move_location_fast(self, loc, dest):
         passable = self.ants.passable
         seen = self.game.seen
         plans = self.plans
+        parent = {}
+        dist = {}
 
-        def f(p):
-            return dest_d(p[-1]) + len(p)
+        def f(l):
+            return dest_d(l) + dist[l]
 
-        def expand(p):
-            l0 = p[-1]
+        def expand(l0):
             for l in l0.neighbours():
-                if l not in p and l not in plans[len(p)] and passable(l) \
+                dist[l] = dist[l0] + 1
+                if l not in parent and l not in plans[dist[l]] and passable(l) \
                         and seen[l]:
-                    yield p + (l,)
-
-        p0 = loc,
-        queue = [(f(p0), p0)]
+                    yield l
+
+        def path_from(l):
+            p = [l]
+            while l != loc:
+                l = parent[l]
+                p.append(l)
+            p.reverse()
+            return p
+
+        dist[loc] = 0
+        queue = [(f(loc), loc)]
         push = partial(heapq.heappush, queue)
         pop = partial(heapq.heappop, queue)
 
-        visited = set()
         while queue:
-            cost, p = pop()
-            if p[-1] == dest:
-                return p[1:]
-
-            for p_next in expand(p):
-                l_next = p_next[-1]
-                if l_next not in visited:
-                    visited.add(l_next)
-                    push((f(p_next), p_next))
+            cost, l0 = pop()
+            if l0 == dest:
+                p = path_from(l0)
+                return p
+
+            for l in expand(l0):
+                if l not in parent:
+                    parent[l] = l0
+                    dist[l] = dist[l0] + 1
+                    push((f(l), l))
 
     def find_food(self):
         components = self.game.components