The London Perl and Raku Workshop takes place on 26th Oct 2024. If your company depends on Perl, please consider sponsoring and/or attending.
 / 
Game-DijkstraMap-0.04
River stage zero No dependents
/ Game::DijkstraMap

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

  # create the dijkstra map
  $dm->map($level);

  # 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->next_best( 1, 6, 'next_sq' );  # 1,7

  $dm->path_best( 1, 1 );
  $dm->path_best( 1, 1, 'next_sq' );

  # change the open door ' to a closed one
  $dm->update( [ 2, 7, -1 ] );
  $dm->recalc;

  $dm->next( 1, 7 );  # nowhere better to move to

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

CONSTRUCTOR

The new method accepts the "ATTRIBUTES" in the usual Moo fashion.

ATTRIBUTES

max_cost

Cost for non-goal non-wall points. A large number by default. These points should be reduced to appropriate weights (steps from the nearest goal point) by normalize_costs.

min_cost

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

bad_cost

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.

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

iters

This is set after the map and recalc method calls and indicates how many iterations it took normalize_costs to stabilize the map.

METHODS

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

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

Returns the adjacent points with lower values than the given cell. Both square and diagonal moves are considered. The return format is 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.

next_best row col [ next-method ]

Calls next (or the method named by the optional next-method argument) and returns 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

Like next but only considers non-diagonal moves.

normalize_costs dimap

Mostly an internal routine called by map or update that reduces max_cost cells as appropriate relative to the connected min_cost cells. Changes the iters attribute.

path_best row col [ next-method ]

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

recalc

Resets the weights of all non-wall non-goal cells and then calls normalize_costs. See below for a discussion of update and recalc.

Returns the object so can be chained with other calls.

str2map string [ split-with ]

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 $/.

update [row, col, value] ..

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 object so can be chained with other calls.

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

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

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.

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.

SEE ALSO

There are various other graph and path finding modules on CPAN that may be more suitable to the task at hand.

AUTHOR

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

COPYRIGHT AND LICENSE

Copyright (C) 2018 by Jeremy Mates

This program is distributed under the (Revised) BSD License: http://www.opensource.org/licenses/BSD-3-Clause