rinkhals: gamelib/animal.py comparison

comparison gamelib/animal.py @ 507:d3ceb9e9c48e

The fox move rewrite

author	Neil Muller <drnlmuller@gmail.com>
date	Thu, 26 Nov 2009 22:52:31 +0000
parents	3ed6c011106d
children	8fbff3505d1d

comparison

equal deleted inserted replaced

-:3b5717d742b2
+:d3ceb9e9c48e
 import sound
 import equipment
 import animations
 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"""
 STEALTH = 0
 def _game_death(self):
 # Call appropriate gameboard cleanup here.
 pass
-def move(self, state):
+def move(self):
-"""Given the game state, return a new position for the object"""
+"""Return a new position for the object"""
 # Default is not to move
 pass
 def attack(self):
 """Given the game state, attack a suitable target"""
 costs = {
 # 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
 # catch a chicken there
 'hendominium' : 30,
 }
 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
 def _game_death(self):
 cost = self.costs.get(tiles.TILE_MAP[this_tile], 100)
 else:
 cost = 100 # Out of bounds is expensive
 return cost
-def _cost_path(self, path):
+def _is_fence(self, pos):
-"""Calculate the cost of a path"""
+if self.gameboard.in_bounds(pos):
-total = 0
+this_tile = self.gameboard.tv.get(pos.to_tile_tuple())
-for pos in path:
+return this_tile == TILE_FENCE
-total += self._cost_tile(pos)
+return False
-return total
+def _check_steps(self, step, border_func, end_func, max_steps):
-def _gen_path(self, start_pos, final_pos):
+steps = 0
-"""Construct a direct path from start_pos to final_pos,
+cur_pos = self.pos
-excluding start_pos"""
+path = []
-return start_pos.intermediate_positions(final_pos)
+while steps < max_steps:
+if not border_func(cur_pos):
-def _find_best_path_step(self, final_pos):
+# Not walking the edge
-"""Find the cheapest path to final_pos, and return the next step
+# Is there a 4-NEIGHBOUR, to path[-1], not in the path that
-along the path."""
+# is a continue
-# We calculate the cost of the direct path
+if not path:
-if final_pos.z < self.pos.z:
+# Rest of search will cover neighbours
-# We need to try heading down.
+return None
-return Position(self.pos.x, self.pos.y, self.pos.z - 1)
+for cand in [path[-1] + x for x in NEIGHBOUR_4]:
-if final_pos.x == self.pos.x and final_pos.y == self.pos.y and \
+if cand in path:
-final_pos.z > self.pos.z:
+continue
-# We try heading up
+if border_func(cand):
-return Position(self.pos.x, self.pos.y, self.pos.z + 1)
+cur_pos = cand
-cur_dist = final_pos.dist(self.pos)
+break
-if cur_dist < 2:
+return None
-# We're right ontop of our target, so just go there
+path.append(cur_pos)
-return final_pos
+if end_func(cur_pos):
-# Find the cheapest spot close to us that moves us closer to the target
+# is there an 8-NEIGHBOUR that also satisfies end_func and is
-neighbours = [Position(self.pos.x + x, self.pos.y + y, self.pos.z) for
+# closer to target
-x in range(-1, 2) for y in range(-1, 2) if (x, y) != (0, 0)]
+dist = self.target.dist(cur_pos)
-best_pos = self.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_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 point in self._last_steps:
-if dist < cur_dist:
+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)
+if self._is_fence(best):
-min_cost = self._cost_path(direct_path)
+path = self._find_fence_gap()
-min_path = direct_path
+elif min_cost == 30:
-# is there a point nearby that gives us a cheaper direct path?
+# building
-# This is delibrately not finding the optimal path, as I don't
+path = self._find_nearest_corner()
-# want the foxes to be too intelligent, although the implementation
+else:
-# isn't well optimised yet
+# We're looping
-# FIXME: Currently, this introduces loops, but the memory kind
+self._last_steps = []
-# 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]
-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
 return self.pos
-return self._find_best_path_step(self.landmarks[-1])
+if path:
+self.path = path[1:] # exclude 1st step
-def _select_target(self):
+return path[0]
+return best
+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
+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_prey(self):
 min_dist = 999
 self.closest = None
 for chicken in self.gameboard.chickens:
 dist = chicken.pos.dist(self.pos)
 if chicken.abode:
 if len(chicken.weapons()) > 0:
 dist += 5 # Prefer unarmed chickens
 if dist < min_dist:
 min_dist = dist
 self.closest = chicken
+self.target = chicken.pos
-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()
 if not self.closest:
 # No more chickens, so leave
 self.hunting = False
+self.target = self.start_pos
 return self.pos
-if self.closest.pos == self.pos:
-# No need to move
-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"""
 chicken = self.gameboard.get_animal_at_pos(self.pos, 'chicken')
 if chicken:
 def _catch_chicken(self, chicken):
 """Catch a chicken"""
 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)
+moves = [self.pos + step for step in NEIGHBOUR_8]
-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]
 # find the cheapest point in moves that's not blocked
 final_pos = None
 min_cost = 1000
 for poss in moves:
 if self.gameboard.get_animal_at_pos(poss, 'fox'):
 # Add some randomness in this case
 final_pos = poss
 if not final_pos:
 # No good choice, so stay put
 return self.pos
-if self.gameboard.in_bounds(final_pos):
+if self._is_fence(final_pos) and not self.dig_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:
 return self._dig(final_pos)
-self.last_steps.append(final_pos)
+self._last_steps.append(final_pos)
-if len(self.last_steps) > 3:
+if len(self._last_steps) > 6:
-self.last_steps.pop(0)
+self._last_steps.pop(0)
 return final_pos
 def _dig(self, dig_pos):
 """Setup dig parameters, to be overridden if needed"""
 self.tick = 5
 self.tick -= 1
 # We're still digging through the fence
 # 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 not self._is_fence(self.dig_pos):
-if tiles.TILE_MAP[this_tile] != 'fence':
 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
 change_visible = False
 # See if we're entering/leaving a building
 chicken.damage()
 self.closest = None
 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"""
 STEALTH = 80
 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
 for chicken in self.gameboard.chickens:
 dist = chicken.pos.dist(self.pos)
 if not chicken.eggs:
 dist += 100 # The closest eggs have to be *far* away to be safe
 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"""
 return dig_pos

Mercurial > rinkhals

comparison gamelib/animal.py @ 507:d3ceb9e9c48e