Commits

Lars Yencken committed 33db538

Improve frontier consideration.

Comments (0)

Files changed (1)

 
 import heapq
 from functools import partial
+import random
 
 from ants import Ants
 
-# define a class with a do_turn method
-# the Ants.run method will parse and update bot input
-# it will also run the do_turn method for us
-class MoveState(object):
-    def __init__(self, ants, bot):
+class GameTurn(object):
+    "Game state for an individual move."
+    def __init__(self, ants, game):
         self.ants = ants
-        self.bot = bot
+        self.game = game
         self.targets = {}
         self.orders = {}
+        self.needs_orders = set(ants.my_ants())
 
         # prevent stepping on own hill
         for hill_loc in ants.my_hills():
             self.orders[hill_loc] = None
 
     def do_move_direction(self, loc, direction):
+        "Move in a given direction, handling conflicting orders."
         new_loc = self.ants.destination(loc, direction)
         if (self.ants.unoccupied(new_loc) and new_loc not in self.orders):
             self.ants.issue_order((loc, direction))
             self.orders[new_loc] = loc
+            self.needs_orders.remove(loc)
             return True
         else:
             return False
 
     def do_move_location(self, loc, dest):
+        "Slow but exact pathfinding."
         p = self.find_path(loc, dest)
         if p:
             new_loc = p[0]
                 return True
 
         return False
-        #directions = self.ants.direction(loc, dest)
-        #for direction in directions:
-            #if self.do_move_direction(loc, direction):
-                #self.targets[dest] = loc
-                #return True
-        #return False
+    
+    def do_move_location_fast(self, loc, dest):
+        "Fast and approximate pathfinding."
+        directions = self.ants.direction(loc, dest)
+        for direction in directions:
+            if self.do_move_direction(loc, direction):
+                self.targets[dest] = loc
+                return True
+        return False
 
     def find_path(self, loc, dest):
         "A* search from the location to the destination."
             for p_next in expand(p):
                 push((f(p_next), p_next))
 
+    def find_food(self):
+        ant_dist = []
+        distance = self.ants.distance
+        for food_loc in self.ants.food():
+            for ant_loc in list(self.needs_orders):
+                dist = distance(ant_loc, food_loc)
+                ant_dist.append((dist, ant_loc, food_loc))
+
+        ant_dist.sort()
+        for dist, ant_loc, food_loc in ant_dist:
+            if food_loc not in self.targets \
+                    and ant_loc not in self.targets.values():
+                self.do_move_location(ant_loc, food_loc)
+
+    def attack_hills(self):
+        # attack enemy hills
+        ant_dist = []
+        distance = self.ants.distance
+        for hill_loc in self.game.hills:
+            for ant_loc in list(self.needs_orders):
+                if ant_loc not in self.orders.values():
+                    dist = distance(ant_loc, hill_loc)
+                    ant_dist.append((dist, ant_loc))
+        ant_dist.sort()
+        for dist, ant_loc in ant_dist:
+            self.do_move_location(ant_loc, hill_loc)
+
+    def explore(self):
+        # explore unseen areas
+        distance = self.ants.distance
+        frontier = self.build_frontier(self.game.unseen)
+        for ant_loc in list(self.needs_orders):
+            unseen_dist = []
+            for unseen_loc in frontier:
+                dist = distance(ant_loc, unseen_loc)
+                unseen_dist.append((dist, unseen_loc))
+            unseen_dist.sort()
+            for dist, unseen_loc in unseen_dist:
+                if self.do_move_location(ant_loc, unseen_loc):
+                    break
+
+    def build_frontier(self, unseen):
+        frontier = unseen.copy()
+        rows = self.ants.rows
+        cols = self.ants.cols
+        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:
+                    frontier.remove(l)
+
+        return frontier
+
+    def have_time(self):
+        return self.ants.time_remaining() > 300
+
+    def random_walk(self):
+        "Do a random walk with all remaining ants."
+        for loc in list(self.needs_orders):
+            directions = ['n', 's', 'e', 'w']
+            random.shuffle(directions)
+            for d in directions:
+                if self.do_move_direction(loc, d):
+                    break
+
 class MyBot(object):
+    "Game state bot, persistent across turns."
     def __init__(self):
         self.unseen = set()
     
     def do_setup(self, ants):
+        "Initialise state with game variables."
         for row in range(ants.rows):
             for col in range(ants.cols):
                 self.unseen.add((row, col))
         self.hills = []
 
     def do_turn(self, ants):
-        state = MoveState(ants, self)
+        "Give orders to all of our ants."
+        self.remember_hills(ants)
+        self.remember_seen(ants)
 
-        # head for food
-        ant_dist = []
-        for food_loc in ants.food():
-            for ant_loc in ants.my_ants():
-                dist = ants.distance(ant_loc, food_loc)
-                ant_dist.append((dist, ant_loc, food_loc))
-
-        ant_dist.sort()
-        for dist, ant_loc, food_loc in ant_dist:
-            if food_loc not in state.targets \
-                    and ant_loc not in state.targets.values():
-                state.do_move_location(ant_loc, food_loc)
-
-        for hill_loc, hill_owner in ants.enemy_hills():
-            if hill_loc not in self.hills:
-                self.hills.append(hill_loc)
-
-        # attack enemy hills
-        ant_dist = []
-        for hill_loc in self.hills:
-            for ant_loc in ants.my_ants():
-                if ant_loc not in state.orders.values():
-                    dist = ants.distance(ant_loc, hill_loc)
-                    ant_dist.append((dist, ant_loc))
-        ant_dist.sort()
-        for dist, ant_loc in ant_dist:
-            state.do_move_location(ant_loc, hill_loc)
+        turn = GameTurn(ants, self)
+        turn.find_food()
+        turn.attack_hills()
+        turn.explore()
 
+    def remember_seen(self, ants):
         # update unseen map
         remove = []
+        visible = ants.visible
         for loc in self.unseen:
-            if ants.visible(loc):
+            if visible(loc):
                 remove.append(loc)
         for loc in remove:
             self.unseen.remove(loc)
 
-        # explore unseen areas
-        has_orders = set(state.orders.values())
-        for ant_loc in ants.my_ants():
-            if ant_loc in has_orders:
-                continue
+    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)
 
-            unseen_dist = []
-            for unseen_loc in self.unseen:
-                dist = ants.distance(ant_loc, unseen_loc)
-                unseen_dist.append((dist, unseen_loc))
-            unseen_dist.sort()
-            for dist, unseen_loc in unseen_dist:
-                if state.do_move_location(ant_loc, unseen_loc):
-                    break
- 
 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.