SATCHを用いたナビアプリ(1)のサーバ側スクリプト

map_1F.txt
K1号館1F
|―――――――――――――――――――――――――――|
|+++++++++++++++++++++++++++|
|―――――――――――――――――――――――|+++|
|+++++++++++++|・・・・|++++|+++|
|++++++++|―|*|P|・・・@出入++|+++|
|+++|――――P*・・・・・・・・|――――|+++|
|+++|+++++|・|―――|・・・++++|+++|
|+++|+++++|・|+階+|・・・・・・+|+++|
|―――――――――|・|―――|・・・・・・+|+++|
|+++++++++|・|+++|・・+||・+|+++|
|+++++++++|・|E―E|・・+||・+|+++|
|+++++++++|・|+*+|・・+||・+|+++|
|++++++++プ*・・・・・・・・+||・+|+++|
|―――――――――|・・・・・・・・+||・+|+++|
|++++++++ソ*・・・・・・・・+||・+|+++|
|+++++++++|・|+*+|・・+||・+|+++|
|+++++++++|・|E―E|・・+||・+|+++|
|+++++++++|・|+++|・・+||・+|+++|
|+++++++++|・|―――|・・・・・・+|+++|
|++++++++ネ*・|+階+|・・・・・・+|+++|
|―――――――――|・|―――|・・|――――|+++|
|++++++++メ*・|―P―|・・|――――|+++|
|+++++++++|・|―――|・・@出入++|+++|
|+++++++++|++++++++|++++|+++|
|+++++++++|*―――*―*――――――|+++|
|+++++++++|女+|+男+多|+++++++++|
|―――――――――――――――――――――――――――|

map_10F.txt
K1号館10F
|―――――――――――――――――――――――――――|
|+++++++++|・・・・・・・|+++++++++|
|+++++++++|C・・・・・C|+++++++++|
|+++++++++|・|―――|・|+++++++++|
|+++++++++|・|*――|・|+++++++++|
|+++++++++*C・・・・・C*白++++++++|
|―――――――――|・|―――|・|―――――――――|
|+++++++++|・|+階+|・|+++++++++|
|+++++++++|・|―――|・|+++++++++|
|+++++++++|・|+++|・|+++++++++|
|++++++++井*・|E―E|・*黒++++++++|
|―――――――――|・|+*+|・|―――――――――|
|+++井教*・+++・++・++・+++・*黒教+++|
|―――――|・・・・C・・・・・C・・・・|―――――|
|+++平教*・+++・++・++・+++・*福教+++|
|―――――――――|・|+*+|・|―――――――――|
|++++++++平*・|E―E|・*福++++++++|
|+++++++++|・|+++|・|+++++++++|
|+++++++++|・|―――|・|+++++++++|
|+++++++++|・|+階+|・|+++++++++|
|―――――――――|・|―――|・|―――――――――|
|++++++++坂*・|―P―|・*梶++++++++|
|+++++++++|・|―――|・|+++++++++|
|+++++++++|C・・・・・C|+++++++++|
|+++++++++|・|―|―|・|+++++++++|
|+++++++++|・*男|女*・|+++++++++|
|―――――――――――――――――――――――――――|

map_11F.txt
K1号館11F
|―――――――――――――――――――――――――――|
|+|+++|+++|・・・・・・・|+++++++++|
|+|+++|+++|・・・・・・・|+++++++++|
|+|++春|++西|C・・・・・C|+++++++++|
|+|――*―――*|・|*|P|・|+++++++++|
|助*・・・・・・・・C・・・・・C*小++++++++|
|―――――――――|・|―――|・|―――――――――|
|+++++++++|・|+階+|・|+++++++++|
|+++++++++|・|―――|・|+++++++++|
|+++++++++|・|+++|・|+++++++++|
|++++++++富*・|E―E|・*服++++++++|
|―――――――――|・|+*+|・|―――――――――|
|+++富教*・+++・++・++・+++・*服教+++|
|―――――|・・・・C・・・・・C・・・・|―――――|
|+++谷教*・+++・++・++・+++・*徳教+++|
|―――――――――|・|+*+|・|―――――――――|
|++++++++谷*・|E―E|・*徳++++++++|
|+++++++++|・|+++|・|+++++++++|
|+++++++++|・|―――|・|+++++++++|
|+++++++++|・|+階+|・|+++++++++|
|―――――――――|・|―――|・|―――――――――|
|++++++++佐*・|―P―|・*速++++++++|
|+++++++++|・|―――|・|+++++++++|
|+++++++++|C・・・・・C|+++++++++|
|+++++++++|・|―|―|・|+++++++++|
|+++++++++|・*男|女*・|+++++++++|
|―――――――――――――――――――――――――――|

