From 32163e6691e1da7b6adfde97314be40ae57120ec Mon Sep 17 00:00:00 2001 From: Peter Ward Date: Fri, 11 Apr 2014 17:29:47 +1000 Subject: distance_relaxer returns a list of shortest moves in predecessors GameState has an expected_position() method. --- robots/algorithms.pyx | 43 +++++++++++++++++++++++++++++++++++-------- robots/game.py | 17 ++++++++--------- robots/state.py | 24 +++++++++++++++++++++--- robots/utils.py | 13 +++++++++++++ 4 files changed, 77 insertions(+), 20 deletions(-) diff --git a/robots/algorithms.pyx b/robots/algorithms.pyx index 620cfce..3bf6916 100644 --- a/robots/algorithms.pyx +++ b/robots/algorithms.pyx @@ -10,17 +10,31 @@ ctypedef np.int32_t ITYPE_t ctypedef cython.bint bool -from robots.constants import DIRECTIONS - INFINITY = float('inf') FAKE_INFINITY = 1<<31 - 1 +PREDECESSORS = {} +for i in range(16): + p = [] + if i & 1: + p.append('U') + if i & 2: + p.append('D') + if i & 4: + p.append('L') + if i & 8: + p.append('R') + PREDECESSORS[i] = p + def distance_relaxer(distances, iterations=None): width = len(distances[0]) height = len(distances) predecessors = [ - [None] * width + [ + [] + for _ in range(width) + ] for _ in range(height) ] @@ -68,7 +82,6 @@ cdef void _distance_relaxer( int iterations, Py_ssize_t width, Py_ssize_t height, - DIRECTIONS=DIRECTIONS, ): cdef Py_ssize_t x, y cdef Py_ssize_t nx, ny @@ -76,6 +89,7 @@ cdef void _distance_relaxer( cdef int i = 0 cdef bool updated + cdef int p while i != iterations: updated = False @@ -86,6 +100,8 @@ cdef void _distance_relaxer( if distance == -1: continue + p = 0 + nx = x ny = (y - 1) % height this_distance = distances[ny, nx] @@ -93,9 +109,11 @@ cdef void _distance_relaxer( if this_distance != FAKE_INFINITY: this_distance += 1 if this_distance < distances[y, x]: + p = 0 distances[y, x] = this_distance - predecessors[y][x] = 'U' updated = True + if this_distance == distances[y, x]: + p |= 1 nx = x ny = (y + 1) % height @@ -104,9 +122,11 @@ cdef void _distance_relaxer( if this_distance != FAKE_INFINITY: this_distance += 1 if this_distance < distances[y, x]: + p = 0 distances[y, x] = this_distance - predecessors[y][x] = 'D' updated = True + if this_distance == distances[y, x]: + p |= 2 nx = (x - 1) % width ny = y @@ -115,9 +135,11 @@ cdef void _distance_relaxer( if this_distance != FAKE_INFINITY: this_distance += 1 if this_distance < distances[y, x]: + p = 0 distances[y, x] = this_distance - predecessors[y][x] = 'L' updated = True + if this_distance == distances[y, x]: + p |= 4 nx = (x + 1) % width ny = y @@ -126,9 +148,14 @@ cdef void _distance_relaxer( if this_distance != FAKE_INFINITY: this_distance += 1 if this_distance < distances[y, x]: + p = 0 distances[y, x] = this_distance - predecessors[y][x] = 'R' updated = True + if this_distance == distances[y, x]: + p |= 8 + + if p: + predecessors[y][x] = PREDECESSORS[p] if not updated: break diff --git a/robots/game.py b/robots/game.py index cb065ec..9b5c339 100644 --- a/robots/game.py +++ b/robots/game.py @@ -2,6 +2,8 @@ from collections import defaultdict, deque from contextlib import contextmanager from copy import deepcopy from random import random +import time +import traceback from robots.constants import Action, City, DIRECTIONS, Energy, ENERGY_BY_ACTION from robots.state import GameState @@ -104,9 +106,10 @@ class Game: 'Got unexpected action %r' % (action,) ) - except Exception as e: + except Exception: # TODO: log this exception - print(e) + traceback.print_exc() + time.sleep(1) else: for bot, action in zip(my_robots, result): @@ -128,15 +131,11 @@ class Game: action = Action.NOTHING elif action != Action.NOTHING: - dx, dy = DIRECTIONS[action] - nx = (x + dx) % self.state.width - ny = (y + dy) % self.state.height + nx, ny = self.state.expected_position(x, y, action) - if self.state.cities[ny][nx] in City.traversable: - x = nx - y = ny - else: + if x == nx and y == ny: action = Action.NOTHING + x, y = nx, ny energy -= ENERGY_BY_ACTION[action] diff --git a/robots/state.py b/robots/state.py index 5a1450d..8a47139 100644 --- a/robots/state.py +++ b/robots/state.py @@ -1,7 +1,7 @@ from collections import defaultdict, Counter -from robots.constants import City -from robots.utils import ceil_div +from robots.constants import City, DIRECTIONS +from robots.utils import ceil_div#, immutable class GameState: """The state of a game at a point in time. @@ -18,7 +18,8 @@ class GameState: self.robots_by_player = {} def __hash__(self): - return hash(self._authorative_state) + return id(self) +# return hash(immutable(self._authorative_state)) def __eq__(self, other): if isinstance(other, GameState): @@ -112,3 +113,20 @@ class GameState: def n_cities_to_win(self): """How many cities you need to pledge allegiance to you to win.""" return ceil_div(self.n_allegiable_cities, self.n_alive_players) + + def expected_position(self, x, y, action): + """ + Return the expected position for a robot at (x, y) if it performs the + given action. + Of course, combat (and possibly other factors in the future) may + influence whether it actually ends up at the returned position. + """ + dx, dy = DIRECTIONS[action] + nx = (x + dx) % self.width + ny = (y + dy) % self.height + + if self.cities[ny][nx] in City.traversable: + x = nx + y = ny + + return (x, y) diff --git a/robots/utils.py b/robots/utils.py index e269a02..5793a00 100644 --- a/robots/utils.py +++ b/robots/utils.py @@ -10,6 +10,19 @@ def ceil_div(a, b): def ilen(items): return sum(1 for _ in items) +def immutable(value): + if isinstance(value, str): + return value + try: + return immutable(list(sorted(value.items()))) + except AttributeError: + pass + try: + return tuple(immutable(v) for v in value) + except TypeError: + pass + return value + def add_spawns(map_, n_spawns, city=None): available = [] for x, y, cell in iter_board(map_): -- cgit v1.2.3