2007-12-01

タクティクスオガる

Perl

http://shohoji.net/blog/archives/001719.html
これを読んで。Perlで似たようなことをやってみた。
タクティクスオウガバトルのクローンみたいな感じになった。
make_map.plでマップ情報を格納したmap.plを作る。
move.plはmap.plを読み込んで動作する。ランダムに選んだ1マスをゴールとして、そのマスにいたるためのコスト表を作る。
ただ、リンク先の「コストが低いほうを選ぶ」と言うルールは変わらないが、それに加えて「高低差などを吟味して行ける方向の中から」と言う前提がつく。

make_map.pl

16*16のマップを作る。
マップは、高低差、そのマスに進入するためのコスト、障害物によって構成されている。

障害物のあるところには入れないとする。
高低差は、高いところは1段上まで、低いところは2段下まで移動できるとする。

use strict;
use Data::Dumper;

# マップの広さは16*16
my $max_x = 15;
my $max_y = 15;

# マップの高さレイヤー
my $high = [];

my @place = ([int(rand()*($max_x+1)), int(rand()*($max_y+1))]); # 初期位置を決める。
sub work {
	my ( $x, $y ) = @_;
	if ( defined $high->[$x]->[$y] ) {
		return $high->[$x]->[$y];
	} else {
		push @place, [$x, $y];
		return undef;
	}
}
while ( @place ) {
	my $place = shift @place; # この位置の高さを決める。
	my ( $x, $y ) = @{$place};
	defined $high->[$x]->[$y] and next;

	# 四方を調べる。
	my @around = ();
	$x > 0 and push @around, &work($x-1, $y);
	$y > 0 and push @around, &work($x, $y-1);
	$x < $max_x and push @around, &work($x+1, $y);
	$y < $max_y and push @around, &work($x, $y+1);
	@around = grep { defined $_ } @around;
	# その場所の高さは、周囲のどれか±1になる。
	if ( @around ) {
		$high->[$x]->[$y] = $around[int(rand()*scalar @around)]+int(rand()*3)-1;
	} else {
		# さもなければ5じゃー。
		$high->[$x]->[$y] = 5;
	}
}
foreach my $x ( 0..$max_x ) {
	foreach my $y ( 0..$max_y ) {
		$high->[$x]->[$y] < 0 and $high->[$x]->[$y] = 0;
		$high->[$x]->[$y] > 9 and $high->[$x]->[$y] = 9;
	}
}

# マップの障害物レイヤー
my $wall = [];
# 障害物の周囲には障害物を設置しない。
foreach ( 1..16 ) { # 障害物の数は16
	while ( 1 ) {
		my $x = int(rand()*($max_x+1));
		my $y = int(rand()*($max_x+1));
		my $temp = 0;
		# 周囲を調べる。
		if ( $x > 0      and $y > 0      ) { $temp += $wall->[$x-1]->[$y-1]; }
		if ( $x > 0                      ) { $temp += $wall->[$x-1]->[$y  ]; }
		if ( $x > 0      and $y < $max_y ) { $temp += $wall->[$x-1]->[$y+1]; }
		if (                 $y > 0      ) { $temp += $wall->[$x  ]->[$y-1]; }
		if (                 $y < $max_y ) { $temp += $wall->[$x  ]->[$y+1]; }
		if ( $x < $max_x and $y > 0      ) { $temp += $wall->[$x+1]->[$y-1]; }
		if ( $x < $max_x                 ) { $temp += $wall->[$x+1]->[$y  ]; }
		if ( $x < $max_x and $y < $max_y ) { $temp += $wall->[$x+1]->[$y+1]; }
		$temp > 0 and next; # 障害物が周囲に存在するならば場所の決めなおし。
		$wall->[$x]->[$y] = 1;
		last;
	}
}

# マップの地形データ
# 地形と言うよりも、そのマスに入るために必要なコスト
my $cost = [];
foreach my $x ( 0..$max_x ) {
	foreach my $y ( 0..$max_y ) {
		$cost->[$x]->[$y] = int(rand()*5)+1;
	}
}

open ( OUT, '>map.pl' );
print OUT Data::Dumper->new([$high], ['map_h'])->Dump();
print OUT Data::Dumper->new([$wall], ['map_w'])->Dump();
print OUT Data::Dumper->new([$cost], ['map_c'])->Dump();
close ( OUT );

move.pl

