Location : Home > Languages > Perl > Package
Title : Algorithm::Metric::Chessboard
 		Toolbox Logo

名称

　Algorithm::Metric::Chessboard - 正方格子上での距離（チェス盤距離）をオプションでワームホールの存在を認めて計算

説明

　チェス盤上の２点間を、縦・横・対角線に１つずつしか移動できないという条件下での最短距離を計算する。
　何も条件を課さない場合には点 (x1, y1) から点 (x2, y2) までの距離は

d( (x1, y1), (x2, y2) ) = max( abs( x1 - x2 ), abs( y1 - y2) )

となる。
　しかし空間にワームホール（wormholes）を認めると実際の距離は短くなる。ただしワームホールを使った移動には固定のペナルティを課すものとする。

概要

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

メソッド

new

　wormholes はオプションである。wormhole_cost のデフォルト値は 0 である。

nearest_wormhole

　Algorithm::Metric::Chessboard::Wormhole オブジェクトを返す。

shortest_journey

　Algorithm::Metric::Chessboard::Journey オブジェクトを返す。

著者

　Kake Pugh, <kake@earth.li>

著作権

　Copyright (C) 2004 Kake Pugh. All Rights Reserved.

　本モジュールはフリーソフトウェアであり、Perl 本体と同等の条件で修正／再配布してよい。

クレジット

　Jon Chin は名前を見つけ出すのを助けてくれたし、Andy Armstrong と Mike Stevens は問題の記述を明確にしてくれた。

参考資料

　なぜこのモジュールを書いたかについては：

【訳注と解説】

  1. 数学の世界で街区距離（city block distance）などと呼ばれるものに近いような気もするが、これは、街の道路に沿っての移動。でも、これはチェス盤の□から□への移動、なんだろう。だから、「斜め」なんていう移動が想定されてる。要するに隣接しているセルへなら移動できる、ということ。
  2. もともとゲーム画面でのセルとかヘキサゴン間の移動距離を求めたかったんだろうねぇ。でも、「ワームホール」ってズルいなぁ。
Toolbox Logo
 Updated : 2006/09/25