# HG changeset patch # User Neil Muller # Date 1259275951 0 # Node ID d3ceb9e9c48eb6869e0e0169e3f049cef8e22060 # Parent 3b5717d742b232ef612916b7dd20d280e0b8dd05 The fox move rewrite diff -r 3b5717d742b2 -r d3ceb9e9c48e gamelib/animal.py --- a/gamelib/animal.py Thu Nov 26 22:50:57 2009 +0000 +++ b/gamelib/animal.py Thu Nov 26 22:52:31 2009 +0000 @@ -13,6 +13,16 @@ import serializer import constants + +NEIGHBOUR_4 = [Position(-1, 0), Position(1, 0), Position(0, 1), Position(0, -1)] + + +NEIGHBOUR_8 = [Position(-1, 0), Position(1, 0), Position(0, 1), Position(0, -1), + Position(1, 1), Position(1, -1), Position(-1, 1), Position(-1, -1)] + + +TILE_FENCE = tiles.REVERSE_TILE_MAP['fence'] + class Animal(Sprite, serializer.Simplifiable): """Base class for animals""" @@ -80,8 +90,8 @@ # Call appropriate gameboard cleanup here. pass - def move(self, state): - """Given the game state, return a new position for the object""" + def move(self): + """Return a new position for the object""" # Default is not to move pass @@ -317,7 +327,7 @@ # weighting for movement calculation 'grassland' : 2, 'woodland' : 1, # Try to keep to the woods if possible - 'broken fence' : 2, + 'broken fence' : 1, 'fence' : 25, 'guardtower' : 2, # We can pass under towers 'henhouse' : 30, # Don't go into a henhouse unless we're going to @@ -327,16 +337,18 @@ def __init__(self, pos, gameboard): Animal.__init__(self, pos, gameboard) - self.landmarks = [self.pos] + self.start_pos = self.pos + self.target = None self.hunting = True self.dig_pos = None self.tick = 0 self.safe = False self.closest = None - self.last_steps = [] # Foxes don't occupy places in the same way chickens do, but they # can still be inside self.building = None + self._last_steps = [] + self.path = [] def outside(self): return self.building is None @@ -352,88 +364,230 @@ cost = 100 # Out of bounds is expensive return cost - def _cost_path(self, path): - """Calculate the cost of a path""" - total = 0 - for pos in path: - total += self._cost_tile(pos) - return total + def _is_fence(self, pos): + if self.gameboard.in_bounds(pos): + this_tile = self.gameboard.tv.get(pos.to_tile_tuple()) + return this_tile == TILE_FENCE + return False - def _gen_path(self, start_pos, final_pos): - """Construct a direct path from start_pos to final_pos, - excluding start_pos""" - return start_pos.intermediate_positions(final_pos) + def _check_steps(self, step, border_func, end_func, max_steps): + steps = 0 + cur_pos = self.pos + path = [] + while steps < max_steps: + if not border_func(cur_pos): + # Not walking the edge + # Is there a 4-NEIGHBOUR, to path[-1], not in the path that + # is a continue + if not path: + # Rest of search will cover neighbours + return None + for cand in [path[-1] + x for x in NEIGHBOUR_4]: + if cand in path: + continue + if border_func(cand): + cur_pos = cand + break + return None + path.append(cur_pos) + if end_func(cur_pos): + # is there an 8-NEIGHBOUR that also satisfies end_func and is + # closer to target + dist = self.target.dist(cur_pos) + fin_pos = None + for pos in [cur_pos + x for x in NEIGHBOUR_8]: + if end_func(pos) and self.target.dist(pos) < dist: + fin_pos = pos + dist = self.target.dist(pos) + if fin_pos: + path.append(fin_pos) + return path + steps += 1 + cur_pos = cur_pos + step + return None + + def _search_for_path(self, border_func, end_func, max_steps): + paths = [None] * 4 + paths[0] = self._check_steps(Position(-1, 0), border_func, end_func, max_steps) + paths[1] = self._check_steps(Position(0, -1), border_func, end_func, max_steps) + paths[2] = self._check_steps(Position(1, 0), border_func, end_func, max_steps) + paths[3] = self._check_steps(Position(0, 1), border_func, end_func, max_steps) + cands = [x for x in paths if x is not None] + if not cands: + return None + elif len(cands) == 1: + return cands[0][1:] + # take the end point closest to our target + final_path = cands[0] + min_dist = final_path[-1].dist(self.target) + for this_path in cands[1:]: + dist = this_path[-1].dist(self.target) + if dist < min_dist: + min_dist = dist + final_path = this_path + elif dist == min_dist and random.randint(0, 1) == 0: + final_path = this_path + return final_path[1:] # path's include self.pos - def _find_best_path_step(self, final_pos): - """Find the cheapest path to final_pos, and return the next step - along the path.""" - # We calculate the cost of the direct path - if final_pos.z < self.pos.z: - # We need to try heading down. - return Position(self.pos.x, self.pos.y, self.pos.z - 1) - if final_pos.x == self.pos.x and final_pos.y == self.pos.y and \ - final_pos.z > self.pos.z: - # We try heading up - return Position(self.pos.x, self.pos.y, self.pos.z + 1) - cur_dist = final_pos.dist(self.pos) - if cur_dist < 2: - # We're right ontop of our target, so just go there - return final_pos - # Find the cheapest spot close to us that moves us closer to the target - neighbours = [Position(self.pos.x + x, self.pos.y + y, self.pos.z) for - x in range(-1, 2) for y in range(-1, 2) if (x, y) != (0, 0)] - best_pos = self.pos + def _find_nearest_corner(self): + """Find the nearest corner of the bulding""" + COST_MARGIN = 25 + def border(pos): + cost = self._cost_tile(pos) + if cost >= COST_MARGIN: + return False # in building isn't border + for tpos in [pos + step for step in NEIGHBOUR_8]: + if self.gameboard.in_bounds(tpos): + cost = self._cost_tile(tpos) + if cost >= COST_MARGIN: + return True + return False + + def corner(pos): + # A corner is not 4-connected to a building + if not border(pos): + return False + for tpos in [pos + step for step in NEIGHBOUR_4]: + if self.gameboard.in_bounds(tpos): + cost = self._cost_tile(tpos) + if cost >= COST_MARGIN: + return False + return True + + # We check left, then right and take the shortest if both are valid + return self._search_for_path(border, corner, 6) + + def _find_fence_gap(self): + # We search for a gap in the fence + # we know we are next to fence. A gap in the fence is + # a point that borders the fence where the fence is not + # 4-connected + + COST_MARGIN = 25 + + def border(pos): + if self._is_fence(pos) or self._cost_tile(pos) >= COST_MARGIN: + return False + for tpos in [pos + step for step in NEIGHBOUR_8]: + if self._is_fence(tpos) or self._cost_tile(tpos) >= COST_MARGIN: + print 'border pos', pos, self._cost_tile(pos) + return True + return False + + def is_gap(pos): + # A gap neighbours only fence tiles which has < 2 4-neighbours + if self._is_fence(pos): + return False + fence_neighbours = [0] + for tpos in [pos + step for step in NEIGHBOUR_8]: + if self._is_fence(tpos): + connections = 0 + for fpos in [tpos + step for step in NEIGHBOUR_4]: + if self.gameboard.in_bounds(fpos): + if self._is_fence(fpos) or self._cost_tile(tpos) >= COST_MARGIN: + # Expensive building is considered fence + connections += 1 + else: + # Fence connecting to out of bounds counts as fence + connections += 1 + fence_neighbours.append(connections) + return max(fence_neighbours) < 2 + + return self._search_for_path(border, is_gap, 7) + + def _find_min_cost_neighbour(self, target): + """Find the minimum cost neighbour that's closer to target""" + cur_dist = target.dist(self.pos) + neighbours = [self.pos + step for step in NEIGHBOUR_8] min_cost = 1000 min_dist = cur_dist + best = self.pos for point in neighbours: - dist = point.dist(final_pos) - if dist < cur_dist: + if point in self._last_steps: + continue + dist = point.dist(target) + if dist <= min_dist: cost = self._cost_tile(point) if cost < min_cost or (min_cost == cost and dist < min_dist): # Prefer closest of equal cost points min_dist = dist min_cost = cost best = point - if min_cost < 20 or not self.gameboard.in_bounds(self.pos): + elif min_cost == cost and random.randint(0, 1) == 0: + # Be slightly non-deterministic when presented with + # equal choices + best = point + return best, min_cost + + def _find_best_path_step(self): + """Find the cheapest path to final_pos, and return the next step + along the path.""" + if self.path: + next_step = self.path.pop(0) + if next_step.dist(self.pos) < 2: + return next_step + else: + # Been bounced off the path + self.path = [] + if self.target.z < self.pos.z: + # We need to try heading down. + return Position(self.pos.x, self.pos.y, self.pos.z - 1) + if self.target.x == self.pos.x and self.target.y == self.pos.y and \ + self.target.z > self.pos.z: + # We try heading up + return Position(self.pos.x, self.pos.y, self.pos.z + 1) + cur_dist = self.target.dist(self.pos) + best, min_cost = self._find_min_cost_neighbour(self.target) + if cur_dist < 2: + # We're right ontop of our target, so just go there + return self.target + # Find the cheapest spot close to us that moves us closer to the target + if min_cost < 20 or not self.gameboard.in_bounds(self.pos) \ + or not self.gameboard.in_bounds(best): # If we're not on the gameboard yet, there's no point in looking # for an optimal path. return best # Else expensive step, so think further - direct_path = self._gen_path(self.pos, final_pos) - min_cost = self._cost_path(direct_path) - min_path = direct_path - # is there a point nearby that gives us a cheaper direct path? - # This is delibrately not finding the optimal path, as I don't - # want the foxes to be too intelligent, although the implementation - # isn't well optimised yet - # FIXME: Currently, this introduces loops, but the memory kind - # avoids that. Fixing this is the next goal. - poss = [Position(self.pos.x + x, self.pos.y + y, self.pos.z) for - x in range(-3, 4) for y in range(-3, 4) if (x, y) != (0, 0)] - for start in poss: - cand_path = self._gen_path(self.pos, start) + \ - self._gen_path(start, final_pos) - cost = self._cost_path(cand_path) - if cost < min_cost: - min_cost = cost - min_path = cand_path - if not min_path: - return final_pos - return min_path[0] + if self._is_fence(best): + path = self._find_fence_gap() + elif min_cost == 30: + # building + path = self._find_nearest_corner() + else: + # We're looping + self._last_steps = [] + return self.pos + if path: + self.path = path[1:] # exclude 1st step + return path[0] + return best - def _find_path_to_woodland(self): - """Dive back to woodland through the landmarks""" - # find the closest point to our current location in walked path - if self.pos == self.landmarks[-1]: - if len(self.landmarks) > 1: - self.landmarks.pop() # Moving to the next landmark - if not self.gameboard.in_bounds(self.pos) and not self.hunting: - # Safely out of sight - self.safe = True + def _calc_next_move(self): + """Find the path to the target""" + if self.hunting: + # Check if we need to update our idea of a target + if not self.closest or self.closest not in self.gameboard.chickens: + # Either no target, or someone ate it + self._select_prey() + elif not self.target: + self.target = self.closest.pos + if not self.target: + self.target = self.start_pos + self._last_steps = [] + if self.target == self.pos: + # No need to move, but we will need to update the target + self.target = None return self.pos - return self._find_best_path_step(self.landmarks[-1]) + if self.target.to_tile_tuple() == self.pos.to_tile_tuple(): + # Only differ in z, so next step is in z + if self.target.z < self.pos.z: + new_z = self.pos.z - 1 + else: + new_z = self.pos.z + 1 + return Position(self.pos.x, self.pos.y, new_z) + return self._find_best_path_step() - def _select_target(self): + def _select_prey(self): min_dist = 999 self.closest = None for chicken in self.gameboard.chickens: @@ -445,28 +599,12 @@ if dist < min_dist: min_dist = dist self.closest = chicken - - def _find_path_to_chicken(self): - """Find the path to the closest chicken""" - # Find the closest chicken - if self.closest not in self.gameboard.chickens: - # Either no target, or someone ate it - self._select_target() + self.target = chicken.pos if not self.closest: # No more chickens, so leave self.hunting = False - return self.pos - if self.closest.pos == self.pos: - # No need to move + self.target = self.start_pos return self.pos - if self.closest.pos.to_tile_tuple() == self.pos.to_tile_tuple(): - # Only differ in z, so next step is in z - if self.closest.pos.z < self.pos.z: - new_z = self.pos.z - 1 - else: - new_z = self.pos.z + 1 - return Position(self.pos.x, self.pos.y, new_z) - return self._find_best_path_step(self.closest.pos) def attack(self): """Attack a chicken""" @@ -480,29 +618,26 @@ chicken.damage() self.closest = None self.hunting = False - self.last_steps = [] # Forget history here + self.target = self.start_pos + self._last_steps = [] def _update_pos(self, new_pos): """Update the position, making sure we don't step on other foxes""" + if not self.hunting and not self.gameboard.in_bounds(self.pos): + self.safe = True + return self.pos if new_pos == self.pos: # We're not moving, so we can skip all the checks return new_pos blocked = self.gameboard.get_animal_at_pos(new_pos, 'fox') is not None - if not blocked and new_pos.z == self.pos.z: - # We're only worried about loops when not on a ladder - blocked = new_pos in self.last_steps final_pos = new_pos if blocked: - if new_pos.z != self.pos.z: + if new_pos.z != self.pos.z or self.pos.z != 0: # We can only move up and down a ladder moves = [Position(self.pos.x, self.pos.y, z) for z in range(self.pos.z-1, self.pos.z + 2) if z >= 0] else: - moves = [Position(x, y) for x in range(self.pos.x-1, self.pos.x + 2) - for y in range(self.pos.y-1, self.pos.y + 2) - if Position(x,y) != self.pos and - Position(x, y) not in self.last_steps and - self.pos.z == 0] + moves = [self.pos + step for step in NEIGHBOUR_8] # find the cheapest point in moves that's not blocked final_pos = None min_cost = 1000 @@ -519,18 +654,11 @@ if not final_pos: # No good choice, so stay put return self.pos - if self.gameboard.in_bounds(final_pos): - this_tile = self.gameboard.tv.get(final_pos.to_tile_tuple()) - else: - this_tile = tiles.REVERSE_TILE_MAP['woodland'] - if tiles.TILE_MAP[this_tile] == 'broken fence' and self.hunting: - # We'll head back towards the holes we make/find - self.landmarks.append(final_pos) - elif tiles.TILE_MAP[this_tile] == 'fence' and not self.dig_pos: + if self._is_fence(final_pos) and not self.dig_pos: return self._dig(final_pos) - self.last_steps.append(final_pos) - if len(self.last_steps) > 3: - self.last_steps.pop(0) + self._last_steps.append(final_pos) + if len(self._last_steps) > 6: + self._last_steps.pop(0) return final_pos def _dig(self, dig_pos): @@ -560,17 +688,14 @@ # Check the another fox hasn't dug a hole for us # We're too busy digging to notice if a hole appears nearby, # but we'll notice if the fence we're digging vanishes - this_tile = self.gameboard.tv.get(self.dig_pos.to_tile_tuple()) - if tiles.TILE_MAP[this_tile] != 'fence': + if not self._is_fence(self.dig_pos): self.tick = 0 else: # We've dug through the fence, so make a hole self._make_hole() return - elif self.hunting: - desired_pos = self._find_path_to_chicken() else: - desired_pos = self._find_path_to_woodland() + desired_pos = self._calc_next_move() final_pos = self._update_pos(desired_pos) self._fix_face(final_pos) self.pos = final_pos @@ -638,7 +763,8 @@ self.chickens_eaten += 1 if self.chickens_eaten > 2: self.hunting = False - self.last_steps = [] + self.target = self.start_pos + self._last_steps = [] class Rinkhals(Fox): """The Rinkhals has eclectic tastes""" @@ -646,7 +772,10 @@ IMAGE_FILE = 'sprites/rinkhals.png' CONFIG_NAME = 'rinkhals' - def _select_target(self): + costs = Fox.costs.copy() + costs['fence'] = 2 + + def _select_prey(self): """The Rinkhals eats eggs""" min_dist = 999 self.closest = None @@ -657,13 +786,15 @@ if dist < min_dist: min_dist = dist self.closest = chicken + self.target = self.closest.pos def _catch_chicken(self, chicken): """The Rinkhals eats eggs, but does not harm chickens""" chicken.remove_eggs() self.closest = None self.hunting = False - self.last_steps = [] + self.target = self.start_pos + self._last_steps = [] def _dig(self, dig_pos): """Snakes ignore fences"""