map_MF.txt
K1号館MF
|―――――――――――――――――――――――――――|
|+|+++|+++|+++++++|+++++++++|
|+|+++|+++|+++++++|+++++++++|
|+|++春|++西|+++++++|+++++++++|
|+|――*―――*|+|*|P|+|+++++++++|
|助*+++++++++++++++*小++++++++|
|―――――――――|+|―――|+|―――――――――|
|+++++++++|+|+階+|+|+++++++++|
|+++++++++|+|―――|+|+++++++++|
|+++++++++|+|+++|+|+++++++++|
|++++++++富*+|E―E|+*服++++++++|
|―――――――――|+|+―+|+|―――――――――|
|+++富教*+++++++・+++++++*服教+++|
|―――――|+++++++++++++++|―――――|
|+++谷教*+++++++・+++++++*徳教+++|
|―――――――――|+|+―+|+|―――――――――|
|++++++++谷*+|E―E|+*徳++++++++|
|+++++++++|+|+++|+|+++++++++|
|+++++++++|+|―――|+|+++++++++|
|+++++++++|+|+階+|+|+++++++++|
|―――――――――|+|―――|+|―――――――――|
|++++++++佐*+|―P―|+*速++++++++|
|+++++++++|+|―――|+|+++++++++|
|+++++++++|+++++++|+++++++++|
|+++++++++|+|―|―|+|+++++++++|
|+++++++++|+*男|女*+|+++++++++|
|―――――――――――――――――――――――――――|

navitest8.cgi
#!/usr/local/bin/perl

use CGI qw(:standard);
use XML::Writer;
use Encode;
use KAIT::Map3d;

my $q = new CGI();
my $start = $q->param("start");
my $target = $q->param("target");

my $g1 = KAIT::Map3d->new();

my $f1 = $g1->getFloor($start);
my $f2 = $g1->getFloor($target);

my $flag = 1;
my $path1 = $g1->findPath($start, $target);
my $path2;

if ($f1 != $f2) {
	$flag = 2;
	$g1 = KAIT::Map3d->new();
	$path2 = $g1->findPath2($path1, $start, $target);
}

my $output = '';
if ($flag == 1) {
	$output = $g1->createNaviData1($path1);
}
elsif ($flag == 2) {
	$output = $g1->createNaviData2($path1, $path2);
}

my $string = decode( 'shiftjis', $output );
print header('text/xml'), encode( 'utf8', $string );

init3d.pm
package KAIT::init3d;

*FLOOR_DATA = [ 'dummy', 'map_1F.txt', 'map_MF.txt', 'map_10F.txt', 'map_MF.txt', 'map_11F.txt', ];

*SYMBOL_PASS = { '・' => 1, 'C' => 1,};

*SYMBOL_MARKER = {'*' => 1, '@' => 1, };

*SYMBOL_CORNER = {'C' => 1, };

*ELEVATOR_MARKER = [ '15.12', '15.16', ];

*SPOTS = { 
# 1F

#入り口(K2号館側)
'1' => '19.5.1',

#入り口(マクドナルド側)
'2' => '19.23.1', 

#エレベータ(1A,1B)
'3' => '15.13.1', 

#エレベータ(1C,1D)
'4' => '15.15.1', 

# 10F

#平野教員室(1005)
'1005' => '8.15.10',

#平野研究室(1006)
'1006' => '12.17.10',

#坂内研究室(1007)
'1007' => '12.22.10',

#坂内教員室(1008)
#'1008' => '..10',

#梶教員室(1009)
#'1009' => '..10',

#梶研究室・牧研究室(1010)
'1010' => '18.22.10',

#福井研究室(1011)
'1011' => '18.17.10',

#福井教員室(1012)
'1012' => '22.15.10',

#黒川教員室(1013)
'1013' => '22.13.10',

#黒川研究室(1014)
'1014' => '18.11.10',

#エレベータ(10A,10B)
'5' => '15.13.10', 

#エレベータ(10C,10D)
'6' => '15.15.10', 

# 11F

#西村(広)教員室(1101)
'1101' => '10.6.11',

#春日教員室(1102)
'1102' => '6.6.11',

#共通教員室(1103)
'1103' => '4.6.11',

#富川研究室・山内研究室(1104)
'1104' => '12.11.11',

#富川教員室(1105)
'1105' => '8.13.11',

#谷中教員室(1106)
'1106' => '8.15.11',

#谷中研究室(1107)
'1107' => '12.17.11',

#佐藤研究室・鈴木(浩)研究室(1108)
'1108' => '12.22.11',

#佐藤教員室(1109)
#'1109' => '..11',

#速水教員室(1110)
#'1110' => '..11',

#速水研究室(1111)
'1111' => '18.22.11',

#徳弘研究室(1112)
'1112' => '18.17.11',

#徳弘教員室(1113)
'1113' => '22.15.11',

#服部(元)教員室(1114)
'1114' => '22.13.11',

#服部(元)研究室・小坂研究室(1115)
'1115' => '18.11.11',

#小島研究室(1116)
'1116' => '18.6.11',

#小島教員室(1117)
#'1117' => '..11',

#エレベータ(11A,11B)
'7' => '15.13.11', 

#エレベータ(11C,11D)
'8' => '15.15.11', 

};

Map3d.pm
#########################

package KAIT::Map3d;

BEGIN {
  use base AI::Pathfinding::AStar;
};

use KAIT::init3d;