こっちが本体。

use strict;

# マップの読み込み
our $map_h = undef;
our $map_w = undef;
our $map_c = undef;
require 'map.pl';

# ユニットの移動ルール
# 登りは1段差まで。
# 降りは2段差まで。
# 斜めには移動できない。
# 方向転換のコストは0

# マップの大きさを規定。
my $max_x = 15;
my $max_y = 15;

# ゴール地点を決定。
my $goal_x = undef;
my $goal_y = undef;
while ( 1 ) {
	$goal_x = int(rand()*($max_x+1));
	$goal_y = int(rand()*($max_y+1));
	$map_w->[$goal_x]->[$goal_y] or last;
}

# 考え方
# ダイクストラ法！
my $cost = []; # コスト
my @place = ( [$goal_x, $goal_y] );
$cost->[$goal_x]->[$goal_y] = 0;
while ( @place ) {
	my $target = shift @place;
	my ( $x, $y ) = @{$target};
	# この地点に隣接する地点をピックアップ。
	my @turn = (
		[$x-1, $y],
		[$x+1, $y],
		[$x, $y-1],
		[$x, $y+1]
	);
	
	# マップの内外判定
	@turn = grep { $_->[0] > -1 } @turn;
	@turn = grep { $_->[0] < $max_x+1 } @turn;
	@turn = grep { $_->[1] > -1 } @turn;
	@turn = grep { $_->[1] < $max_y+1 } @turn;

	# そこに壁はないか？　あったら除外。
	@turn = grep { !$map_w->[$_->[0]]->[$_->[1]] } @turn;

	# そこは段差的に移動可能か？
	my $high = $map_h->[$x]->[$y]; # 現在の高さ
	@turn = grep { ($high - $map_h->[$_->[0]]->[$_->[1]]) < 2 } @turn; # 高すぎ
	@turn = grep { ($map_h->[$_->[0]]->[$_->[1]] - $high) < 3 } @turn; # 低すぎ

	if ( @turn ) {
		foreach my $turn ( @turn ) {
			my $temp_cost = $cost->[$x]->[$y] + $map_c->[$x]->[$y];
			if ( defined $cost->[$turn->[0]]->[$turn->[1]] ) {
				if ( $cost->[$turn->[0]]->[$turn->[1]] > $temp_cost ) {
					$cost->[$turn->[0]]->[$turn->[1]] = $temp_cost;
					push @place, $turn;
				}
			} else {
				$cost->[$turn->[0]]->[$turn->[1]] = $temp_cost;
				push @place, $turn;
			}
		}
	}
}

# 結果の表示
print 'hight'.(' ' x ($max_x-4));
print ' ';
print 'cost'.(' ' x ($max_x-3));
print "\n";
foreach my $y ( 0..$max_y ) {
	foreach my $x ( 0..$max_x ) {
		print $map_w->[$x]->[$y] ? '-' : $map_h->[$x]->[$y];
	}
	print " ";
	foreach my $x ( 0..$max_x ) {
		print $map_w->[$x]->[$y] ? '-' : $map_c->[$x]->[$y];
	}
	print "\n";
}
print "goal : ( $goal_x, $goal_y )\n";
foreach my $y ( 0..$max_y ) {
	foreach my $x ( 0..$max_x ) {
		if ( $x == $goal_x and $y == $goal_y ) {
			print "GL";
		} elsif ( $map_w->[$x]->[$y] ) {
			print '--';
		} elsif ( defined $cost->[$x]->[$y] ) {
			printf "%02d", $cost->[$x]->[$y];
		} else {
			print 'XX';
		}
		print " "
	}
	print "\n";
}

実行例

