Game::DijkstraMap - a numeric grid of weights plus some related functions
use Game::DijkstraMap; my $dm = Game::DijkstraMap->new; # x is where the player is (the goal) and the rest are # considered as walls or floor tiles (see the costfn) my $level = Game::DijkstraMap->str2map(<<'EOM'); ######### #.h.....# #.#####'# #.#.###x# ######### EOM # setup the dijkstra map $dm->map($level); # or, the above can be condensed down to use Game::DijkstraMap; my $dm = Game::DijkstraMap->new( str2map => <<'EOM' ); ... EOM # path finding is now possible $dm->next( 1, 2 ); # [[1,3], 6] $dm->next( 1, 6 ); # [[1,7], 2], [[2,7], 1] $dm->next_sq( 1, 6 ); # [[1,7], 2] $dm->next_best( 1, 6 ); # 2,7 $dm->path_best( 1, 1 ); $dm->next_m('next_sq'); $dm->next_best( 1, 6 ); # 1,7 $dm->path_best( 1, 1 ); # change the open door ' to a closed one $dm->update( [ 2, 7, -1 ] ); $dm->recalc; $dm->next( 1, 7 ); # nowhere better to move to $dm->unconnected; # [[3,3]]
This module implements code described by "The Incredible Power of Dijkstra Maps" article. Such maps have various uses in roguelikes or other games. This implementation may not be fast but should allow quick prototyping of map-building and path-finding exercises.
http://www.roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps
The "CONSIDERATIONS" section describes what this module does in more detail.
The new method accepts the "ATTRIBUTES" in the usual Moo fashion. Additionally map xor str2map parameters may be passed to reduce object construction verbosity:
# these are equivalent Game::DijkstraMap->new->map( Game::DijkstraMap->str2map($level) ) Game::DijkstraMap->new( str2map => $level )
Cost for non-goal non-wall points. A large number by default. These points are reduced to appropriate weights (steps from the nearest goal point) by normalize_costs which is called by map or recalc.
Cost for points that are goals (there can be one or more goals on a grid). Zero by default.
Cost for cells through which motion is illegal (walls, typically, though a map for cats may also treat water as impassable). -1 by default, and ignored when updating the map. This value for optimization purposes is assumed to be lower than min_cost.
-1
A code reference called with the object and each cell of the map passed to map. This function must convert the contents of the cell into suitable cost numbers for the Dijkstra Map. Defaults to a function that assigns bad_cost to # (walls), min_cost to x (goals), and otherwise max_cost for what is assumed to be floor tiles.
#
x
If the map is instead a grid of objects, there may need to be a suitable method call in those objects that returns the cost of what the cell contains that a custom costfn then calls.
The Dijkstra Map, presently an array reference of array references of integer values. Do not change this reference unless you know what you are doing. It can also be assigned to directly, for better or worse.
Most method calls will fail if this is not set; be sure to load a level map first with the map method (or manually).
This is set after the map and recalc method calls and indicates how many iterations it took normalize_costs to stabilize the map.
A string used by various next_* methods to use as a method to find adjacent squares to move to, next by default (which allows for diagonal motions) but could instead be next_sq.
next
next_sq
These methods will throw exceptions if something goes awry (especially when given known bad input, or when dimap has not been set).
Constructs and returns a new dimap data structure ideally in combination with one or more other Dijkstra Map objects. Cells will be marked as bad_cost if any object lists that for the cell; otherwise the new values will be a weighted combination of the values for each cell for each object. The param are the same as used by next_with.
Accepts a level map (an array reference of array references, or a 2D grid) and uses the costfn to convert the objects in that map to the internal Dijkstra Map that is held in the dimap attribute.
Returns the object so can be chained with other calls.
Returns the adjacent points with lower values than the given cell. Both square and diagonal moves are considered, unlike in normalize_costs. The return format is an array reference to a (possibly empty) list of array references in the form of [[row,col],value],... in no order that should be relied on.
[[row,col],value],...
"THE DREADED DIAGONAL" has a longer discussion of such moves.
Use by default by various other next_* methods, unless that is changed via the next_m attribute.
Uses the next_m method to return only the coordinate of a best move as an array reference (or undef if there is no such move). The coordinates are shuffled and then sorted by value to avoid bias from the order in which the adjacent coordinates are iterated over internally.
undef
Like next but only considers non-diagonal moves. May need to be set via the next_m attribute if various other next_* calls should only deal with non-diagonal motions.
Similar to next_best though considers all adjacent cells (via the next_m method) and for each cell calculates a weighted cost from the list of objs and weights provided in param and then returns the shuffled best cost from the result of those calculations. This allows the combination of multiple maps to determine the best move
$dm->next_with( 0, 0, { objs => [ $map1, $map2, ... ], weights => [ $w1, $w2, ... ], my_weight => $w } ),
though this may create local minimums a path cannot escape from or other problems, depending on how the maps combine. If no weights is provided for one or more of the objs those objs will be silently ignored. If no my_weight is provided the weights in the $dm map will be used as is.
$dm
See also dimap_with.
A custom version of this method may need to be written--this implementation will for example not leave a local minimum point.
Mostly an internal routine called by map or recalc that reduces cells as appropriate relative to min_cost cells. Changes the iters attribute. Note that this method has a square move bias and will not connect areas joined only by a diagonal; @ would not be able to reach the goal x in the following map:
@
###### #@.#x# #.##.# ##...# ######
The next method is able to walk diagonal paths but only where a adjacent square cell was available during normalize_costs.
Finds a best path to a goal via repeated calls to next or optionally some other method such as next_sq. Returns the path as an array reference of array references (a reference to a list of points).
Resets the weights of all non-wall non-goal cells and then calls normalize_costs. See below for a discussion of update and recalc.
Utility method that converts string maps to a form suitable to be passed to the map method. Without the optional split-with argument the string will be split into lines using $/.
$/
Utility method that converts the supplied array-of-arrays to tab-separated values or lacking that uses the internal dimap. Useful to study what dimap_with does in conjunction with the string version of the level map. max_cost may need to be lowered as ~0 can be needlessly large for small test maps.
~0
Returns an array reference to a (possibly empty) list of unconnected points, those that have no way to reach any of the goals. Only call this after map or if there have been updates recalc as otherwise the information will not be available or could be stale. All diagonal moves are considered legal for this calculation.
bad_cost cells (walls) are not considered unconnected, only open cells that after the dimap has been calculated still have max_cost assigned to them.
Updates the given row and column with the given value for each array reference passed. Does not recalculate the weights; see below for a longer discussion.
Returns the values for the given list of points.
Given the map where h represents a hound, @ our doomed yet somehow still optimistic hero, ' an open door, and so forth,
h
'
012345678 -+--------- turn 1 0|######### 1|#h......# 2|#.#####'# 3|#.#####@# 4|#########
A Dijkstra Map with the player as the only goal would be the following grid of integers that outline the corridor leading to the player
0 1 2 3 4 5 6 7 8 -+-------------------------- 0|-1|-1|-1|-1|-1|-1|-1|-1|-1 1|-1| 8| 7| 6| 5| 4| 3| 2|-1 2|-1| 9|-1|-1|-1|-1|-1| 1|-1 3|-1|10|-1|-1|-1|-1|-1| 0|-1 4|-1|-1|-1|-1|-1|-1|-1|-1|-1
which allows the hound to move towards the player by trotting down the positive integers, or to flee by going the other way. This map may need to be updated when the player moves or changes the map; for example the player could close the door:
######### turn 2 #..h....# #.#####+# #.#####@# #########
This change can be handled in various ways. A door may be as a wall to a hound, so updated to be one
$map->update( [ 2, 7, $map->bad_cost ] );
results in the map
0 1 2 3 4 5 6 7 8 -+-------------------------- 0|-1|-1|-1|-1|-1|-1|-1|-1|-1 1|-1| 8| 7| 6| 5| 4| 3| 2|-1 2|-1| 9|-1|-1|-1|-1|-1|-1|-1 3|-1|10|-1|-1|-1|-1|-1| 0|-1 4|-1|-1|-1|-1|-1|-1|-1|-1|-1
and a hound waiting outside the door, ready to spring (or maybe it gets bored and wanders off, depending on the monster AI and how much patience our hero has). The situation could also be handled by not updating the map and code outside of this module handling the hound/closed door interaction.
The recalc method may be necessary where due to the closed door there is a new and longer path around to the player that should be followed:
######### turn 2 (door was closed on turn 1) #....h..# #.#####+######### #.#####@........# #.#############.# #...............# ################# $map->update(...) # case 1 $map->update(...)->recalc; # case 2
Case 1 would have the hound move to the door while case 2 would instead cause the hound to move around the long way. If the door after case 2 is opened and only an update is done, the new shorter route would only be considered by monsters directly adjacent to the now open door (weight path 34, 1, 0 and also 33, 1, 0 if diagonal moves are permitted) and not those at 32, 31, etc. along the longer route; for those to see the change of the door another recalc would need to be done.
Treatment of diagonal moves varies. Brogue and POWDER by default deny the player the ability to move to the lower right cell
#### #..# #.@# ###.
while Angband or Dungeon Crawl Stone Soup allow the move. POWDER does not allow the player to move diagonally to the upper left cell (unless polymorphed) while all the others mentioned would. Also the best square to move to could be occupied by another monster, magically conjured flames, etc. This is why next and next_sq are fairly generic; next_best may not return an ideal move given other considerations.
In this module normalize_costs (like in Brogue, where the algorithm comes from) only considers square moves when calculating the costs so will not find solely diagonal paths that Andband or DCSS consider legal.
Please report any bugs or feature requests to bug-game-dijkstramap at rt.cpan.org, or through the web interface at http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Game-DijkstraMap.
bug-game-dijkstramap at rt.cpan.org
Patches might best be applied towards:
https://github.com/thrig/Game-DijkstraMap
New code that is not much battle-tested. Also a first implementation that suffers from hmm, how should this work? design.
normalize_costs is not very good with long and mostly unconnected corridors; this could be improved on by considering adjacent unseen cells after a cell changes in addition to full map iterations.
normalize_costs needs a version that supports counting costs along diagonals, not just square moves (and either costing diagonals as 1 or better yet sqrt(2)).
sqrt(2)
https://github.com/thrig/ministry-of-silly-vaults has example code that uses this module (and a Common LISP implementation that supports path finding in arbitrary (as limited by ARRAY-RANK-LIMIT (or available memory (or so forth))) dimensions).
Game::TextPatterns may help generate or modify data that can be then fed to this module.
There are various other graph and path finding modules on CPAN that may be more suitable to the task at hand.
thrig - Jeremy Mates (cpan:JMATES) <jmates at cpan.org>
<jmates at cpan.org>
Copyright (C) 2018 by Jeremy Mates
This program is distributed under the (Revised) BSD License: http://www.opensource.org/licenses/BSD-3-Clause
To install Game::DijkstraMap, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Game::DijkstraMap
CPAN shell
perl -MCPAN -e shell install Game::DijkstraMap
For more information on module installation, please visit the detailed CPAN module installation guide.