Return to repo list

heart-of-gold

Tactical RPG written in python, using pygame.
Return to HMagellan.com

commit 1ab179b32ef82b635bbc5598012658d0379bb643
parent 59f9ee1172e4954d6e12fee3415d3ad729ce713d
Author: Erik Letson <hmagellan@hmagellan.com>
Date:   Tue, 27 Oct 2020 00:11:52 -0500

Implemented Dijkstras algo to find moves

Diffstat:
Mdata/json/stats/jisella_1.json | 2+-
Mdata/map/testmap1.tmx | 6+++---
Msrc/board.py | 129++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-------
Msrc/manager.py | 10----------
4 files changed, 122 insertions(+), 25 deletions(-)

diff --git a/data/json/stats/jisella_1.json b/data/json/stats/jisella_1.json @@ -15,7 +15,7 @@ "INT_GR" : 90, "WIS" : 30, "WIS_GR" : 90, - "MOVE" : 5, + "MOVE" : 4, "CRIT" : 10, "SKIL" : 4, "RANK" : 1, diff --git a/data/map/testmap1.tmx b/data/map/testmap1.tmx @@ -1,5 +1,5 @@ <?xml version="1.0" encoding="UTF-8"?> -<map version="1.4" tiledversion="1.4.1" orientation="orthogonal" renderorder="right-down" width="18" height="18" tilewidth="64" tileheight="64" infinite="0" nextlayerid="3" nextobjectid="1"> +<map version="1.2" tiledversion="1.3.2" orientation="orthogonal" renderorder="right-down" compressionlevel="0" width="18" height="18" tilewidth="64" tileheight="64" infinite="0" nextlayerid="3" nextobjectid="1"> <tileset firstgid="1" source="tsx/testtiles1.tsx"/> <layer id="1" name="BaseTileLayer" width="18" height="18"> <data encoding="csv"> @@ -11,8 +11,8 @@ 1,1,1,1,1,1,2,2,2,2,3,4,4,4,4,4,4,4, 1,1,1,1,1,1,1,2,2,2,3,3,4,4,4,4,4,4, 1,1,1,1,1,1,1,2,2,2,2,3,3,4,4,4,4,4, -1,1,1,1,1,1,1,1,2,2,2,2,3,3,4,4,4,4, -1,1,1,1,1,1,1,1,1,2,2,2,2,3,3,4,4,4, +1,1,1,1,1,1,4,1,2,2,4,2,3,3,4,4,4,4, +1,1,1,1,1,1,1,1,4,4,2,2,2,3,3,4,4,4, 1,1,1,1,1,1,1,1,1,1,2,2,2,2,3,3,4,4, 2,2,1,1,1,1,1,1,1,1,1,2,2,2,2,3,3,4, 3,3,2,1,1,1,1,1,1,1,1,1,2,2,2,2,3,4, diff --git a/src/board.py b/src/board.py @@ -1,4 +1,4 @@ -import pygame, pytmx, os +import pygame, pytmx, os, queue from . import manager, vgo from .constants import BOARD_PATH @@ -11,6 +11,7 @@ from .constants import BOARD_PATH # to frame-by-frame board interaction. This file should not require # so much refactoring as vgo.py to bring the new implementation of # managers into compliance here. +# 2. Moving an active entity should be a BoardManager thing. # This file contains: # 1. The BoardManager class, which manages boards and swaps between them @@ -37,6 +38,11 @@ class BoardManager(manager.Manager): self.current_board = None self.loaded_boards = {} self.board_overlay = pygame.sprite.LayeredDirty() + + # Move values + self.moving_entity = None + self.move_targets = {} # Keys = (x, y) of tiles, vals are a list of (x, y) tuples representing the path to be taken + self.chosen_move = [] # The move to actually exectute def load_board_from_file(self, boardfile): """ @@ -112,16 +118,117 @@ class BoardManager(manager.Manager): self.load_overlay() # Next, if there are some extant tile_pos moves listed, display them - if tile_pos_list != None: - for layer in self.current_board.tmx_data.visible_layers: - if isinstance(layer, pytmx.TiledTileLayer): - for x, y, gid in layer: - for p in tile_pos_list: - if p == (x, y) and self.current_board.tmx_data.get_tile_properties_by_gid(gid)["Passable"] == 1 and self.game.entity_manager.selected_entity.tile_pos != (x, y): - v = vgo.VisibleGameObject(self.game.sheet_manager.loaded_sheets["board_overlays_1"], (1, 0)) - v.set_position((x * self.current_board.tmx_data.tilewidth, y * self.current_board.tmx_data.tileheight)) - v.custom_flags = ("OverlayMove", (x, y)) - self.board_overlay.add(v) + #if tile_pos_list != None: + # for layer in self.current_board.tmx_data.visible_layers: + # if isinstance(layer, pytmx.TiledTileLayer): + # for x, y, gid in layer: + # for p in tile_pos_list: + # if p == (x, y) and self.current_board.tmx_data.get_tile_properties_by_gid(gid)["Passable"] == 1 and self.game.entity_manager.selected_entity.tile_pos != (x, y): + # v = vgo.VisibleGameObject(self.game.sheet_manager.loaded_sheets["board_overlays_1"], (1, 0)) + # v.set_position((x * self.current_board.tmx_data.tilewidth, y * self.current_board.tmx_data.tileheight)) + # v.custom_flags = ("OverlayMove", (x, y)) + # self.board_overlay.add(v) + + # TEMP!!!! + self.create_move_range(self.game.entity_manager.selected_entity) + for t in self.move_targets: + v = vgo.VisibleGameObject(self.game.sheet_manager.loaded_sheets["board_overlays_1"], (1, 0)) + v.set_position((t[0] * self.current_board.tmx_data.tilewidth, t[1] * self.current_board.tmx_data.tileheight)) + v.custom_flags = ("OverlayMove", t) + self.board_overlay.add(v) + + def create_move_range(self, entity): + """ + Create a legal move range for the given entity + and set that entity as the moving entity. This + is mostly a subtractive process. + """ + # Setup + self.empty_move_range() + movemax = entity.unit.active_stats["MOVE"] + mx = 0 + my = 0 + distances = {} + adj_list = {} + #visited = {} # NOTE: Ignoring visited nodes seems to break it + pq = queue.PriorityQueue() + index = -1 + min_val = -1 + new_dist = 0 + + # First, enumerate all tile positions in the legal move range + # except those that are impassable + for layer in self.current_board.tmx_data.visible_layers: + if isinstance(layer, pytmx.TiledTileLayer): + for x, y, gid in layer: + mx = entity.tile_pos[0] - x + my = entity.tile_pos[1] - y + if (abs(mx) + abs(my)) <= movemax and self.current_board.tmx_data.get_tile_properties_by_gid(gid)["Passable"] == 1: + distances[(x, y)] = movemax + 1 # So we are always greater than the max move + + # Next, calculate the move from the starting pos to each potential + # This implements Dijkstra's algorithm (kinda) + distances[entity.tile_pos] = 0 + adj_list = self.get_adjacency_list(list(distances.keys())) + #visited = { d : False for d in distances } + pq.put((entity.tile_pos, 0)) + + while not pq.empty(): + index, min_val = pq.get() + #visited[index] = True + + if distances[index] >= min_val: + for n in adj_list[index]: + #if adj_list[index][n] in visited.keys() and not visited[adj_list[index][n]]: + if adj_list[index][n] in distances.keys(): + new_dist = distances[index] + 1 + if new_dist < distances[adj_list[index][n]]: + distances[adj_list[index][n]] = new_dist + pq.put((adj_list[index][n], new_dist)) + + # Next, remove all all potentials with path length > movemax + for ds in distances: + if distances[ds] <= movemax: + self.move_targets[ds] = distances[ds] + + def get_adjacent_tiles_by_tile_pos(self, tile_pos): + """ + Return cardinal adjacent tiles of the given tile_pos. + Return value is a dict, the values of which are either + (x, y) tuples or None if the adjacent is outside of the + bounds of the board. + """ + adj = {(-1, 0) : None, (1, 0) : None, (0, -1) : None, (0, 1): None} + mx = 0 + my = 0 + for x in range(0, self.current_board.tmx_data.width): + for y in range(0, self.current_board.tmx_data.height): + mx = tile_pos[0] - x + my = tile_pos[1] - y + if (mx, my) in adj.keys(): + adj[(mx, my)] = (x, y) + + return adj + + def get_adjacency_list(self, tiles): + """ + Return an adjaceny list of all the tiles included + in 'tiles'. Tiles should be a list or tuple. The + return value is a dict. + """ + adj_list = {} + for t in tiles: + adj_list[t] = self.get_adjacent_tiles_by_tile_pos(t) + return adj_list + + def empty_move_range(self): + """ + Reset to a default, non-moving state. + """ + self.moving_entity = None + self.move_targets = {} + self.chosen_move = [] + self.load_overlay() def update_board(self, surface = None): """ diff --git a/src/manager.py b/src/manager.py @@ -12,16 +12,6 @@ from .constants import * # managers could be called together as a group to update in game, and could possibly be stored in a dict rather than have individual attributes # they are associated with (would be very useful if implementing the ManagerBus() object). # 3. Support for a ManagerBus() object (details pending, refer to main.py) -# 4. A generic "trigger_effects(self, effect_list)" method. This would implement a regularized form of the methods already present in SceneManager -# and MenuManager. It would rely on a regular style of effect-encoding in JSONs, but that already exists in the codebase and so far seems general -# enough for all possible extensions in this game. The "trigger_effects" could be extended by calling super() and then extending as needed in the -# new object. One detail that would have to ironed out is that all effects would have to have a unified unique naming structure across all JSONs -# and managers (nearly there already, minor detail not really a problem). Perhaps there should be an enum for the effects that should be common -# across all managers? Additional single-manager-specific effects could be added as an attribute enum of the given manager at init and the extended -# version of "trigger_effects()" could search this other enum instead of the universal one defined in constants.py. Also, a manager should have a -# "effectual" bool value and associated setgets that determines whether or not it even checks for effects under any circumstances (this should -# be subordinate to "activated" and dependent on the latter to function). This means that effect-checking should probably be a regular part of the -# update loop rather that specifically called for by objects themselves (this is ambiguous right now). # 5. Perhaps a generic "load_json" function that could be extended? The base function could store the JSON in a dict in the manager object, keyed by # file name. Extensions could be added for specific JSON fields/local values. This may not be possible, however, need to investigate...