hight            cost
5122333678976-55 3212354535255-23
6545234678877966 1144243524145551
54465445-7998976 41455232-1114534
333344-6789-9987 215235-5243-1324
2244445658989999 4214515311345235
3145336776688899 1145112423433514
4344-77786677899 1433-54533234242
233335-545554999 132135-334422152
332367665-465999 423351244-432553
234-66775632344- 515-32443512234-
4458776667234559 3122541311222212
4565666548344445 3155555251551153
53-477544733445- 24-313343342245-
332766-55-343434 124314-22-453533
3444567676567453 3323511352435221
-34-767878777856 -43-143215132115
goal : ( 1, 10 )
20 45 44 42 39 37 39 43 45 47 45 49 54 -- 63 63
19 18 19 23 37 33 36 38 43 43 44 45 49 54 58 62
16 17 18 22 26 31 33 36 -- 42 43 44 45 49 55 58
14 16 17 21 23 26 -- 35 36 38 42 -- 49 50 53 55
10 14 16 17 21 26 27 32 35 38 39 42 46 51 53 56
09 16 12 13 26 27 27 29 33 35 38 42 45 48 53 54
08 07 09 10 -- 18 23 27 32 35 38 40 43 47 49 53
07 04 07 09 10 13 -- 25 28 31 35 39 41 49 50 55
04 02 04 07 19 18 19 21 25 -- 39 41 43 50 55 57
02 01 02 -- 21 19 21 25 29 31 43 44 46 48 51 --
01 GL 01 22 17 21 25 26 29 30 44 46 48 50 52 XX
02 01 02 07 12 17 22 27 29 31 46 48 50 51 52 57
05 34 -- 12 17 18 27 29 32 32 51 53 51 52 56 --
34 32 34 19 18 19 -- 28 30 -- 55 55 53 56 61 64
32 29 27 24 19 23 24 25 28 33 35 39 42 61 63 67
-- 32 29 -- 24 24 25 28 30 31 36 37 40 42 65 66

( 1, 10 )=GLに行くために、どれだけのコストがかかるのかの表。
たとえば、一番右下のマスからGLに行くためには、66必要だとわかる。
移動する方向は、そこから安いコストのマスを選べばいい。
ただしこの時。

最安値が複数あればランダム選択。
高低差を考慮すれば、行けないマスがある。（目安として6以上コストに差があれば断絶があると考えられる）

考察

こういうのは、ダイクストラ法のそれも有向グラフの応用なんだろうけど、エッジの長さ（コスト）がほぼ同値だったりするので厳密に適用する必要がない。
これで「一段上のマスに進入するためには、余分に移動力を消費する」とかのルールがあれば、ダイクストラ法の真価が発揮されるんだろうけど。

2007-12-01

出るらしい

ロボ娘フィギュアユリア100式

ユリア100式 LIGHTNING Figure 完成品フィギュア First Classが出るんだって！

2007-12-01

いい加減にしたい

日記

2007-12-01

いい加減にしたい

日記

2007-12-01

タクティクスオガる

Perl

make_map.pl

16*16のマップを作る。
マップは、高低差、そのマスに進入するためのコスト、障害物によって構成されている。

障害物のあるところには入れないとする。
高低差は、高いところは1段上まで、低いところは2段下まで移動できるとする。

use strict;
use Data::Dumper;

# マップの広さは16*16
my $max_x = 15;
my $max_y = 15;

# マップの高さレイヤー
my $high = [];

my @place = ([int(rand()*($max_x+1)), int(rand()*($max_y+1))]); # 初期位置を決める。
sub work {
	my ( $x, $y ) = @_;
	if ( defined $high->[$x]->[$y] ) {
		return $high->[$x]->[$y];
	} else {
		push @place, [$x, $y];
		return undef;
	}
}
while ( @place ) {
	my $place = shift @place; # この位置の高さを決める。
	my ( $x, $y ) = @{$place};
	defined $high->[$x]->[$y] and next;

	# 四方を調べる。
	my @around = ();
	$x > 0 and push @around, &work($x-1, $y);
	$y > 0 and push @around, &work($x, $y-1);
	$x < $max_x and push @around, &work($x+1, $y);
	$y < $max_y and push @around, &work($x, $y+1);
	@around = grep { defined $_ } @around;
	# その場所の高さは、周囲のどれか±1になる。
	if ( @around ) {
		$high->[$x]->[$y] = $around[int(rand()*scalar @around)]+int(rand()*3)-1;
	} else {
		# さもなければ5じゃー。
		$high->[$x]->[$y] = 5;
	}
}
foreach my $x ( 0..$max_x ) {
	foreach my $y ( 0..$max_y ) {
		$high->[$x]->[$y] < 0 and $high->[$x]->[$y] = 0;
		$high->[$x]->[$y] > 9 and $high->[$x]->[$y] = 9;
	}
}