sub new
{
    my $invocant = shift;
    my $class = ref($invocant) || $invocant;
    my $self = bless {}, $class;

	my @w1 = @{$KAIT::init3d::{FLOOR_DATA}};
	my %pass_symbol = %{$KAIT::init3d::{SYMBOL_PASS}};
	my %corner_symbol = %{$KAIT::init3d::{SYMBOL_CORNER}};
	my %marker_symbol = %{$KAIT::init3d::{SYMBOL_MARKER}};
	
	my %conv1 = (1 => 1, 2 => 2,  3 => 10, 4 => 4, 5 => 11);
	
	my $width = -1;
	my $height = -1;

	$self->{map} = {};
	$self->{symbol} = {};
	$self->{symbol}->{'width'} = $width;
	$self->{symbol}->{'height'} = $height;
	$self->{symbol}->{marker} = {};
	$self->{symbol}->{corner} = {};

	for (my $i = 1; $i <= 5; $i++) {
		my @line = readMap($w1[$i]);
		$height = @line - 1 if ($height < 0);
		
		for (my $ii = 1; $ii <= $height; $ii++) {
	  		chop($line[$ii]);
		}
		$width = length_sjis($line[1]) if ($width < 0);

		$self->{symbol}->{'width'} = $width if ($self->{symbol}->{'width'} < 0);
		$self->{symbol}->{'height'} = $height if ($self->{symbol}->{'height'} < 0);

		my $z = $i;
		for(my $y=1; $y<=$height; $y++) 
		{
    		my $str = $line[$y];
    		my $j = 0;
			for(my $x=1; $x<=$width; $x++)
			{
				my $c = substr($str, $j, 2);
				$self->{symbol}->{$x.'.'.$y.'.'.$z} = $c;
			
				if (exists $pass_symbol{$c}) {
					$self->{map}->{$x.'.'.$y.'.'.$z} = 1;
				}
				else {
					$self->{map}->{$x.'.'.$y.'.'.$z} = 0;
				}
				
				if (exists $marker_symbol{$c}) {
					$self->{symbol}->{marker}->{$x.'.'.$y.'.'.$z} = 1;
				}
				
				if (exists $corner_symbol{$c}) {
					$self->{symbol}->{corner}->{$x.'.'.$y.'.'.$z} = 1;
				}
				
				$j += 2;
			}
		}
	}
	
	
	
    return $self;
}

sub readMap
{
  my ($map_filename) = @_;
  open(FH, $map_filename);
  my @list = <FH>;
  close(FH);
  
  return @list;
}

sub length_sjis {
	my $str = shift;
	my $cnt = 0;
	while( $str =~ m/
		[\x00-\x7F\xA1-\xDF]|
		[\x81-\x9F\xE0-\xFC][\x40-\x7E\x80-\xFC]
		/gx
	) {
		$cnt++;
	}
	return $cnt;
}

#some support routines

sub getOrth
{
	my ($source) = @_;

	my @return = ();
	my ($x, $y, $z) = split(/\./, $source);

	push @return, ($x+1).'.'.$y.'.'.$z, ($x-1).'.'.$y.'.'.$z, $x.'.'.($y+1).'.'.$z, $x.'.'.($y-1).'.'.$z;
	return @return;
}

#get diagonal neightbours
sub getDiag
{
	my ($source) = @_;

	my @return = ();
	my ($x, $y, $z) = split(/\./, $source);

	push @return, ($x+1).'.'.($y+1).'.'.$z, ($x+1).'.'.($y-1).'.'.$z, ($x-1).'.'.($y+1).'.'.$z, ($x-1).'.'.($y-1).'.'.$z;
	return @return;
}

#calculate the Heuristic
sub calcH
{
	my ($source, $target) = @_;

	my ($x1, $y1, $z1) = split(/\./, $source);
	my ($x2, $y2, $z2) = split(/\./, $target);

	return (abs($x1-$x2) + abs($y1-$y2) + abs($z1-$z2));
}

#get Horizon  neighbours
sub getHori
{
	my ($source) = @_;

	my @return = ();
	my ($x, $y, $z) = split(/\./, $source);

	push @return, $x.'.'.$y.'.'.($z+1), $x.'.'.$y.'.'.($z-1);
	return @return;
}


#the routine required by AI::Pathfinding::AStar
sub getSurrounding
{
	my ($self, $source, $target) = @_;

	my %map = %{$self->{map}};
	my ($src_x, $src_y, $src_z) = split(/\./, $source);

	my $surrounding = [];

	#orthogonal moves cost 10, diagonal cost 140
	foreach my $node (getOrth($source))
	{
		if ( (exists $map{$node}) && ($map{$node}) )
			{push @$surrounding, [$node, 10, calcH($node, $target)];}
	}
	foreach my $node (getDiag($source))
	{
		if ( (exists $map{$node}) && ($map{$node}) )
			{push @$surrounding, [$node, 140, calcH($node, $target)];}
	}
	foreach my $node (getHori($source))
	{
		if ( (exists $map{$node}) && ($map{$node}) )
			{push @$surrounding, [$node, 200, calcH($node, $target)];}
	}

	return $surrounding;
}

