The London Perl and Raku Workshop takes place on 26th Oct 2024. If your company depends on Perl, please consider sponsoring and/or attending.

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

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

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.

Must not be accessed by calls to recalc or update before being set by 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).

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.

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.

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

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.

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.

If you know all the cells that are floor tiles these could be passed to update after the map changes or the player moves; this may be less expensive than recalc as that must inspect each cell in the 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. Need to add path finding (routes) and next cell (steps along routes) methods.

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