# マップの障害物レイヤー
my $wall = [];
# 障害物の周囲には障害物を設置しない。
foreach ( 1..16 ) { # 障害物の数は16
	while ( 1 ) {
		my $x = int(rand()*($max_x+1));
		my $y = int(rand()*($max_x+1));
		my $temp = 0;
		# 周囲を調べる。
		if ( $x > 0      and $y > 0      ) { $temp += $wall->[$x-1]->[$y-1]; }
		if ( $x > 0                      ) { $temp += $wall->[$x-1]->[$y  ]; }
		if ( $x > 0      and $y < $max_y ) { $temp += $wall->[$x-1]->[$y+1]; }
		if (                 $y > 0      ) { $temp += $wall->[$x  ]->[$y-1]; }
		if (                 $y < $max_y ) { $temp += $wall->[$x  ]->[$y+1]; }
		if ( $x < $max_x and $y > 0      ) { $temp += $wall->[$x+1]->[$y-1]; }
		if ( $x < $max_x                 ) { $temp += $wall->[$x+1]->[$y  ]; }
		if ( $x < $max_x and $y < $max_y ) { $temp += $wall->[$x+1]->[$y+1]; }
		$temp > 0 and next; # 障害物が周囲に存在するならば場所の決めなおし。
		$wall->[$x]->[$y] = 1;
		last;
	}
}

# マップの地形データ
# 地形と言うよりも、そのマスに入るために必要なコスト
my $cost = [];
foreach my $x ( 0..$max_x ) {
	foreach my $y ( 0..$max_y ) {
		$cost->[$x]->[$y] = int(rand()*5)+1;
	}
}

open ( OUT, '>map.pl' );
print OUT Data::Dumper->new([$high], ['map_h'])->Dump();
print OUT Data::Dumper->new([$wall], ['map_w'])->Dump();
print OUT Data::Dumper->new([$cost], ['map_c'])->Dump();
close ( OUT );

move.pl

こっちが本体。

use strict;

# マップの読み込み
our $map_h = undef;
our $map_w = undef;
our $map_c = undef;
require 'map.pl';

# ユニットの移動ルール
# 登りは1段差まで。
# 降りは2段差まで。
# 斜めには移動できない。
# 方向転換のコストは0

# マップの大きさを規定。
my $max_x = 15;
my $max_y = 15;

# ゴール地点を決定。
my $goal_x = undef;
my $goal_y = undef;
while ( 1 ) {
	$goal_x = int(rand()*($max_x+1));
	$goal_y = int(rand()*($max_y+1));
	$map_w->[$goal_x]->[$goal_y] or last;
}

# 考え方
# ダイクストラ法！
my $cost = []; # コスト
my @place = ( [$goal_x, $goal_y] );
$cost->[$goal_x]->[$goal_y] = 0;
while ( @place ) {
	my $target = shift @place;
	my ( $x, $y ) = @{$target};
	# この地点に隣接する地点をピックアップ。
	my @turn = (
		[$x-1, $y],
		[$x+1, $y],
		[$x, $y-1],
		[$x, $y+1]
	);
	
	# マップの内外判定
	@turn = grep { $_->[0] > -1 } @turn;
	@turn = grep { $_->[0] < $max_x+1 } @turn;
	@turn = grep { $_->[1] > -1 } @turn;
	@turn = grep { $_->[1] < $max_y+1 } @turn;

	# そこに壁はないか？　あったら除外。
	@turn = grep { !$map_w->[$_->[0]]->[$_->[1]] } @turn;

	# そこは段差的に移動可能か？
	my $high = $map_h->[$x]->[$y]; # 現在の高さ
	@turn = grep { ($high - $map_h->[$_->[0]]->[$_->[1]]) < 2 } @turn; # 高すぎ
	@turn = grep { ($map_h->[$_->[0]]->[$_->[1]] - $high) < 3 } @turn; # 低すぎ

	if ( @turn ) {
		foreach my $turn ( @turn ) {
			my $temp_cost = $cost->[$x]->[$y] + $map_c->[$x]->[$y];
			if ( defined $cost->[$turn->[0]]->[$turn->[1]] ) {
				if ( $cost->[$turn->[0]]->[$turn->[1]] > $temp_cost ) {
					$cost->[$turn->[0]]->[$turn->[1]] = $temp_cost;
					push @place, $turn;
				}
			} else {
				$cost->[$turn->[0]]->[$turn->[1]] = $temp_cost;
				push @place, $turn;
			}
		}
	}
}