sub findPath {
	my ($self, $start, $target) = @_;

	my %conv1 = (1 => 1, 10 => 3, 11 => 5);
	my %conv2 = (1 => 1, 3 => 10, 5 => 11);
	
	my %spots_hash = %{$KAIT::init3d::{SPOTS}};
	
	my $start2 = $start;
	$start2 = $spots_hash{$start} unless ($start =~ /^(\d+)\.(\d+)\.(\d+)$/);
	
	my $target2 = $target;
	$target2 = $spots_hash{$target} unless ($target =~ /^(\d+)\.(\d+)\.(\d+)$/);
	
		
	my $x, $y, $z;
	
	($x, $y, $z) = split(/\./, $start2);
	my $s = $x.'.'.$y.'.'.$conv1{$z};
	($x, $y, $z) = split(/\./, $target2);
	my $t = $x.'.'.$y.'.'.$conv1{$z};
	
	my $path0 = $self->SUPER::findPath( $s, $t );
	my $n = @$path0;
	my $dum1, $dum2, $start_z, $target_z;
	
	($dum1, $dum2, $start_z) = split(/\./, $path0->[0]);
	($dum1, $dum2, $target_z) = split(/\./, $path0->[$n-1]);
	
	my $path = [];
	
	for (my $i = 0; $i < $n; $i++) {
		my ($x, $y, $z) = split(/\./, $path0->[$i]);
		if ($z == $start_z || $z == $target_z) {
			push(@$path, $x.'.'.$y.'.'.$conv2{$z});
		}
	}

	return $path;
}

sub getFloor {
	my ($self, $target) = @_;
	
	my %spots_hash = %{$KAIT::init3d::{SPOTS}};
	my $t = $spots_hash{$target};
	
	my $x, $y, $z;
	($x, $y, $z) = split(/\./, $t);
	
	return $z;
}

sub findPath2
{
	my ($self, $path1, $start, $target) = @_;
	
	my %spots_hash = %{$KAIT::init3d::{SPOTS}};
	my $n = @$path1;
	my $x, $y, $z, $f1, $f2, $f;

	($x, $y, $f1) = split(/\./, $path1->[0]);
	($x, $y, $f2) = split(/\./, $path1->[$n-1]);

	my $path2 = [];
	my $s2;
	my $start2;
	for (my $i = 0; $i < $n; $i++) {
		($x, $y, $f) = split(/\./, $path1->[$i]);
		if ($f == $f1) {
			push(@$path2, $path1->[$i]);
		}
		else {
			$s2 = $path1->[$i];
			last;
		}
	}
	
	if ($f2 == 1) {
		if ($spots_hash{'3'} eq $s2) {
			$start2 = $spots_hash{'4'};
		}
		else {
			$start2 = $spots_hash{'3'};
		}
	}
	elsif ($f2 == 10) {
		if ($spots_hash{'5'} eq $s2) {
			$start2 = $spots_hash{'6'};
		}
		else {
			$start2 = $spots_hash{'5'};
		}
	}
	elsif ($f2 == 11) {
		if ($spots_hash{'7'} eq $s2) {
			$start2 = $spots_hash{'8'};
		}
		else {
			$start2 = $spots_hash{'7'};
		}
	}
	
	my $path3 = $self->findPath($start2, $target);
	$n = @$path3;
	for (my $i = 0; $i < $n; $i++) {
		push(@$path2, $path3->[$i]);
	}

	return $path2;
}

sub calcVec
{
	my ($vx, $vy) = @_;
	my $v;
	if ($vx == 0) {
		if ($vy > 0) {
			$v = '↓';
		}
		else {
			$v = '↑';
		}
	}
	else {
		if ($vx > 0) {
			$v = '→';
		}
		else {
			$v = '←';
		}
	}
	
	return $v;
}

