from collections import namedtuple
from queue import PriorityQueue
[docs]
class BattleMap:
"""
A representation of the battlemap on the table. Used for movement, range, etc.
"""
invalid_point_errorMsg = "Points on a grid must have integers for x and y coordinates"
Point = namedtuple('Point', ['x', 'y'])
# f is total cost of the node
# g is distance between the current node and the start node
# h is heuristic (estimated distance from current node to end node)
PointWithDistance = namedtuple('PointWithDistance', ['x', 'y', 'f', 'g', 'h'])
def __init__(self, **kwargs):
"""
Validate the input and set the instance variables
:param kwargs: keyword arguments. Valid arguments are as follows:
:param x_min: the leftmost x coordinate
:type x_size: int
:param x_max: the rightmost x coordinate
:type x_size: int
:param y_min: the bottommost y coordinate
:type y_min: int
:param y_max: the topmost y coordinate
:type y_max: int
:param square_size: the size (in feet) of one square on the grid
:type square_size: int
:param dark_info: information about which squares are dark. keys for normal and magical
:type dark_info: dict
:param non_traversable_terrain: information about which squares cannot be passed through by anybody
:type non_traversable_terrain: set
:param difficult_terrain: information about which squares are difficult terrain
:type difficult_terrain: set
:param swimmable_terrain: information about which squares can only be traversed by swimming
:type swimmable_terrain: set
:param damage_terrain_dict: information about which squares cause someone traveling through to take damage
:type damage_terrain: dict
:param occupied_terrain_dict: information about which squares are occupied (and by whom)
:type occupied_terrain_dict: dict
"""
dimensions = kwargs.get("dimensions", (0, 0, 0, 0))
if not isinstance(dimensions, tuple) and not isinstance(dimensions, list) or len(dimensions) != 4:
raise ValueError("dimensions must be provided as a tuple or list: [x_min, x_max, y_min, y_max]")
x_min = kwargs.get("x_min", dimensions[0])
if not isinstance(x_min, int):
raise ValueError("x_min must be an integer")
self._x_min = x_min
x_max = kwargs.get("x_max", dimensions[1])
if not isinstance(x_max, int):
raise ValueError("x_max must be an integer")
if x_max <= x_min:
raise ValueError("x_max must be greater than x_min")
self._x_max = x_max
y_min = kwargs.get("y_min", dimensions[2])
if not isinstance(y_min, int):
raise ValueError("y_min must be an integer")
self._y_min = y_min
y_max = kwargs.get("y_max", dimensions[3])
if not isinstance(y_max, int):
raise ValueError("y_max must be an integer")
if y_max <= y_min:
raise ValueError("y_max must be greater than y_min")
self._y_max = y_max
square_size = kwargs.get("square_size", 5) # default size is 5 feet
if not isinstance(square_size, int) or square_size < 5:
raise ValueError("square_size must be an integer >= 5")
self._square_size = square_size
dark_info = kwargs.get("dark_info")
if dark_info:
normal_dark = dark_info.get("normal")
if normal_dark:
BattleMap.validate_points(normal_dark)
self._normal_dark = normal_dark
else:
self._normal_dark = set()
magical_dark = dark_info.get("magical")
if magical_dark:
BattleMap.validate_points(magical_dark)
self._magical_dark = magical_dark
else:
self._magical_dark = set()
non_traversable_terrain = kwargs.get("non_traversable_terrain")
if non_traversable_terrain:
BattleMap.validate_points(non_traversable_terrain)
self._non_traversable_terrain = non_traversable_terrain
else:
self._non_traversable_terrain = set()
difficult_terrain = kwargs.get("difficult_terrain")
if difficult_terrain:
BattleMap.validate_points(difficult_terrain)
if self._non_traversable_terrain.intersection(difficult_terrain):
raise ValueError("Non-traversable terrain cannot be difficult terrain")
self._difficult_terrain = difficult_terrain
else:
self._difficult_terrain = set()
swimmable_terrain = kwargs.get("swimmable_terrain")
if swimmable_terrain:
BattleMap.validate_points(swimmable_terrain)
if self._non_traversable_terrain.intersection(swimmable_terrain):
raise ValueError("Non-traversable terrain cannot be swimmable terrain")
self._swimmable_terrain = swimmable_terrain
else:
self._swimmable_terrain = set()
damage_terrain_dict = kwargs.get("damage_terrain_dict")
if damage_terrain_dict:
if not isinstance(damage_terrain_dict, dict):
raise ValueError(
"damage_terrain_dict must be a dict mapping points "
"to an Attack for the damage dealt in those points")
for key in damage_terrain_dict:
if not isinstance(key, BattleMap.Point):
raise ValueError("damage_terrain_dict must be a dict mapping points "
"to an Attack for the damage dealt in those points")
try:
damage_terrain_dict[key].get_dpr(ac=10)
except AttributeError:
raise ValueError("values in damage_terrain_dict must be Attacks with a get_dpr method")
self._damage_terrain = damage_terrain_dict
else:
self._damage_terrain = {}
occupied_terrain_dict = kwargs.get("occupied_terrain_dict")
if occupied_terrain_dict:
if not isinstance(occupied_terrain_dict, dict):
raise ValueError("occupied_terrain_dict must be a dict mapping points to the combatants in those points")
for key in occupied_terrain_dict:
if not isinstance(key, BattleMap.Point):
raise ValueError("occupied_terrain_dict must be a dict mapping points to the "
"combatants in those points")
self._occupied_terrain = occupied_terrain_dict
else:
self._occupied_terrain = {}
[docs]
@staticmethod
def validate_point(point):
"""
Check that the given point is valid for use in this :py:class:`BattleMap`
:param point: the point to check
:raise: ValueError if the point is invalid
"""
if not isinstance(point, BattleMap.Point):
raise ValueError(BattleMap.invalid_point_errorMsg)
if not isinstance(point.x, int) or not isinstance(point, BattleMap.Point):
raise ValueError(BattleMap.invalid_point_errorMsg)
[docs]
@staticmethod
def validate_points(points: set):
"""
Check that all points in the list are valid for use in this :py:class:`BattleMap`
:param points: the list of points to check
:raise: ValueError if any of the points (or the points argument itself) is invalid
"""
if not isinstance(points, set):
raise ValueError("must provide points in a set")
for point in points:
BattleMap.validate_point(point)
[docs]
def get_square_size(self):
return self._square_size
[docs]
def get_light_source(self, point: Point):
if point in self._magical_dark:
return "magic"
if point in self._normal_dark:
return "dark"
return "normal"
[docs]
def set_normal_dark_point(self, point: Point):
"""
Add the given point to self._normal_dark. Does not change any magical darkness that might be present.
:param point: the `Point` to become dark
:return: None
"""
self._normal_dark.add(point)
[docs]
def set_magical_dark_point(self, point: Point):
"""
Add the given point to self._magical_dark. Does not change any normal darkness that might be present.
:param point: the `Point` to become dark
:return: None
"""
self._magical_dark.add(point)
[docs]
def dispel_normal_darkness(self, point: Point):
"""
Remove normal darkness from the given point. Does not change any magical darkness that might be present.
:param point: the `Point` to remove darkness from
:return: None
"""
if point in self._normal_dark:
self._normal_dark.remove(point)
[docs]
def dispel_magical_darkness(self, point: Point):
"""
Remove magical darkness from the given point. Does not change any normal darkness that might be present.
:param point: the `Point` to remove darkness from
:return: None
"""
if point in self._magical_dark:
self._magical_dark.remove(point)
[docs]
def dispel_all_darkness(self, point: Point):
"""
Remove all darkness (normal and magical) from the given point.
:param point: the `Point` to remove darkness from
:return: None
"""
self.dispel_normal_darkness(point)
self.dispel_magical_darkness(point)
[docs]
def is_in_bounds(self, point: Point):
return self._x_min <= point.x <= self._x_max \
and self._y_min <= point.y <= self._y_max
[docs]
def is_walkable(self, point: Point):
"""
:param point: the point to check
:return: True if the point is traversable and not swimmable, False otherwise
"""
return self.is_traversable(point) and point not in self._swimmable_terrain
[docs]
def is_swimmable(self, point: Point):
"""
:param point: the point to check
:return: True if the point is swimmable, False otherwise
"""
return self.is_traversable(point) and point in self._swimmable_terrain
[docs]
def is_traversable(self, point: Point):
"""
:param point: the point to check
:return: True if the point can be traveled through, False otherwise
"""
return point not in self._non_traversable_terrain and point not in self._occupied_terrain
[docs]
def get_dpr_for_point(self, point: Point, ac=10):
"""
Get the expected damage for entering the given point
:param point: the point to check
:param ac: the ac of the Combatant that will be entering the given point
:return: the expected damage
"""
if point not in self._damage_terrain:
return 0
return self._damage_terrain[point].get_dpr(ac=ac)
[docs]
def set_damage_for_point(self, point: Point, attack):
"""
Store the given point in self._damage_terrain
:param point: the Point to add damage for
:param attack: the attack to get dpr from. Replaces any previous attack that was stored for `point`
:return:
"""
try:
attack.get_dpr(ac=10)
except AttributeError:
raise ValueError("values in damage_terrain_dict must be Attacks with a get_dpr method")
self._damage_terrain[point] = attack
[docs]
def clear_damage_for_point(self, point):
"""
Remove the given point from self._damage_terrain, setting dpr back to 0
:param point: the point to clear damage for
:return:
"""
del self._damage_terrain[point]
[docs]
def get_occupant(self, point: Point):
"""
:param point: the point to check
:return: the occupant in the given point, or False if nobody is there
"""
return self._occupied_terrain.get(point, False)
[docs]
def set_occupant(self, point: Point, occupant):
"""
Put `occupant` in the given point. Note: if there was an occupant at `point`, they are replaced.
:param point: the point to occupy
:param occupant: the Combatant that will occupy the point
:return: None
"""
self._occupied_terrain[point] = occupant
[docs]
def get_neighbors(self, point: Point, distance=5):
"""
Get all points adjacent (orthogonal and diagonal) to `point` that are within the bounds of the map.
Note: if a neighbor would be out of bounds,
get the neighbor that would be within bounds (e.g., 5ft away instead of 10ft)
:param point: the point to get neighbors of
:param distance: how many feet away from `point` to look for neighbors
:return: a list of all adjacent, in-map neighbors
"""
square_distance = distance // self._square_size
min_val = -1 * square_distance
max_val = square_distance
x_min = max(point.x + min_val, self._x_min)
x_max = min(point.x + max_val, self._x_max)
y_min = max(point.y + min_val, self._y_min)
y_max = min(point.y + max_val, self._y_max)
neighbors = []
# make the top row
for x in range(x_min, x_max + 1):
new_point = BattleMap.Point(x, y_max)
if new_point == point:
continue
neighbors.append(new_point)
# make the right column
for y in range(y_max - 1, y_min - 1, -1):
new_point = BattleMap.Point(x_max, y)
if new_point == point:
continue
neighbors.append(new_point)
# make the bottom row
for x in range(x_max - 1, x_min - 1, -1):
new_point = BattleMap.Point(x, y_min)
if new_point == point:
continue
neighbors.append(new_point)
# make the left column
for y in range(y_min + 1, y_max):
new_point = BattleMap.Point(x_min, y)
if new_point == point:
continue
neighbors.append(new_point)
return neighbors
[docs]
def get_traversable_neighbors(self, point: Point):
"""
Get all points adjacent (orthogonal and diagonal) to `point` that are traversable and within the bounds of the map
:param point: the point to get neighbors of
:return: a list of all adjacent, in-map, traversable neighbors
"""
neighbors = self.get_neighbors(point)
return list(filter(self.is_traversable, neighbors))
[docs]
def get_distance_to_traverse(self, point: Point, can_ignore_difficult=False, can_ignore_swim=False):
"""
Calculate the distance to travel onto a given point, returning the distance and what type of movement is needed
:param point: the point to check
:param can_ignore_difficult: True if difficult terrain counts the same as normal
:param can_ignore_swim: True if swimming counts the same as normal
:return: a tuple with the movement speed to traverse the point and the movement type,
or False if the point is not traversable
"""
distance = self._square_size
movement_type = ""
if not self.is_traversable(point):
return False
if point in self._difficult_terrain and not can_ignore_difficult:
distance *= 2
elif point in self._swimmable_terrain:
movement_type = "swim"
if not can_ignore_swim:
distance *= 2
return distance, movement_type
[docs]
def get_heuristic_distance(self, start: Point, end: Point):
"""
Estimate the distance from a start point to an end point. Assumes diagonal moves are the same distance as
orthogonal (i.e., ignore the Pythagorean Theorem)
:param start: the point to start the search at
:param end: the point to end the search
:return: the calculated distance (in this case, maximum of x distance and y distance)
"""
x_dist = abs(start.x - end.x)
y_dist = abs(start.y - end.y)
return max(x_dist, y_dist) * self._square_size
[docs]
def find_path(self, start: Point, goal: Point, can_ignore_difficult=False, can_ignore_swim=False, ac=10):
# pylint: disable=too-many-arguments
"""
Find a path from source to dest using A star algorithm.
Could be overridden in a subclass to use a different algorithm.
Code taken from https://www.redblobgames.com/pathfinding/a-star/introduction.html
:param start: the starting point
:param goal: the ending point. Double-check that the goal is in bounds.
We don't check that the start is in bounds because that's not an expected use case.
:param can_ignore_difficult: True if difficult terrain counts the same as normal
:param can_ignore_swim: True if swimming counts the same as normal
:param ac: The AC of the Combatant that will be taking this path
:return: a dict with info about the path: path -> list of `Point`s,
distance -> int of total distance, swim_distance -> int of distance that requires swimming,
damage -> estimated damage taken
"""
if not self.is_in_bounds(goal):
return False
frontier = PriorityQueue()
frontier.put((0, start))
came_from = {start: None}
distance_so_far = {start: 0}
swim_distance_so_far = {start: 0}
# in 3d maps, other types of distance may be supported, such as Fly and Climb
damage_so_far = {start: 0}
while not frontier.empty():
current = frontier.get()[1] # get the point with the lowest heuristic value
if current == goal:
path = self.construct_path(current, came_from)
distance = distance_so_far[current]
swim_distance = swim_distance_so_far[current]
damage = damage_so_far[current]
return {
'path': path,
'distance': distance,
'swim_distance': swim_distance,
'damage': damage,
}
for neighbor in self.get_traversable_neighbors(current):
distance_to_neighbor = self.get_distance_to_traverse(neighbor, can_ignore_difficult, can_ignore_swim)
new_distance = distance_so_far[current] + distance_to_neighbor[0]
if neighbor not in distance_so_far or new_distance < distance_so_far[neighbor]:
distance_so_far[neighbor] = new_distance
new_swim_distance = swim_distance_so_far[current] + (
distance_to_neighbor[0] if distance_to_neighbor[1] == "swim" else 0)
swim_distance_so_far[neighbor] = new_swim_distance
new_damage = damage_so_far[current] + self.get_dpr_for_point(neighbor, ac=ac)
damage_so_far[neighbor] = new_damage
priority = new_distance + self.get_heuristic_distance(neighbor, goal)
frontier.put((priority, neighbor))
came_from[neighbor] = current
return False # no path was found
[docs]
@staticmethod
def construct_path(point: Point, came_from: dict):
"""
Construct the path found by A star algorithm
:param point: the end point of the path
:param came_from: a dictionary mapping each point to the point that came before it
:return: a list of points in order of the path, ending with `point`
"""
result = []
current = point
while came_from[current] is not None:
result.append(current)
current = came_from[current]
result.reverse()
return result