# 結果の表示
print 'hight'.(' ' x ($max_x-4));
print ' ';
print 'cost'.(' ' x ($max_x-3));
print "\n";
foreach my $y ( 0..$max_y ) {
	foreach my $x ( 0..$max_x ) {
		print $map_w->[$x]->[$y] ? '-' : $map_h->[$x]->[$y];
	}
	print " ";
	foreach my $x ( 0..$max_x ) {
		print $map_w->[$x]->[$y] ? '-' : $map_c->[$x]->[$y];
	}
	print "\n";
}
print "goal : ( $goal_x, $goal_y )\n";
foreach my $y ( 0..$max_y ) {
	foreach my $x ( 0..$max_x ) {
		if ( $x == $goal_x and $y == $goal_y ) {
			print "GL";
		} elsif ( $map_w->[$x]->[$y] ) {
			print '--';
		} elsif ( defined $cost->[$x]->[$y] ) {
			printf "%02d", $cost->[$x]->[$y];
		} else {
			print 'XX';
		}
		print " "
	}
	print "\n";
}

実行例

hight            cost
5122333678976-55 3212354535255-23
6545234678877966 1144243524145551
54465445-7998976 41455232-1114534
333344-6789-9987 215235-5243-1324
2244445658989999 4214515311345235
3145336776688899 1145112423433514
4344-77786677899 1433-54533234242
233335-545554999 132135-334422152
332367665-465999 423351244-432553
234-66775632344- 515-32443512234-
4458776667234559 3122541311222212
4565666548344445 3155555251551153
53-477544733445- 24-313343342245-
332766-55-343434 124314-22-453533
3444567676567453 3323511352435221
-34-767878777856 -43-143215132115
goal : ( 1, 10 )
20 45 44 42 39 37 39 43 45 47 45 49 54 -- 63 63
19 18 19 23 37 33 36 38 43 43 44 45 49 54 58 62
16 17 18 22 26 31 33 36 -- 42 43 44 45 49 55 58
14 16 17 21 23 26 -- 35 36 38 42 -- 49 50 53 55
10 14 16 17 21 26 27 32 35 38 39 42 46 51 53 56
09 16 12 13 26 27 27 29 33 35 38 42 45 48 53 54
08 07 09 10 -- 18 23 27 32 35 38 40 43 47 49 53
07 04 07 09 10 13 -- 25 28 31 35 39 41 49 50 55
04 02 04 07 19 18 19 21 25 -- 39 41 43 50 55 57
02 01 02 -- 21 19 21 25 29 31 43 44 46 48 51 --
01 GL 01 22 17 21 25 26 29 30 44 46 48 50 52 XX
02 01 02 07 12 17 22 27 29 31 46 48 50 51 52 57
05 34 -- 12 17 18 27 29 32 32 51 53 51 52 56 --
34 32 34 19 18 19 -- 28 30 -- 55 55 53 56 61 64
32 29 27 24 19 23 24 25 28 33 35 39 42 61 63 67
-- 32 29 -- 24 24 25 28 30 31 36 37 40 42 65 66

最安値が複数あればランダム選択。
高低差を考慮すれば、行けないマスがある。（目安として6以上コストに差があれば断絶があると考えられる）

考察

2007-12-01

出るらしい

ロボ娘フィギュアユリア100式

ユリア100式 LIGHTNING Figure 完成品フィギュア First Classが出るんだって！

2007-12-01

いい加減にしたい

日記

2007-12-01

タクティクスオガる

Perl

make_map.pl

16*16のマップを作る。
マップは、高低差、そのマスに進入するためのコスト、障害物によって構成されている。

障害物のあるところには入れないとする。
高低差は、高いところは1段上まで、低いところは2段下まで移動できるとする。

use strict;
use Data::Dumper;

# マップの広さは16*16
my $max_x = 15;
my $max_y = 15;

# マップの高さレイヤー
my $high = [];