sub createNaviData1
{
	my ($self, $path1) = @_;
	
	my @navi = ();
	my %conv1 = (1 => 1, 10 => 3, 11 => 5);
	my %conv2 = (1 => 1, 3 => 10, 5 => 11);
		
	my $width = $self->{symbol}->{'width'};
	my $height = $self->{symbol}->{'height'};
	
	my $x, $y, $z;
	my $n = @$path1;
	my @path = ();
	for (my $i = 0; $i < $n; $i++) {
		($x, $y, $z) = split(/\./, $path1->[$i]);
		push(@path, $x.'.'.$y.'.'.$conv1{$z});
	}
	
	
	# 出発時の進行方向調査
	my $xx1, $yy1, $xx2, $yy2, $zz;
	my $vec1, $vec2;
	my %corner_pat = (
		"→↑" => 7,
		"→↓" => 3,
		"←↑" => 3,
		"←↓" => 7,
		"↑→" => 3,
		"↑←" => 7,
		"↓→" => 7,
		"↓←" => 3,

		"→←" => 5,
		"←→" => 5,
		"↑↓" => 5,
		"↓↑" => 5,

		"→→" => 1,
		"←←" => 1,
		"↑↑" => 1,
		"↓↓" => 1,
	);
	($xx1, $yy1, $zz) = split(/\./, $path[0]);
   	my $mp_x, $mp_y, $mp_z;
   	my @x_off = ( 0, 1, 0, -1 );
   	my @y_off = ( -1, 0, 1, 0 );
   	
   	for (my $i = 0; $i < 4; $i++) {
   		$mp_x = $xx1 + $x_off[$i];
   		$mp_y = $yy1 + $y_off[$i];
		$mp_z = $zz;
		
		if (exists $self->{symbol}->{marker}->{$mp_x.'.'.$mp_y.'.'.$mp_z}) {
		    $vec1 = calcVec($mp_x - $xx1, $mp_y - $yy1);
			last;
		}
   	}
	($xx2, $yy2, $zz) = split(/\./, $path[1]);
	$vec2 = calcVec($xx2 - $xx1, $yy2 - $yy1);
	push(@navi, $corner_pat{$vec1 . $vec2});


	# 角の進行方向調査
	my $cx, $cy;
	for (my $i = 1; $i < ($n-1); $i++) {
		($cx, $cy, $zz) = split(/\./, $path[$i]);
		
		if (exists $self->{symbol}->{corner}->{$cx.'.'.$cy.'.'.$zz}) {
			
			($xx1, $yy1, $zz) = split(/\./, $path[$i-1]);
			($xx2, $yy2, $zz) = split(/\./, $path[$i+1]);

			$vec1 = calcVec($cx - $xx1, $cy - $yy1);
			$vec2 = calcVec($xx2 - $cx, $yy2 - $cy);
			push(@navi, $corner_pat{$vec1 . $vec2});
		}
	}
	
	
	# 目的地の方角調査
	my %direction_pat = (
		"↑" => 1,
		"→" => 3,
		"↓" => 5,
		"←" => 7,
	);
	($xx1, $yy1, $zz) = split(/\./, $path[$n-2]);
	($xx2, $yy2, $zz) = split(/\./, $path[$n-1]);
	 $vec1 = calcVec($xx2 - $xx1, $yy2 - $yy1);
	for (my $i = 0; $i < 4; $i++) {
   		$mp_x = $xx2 + $x_off[$i];
   		$mp_y = $yy2 + $y_off[$i];
		$mp_z = $zz;
		
		if (exists $self->{symbol}->{marker}->{$mp_x.'.'.$mp_y.'.'.$mp_z}) {
		    $vec2 = calcVec($mp_x - $xx2, $mp_y - $yy2);
			last;
		}
   	}
	push(@navi, $corner_pat{$vec1 . $vec2});
	
# -----------------------------------------------	
	my %direction_msg = (
		"1" => "前に進んでください!",
		"3" => "右に進んでください!",
		"5" => "後ろに進んでください!",
		"7" => "左に進んでください!",
	);

	my %target_direction_msg = (
		"1" => "前方に目的地があります!",
		"3" => "右側に目的地があります!",
		"5" => "後方に目的地があります!",
		"7" => "左側に目的地があります!",
	);

	$n = @navi;
	my $output = '<?xml version="1.0" encoding="UTF-8"?>';
	$output = $output . "\n<navi>";

	$output = $output . "\n<path>";

	for (my $i = 0; $i < ($n-1); $i++) {
		$output = $output . "\n<guide>";

		$output = $output . "\n<command>";
		$output = $output . $navi[$i];
		$output = $output . "</command>";
		
		my $navi_msg = $direction_msg{$navi[$i]};
		
		if (($i+1) == $n-1) {
			$navi_msg = $navi_msg . $target_direction_msg{$navi[$i+1]};
		}
		
		$output = $output . "\n<msg>";
		$output = $output . $navi_msg;
		$output = $output . "</msg>";
		
		$output = $output . "\n</guide>";
	}

	$output = $output . "\n</path>";

	$output = $output . "\n</navi>";

	return $output;
}

