various improvements

5 files changed, 178 insertions, 18 deletions

diff --git a/robots/__init__.py b/robots/__init__.py
index 089cb44..f47e080 100644
--- a/robots/__init__.py
+++ b/robots/__init__.py
@@ -1,3 +1,3 @@
 from robots.cursesviewer import CursesViewer
 from robots.game import Game
-from robots.utils import empty_map
+from robots.utils import empty_map, border_map
diff --git a/robots/cursesviewer.py b/robots/cursesviewer.py
index b37a06a..0131894 100644
--- a/robots/cursesviewer.py
+++ b/robots/cursesviewer.py
@@ -64,12 +64,13 @@ class CursesViewer:
     def run(self):
         limiter = rate_limit(10)
 
-        self.draw_board()
         while not self.game.finished:
             next(limiter)
 
-            self.game.next()
             self.draw_board()
+            self.game.next()
+
+        self.draw_board()
 
         winners = self.game.finished
         if winners is True:
diff --git a/robots/game.py b/robots/game.py
index d87c495..b85d0b5 100644
--- a/robots/game.py
+++ b/robots/game.py
@@ -1,4 +1,4 @@
-from collections import defaultdict
+from collections import defaultdict, OrderedDict
 from contextlib import contextmanager
 from copy import deepcopy
 
@@ -52,7 +52,7 @@ def _extract_spawn_points(map_):
 class Game:
     def __init__(self, map_):
         self.bots = {}
-        self.players = {}
+        self.players = OrderedDict()
 
         self.board = deepcopy(map_)
         self._spawns = _extract_spawn_points(self.board)
@@ -62,6 +62,8 @@ class Game:
             '.': self.available_tiles,
         }
 
+        self.time = 0
+
     def add_bot(self, bot, name=None):
         if name is None:
             name = bot.__name__
@@ -78,6 +80,7 @@ class Game:
         self.players[name] = {
             'robots': [spawn],
             'spawn': spawn,
+            'last_spawn': 0,
         }
         self._painted_tiles[name] = 0
 
@@ -175,6 +178,10 @@ class Game:
             new_robots[whoami].append((x, y))
             bot_locations[x, y] += 1
 
+        for whoami, (x, y) in self.spawn_bots():
+            new_robots[whoami].append((x, y))
+            bot_locations[x, y] += 1
+
         to_remove = set(
             (x, y)
             for (x, y), count in bot_locations.items()
@@ -188,6 +195,36 @@ class Game:
                 if (x, y) not in to_remove
             ]
 
+    def get_spawn_time(self, whoami):
+        n_robots = len(self.players[whoami]['robots'])
+        if n_robots == 0:
+            return float('inf')
+        fraction_unowned = 1.0 - (
+            self._painted_tiles[whoami] /
+            self.available_tiles
+        )
+        return int(10 * fraction_unowned) + 1
+
+    def spawn_bots(self):
+        for whoami, info in self.players.items():
+            spawn_time = self.get_spawn_time(whoami)
+#            print(whoami, spawn_time)
+            time_since_last_spawn = self.time - info['last_spawn']
+            n_tiles = self._painted_tiles[whoami]
+            if time_since_last_spawn >= spawn_time:
+                yield whoami, info['spawn']
+                info['last_spawn'] = self.time
+
     def next(self):
         actions = self.call_bots()
         self.apply_actions(actions)
+
+        import sys
+        print(
+            *(len(info['robots']) for info in self.players.values()),
+            sep='\t',
+            file=sys.stderr
+        )
+        sys.stderr.flush()
+
+        self.time += 1
diff --git a/robots/utils.py b/robots/utils.py
index 4473a6b..544bec7 100644
--- a/robots/utils.py
+++ b/robots/utils.py
@@ -1,18 +1,35 @@
 from random import sample
 import time
 
+def add_spawns(map_, n_spawns):
+    available = []
+    for x, y, cell in iter_board(map_):
+        if cell != '*':
+            available.append((x, y))
+
+    spawns = sample(available, n_spawns)
+    for i, (x, y) in enumerate(spawns):
+        map_[y][x] = str(i)
+
 def empty_map(width, height, n_spawns):
     board = [['.'] * width for y in range(height)]
 
