From 32163e6691e1da7b6adfde97314be40ae57120ec Mon Sep 17 00:00:00 2001
From: Peter Ward <peteraward@gmail.com>
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