sub createNaviData2
{
	my ($self, $path1, $path2) = @_;
	
	my %spots_hash = %{$KAIT::init3d::{SPOTS}};
	
	my @navi1 = ();
	my @navi2 = ();
	
	my %conv1 = (1 => 1, 10 => 3, 11 => 5);
	my %conv2 = (1 => 1, 3 => 10, 5 => 11);
		
	my $width = $self->{symbol}->{'width'};
	my $height = $self->{symbol}->{'height'};
	
	my $x, $y, $z;
	my $n = @$path1;
	my @path = ();
	for (my $i = 0; $i < $n; $i++) {
		($x, $y, $z) = split(/\./, $path1->[$i]);
		push(@path, $x.'.'.$y.'.'.$conv1{$z});
	}
	

	my %corner_pat = (
		"→↑" => 7,
		"→↓" => 3,
		"←↑" => 3,
		"←↓" => 7,
		"↑→" => 3,
		"↑←" => 7,
		"↓→" => 7,
		"↓←" => 3,

		"→←" => 5,
		"←→" => 5,
		"↑↓" => 5,
		"↓↑" => 5,

		"→→" => 1,
		"←←" => 1,
		"↑↑" => 1,
		"↓↓" => 1,
	);

	my %direction_pat = (
		"↑" => 1,
		"→" => 3,
		"↓" => 5,
		"←" => 7,
	);
	
	my $xx1, $yy1, $xx2, $yy2, $zz;
	my $vec1, $vec2;
	my $cx, $cy, $ii;
	my $mp_x, $mp_y, $mp_z;
   	my @x_off = ( 0, 1, 0, -1 );
   	my @y_off = ( -1, 0, 1, 0 );

	($xx1, $yy1, $zz) = split(/\./, $path[0]);
	if ($conv2{$zz} == 1) { # 出発が1Fの時
		($x, $y, $z) = split(/\./, $path1->[$n-1]);
		
		if ($path1->[0] eq $spots_hash{'1'}) { #入り口(K2号館側)
			push(@navi1, '-8,'.$z);
		}
		else { #入り口(マクドナルド側)
			push(@navi1, '-2,'.$z);
		}
		
		for ($ii = 1; $ii < $n; $ii++) {
			($x, $y, $z) = split(/\./, $path[$ii]);
			if ($z != $zz) {
				last;
			}
		}
	}
	else {
		# 出発時の進行方向調査
   		for (my $i = 0; $i < 4; $i++) {
   			$mp_x = $xx1 + $x_off[$i];
   			$mp_y = $yy1 + $y_off[$i];
			$mp_z = $zz;
		
			if (exists $self->{symbol}->{marker}->{$mp_x.'.'.$mp_y.'.'.$mp_z}) {
		    	$vec1 = calcVec($mp_x - $xx1, $mp_y - $yy1);
				last;
			}
   		}
		($xx2, $yy2, $z) = split(/\./, $path[1]);
		$vec2 = calcVec($xx2 - $xx1, $yy2 - $yy1);
		push(@navi1, $corner_pat{$vec1 . $vec2});

		# 角の進行方向調査
		for ($ii = 1; $ii < ($n-1); $ii++) {
			($cx, $cy, $z) = split(/\./, $path[$ii]);
			if ($z != $zz) {
				last;
			}
			
			if (exists $self->{symbol}->{corner}->{$cx.'.'.$cy.'.'.$z}) {
			
				($xx1, $yy1, $z) = split(/\./, $path[$ii-1]);
				($xx2, $yy2, $z) = split(/\./, $path[$ii+1]);

				$vec1 = calcVec($cx - $xx1, $cy - $yy1);
				$vec2 = calcVec($xx2 - $cx, $yy2 - $cy);
				push(@navi1, $corner_pat{$vec1 . $vec2});
			}
		}
		
		($x, $y, $z) = split(/\./, $path1->[$n-1]);
		my $nn = @navi1;
		$navi1[$nn - 1] = (-1 * $navi1[$nn - 1]) . ',' . $z;
	}

	# 2番目のフロア
	($xx1, $yy1, $zz) = split(/\./, $path[$ii]);
	if ($conv2{$zz} == 1) { # 目的地が1Fの時
		if ($path1->[$ii] eq $spots_hash{'3'}) { #A,B
			if ($path1->[$n-1] eq $spots_hash{'1'}) { #入り口(K2号館側)
				push(@navi1, '6,1');
				push(@navi1, '1');
			}
			else { #入り口(マクドナルド側)
				push(@navi1, '8,1');
				push(@navi1, '1');
			}
		}
		else { #C,D
			if ($path1->[$n-1] eq $spots_hash{'1'}) { #入り口(K2号館側)
				push(@navi1, '2,2');
				push(@navi1, '1');

			}
			else { #入り口(マクドナルド側)
				push(@navi1, '4,2');
				push(@navi1, '1');
			}
		}
	}
	else {
		# エレベータ降りた後の方向調査
		($cx, $cy, $zz) = split(/\./, $path[$ii+1]);
		($xx2, $yy2, $zz) = split(/\./, $path[$ii+2]);
		$vec1 = calcVec($cx - $xx1, $cy - $yy1);
		$vec2 = calcVec($xx2 - $cx, $yy2 - $cy);
		
		if ($path1->[$ii] eq $spots_hash{'5'} || $path1->[$ii] eq $spots_hash{'7'}) { #A,B
			push(@navi1, $corner_pat{$vec1 . $vec2}.',1');
		}
		else { #C,D
			push(@navi1, $corner_pat{$vec1 . $vec2}.',2');
		}
		
		# 角の進行方向調査
		for (my $i = $ii + 2; $i < ($n-1); $i++) {
			($cx, $cy, $zz) = split(/\./, $path[$i]);
			
			if (exists $self->{symbol}->{corner}->{$cx.'.'.$cy.'.'.$zz}) {
			
				($xx1, $yy1, $zz) = split(/\./, $path[$i-1]);
				($xx2, $yy2, $zz) = split(/\./, $path[$i+1]);

				$vec1 = calcVec($cx - $xx1, $cy - $yy1);
				$vec2 = calcVec($xx2 - $cx, $yy2 - $cy);
				push(@navi1, $corner_pat{$vec1 . $vec2});
			}
		}
		
		# 目的地の方角調査
		($xx1, $yy1, $zz) = split(/\./, $path[$n-2]);
		($xx2, $yy2, $zz) = split(/\./, $path[$n-1]);
	 	$vec1 = calcVec($xx2 - $xx1, $yy2 - $yy1);
		for (my $i = 0; $i < 4; $i++) {
   			$mp_x = $xx2 + $x_off[$i];
   			$mp_y = $yy2 + $y_off[$i];
			$mp_z = $zz;
		
			if (exists $self->{symbol}->{marker}->{$mp_x.'.'.$mp_y.'.'.$mp_z}) {
		    	$vec2 = calcVec($mp_x - $xx2, $mp_y - $yy2);
				last;
			}
   		}
   		push(@navi1, $corner_pat{$vec1 . $vec2});
	}

# ----------------------------------------------------------------------------------
	$n = @$path2;
	@path = ();
	for (my $i = 0; $i < $n; $i++) {
		($x, $y, $z) = split(/\./, $path2->[$i]);
		push(@path, $x.'.'.$y.'.'.$conv1{$z});
	}
	
	($xx1, $yy1, $zz) = split(/\./, $path[0]);
	if ($conv2{$zz} == 1) { # 出発が1Fの時
		($x, $y, $z) = split(/\./, $path2->[$n-1]);
		
		if ($path2->[0] eq $spots_hash{'1'}) { #入り口(K2号館側)
			push(@navi2, '-8,'.$z);
		}
		else { #入り口(マクドナルド側)
			push(@navi2, '-2,'.$z);
		}
		
		for ($ii = 1; $ii < $n; $ii++) {
			($x, $y, $z) = split(/\./, $path[$ii]);
			if ($z != $zz) {
				last;
			}
		}
	}
	else {
		# 出発時の進行方向調査
   		for (my $i = 0; $i < 4; $i++) {
   			$mp_x = $xx1 + $x_off[$i];
   			$mp_y = $yy1 + $y_off[$i];
			$mp_z = $zz;
		
			if (exists $self->{symbol}->{marker}->{$mp_x.'.'.$mp_y.'.'.$mp_z}) {
		    	$vec1 = calcVec($mp_x - $xx1, $mp_y - $yy1);
				last;
			}
   		}
		($xx2, $yy2, $z) = split(/\./, $path[1]);
		$vec2 = calcVec($xx2 - $xx1, $yy2 - $yy1);
		push(@navi2, $corner_pat{$vec1 . $vec2});

		# 角の進行方向調査
		for ($ii = 1; $ii < ($n-1); $ii++) {
			($cx, $cy, $z) = split(/\./, $path[$ii]);
			if ($z != $zz) {
				last;
			}
			
			if (exists $self->{symbol}->{corner}->{$cx.'.'.$cy.'.'.$z}) {
			
				($xx1, $yy1, $z) = split(/\./, $path[$ii-1]);
				($xx2, $yy2, $z) = split(/\./, $path[$ii+1]);

				$vec1 = calcVec($cx - $xx1, $cy - $yy1);
				$vec2 = calcVec($xx2 - $cx, $yy2 - $cy);
				push(@navi2, $corner_pat{$vec1 . $vec2});
			}
		}
		
		($x, $y, $z) = split(/\./, $path2->[$n-1]);
		my $nn = @navi2;
		$navi2[$nn - 1] = (-1 * $navi2[$nn - 1]) . ',' . $z;
	}

	# 2番目のフロア
	($xx1, $yy1, $zz) = split(/\./, $path[$ii]);
	if ($conv2{$zz} == 1) { # 目的地が1Fの時
		if ($path2->[$ii] eq $spots_hash{'3'}) { #A,B
			if ($path2->[$n-1] eq $spots_hash{'1'}) { #入り口(K2号館側)
				push(@navi2, '6,1');
				push(@navi2, '1');
			}
			else { #入り口(マクドナルド側)
				push(@navi2, '8,1');
				push(@navi2, '1');
			}
		}
		else { #C,D
			if ($path2->[$n-1] eq $spots_hash{'1'}) { #入り口(K2号館側)
				push(@navi2, '2,2');
				push(@navi2, '1');

			}
			else { #入り口(マクドナルド側)
				push(@navi2, '4,2');
				push(@navi2, '1');
			}
		}
	}
	else {
		# エレベータ降りた後の方向調査
		($cx, $cy, $zz) = split(/\./, $path[$ii+1]);
		($xx2, $yy2, $zz) = split(/\./, $path[$ii+2]);
		$vec1 = calcVec($cx - $xx1, $cy - $yy1);
		$vec2 = calcVec($xx2 - $cx, $yy2 - $cy);
		
		if ($path2->[$ii] eq $spots_hash{'5'} || $path2->[$ii] eq $spots_hash{'7'}) { #A,B
			push(@navi2, $corner_pat{$vec1 . $vec2}.',1');
		}
		else { #C,D
			push(@navi2, $corner_pat{$vec1 . $vec2}.',2');
		}
		
		# 角の進行方向調査
		for (my $i = $ii + 2; $i < ($n-1); $i++) {
			($cx, $cy, $zz) = split(/\./, $path[$i]);
			
			if (exists $self->{symbol}->{corner}->{$cx.'.'.$cy.'.'.$zz}) {
			
				($xx1, $yy1, $zz) = split(/\./, $path[$i-1]);
				($xx2, $yy2, $zz) = split(/\./, $path[$i+1]);

				$vec1 = calcVec($cx - $xx1, $cy - $yy1);
				$vec2 = calcVec($xx2 - $cx, $yy2 - $cy);
				push(@navi2, $corner_pat{$vec1 . $vec2});
			}
		}
		
		# 目的地の方角調査
		($xx1, $yy1, $zz) = split(/\./, $path[$n-2]);
		($xx2, $yy2, $zz) = split(/\./, $path[$n-1]);
	 	$vec1 = calcVec($xx2 - $xx1, $yy2 - $yy1);
		for (my $i = 0; $i < 4; $i++) {
   			$mp_x = $xx2 + $x_off[$i];
   			$mp_y = $yy2 + $y_off[$i];
			$mp_z = $zz;
		
			if (exists $self->{symbol}->{marker}->{$mp_x.'.'.$mp_y.'.'.$mp_z}) {
		    	$vec2 = calcVec($mp_x - $xx2, $mp_y - $yy2);
				last;
			}
   		}
   		push(@navi2, $corner_pat{$vec1 . $vec2});
	}
	
# ----------------------------------------------------------------------------------	
	my %direction_msg = (
		"1" => "前に進んでください!",
		"3" => "右に進んでください!",
		"5" => "後ろに進んでください!",
		"7" => "左に進んでください!",

		"2" => "右斜め前に進んでください!",
		"8" => "左斜め前に進んでください!",

		"4" => "右斜め後ろに進んでください!",
		"6" => "左斜め後ろに進んでください!",
		
	);

	my %target_direction_msg = (
		"1" => "前方に目的地があります!",
		"3" => "右側に目的地があります!",
		"5" => "後方に目的地があります!",
		"7" => "左側に目的地があります!",
	);
	
	
	my $p1, $p2;
	
	$n = @navi1;

	my $output = '<?xml version="1.0" encoding="UTF-8"?>';
	$output = $output . "\n<navi>";

	$output = $output . "\n<path>";
	
	for (my $i = 0; $i < ($n-1); $i++) {
		if (index($navi1[$i], ',') >= 0) {
			($p1, $p2) = split(/,/, $navi1[$i]);
			if ($p1 < 0) { # エレベータに乗れ
				$output = $output . "\n<guide>";

				$output = $output . "\n<command>" . ((-$p1) + 10) . "</command>";
				my $msg = $direction_msg{-$p1};
				$output = $output . "\n<msg>";
				$output = $output . $msg;
				$output = $output . "</msg>";
				
				$output = $output . "</guide>";

				$output = $output . "\n<guide>";
				$output = $output . "\n<command>0</command>";
				$msg = "エレベータに乗って" . $p2 . "階に行ってください!";
				$msg = $msg . "エレベータ内でカラーバーを撮影してください!";
				
				$output = $output . "\n<msg>";
				$output = $output . $msg;
				$output = $output . "</msg>";
				
				$output = $output . "</guide>";

			}
			else {
				$output = $output . "\n<guide>";
				$output = $output . "\n<command>" . (-$p2) . "</command>";
				$output = $output . "</guide>";

				$output = $output . "\n<guide>";
				$output = $output . "\n<command>" . $p1 . "</command>";
			
				my $msg = $direction_msg{$p1};
				if (($i+1) == ($n-1)) {
					$msg = $msg . $target_direction_msg{$navi1[$i+1]};
				}
				
				$output = $output . "\n<msg>";
				$output = $output . $msg;
				$output = $output . "</msg>";
								
				$output = $output . "</guide>";
			}
		}
		else {
			$output = $output . "\n<guide>";

			$output = $output . "\n<command>";
			$output = $output . $navi1[$i];
			$output = $output . "</command>";
			
			my $msg = $direction_msg{$navi1[$i]};
			if (($i+1) == ($n-1)) {
				$msg = $msg . $target_direction_msg{$navi1[$i+1]};
			}
			$output = $output . "\n<msg>";
			$output = $output . $msg;
			$output = $output . "</msg>";
			
			$output = $output . "</guide>";
		}
	}

	$output = $output . "\n</path>";

	$n = @navi2;

	$output = $output . "\n<path>";
	
	for (my $i = 0; $i < ($n-1); $i++) {
		if (index($navi2[$i], ',') >= 0) {
			($p1, $p2) = split(/,/, $navi2[$i]);
			if ($p1 < 0) { # エレベータに乗れ
				$output = $output . "\n<guide>";

				$output = $output . "\n<command>" . ((-$p1) + 10) . "</command>";
				my $msg = $direction_msg{-$p1};
				$output = $output . "\n<msg>";
				$output = $output . $msg;
				$output = $output . "</msg>";
				
				$output = $output . "</guide>";

				$output = $output . "\n<guide>";
				$output = $output . "\n<command>0</command>";
				$msg = "エレベータに乗って" . $p2 . "階に行ってください!";
				$msg = $msg . "エレベータ内でカラーバーを撮影してください!";
				
				$output = $output . "\n<msg>";
				$output = $output . $msg;
				$output = $output . "</msg>";
				
				$output = $output . "</guide>";

			}
			else {
				$output = $output . "\n<guide>";
				$output = $output . "\n<command>" . (-$p2) . "</command>";
				$output = $output . "</guide>";

				$output = $output . "\n<guide>";
				$output = $output . "\n<command>" . $p1 . "</command>";
			
				my $msg = $direction_msg{$p1};
				if (($i+1) == ($n-1)) {
					$msg = $msg . $target_direction_msg{$navi2[$i+1]};
				}
				
				$output = $output . "\n<msg>";
				$output = $output . $msg;
				$output = $output . "</msg>";
								
				$output = $output . "</guide>";
			}
		}
		else {
			$output = $output . "\n<guide>";

			$output = $output . "\n<command>";
			$output = $output . $navi2[$i];
			$output = $output . "</command>";
			
			my $msg = $direction_msg{$navi2[$i]};
			if (($i+1) == ($n-1)) {
				$msg = $msg . $target_direction_msg{$navi2[$i+1]};
			}
			$output = $output . "\n<msg>";
			$output = $output . $msg;
			$output = $output . "</msg>";
			
			$output = $output . "</guide>";
		}
	}

	$output = $output . "\n</path>";

	$output = $output . "\n</navi>";

	return $output;
}

1;