-    all_positions = [
-        (x, y)
-        for x in range(width)
-        for y in range(height)
+    add_spawns(board, n_spawns)
+    return board
+
+def border_map(width, height, n_spawns):
+    board = [
+        ['.'] * (width + 2)
+        for y in range(height + 2)
     ]
-    spawns = sample(all_positions, n_spawns)
+    for x in range(width + 2):
+        board[0][x] = '*'
+        board[-1][x] = '*'
+    for y in range(height + 2):
+        board[y][0] = '*'
+        board[y][-1] = '*'
 
-    for i, (x, y) in enumerate(spawns):
-        board[y][x] = str(i)
+    add_spawns(board, n_spawns)
     return board
 
 def rate_limit(fps):
diff --git a/simple.py b/simple.py
index 1acdd99..78d4a7c 100644
--- a/simple.py
+++ b/simple.py
@@ -1,17 +1,122 @@
+from collections import defaultdict
+
 import random
 import robots
 
+iter_board = robots.utils.iter_board
+DIRECTIONS = robots.game.DIRECTIONS
+
+def shuffled(items):
+    items = list(items)
+    random.shuffle(items)
+    return items
+
+def get_enemy_robots(me, players):
+    robots = {}
+    for name, info in players.items():
+        if name != me:
+            for x, y in info['robots']:
+                robots[x, y] = name
+    return robots
+
+def paths_to_enemies(enemies, board, iterations=None):
+    width = len(board[0])
+    height = len(board)
+
+    if iterations is None:
+        iterations = 10
+
+    distances = []
+    for y in range(height):
+        distances.append([])
+        for x in range(width):
+            if (x, y) in enemies:
+                value = (0, None, (x, y))
+            else:
+                value = (float('inf'), None, None)
+            distances[-1].append(value)
+
+    DIRECTION_ITEMS = shuffled(DIRECTIONS.items())
+    for i in range(iterations):
+        for y in range(height):
+            for x in range(width):
+                for move, (dx, dy) in DIRECTION_ITEMS:
+                    nx = (x + dx) % width
+                    ny = (y + dy) % height
+                    if board[ny][nx] == '*':
+                        continue
+
+                    current_dist = distances[y][x][0]
+
+                    this_dist, _, dest = distances[ny][nx]
+                    this_dist += 1
+
+                    if this_dist < current_dist:
+                        distances[y][x] = (this_dist, move, dest)
+
+    return distances
+
+def attacker(whoami, players, board):
+    width = len(board[0])
+    height = len(board)
+
+    my_robots = players[whoami]['robots']
+    enemies = get_enemy_robots(whoami, players)
+    paths = paths_to_enemies(enemies, board)
+
+    allocations = defaultdict(list)
+    for x, y in my_robots:
+        dist, dir, dest = paths[y][x]
+        allocations[dest].append((dist, dir, (x, y)))
+
+    searchers = int(len(my_robots) * 0.7)
+
+    assignments = {}
+    for options in allocations.values():
+        for dist, dir, robot in sorted(options)[:searchers]:
+            assignments[robot] = dir
+
+    results = []
+    for x, y in my_robots:
+        choice = assignments.get((x, y))
+        if board[y][x] != whoami and (not choice or random.random() < 0.5):
+            choice = 'P'
+        elif choice:
+            pass
+        else:
+            moves = []
+            for dir, (dx, dy) in DIRECTIONS.items():
+                nx = (x + dx) % width
+                ny = (y + dy) % height
+                if board[ny][nx] != '*':
+                    moves.append(dir)
+            choice = random.choice(moves or '-')
+        results.append(choice)
+
+    return ''.join(results)
+
+def never_paint(whoami, players, board):
+    my_robots = players[whoami]['robots']
+    return ''.join(
+        random.choice('ULD--')
+        for _ in range(len(my_robots))
+    )
+
 def bot(whoami, players, board):
     my_robots = players[whoami]['robots']
-    action = random.choice('URP')
-    return action * len(my_robots)
+    return ''.join(
+        random.choice('ULDRPP')
+        for _ in range(len(my_robots))
+    )
 
 if __name__ == '__main__':
-    random.seed(64)
-    map_ = robots.empty_map(10, 10, 4)
+#    random.seed(42)
+    map_ = robots.border_map(30, 10, 4)
+
     game = robots.Game(map_)
-    game.add_bot(bot, 'Alice')
+    game.add_bot(attacker, 'Alice')
+    game.add_bot(attacker, 'Adam')
+    game.add_bot(bot, 'Barry')
     game.add_bot(bot, 'Bob')
-    game.add_bot(bot, 'Charlie')
     viewer = robots.CursesViewer(game)
     viewer.run()