Algorithm::Metric::Chessboard - Calculate distances on a square grid with optional wormholes (the 'chessboard metric').
Calculates the minimum number of moves between two points in a game played on a square grid, where one move is a jump from a point to a horizontal, vertical or diagonal neighbour.
With no other features, the number of moves taken to go from the point (x1, y1) to (x2, y2) would be quite simple:
(x1, y1)
(x2, y2)
d( (x1, y1), (x2, y2) ) = max( abs( x1 - x2 ), abs( y1 - y2) )
However within the space are "wormholes" which allow you to travel between any two distant points, so the actual number of moves may be smaller than the above. Wormhole travel costs a fixed number of moves.
my @wormholes = ( Algorithm::Metric::Chessboard::Wormhole->new( x => 5, y => 30 ), Algorithm::Metric::Chessboard::Wormhole->new( x => 98, y => 99 ), ); my $grid = Algorithm::Metric::Chessboard->new( x_range => [ 0, 99 ], y_range => [ 0, 99 ], wormholes => \@wormholes, wormhole_cost => 3, ); my $wormhole = $grid->nearest_wormhole( x => 26, y => 53 ); my $journey = $grid->shortest_journey(start => [1, 6], end => [80, 1]);
my @wormholes = ( Algorithm::Metric::Chessboard::Wormhole->new( x => 5, y => 30, ), Algorithm::Metric::Chessboard::Wormhole->new( x => 98, y => 99, ), ); my $grid = Algorithm::Metric::Chessboard->new( x_range => [ 0, 99 ], y_range => [ 0, 99 ], wormholes => \@wormholes, wormhole_cost => 3, );
wormholes is optional. wormhole_cost defaults to 0.
wormholes
wormhole_cost
my $wormhole = $grid->nearest_wormhole( x => 26, y => 53 ); print "Nearest wormhole is " . $wormhole->id . " at (" . $wormhole->x . ", " . $wormhole->y . ")";
Returns a Algorithm::Metric::Chessboard::Wormhole object.
my $journey = $grid->shortest_journey( start => [1, 6], end => [80, 1], ); my $distance = $journey->distance; my @via = $journey->via; print "Shortest journey is $distance move" . ( $distance == 1 ? "" : "s" ); if ( scalar @via ) { print " via " . $via[0]->id . " and " . $via[1]->id; }
Returns a Algorithm::Metric::Chessboard::Journey object.
Kake Pugh (kake@earth.li).
Copyright (C) 2004 Kake Pugh. All Rights Reserved.
This module is free software; you can redistribute it and/or modify it under the same terms as Perl itself.
Jon Chin helped me figure out the name, Andy Armstrong and Mike Stevens helped me clarify the statement of the problem.
Why I wrote this:
Gothador - Devilishly Good Fun!
Vampires! The Dark Alleyway
To install Algorithm::Metric::Chessboard, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Algorithm::Metric::Chessboard
CPAN shell
perl -MCPAN -e shell install Algorithm::Metric::Chessboard
For more information on module installation, please visit the detailed CPAN module installation guide.