From f8a9f2b824f0fbbb1e1e9d4a58659a513c8bbe78 Mon Sep 17 00:00:00 2001 From: Peter Ward Date: Sat, 22 Feb 2014 22:44:10 +1100 Subject: various improvements --- robots/__init__.py | 2 +- robots/cursesviewer.py | 5 ++- robots/game.py | 41 ++++++++++++++++- robots/utils.py | 31 ++++++++++--- simple.py | 117 ++++++++++++++++++++++++++++++++++++++++++++++--- 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() -- cgit v1.2.3