my @place = ([int(rand()*($max_x+1)), int(rand()*($max_y+1))]); # 初期位置を決める。
sub work {
	my ( $x, $y ) = @_;
	if ( defined $high->[$x]->[$y] ) {
		return $high->[$x]->[$y];
	} else {
		push @place, [$x, $y];
		return undef;
	}
}
while ( @place ) {
	my $place = shift @place; # この位置の高さを決める。
	my ( $x, $y ) = @{$place};
	defined $high->[$x]->[$y] and next;

	# 四方を調べる。
	my @around = ();
	$x > 0 and push @around, &work($x-1, $y);
	$y > 0 and push @around, &work($x, $y-1);
	$x < $max_x and push @around, &work($x+1, $y);
	$y < $max_y and push @around, &work($x, $y+1);
	@around = grep { defined $_ } @around;
	# その場所の高さは、周囲のどれか±1になる。
	if ( @around ) {
		$high->[$x]->[$y] = $around[int(rand()*scalar @around)]+int(rand()*3)-1;
	} else {
		# さもなければ5じゃー。
		$high->[$x]->[$y] = 5;
	}
}
foreach my $x ( 0..$max_x ) {
	foreach my $y ( 0..$max_y ) {
		$high->[$x]->[$y] < 0 and $high->[$x]->[$y] = 0;
		$high->[$x]->[$y] > 9 and $high->[$x]->[$y] = 9;
	}
}

# マップの障害物レイヤー
my $wall = [];
# 障害物の周囲には障害物を設置しない。
foreach ( 1..16 ) { # 障害物の数は16
	while ( 1 ) {
		my $x = int(rand()*($max_x+1));
		my $y = int(rand()*($max_x+1));
		my $temp = 0;
		# 周囲を調べる。
		if ( $x > 0      and $y > 0      ) { $temp += $wall->[$x-1]->[$y-1]; }
		if ( $x > 0                      ) { $temp += $wall->[$x-1]->[$y  ]; }
		if ( $x > 0      and $y < $max_y ) { $temp += $wall->[$x-1]->[$y+1]; }
		if (                 $y > 0      ) { $temp += $wall->[$x  ]->[$y-1]; }
		if (                 $y < $max_y ) { $temp += $wall->[$x  ]->[$y+1]; }
		if ( $x < $max_x and $y > 0      ) { $temp += $wall->[$x+1]->[$y-1]; }
		if ( $x < $max_x                 ) { $temp += $wall->[$x+1]->[$y  ]; }
		if ( $x < $max_x and $y < $max_y ) { $temp += $wall->[$x+1]->[$y+1]; }
		$temp > 0 and next; # 障害物が周囲に存在するならば場所の決めなおし。
		$wall->[$x]->[$y] = 1;
		last;
	}
}

# マップの地形データ
# 地形と言うよりも、そのマスに入るために必要なコスト
my $cost = [];
foreach my $x ( 0..$max_x ) {
	foreach my $y ( 0..$max_y ) {
		$cost->[$x]->[$y] = int(rand()*5)+1;
	}
}

open ( OUT, '>map.pl' );
print OUT Data::Dumper->new([$high], ['map_h'])->Dump();
print OUT Data::Dumper->new([$wall], ['map_w'])->Dump();
print OUT Data::Dumper->new([$cost], ['map_c'])->Dump();
close ( OUT );

move.pl

こっちが本体。

use strict;

# マップの読み込み
our $map_h = undef;
our $map_w = undef;
our $map_c = undef;
require 'map.pl';

# ユニットの移動ルール
# 登りは1段差まで。
# 降りは2段差まで。
# 斜めには移動できない。
# 方向転換のコストは0

# マップの大きさを規定。
my $max_x = 15;
my $max_y = 15;

# ゴール地点を決定。
my $goal_x = undef;
my $goal_y = undef;
while ( 1 ) {
	$goal_x = int(rand()*($max_x+1));
	$goal_y = int(rand()*($max_y+1));
	$map_w->[$goal_x]->[$goal_y] or last;
}

