Lars Yencken avatar Lars Yencken committed 02f83ad

Improve efficiency of A* search.

Comments (0)

Files changed (1)

 #!/usr/bin/env python
-
+# -*- coding: utf-8 -*-
+#
+#  MyBot.py
+#  aichallenge.py
+#
+#  Created by Lars Yencken on 2011-11-02.
+#  Copyright 2011 Lars Yencken. All rights reserved.
+#
+
+"""
+Bot for Google's AI Challenge.
+"""
+
+import sys
 import heapq
 from functools import partial
 import random
         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):
-                push((f(p_next), p_next))
+                l_next = p_next[-1]
+                if l_next not in visited:
+                    visited.add(l_next)
+                    push((f(p_next), p_next))
 
             if len(queue) > 100:
-                return
+                return p[1:]
 
     def find_food(self):
         ant_dist = []
         for i in xrange(rows):
             for j in xrange(cols):
                 l = (i, j)
-                if (i - 1 % rows, j - 1 % cols) in unseen \
-                        and (i - 1 % rows, j + 1 % cols) in unseen \
-                        and (i + 1 % rows, j - 1 % cols) in unseen \
-                        and (i + 1 % rows, j + 1 % rows) in unseen:
+                if ((i - 1) % rows, (j - 1) % cols) in unseen \
+                        and ((i - 1) % rows, (j + 1) % cols) in unseen \
+                        and ((i + 1) % rows, (j - 1) % cols) in unseen \
+                        and ((i + 1) % rows, (j + 1) % rows) in unseen:
                     frontier.remove(l)
 
         return frontier
 
+    def print_frontier(self):
+        self.game.print_map(self.frontier)
+
     def have_time(self):
         return self.ants.time_remaining() > 300
 
                 self.unseen.add((row, col))
 
         self.hills = []
+        self.rows = ants.rows
+        self.cols = ants.cols
 
     def do_turn(self, ants):
         "Give orders to all of our ants."
         turn.attack_hills()
         turn.explore()
         turn.random_walk()
+        print >> sys.stderr, ants.time_taken()
 
     def remember_seen(self, ants):
-        # update unseen map
-        remove = []
         visible = ants.visible
-        for loc in self.unseen:
-            if visible(loc):
-                remove.append(loc)
-        for loc in remove:
-            self.unseen.remove(loc)
+        mark_visible = self.unseen.remove
+        for loc in filter(visible, self.unseen):
+            mark_visible(loc)
 
     def remember_hills(self, ants):
         for hill_loc, hill_owner in ants.enemy_hills():
             if hill_loc not in self.hills:
                 self.hills.append(hill_loc)
 
+    def visible(self):
+        self.print_map(self.unseen)
+
+    def print_map(self, m):
+        render = lambda x: u'O' if x in m else u'•'
+        for i in xrange(self.rows):
+            l = u''.join(render((i, j)) for j in xrange(self.cols))
+            print >> sys.stderr, l
+
 if __name__ == '__main__':
     # psyco will speed up python a little, but is not needed
     try:
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.