aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authornsensfel <SpamShield0@noot-noot.org>2019-05-14 17:38:27 +0200
committernsensfel <SpamShield0@noot-noot.org>2019-05-14 17:38:27 +0200
commitf3f09c301fdb1acf9fb7e77db92bfed3147ab215 (patch)
treeafb2430509cf7868c220be3c891b240cc3add727
parentbeceea45a9840c306f8db79d4d02db400bd6426c (diff)
downloadtacticians-client-f3f09c301fdb1acf9fb7e77db92bfed3147ab215.zip
tacticians-client-f3f09c301fdb1acf9fb7e77db92bfed3147ab215.tar.bz2
Updates Dijkstra's to avoid attacks of opportunity.
-rw-r--r--src/battle/src/Struct/Navigator.elm40
-rw-r--r--src/battle/src/Struct/Path.elm7
-rw-r--r--src/battle/src/Struct/RangeIndicator.elm264
-rw-r--r--src/battle/src/Update/SelectCharacter.elm2
-rw-r--r--src/battle/src/Update/UndoAction.elm2
-rw-r--r--src/shared/battle-map/BattleMap/Struct/Map.elm16
6 files changed, 190 insertions, 141 deletions
diff --git a/src/battle/src/Struct/Navigator.elm b/src/battle/src/Struct/Navigator.elm
index 5bf3c54..bfad3d2 100644
--- a/src/battle/src/Struct/Navigator.elm
+++ b/src/battle/src/Struct/Navigator.elm
@@ -34,26 +34,26 @@ import Struct.RangeIndicator
--------------------------------------------------------------------------------
type alias Type =
{
- starting_location: BattleMap.Struct.Location.Type,
- movement_dist: Int,
- defense_dist: Int,
- attack_dist: Int,
- path: Struct.Path.Type,
- locked_path: Bool,
- range_indicators:
+ starting_location : BattleMap.Struct.Location.Type,
+ movement_dist : Int,
+ defense_dist : Int,
+ attack_dist : Int,
+ path : Struct.Path.Type,
+ locked_path : Bool,
+ range_indicators :
(Dict.Dict
BattleMap.Struct.Location.Ref
Struct.RangeIndicator.Type
),
- cost_fun: (BattleMap.Struct.Location.Type -> Int)
+ tile_data_fun : (BattleMap.Struct.Location.Type -> (Int, Int))
}
type alias Summary =
{
- starting_location: BattleMap.Struct.Location.Type,
- path: (List BattleMap.Struct.Direction.Type),
- markers: (List (BattleMap.Struct.Location.Ref, Struct.Marker.Type)),
- locked_path: Bool
+ starting_location : BattleMap.Struct.Location.Type,
+ path : (List BattleMap.Struct.Direction.Type),
+ markers : (List (BattleMap.Struct.Location.Ref, Struct.Marker.Type)),
+ locked_path : Bool
}
--------------------------------------------------------------------------------
@@ -68,10 +68,10 @@ new : (
Int ->
Int ->
Int ->
- (BattleMap.Struct.Location.Type -> Int) ->
+ (BattleMap.Struct.Location.Type -> (Int, Int)) ->
Type
)
-new start_loc mov_dist def_dist atk_dist cost_fun =
+new start_loc mov_dist def_dist atk_dist tile_data_fun =
{
starting_location = start_loc,
movement_dist = mov_dist,
@@ -85,9 +85,9 @@ new start_loc mov_dist def_dist atk_dist cost_fun =
mov_dist
def_dist
atk_dist
- (cost_fun)
+ (tile_data_fun)
),
- cost_fun = cost_fun
+ tile_data_fun = tile_data_fun
}
get_current_location : Type -> BattleMap.Struct.Location.Type
@@ -157,7 +157,7 @@ lock_path navigator =
0
navigator.defense_dist
navigator.attack_dist
- (navigator.cost_fun)
+ (navigator.tile_data_fun)
),
locked_path = True
}
@@ -171,7 +171,7 @@ unlock_path navigator =
navigator.movement_dist
navigator.defense_dist
navigator.attack_dist
- (navigator.cost_fun)
+ (navigator.tile_data_fun)
),
locked_path = True
}
@@ -185,7 +185,7 @@ lock_path_with_new_attack_ranges range_min range_max navigator =
0
range_min
range_max
- (navigator.cost_fun)
+ (navigator.tile_data_fun)
),
locked_path = True
}
@@ -202,7 +202,7 @@ try_adding_step dir navigator =
else
case
(Struct.Path.try_following_direction
- (navigator.cost_fun)
+ (navigator.tile_data_fun)
(Just navigator.path)
dir
)
diff --git a/src/battle/src/Struct/Path.elm b/src/battle/src/Struct/Path.elm
index 33cc618..0ae3bdf 100644
--- a/src/battle/src/Struct/Path.elm
+++ b/src/battle/src/Struct/Path.elm
@@ -145,12 +145,12 @@ get_summary : Type -> (List BattleMap.Struct.Direction.Type)
get_summary path = path.previous_directions
try_following_direction : (
- (BattleMap.Struct.Location.Type -> Int) ->
+ (BattleMap.Struct.Location.Type -> (Int, Int)) ->
(Maybe Type) ->
BattleMap.Struct.Direction.Type ->
(Maybe Type)
)
-try_following_direction cost_fun maybe_path dir =
+try_following_direction tile_data_fun maybe_path dir =
case maybe_path of
(Just path) ->
let
@@ -159,7 +159,8 @@ try_following_direction cost_fun maybe_path dir =
dir
path.current_location
)
- next_location_cost = (cost_fun next_location)
+ (next_location_cost, next_location_battles) =
+ (tile_data_fun next_location)
in
if (next_location_cost <= Constants.Movement.max_points)
then
diff --git a/src/battle/src/Struct/RangeIndicator.elm b/src/battle/src/Struct/RangeIndicator.elm
index 5d960db..064e1fd 100644
--- a/src/battle/src/Struct/RangeIndicator.elm
+++ b/src/battle/src/Struct/RangeIndicator.elm
@@ -22,43 +22,51 @@ import Constants.Movement
--------------------------------------------------------------------------------
-- TYPES -----------------------------------------------------------------------
--------------------------------------------------------------------------------
+type alias TileData = (Int, Int) -- (TileCost, TileBattles)
+
+-- (TileLocation, TileRequiredBattles)
+type alias TileSearchLocation = (BattleMap.Struct.Location.Ref, Int)
+
type alias Type =
{
- distance: Int,
- true_range: Int,
- atk_range: Int,
- path: (List BattleMap.Struct.Direction.Type),
- marker: Struct.Marker.Type
+ distance : Int,
+ required_battles : Int,
+ taxicab_dist : Int,
+ atk_range : Int,
+ path : (List BattleMap.Struct.Direction.Type),
+ marker : Struct.Marker.Type
}
type alias SearchParameters =
{
- maximum_distance: Int,
- maximum_attack_range: Int,
- minimum_defense_range: Int,
- cost_function: (BattleMap.Struct.Location.Type -> Int),
- true_range_fun: (BattleMap.Struct.Location.Type -> Int)
+ maximum_distance : Int,
+ maximum_attack_range : Int,
+ minimum_defense_range : Int,
+ tile_data_function : (BattleMap.Struct.Location.Type -> (Int, Int)),
+ taxicab_dist_fun : (BattleMap.Struct.Location.Type -> Int)
}
type alias LocatedIndicator =
{
- location_ref: BattleMap.Struct.Location.Ref,
- indicator: Type
+ location_ref : BattleMap.Struct.Location.Ref,
+ required_battles : Int,
+ indicator : Type
}
--------------------------------------------------------------------------------
-- LOCAL -----------------------------------------------------------------------
--------------------------------------------------------------------------------
get_closest : (
Int ->
- BattleMap.Struct.Location.Ref ->
+ TileSearchLocation ->
Type ->
LocatedIndicator ->
LocatedIndicator
)
-get_closest max_dist ref indicator current_best =
+get_closest max_dist (ref, ignored_param) indicator current_best =
if (is_closer max_dist indicator current_best.indicator)
then
{
+ required_battles = indicator.required_battles,
location_ref = ref,
indicator = indicator
}
@@ -68,14 +76,14 @@ get_closest max_dist ref indicator current_best =
is_closer : Int -> Type -> Type -> Bool
is_closer max_dist candidate current =
(
- -- It's closer when moving
+ -- It's closer when moving;
(candidate.distance < current.distance)
||
- (
- -- Or neither are reachable by moving,
+ ( -- Or
+ -- neither are reachable by moving,
(max_dist <= candidate.distance)
&& (max_dist <= current.distance)
- -- but the new one is closer when attacking.
+ -- but the new one is closer when attacking;
&& (candidate.atk_range < current.atk_range)
)
)
@@ -89,16 +97,16 @@ generate_neighbor : (
)
generate_neighbor search_params neighbor_loc dir src_indicator =
let
- node_cost = (search_params.cost_function neighbor_loc)
+ (node_cost, node_battles) =
+ (search_params.tile_data_function neighbor_loc)
new_dist =
if (node_cost == Constants.Movement.cost_when_occupied_tile)
- then
- (search_params.maximum_distance + 1)
- else
- (src_indicator.distance + node_cost)
+ then (search_params.maximum_distance + 1)
+ else (src_indicator.distance + node_cost)
new_atk_range = (src_indicator.atk_range + 1)
- new_true_range = (search_params.true_range_fun neighbor_loc)
- can_defend = (new_true_range > search_params.minimum_defense_range)
+ new_taxicab_dist = (search_params.taxicab_dist_fun neighbor_loc)
+ new_battle_count = (src_indicator.required_battles + node_battles)
+ can_defend = (new_taxicab_dist > search_params.minimum_defense_range)
in
if (new_dist > search_params.maximum_distance)
then
@@ -106,8 +114,9 @@ generate_neighbor search_params neighbor_loc dir src_indicator =
node_cost,
{
distance = (search_params.maximum_distance + 1),
- atk_range = new_atk_range,
- true_range = new_true_range,
+ atk_range = (src_indicator.atk_range + 1),
+ taxicab_dist = new_taxicab_dist,
+ required_battles = new_battle_count,
path = (dir :: src_indicator.path),
marker =
if (can_defend)
@@ -123,7 +132,8 @@ generate_neighbor search_params neighbor_loc dir src_indicator =
{
distance = new_dist,
atk_range = 0,
- true_range = new_true_range,
+ required_battles = new_battle_count,
+ taxicab_dist = new_taxicab_dist,
path = (dir :: src_indicator.path),
marker =
if (can_defend)
@@ -149,82 +159,93 @@ candidate_is_an_improvement : (
SearchParameters ->
BattleMap.Struct.Location.Ref ->
Type ->
- (Dict.Dict BattleMap.Struct.Location.Ref Type) ->
+ (Dict.Dict TileSearchLocation Type) ->
+ (Dict.Dict TileSearchLocation Type) ->
Bool
)
-candidate_is_an_improvement search_params loc_ref candidate alternatives =
- case (Dict.get loc_ref alternatives) of
- (Just alternative) ->
- (is_closer search_params.maximum_distance candidate alternative)
+candidate_is_an_improvement
+ search_params
+ loc_ref
+ candidate
+ candidate_solutions
+ best_solutions =
+ (List.all
+ -- Does it improve on all possible solutions that have less (or as much)
+ -- battles?
+ (\req_battles ->
+ let index = (loc_ref, req_battles) in
+ case (Dict.get index candidate_solutions) of
+ (Just alternative) ->
+ (is_closer
+ search_params.maximum_distance
+ candidate
+ alternative
+ )
- Nothing ->
- True
+ Nothing ->
+ case (Dict.get index best_solutions) of
+ (Just alternative) ->
+ (is_closer
+ search_params.maximum_distance
+ candidate
+ alternative
+ )
+
+ Nothing -> True
+ )
+ (List.range 0 candidate.required_battles)
+ )
handle_neighbors : (
LocatedIndicator ->
- (Dict.Dict BattleMap.Struct.Location.Ref Type) ->
+ (Dict.Dict TileSearchLocation Type) ->
SearchParameters ->
BattleMap.Struct.Direction.Type ->
- (Dict.Dict BattleMap.Struct.Location.Ref Type) ->
- (Dict.Dict BattleMap.Struct.Location.Ref Type)
+ (Dict.Dict TileSearchLocation Type) ->
+ (Dict.Dict TileSearchLocation Type)
)
handle_neighbors src results search_params dir remaining =
let
src_loc = (BattleMap.Struct.Location.from_ref src.location_ref)
neighbor_loc = (BattleMap.Struct.Location.neighbor dir src_loc)
neighbor_loc_ref = (BattleMap.Struct.Location.get_ref neighbor_loc)
+ (candidate_cost, candidate) =
+ (generate_neighbor search_params neighbor_loc dir src.indicator)
+ candidate_index = (neighbor_loc_ref, candidate.required_battles)
in
- case (Dict.get neighbor_loc_ref results) of
- (Just _) ->
- -- A minimal path for this location has already been found
+ if
+ (
+ (candidate_is_acceptable search_params candidate_cost candidate)
+ &&
+ (candidate_is_an_improvement
+ search_params
+ neighbor_loc_ref
+ candidate
remaining
-
- Nothing ->
- let
- (candidate_cost, candidate) =
- (generate_neighbor
- search_params
- neighbor_loc
- dir
- src.indicator
- )
- in
- if
- (
- (candidate_is_acceptable
- search_params
- candidate_cost
- candidate
- )
- &&
- (candidate_is_an_improvement
- search_params
- neighbor_loc_ref
- candidate
- remaining
- )
- )
- then
- (Dict.insert neighbor_loc_ref candidate remaining)
- else
- remaining
+ results
+ )
+ )
+ then (Dict.insert candidate_index candidate remaining)
+ else remaining
find_closest_in : (
SearchParameters ->
- (Dict.Dict BattleMap.Struct.Location.Ref Type) ->
+ (Dict.Dict TileSearchLocation Type) ->
LocatedIndicator
)
find_closest_in search_params remaining =
(Dict.foldl
(get_closest search_params.maximum_distance)
{
+ required_battles = 9999,
location_ref = (-1, -1),
indicator =
{
+ required_battles = 9999,
distance = Constants.Movement.cost_when_out_of_bounds,
path = [],
atk_range = Constants.Movement.cost_when_out_of_bounds,
- true_range = Constants.Movement.cost_when_out_of_bounds,
+ taxicab_dist = Constants.Movement.cost_when_out_of_bounds,
marker = Struct.Marker.CanAttackCanDefend
}
}
@@ -238,7 +259,7 @@ resolve_marker_type search_params indicator =
case
(
(indicator.atk_range > 0),
- (indicator.true_range <= search_params.minimum_defense_range)
+ (indicator.taxicab_dist <= search_params.minimum_defense_range)
)
of
(True, True) -> Struct.Marker.CanAttackCantDefend
@@ -249,31 +270,30 @@ resolve_marker_type search_params indicator =
insert_in_dictionary : (
LocatedIndicator ->
- (Dict.Dict BattleMap.Struct.Location.Ref Type) ->
- (Dict.Dict BattleMap.Struct.Location.Ref Type)
+ (Dict.Dict TileSearchLocation Type) ->
+ (Dict.Dict TileSearchLocation Type)
)
insert_in_dictionary located_indicator dict =
(Dict.insert
- located_indicator.location_ref
+ (located_indicator.location_ref, located_indicator.required_battles)
located_indicator.indicator
dict
)
search : (
- (Dict.Dict BattleMap.Struct.Location.Ref Type) ->
- (Dict.Dict BattleMap.Struct.Location.Ref Type) ->
+ (Dict.Dict TileSearchLocation Type) ->
+ (Dict.Dict TileSearchLocation Type) ->
SearchParameters ->
- (Dict.Dict BattleMap.Struct.Location.Ref Type)
+ (Dict.Dict TileSearchLocation Type)
)
search result remaining search_params =
if (Dict.isEmpty remaining)
- then
- result
+ then result
else
let
closest_located_indicator = (find_closest_in search_params remaining)
finalized_clos_loc_ind =
- {closest_located_indicator|
+ {closest_located_indicator |
indicator =
(resolve_marker_type
search_params
@@ -289,7 +309,13 @@ search result remaining search_params =
result
search_params
)
- (Dict.remove finalized_clos_loc_ind.location_ref remaining)
+ (Dict.remove
+ (
+ finalized_clos_loc_ind.location_ref,
+ finalized_clos_loc_ind.required_battles
+ )
+ remaining
+ )
[
BattleMap.Struct.Direction.Left,
BattleMap.Struct.Direction.Right,
@@ -300,6 +326,25 @@ search result remaining search_params =
search_params
)
+cleanup : (
+ (Dict.Dict TileSearchLocation Type) ->
+ (Dict.Dict BattleMap.Struct.Location.Ref Type)
+ )
+cleanup search_results =
+ (Dict.foldl
+ (\
+ (candidate_location, candidate_battles) candidate result ->
+ case (Dict.get candidate_location result) of
+ (Just current_best) ->
+ if (current_best.required_battles < candidate_battles)
+ then result
+ else (Dict.insert candidate_location candidate result)
+
+ Nothing -> (Dict.insert candidate_location candidate result)
+ )
+ (Dict.empty)
+ search_results
+ )
--------------------------------------------------------------------------------
-- EXPORTED --------------------------------------------------------------------
--------------------------------------------------------------------------------
@@ -308,35 +353,38 @@ generate : (
Int ->
Int ->
Int ->
- (BattleMap.Struct.Location.Type -> Int) ->
+ (BattleMap.Struct.Location.Type -> (Int, Int)) ->
(Dict.Dict BattleMap.Struct.Location.Ref Type)
)
-generate location max_dist def_range atk_range cost_fun =
- (search
- Dict.empty
- (Dict.insert
- (BattleMap.Struct.Location.get_ref location)
+generate location max_dist def_range atk_range tile_data_fun =
+ (cleanup
+ (search
+ Dict.empty
+ (Dict.insert
+ ((BattleMap.Struct.Location.get_ref location), 0)
+ {
+ distance = 0,
+ path = [],
+ atk_range = 0,
+ taxicab_dist = 0,
+ required_battles = 0,
+ marker =
+ if (def_range == 0)
+ then
+ Struct.Marker.CanGoToCanDefend
+ else
+ Struct.Marker.CanGoToCantDefend
+ }
+ Dict.empty
+ )
{
- distance = 0,
- path = [],
- atk_range = 0,
- true_range = 0,
- marker =
- if (def_range == 0)
- then
- Struct.Marker.CanGoToCanDefend
- else
- Struct.Marker.CanGoToCantDefend
+ maximum_distance = max_dist,
+ maximum_attack_range = atk_range,
+ minimum_defense_range = def_range,
+ tile_data_function = (tile_data_fun),
+ taxicab_dist_fun = (BattleMap.Struct.Location.dist location)
}
- Dict.empty
)
- {
- maximum_distance = max_dist,
- maximum_attack_range = atk_range,
- minimum_defense_range = def_range,
- cost_function = (cost_fun),
- true_range_fun = (BattleMap.Struct.Location.dist location)
- }
)
get_marker : Type -> Struct.Marker.Type
diff --git a/src/battle/src/Update/SelectCharacter.elm b/src/battle/src/Update/SelectCharacter.elm
index f26e3b8..8817797 100644
--- a/src/battle/src/Update/SelectCharacter.elm
+++ b/src/battle/src/Update/SelectCharacter.elm
@@ -47,7 +47,7 @@ get_character_navigator model char =
)
(BattleCharacters.Struct.Weapon.get_defense_range weapon)
(BattleCharacters.Struct.Weapon.get_attack_range weapon)
- (BattleMap.Struct.Map.get_movement_cost_function
+ (BattleMap.Struct.Map.get_tile_data_function
model.map
(List.map
(Struct.Character.get_location)
diff --git a/src/battle/src/Update/UndoAction.elm b/src/battle/src/Update/UndoAction.elm
index 85fb6c2..23c9e89 100644
--- a/src/battle/src/Update/UndoAction.elm
+++ b/src/battle/src/Update/UndoAction.elm
@@ -40,7 +40,7 @@ get_character_navigator model char =
)
(BattleCharacters.Struct.Weapon.get_defense_range weapon)
(BattleCharacters.Struct.Weapon.get_attack_range weapon)
- (BattleMap.Struct.Map.get_movement_cost_function
+ (BattleMap.Struct.Map.get_tile_data_function
model.map
(List.map
(Struct.Character.get_location)
diff --git a/src/shared/battle-map/BattleMap/Struct/Map.elm b/src/shared/battle-map/BattleMap/Struct/Map.elm
index fb3f8fb..31333f8 100644
--- a/src/shared/battle-map/BattleMap/Struct/Map.elm
+++ b/src/shared/battle-map/BattleMap/Struct/Map.elm
@@ -6,7 +6,7 @@ module BattleMap.Struct.Map exposing
get_height,
get_markers,
set_markers,
- get_movement_cost_function,
+ get_tile_data_function,
get_omnimods_at,
get_tiles,
get_width,
@@ -179,22 +179,22 @@ decoder =
(Json.Decode.field "w" Json.Decode.int)
)
-get_movement_cost_function : (
+get_tile_data_function : (
Type ->
(List BattleMap.Struct.Location.Type) ->
BattleMap.Struct.Location.Type ->
BattleMap.Struct.Location.Type ->
- Int
+ (Int, Int)
)
-get_movement_cost_function bmap occupied_tiles start_loc loc =
+get_tile_data_function bmap occupied_tiles start_loc loc =
if (has_location loc bmap)
then
case (Array.get (location_to_index loc bmap) bmap.content) of
(Just tile) ->
if ((loc /= start_loc) && (List.member loc occupied_tiles))
- then Constants.Movement.cost_when_occupied_tile
- else (BattleMap.Struct.TileInstance.get_cost tile)
+ then (Constants.Movement.cost_when_occupied_tile, 0)
+ else ((BattleMap.Struct.TileInstance.get_cost tile), 0)
- Nothing -> Constants.Movement.cost_when_out_of_bounds
+ Nothing -> (Constants.Movement.cost_when_out_of_bounds, 0)
else
- Constants.Movement.cost_when_out_of_bounds
+ (Constants.Movement.cost_when_out_of_bounds, 0)