# 考え方
# ダイクストラ法！
my $cost = []; # コスト
my @place = ( [$goal_x, $goal_y] );
$cost->[$goal_x]->[$goal_y] = 0;
while ( @place ) {
	my $target = shift @place;
	my ( $x, $y ) = @{$target};
	# この地点に隣接する地点をピックアップ。
	my @turn = (
		[$x-1, $y],
		[$x+1, $y],
		[$x, $y-1],
		[$x, $y+1]
	);
	
	# マップの内外判定
	@turn = grep { $_->[0] > -1 } @turn;
	@turn = grep { $_->[0] < $max_x+1 } @turn;
	@turn = grep { $_->[1] > -1 } @turn;
	@turn = grep { $_->[1] < $max_y+1 } @turn;

	# そこに壁はないか？　あったら除外。
	@turn = grep { !$map_w->[$_->[0]]->[$_->[1]] } @turn;

	# そこは段差的に移動可能か？
	my $high = $map_h->[$x]->[$y]; # 現在の高さ
	@turn = grep { ($high - $map_h->[$_->[0]]->[$_->[1]]) < 2 } @turn; # 高すぎ
	@turn = grep { ($map_h->[$_->[0]]->[$_->[1]] - $high) < 3 } @turn; # 低すぎ

	if ( @turn ) {
		foreach my $turn ( @turn ) {
			my $temp_cost = $cost->[$x]->[$y] + $map_c->[$x]->[$y];
			if ( defined $cost->[$turn->[0]]->[$turn->[1]] ) {
				if ( $cost->[$turn->[0]]->[$turn->[1]] > $temp_cost ) {
					$cost->[$turn->[0]]->[$turn->[1]] = $temp_cost;
					push @place, $turn;
				}
			} else {
				$cost->[$turn->[0]]->[$turn->[1]] = $temp_cost;
				push @place, $turn;
			}
		}
	}
}

# 結果の表示
print 'hight'.(' ' x ($max_x-4));
print ' ';
print 'cost'.(' ' x ($max_x-3));
print "\n";
foreach my $y ( 0..$max_y ) {
	foreach my $x ( 0..$max_x ) {
		print $map_w->[$x]->[$y] ? '-' : $map_h->[$x]->[$y];
	}
	print " ";
	foreach my $x ( 0..$max_x ) {
		print $map_w->[$x]->[$y] ? '-' : $map_c->[$x]->[$y];
	}
	print "\n";
}
print "goal : ( $goal_x, $goal_y )\n";
foreach my $y ( 0..$max_y ) {
	foreach my $x ( 0..$max_x ) {
		if ( $x == $goal_x and $y == $goal_y ) {
			print "GL";
		} elsif ( $map_w->[$x]->[$y] ) {
			print '--';
		} elsif ( defined $cost->[$x]->[$y] ) {
			printf "%02d", $cost->[$x]->[$y];
		} else {
			print 'XX';
		}
		print " "
	}
	print "\n";
}

実行例

hight            cost
5122333678976-55 3212354535255-23
6545234678877966 1144243524145551
54465445-7998976 41455232-1114534
333344-6789-9987 215235-5243-1324
2244445658989999 4214515311345235
3145336776688899 1145112423433514
4344-77786677899 1433-54533234242
233335-545554999 132135-334422152
332367665-465999 423351244-432553
234-66775632344- 515-32443512234-
4458776667234559 3122541311222212
4565666548344445 3155555251551153
53-477544733445- 24-313343342245-
332766-55-343434 124314-22-453533
3444567676567453 3323511352435221
-34-767878777856 -43-143215132115
goal : ( 1, 10 )
20 45 44 42 39 37 39 43 45 47 45 49 54 -- 63 63
19 18 19 23 37 33 36 38 43 43 44 45 49 54 58 62
16 17 18 22 26 31 33 36 -- 42 43 44 45 49 55 58
14 16 17 21 23 26 -- 35 36 38 42 -- 49 50 53 55
10 14 16 17 21 26 27 32 35 38 39 42 46 51 53 56
09 16 12 13 26 27 27 29 33 35 38 42 45 48 53 54
08 07 09 10 -- 18 23 27 32 35 38 40 43 47 49 53
07 04 07 09 10 13 -- 25 28 31 35 39 41 49 50 55
04 02 04 07 19 18 19 21 25 -- 39 41 43 50 55 57
02 01 02 -- 21 19 21 25 29 31 43 44 46 48 51 --
01 GL 01 22 17 21 25 26 29 30 44 46 48 50 52 XX
02 01 02 07 12 17 22 27 29 31 46 48 50 51 52 57
05 34 -- 12 17 18 27 29 32 32 51 53 51 52 56 --
34 32 34 19 18 19 -- 28 30 -- 55 55 53 56 61 64
32 29 27 24 19 23 24 25 28 33 35 39 42 61 63 67
-- 32 29 -- 24 24 25 28 30 31 36 37 40 42 65 66

最安値が複数あればランダム選択。
高低差を考慮すれば、行けないマスがある。（目安として6以上コストに差があれば断絶があると考えられる）

考察

2007-12-01

出るらしい

ロボ娘フィギュアユリア100式

ユリア100式 LIGHTNING Figure 完成品フィギュア First Classが出るんだって！