package Astar;

use Map;
use Data::Dumper;
use Time::HiRes qw(usleep);

@path = ();

sub search_nowalls
{
	my(@open)=();
	my($i)=0;
	push @open, [@Map::lady_pos, -1, -1, 0];
	my(@expand,$j);
	for($i=0;$i<@open;$i++)
	{
		# expand the node
		do { splice @open, $i+1; last } if @Map::map[$open[$i]->[1]]->[$open[$i]->[0]] eq "#"; # a TV is found, break and cut off things after TV in the list
		@expand=([-1,0],[1,0],[0,-1],[0,1]);
		map { $expand[$_]->[0] += $open[$i]->[0]; $expand[$_]->[1] += $open[$i]->[1]; } (0..3);

		foreach $j (@expand)
		{
			next if isin($j->[0],$j->[1],@open) != -1;
			next if ($j->[0]<0) || ($j->[0]>=$Map::dimensions[0]) || ($j->[1]<0) || ($j->[1]>=$Map::dimensions[1]);
			push @open, [$j->[0], $j->[1], $open[$i]->[0], $open[$i]->[1], $open[$i]->[4]+1] unless $Map::map[$j->[1]]->[$j->[0]] eq "X";
		}

		&Time::HiRes::usleep(1000);
		
	}
	$i = pop @open;
	do { print "Path not found.\n"; exit 0 } if $Map::map[$i->[1]]->[$i->[0]] ne "#";
	my(@parent)=($i->[2], $i->[3]);
	unshift @path, [$i->[0],$i->[1]];
	while(@open)
	{
		$i = pop @open;
		if(($i->[0] == $parent[0]) && ($i->[1] == $parent[1]))
		{
			@parent = ($i->[2], $i->[3]);
			unshift @path, [$i->[0],$i->[1]];
		}
	}
}

sub isin
{
	my($x,$y,@open)=@_;
	my($i);
	for($i=0;$i<@open;$i++)
	{
		return $i if ($x == $open[$i]->[0]) && ($y == $open[$i]->[1]);
	}
	return -1;

}


42;
