view release on metacpan or  search on metacpan

lib/Game/DijkstraMap.pm  view on Meta::CPAN

          return $self->bad_cost;
      }
  );

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

L<https://www.roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps>

The L</CONSIDERATIONS> section describes what this module does in
more detail.

=head1 CONSTRUCTOR

The B<new> method accepts the L</ATTRIBUTES> in the usual L<Moo>
fashion. Additionally I<map> xor I<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 )

=head1 ATTRIBUTES

=over 4

=item B<bad_cost>

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

=item B<costfn>

A code reference called with the object and each cell of the I<map>
passed to B<map>. This function must convert the contents of the cell
into suitable cost numbers for the Dijkstra Map. Defaults to a function
that assigns B<bad_cost> to C<#> (walls), B<min_cost> to C<x> (goals),
and otherwise B<max_cost> for what is assumed to be floor tiles.

If the I<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 B<costfn> then calls.

=item B<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 B<map> or B<str2map>.

=item B<iters>

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

=item B<max_cost>

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

=item B<min_cost>

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

=item B<next_m>

A string used by various B<next_*> methods to use as a method to find
adjacent squares to move to, C<next> by default (which allows for
diagonal motions) but could instead be C<next_sq>.

=item B<normfn>

A code reference that is called by the B<normalize>, B<map>, and
B<recalc> methods to weight the Dijkstra Map as appropriate. The default
B<norm_4way> calculates weights using square or 4-way motion as seen in
Brogue, though diagonals are allowed if the map is open to those; set
B<next_m> as detailed above if diagonal moves are illegal. Other
roguelikes may need an 8-way cost function if diagonal moves are in
general permitted; this is possible with the B<norm_8way> function:

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

=back

=head1 METHODS

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

=over 4

=item B<clone>

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

=item B<dimap_with> I<param>

Constructs and returns a new B<dimap> data structure ideally in
combination with one or more other Dijkstra Map objects. Cells will be
marked as B<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 I<param> are the same as used by B<next_with>.

=item B<each_cell> I<coderef>

Calls the provided I<coderef> for each cell of the B<dimap>; the

lib/Game/DijkstraMap.pm  view on Meta::CPAN

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 B<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 B<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
B<recalc> would need to be done.

=head1 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 B<next> and
B<next_sq> are fairly generic; B<next_best> may not return an ideal move
given other considerations.

The default B<normfn>, B<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 B<norm_8way*> functions to allow path finding
along diagonals.

=head1 GRID BUGS

New code that is not much battle-tested, especially B<norm_8way_euclid>.
Also a first implementation that suffers from "hmm, how should this
work?" design. Something much more efficient should likely be written,
possibly with fewer features.

B<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?

=head1 SEE ALSO

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

=head1 AUTHOR

Jeremy Mates

=head1 COPYRIGHT AND LICENSE

Copyright (C) 2018 by Jeremy Mates

This program is distributed under the (Revised) BSD License.

=cut