From 9ac7e8befde463275086945c1ed5399bb8ef3af0 Mon Sep 17 00:00:00 2001 From: Christian Heller Date: Wed, 16 Dec 2020 18:55:14 +0100 Subject: [PATCH] Use circle-out passes for DijkstraMap, refactor with FovMap code. --- plomrogue/mapping.py | 89 ++++++++++++++++++++++---------------------- plomrogue/things.py | 12 +++--- 2 files changed, 49 insertions(+), 52 deletions(-) diff --git a/plomrogue/mapping.py b/plomrogue/mapping.py index 7b7ad3c..29078d8 100644 --- a/plomrogue/mapping.py +++ b/plomrogue/mapping.py @@ -85,6 +85,10 @@ class MapGeometry(): x = big_yx.x * self.size.x + little_yx.x return YX(y, x) + def basic_circle_out_move(self, position, direction): + mover = getattr(self, 'move__' + direction) + return mover(position) + class MapGeometryWithLeftRightMoves(MapGeometry): @@ -98,10 +102,12 @@ class MapGeometryWithLeftRightMoves(MapGeometry): class MapGeometrySquare(MapGeometryWithLeftRightMoves): + circle_out_directions = (('DOWN', 'LEFT'), ('LEFT', 'UP'), + ('UP', 'RIGHT'), ('RIGHT', 'DOWN')) - def __init__(self, *args, **kwargs): - super().__init__(*args, **kwargs) - self.fov_map_class = FovMapSquare + def circle_out_move(self, yx, direction): + yx = self.basic_circle_out_move(yx, direction[0]) + return self.basic_circle_out_move(yx, direction[1]) def define_segment(self, source_center, radius): source_center = self.undouble_yxyx(*source_center) @@ -118,10 +124,11 @@ class MapGeometrySquare(MapGeometryWithLeftRightMoves): class MapGeometryHex(MapGeometryWithLeftRightMoves): + circle_out_directions = ('DOWNLEFT', 'LEFT', 'UPLEFT', + 'UPRIGHT', 'RIGHT', 'DOWNRIGHT') - def __init__(self, *args, **kwargs): - super().__init__(*args, **kwargs) - self.fov_map_class = FovMapHex + def circle_out_move(self, yx, direction): + return self.basic_circle_out_move(yx, direction) def define_segment(self, source_center, radius): source_center = self.undouble_yxyx(*source_center) @@ -251,7 +258,6 @@ class DijkstraMap(SourcedMap): def __init__(self, *args, **kwargs): # TODO: check potential optimizations: - # - do a first pass circling out from the center # - somehow ignore tiles that have the lowest possible value (we can # compare with a precalculated map for given starting position) # - check if Python offers more efficient data structures to use here @@ -259,18 +265,34 @@ class DijkstraMap(SourcedMap): super().__init__(*args, **kwargs) self.terrain = [255] * self.size_i self[self.center] = 0 + + def work_tile(position_i): + shrunk_test = False + if self.source_map_segment[position_i] in self.block_chars: + return shrunk_test + neighbors = self.geometry.get_neighbors_i(position_i) + for direction in [d for d in neighbors if neighbors[d]]: + j = neighbors[direction] + if self.terrain[j] < self.terrain[position_i] - 1: + self.terrain[position_i] = self.terrain[j] + 1 + shrunk_test = True + return shrunk_test + + # TODO: refactor with FovMap.circle_out() shrunk = True while shrunk: shrunk = False - for i in range(self.size_i): - if self.source_map_segment[i] in self.block_chars: - continue - neighbors = self.geometry.get_neighbors_i(i) - for direction in [d for d in neighbors if neighbors[d]]: - j = neighbors[direction] - if self.terrain[j] < self.terrain[i] - 1: - self.terrain[i] = self.terrain[j] + 1 - shrunk = True + yx = self.center + distance = 1 + while distance <= self.radius: + yx = self.geometry.basic_circle_out_move(yx, 'RIGHT') + for dir_i in range(len(self.geometry.circle_out_directions)): + for dir_progress in range(distance): + direction = self.geometry.circle_out_directions[dir_i] + yx = self.geometry.circle_out_move(yx, direction) + position_i = self.get_position_index(yx) + shrunk = True if work_tile(position_i) else shrunk + distance += 1 # print('DEBUG Dijkstra') # line_to_print = [] # x = 0 @@ -353,7 +375,8 @@ class FovMap(SourcedMap): if unmerged: self.shadow_cones += [cone] - step_size = (CIRCLE / len(self.circle_out_directions)) / distance_to_center + step_size = (CIRCLE / len(self.geometry.circle_out_directions))\ + / distance_to_center number_steps = dir_i * distance_to_center + dir_progress left_arm = correct_arm(step_size / 2 + step_size * number_steps) right_arm = correct_arm(left_arm + step_size) @@ -366,10 +389,6 @@ class FovMap(SourcedMap): else: eval_cone([left_arm, right_arm]) - def basic_circle_out_move(self, pos, direction): - mover = getattr(self.geometry, 'move__' + direction) - return mover(pos) - def circle_out(self, yx, f): # Optimization potential: Precalculate movement positions. # Optimization potential: Precalculate what tiles are shaded by what tile @@ -379,30 +398,10 @@ class FovMap(SourcedMap): distance = 1 yx = YX(yx.y, yx.x) while distance <= self.radius: - yx = self.basic_circle_out_move(yx, 'RIGHT') - for dir_i in range(len(self.circle_out_directions)): + yx = self.geometry.basic_circle_out_move(yx, 'RIGHT') + for dir_i in range(len(self.geometry.circle_out_directions)): for dir_progress in range(distance): - direction = self.circle_out_directions[dir_i] - yx = self.circle_out_move(yx, direction) + direction = self.geometry.circle_out_directions[dir_i] + yx = self.geometry.circle_out_move(yx, direction) f(yx, distance, dir_i, dir_progress) distance += 1 - - - - -class FovMapHex(FovMap): - circle_out_directions = ('DOWNLEFT', 'LEFT', 'UPLEFT', - 'UPRIGHT', 'RIGHT', 'DOWNRIGHT') - - def circle_out_move(self, yx, direction): - return self.basic_circle_out_move(yx, direction) - - - -class FovMapSquare(FovMap): - circle_out_directions = (('DOWN', 'LEFT'), ('LEFT', 'UP'), - ('UP', 'RIGHT'), ('RIGHT', 'DOWN')) - - def circle_out_move(self, yx, direction): - yx = self.basic_circle_out_move(yx, direction[0]) - return self.basic_circle_out_move(yx, direction[1]) diff --git a/plomrogue/things.py b/plomrogue/things.py index a3d622a..950a777 100644 --- a/plomrogue/things.py +++ b/plomrogue/things.py @@ -1,5 +1,5 @@ from plomrogue.errors import GameError, PlayError -from plomrogue.mapping import YX +from plomrogue.mapping import YX, FovMap from plomrogue.misc import quote import random @@ -210,12 +210,11 @@ class Thing_Bottle(Thing): all_players = [t for t in self.game.things if t.type_ == 'Player'] # TODO: refactor with ThingPlayer.prepare_multiprocessible_fov_stencil # and ThingPlayer.fov_test - fov_map_class = self.game.map_geometry.fov_map_class fov_radius = 12 light_blockers = self.game.get_light_blockers() obstacles = [t.position for t in self.game.things if t.blocks_light] - fov = fov_map_class(light_blockers, obstacles, self.game.maps, - self.position, fov_radius, self.game.get_map) + fov = FovMap(light_blockers, obstacles, self.game.maps, + self.position, fov_radius, self.game.get_map) fov.init_terrain() visible_players = [] for p in all_players: @@ -480,12 +479,11 @@ class ThingAnimate(Thing): self.task = self.get_next_task() def prepare_multiprocessible_fov_stencil(self): - fov_map_class = self.game.map_geometry.fov_map_class fov_radius = 3 if self.drunk > 0 else 12 light_blockers = self.game.get_light_blockers() obstacles = [t.position for t in self.game.things if t.blocks_light] - self._fov = fov_map_class(light_blockers, obstacles, self.game.maps, - self.position, fov_radius, self.game.get_map) + self._fov = FovMap(light_blockers, obstacles, self.game.maps, + self.position, fov_radius, self.game.get_map) def multiprocessible_fov_stencil(self): self._fov.init_terrain() -- 2.30.2