NAME

Game::DijkstraMap - a numeric grid of weights plus some related functions

SYNOPSIS

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]]

# custom costfn example -- search in the walls
$dm = Game::DijkstraMap->new(
    costfn => sub {
        my ( $self, $c ) = @_;
        if ( $c eq '#' ) { return $self->max_cost }
        return $self->bad_cost;
    }
);

DESCRIPTION

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 is not fast but should allow for 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.

CONSTRUCTOR

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 )

ATTRIBUTES

bad_cost

Cost for cells through which motion is illegal (walls, typically, though a map for cats may also treat water as impassable). INT_MIN by default (previously -1) and hopefully ignored when updating the map.

costfn

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.

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.

dimap

The Dijkstra Map, presently an array reference of array references of numeric 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 map first e.g. with map or str2map.

iters

This is set during the normalize, map, and recalc method calls and indicates how many iterations it took the normfn to stabilize the map.

max_cost

Cost for non-goal (min_cost) non-wall (bad_cost) cells. INT_MAX by default. These are reduced to appropriate weights (steps from the nearest goal point) by the normfn.

min_cost

Cost for points that are goals (there can be one or more goals on a grid). Zero by default.

next_m

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.

normfn

A code reference that is called by the normalize, map, and recalc methods to weight the Dijkstra Map as appropriate. The default norm_4way calculates weights using square or 4-way motion as seen in Brogue; other roguelikes will need an 8-way cost function if diagonal moves are in general permitted; this is possible with the norm_8way function:

Game::DijkstraMap->new(
    normfn  => \&Game::DijkstraMap::norm_8way,
    str2map => <<'EOM' );
...
EOM

METHODS

These methods will throw exceptions if something goes awry (especially when given known bad input, or when dimap has not been set).

clone

Clones the object by way of MooX::Rebuild but also if the dimap is set that is duplicated into the new object.

dimap_with param

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.

each_cell coderef

Calls the provided coderef for each cell of the dimap; the arguments to the coderef are as shown:

$dm->each_cell(
    sub {
        my ( $dimap, $row, $col, $self ) = @_;
        return if $dimap->[$row][$col] <= $self->min_cost;
        ...
    }
);

The return value of the coderef call is not used.

map map

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.

next row col [ value ]

Returns the adjacent points with lower values than the given cell. Both square and diagonal moves are considered by default, unlike in the default normfn. 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.

"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.

next_best row col

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.

next_sq row col [ value ]

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.

next_with row col param

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.

SUBROUTINES

These are mostly for internal use.

adjacent_values dimap row col maxrow maxcol

Returns the values for valid cells surrounding the given row and col. The order of the values must not be relied on. Shuffle the order to avoid any bias in cases where that may matter (e.g. with shuffle of List::Util).

adjacent_values_diag dimap row col maxrow maxcol

Returns the values for valid cells diagonal to the given row and col.

adjacent_values_sq dimap row col maxrow maxcol

Returns the values for valid cells square (4-way) to the given row and col.

norm_4way dimap mincost maxcost badcost

This is called by normalize, map, or recalc via the normfn attribute and weights cell cost values relative to the min_cost cells. Returns a value that is set to the iters attribute.

As of module version 1.04 negative values can be normalized, though mixing positive and negative numbers adjacent in the same map may have issues as only the magnitude of the number is considered when searching for the best cost.

This method onlu considers square (4-way) moves in the compass directions 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 norm_4way.

norm_8way dimap mincost maxcost badcost

Like norm_4way though assigns the same cost to all surrounding cells. Should allow for diagonal path finding.

norm_8way_euclid dimap mincost maxcost badcost

A more complicated version of norm_8way that tries to assign a cost of sqrt(2) to diagonals instead of the more typical non-Euclidean treatment.

CONSIDERATIONS

Given the map where h represents a hound, @ our doomed yet somehow still optimistic hero, ' an open door, and so forth,

  012345678
-+--------- turn 1
0|#########
1|#h......#
2|#.#####'#
3|#.#####@#
4|#########

A Dijkstra Map with the player as the only goal might be the following grid of numbers that outline the corridor leading to the player; the impassable walls here are represented with -1 (the bad_cost is now a much lower value by default).

   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

This allows the hound to move towards the player by trotting down the positive numbers, or to flee by going the other way. The map will need to be updated when the player moves or the map changes; 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 might instead cause the hound to start moving 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.

THE DREADED DIAGONAL

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, or when dressed as a Barbarian) 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.

The default normfn, norm_4way (like in Brogue, where the algorithm comes from) only considers square moves when calculating the costs so will not find various diagonal paths that Andband or DCSS consider legal; use one of the norm_8way* functions to allow path finding along diagonals.

GRID BUGS

Reporting Bugs

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.

Patches might best be applied towards:

https://github.com/thrig/Game-DijkstraMap

Known Issues

New code that is not much battle-tested, especially norm_8way_euclid. Also a first implementation that suffers from "hmm, how should this work?" design.

norm_4way is not very good with long and mostly unconnected corridors; this might be improved on by considering adjacent unseen cells after a cell changes in addition to full map iterations?

AUTHOR

thrig - Jeremy Mates (cpan:JMATES) <jmates at cpan.org>

COPYRIGHT AND LICENSE

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.

	Global
`s`	Focus search bar
`?`	Bring up this help dialog

	GitHub
`g` `p`	Go to pull requests
`g` `i`	go to github issues (only if github is preferred repository)

	POD
`g` `a`	Go to author
`g` `c`	Go to changes
`g` `i`	Go to issues
`g` `d`	Go to dist
`g` `r`	Go to repository/SCM
`g` `s`	Go to source
`g` `b`	Go to file browse

	Search terms
module: (e.g. module:Plugin)
distribution: (e.g. distribution:Dancer auth)
author: (e.g. author:SONGMU Redis)
version: (e.g. version:1.00)