package Waypoint;

use strict;
use warnings;
use include;

use Exporter;
our @ISA = ("Exporter");
our @EXPORT = ("preprock", "euclid", "offset");

sub preprock {
  my $map = shift;
  magnetize($map);
  voronoi($map);
}

sub euclid {
  my ($y1, $x1, $y2, $x2) = @_;
  return sqrt((($y1 - $y2) ** 2) + (($x1 - $x2) ** 2));
}

sub offset {
  my $magnet = shift;
  return ($magnet->[0]{Y} + $magnet->[1], $magnet->[0]{X} + $magnet->[2]);
}

sub magnetize {
  my $map = shift;
  my @mags;
  my $sym = "a";
  foreach my $y (1 .. $map->height - 1) {
    foreach my $x (1 .. $map->width - 1) {
      my $tile = $map->{Map}[$y][$x]{_};
      next unless $tile eq "#";

      if ($map->{Map}[$y][$x-1]{_} eq "." and $map->{Map}[$y][$x+1]{_} eq "#") {
        push @mags, { At => [$y, $x - 1], To => [] };
      }

      if ($map->{Map}[$y][$x+1]{_} eq "." and $map->{Map}[$y][$x-1]{_} eq "#") {
        push @mags, { At => [$y, $x + 1], To => [] };
      }

      if ($map->{Map}[$y-1][$x]{_} eq "." and $map->{Map}[$y+1][$x]{_} eq "#") {
        push @mags, { At => [$y - 1, $x], To => [] };
      }

      if ($map->{Map}[$y+1][$x]{_} eq "." and $map->{Map}[$y-1][$x]{_} eq "#") {
        push @mags, { At => [$y + 1, $x], To => [] };
      }
    }
  }

  foreach my $id (0 .. $#mags) {
    my $mag = $mags[$id];
    # See which other magnets $mag is connectable to.
    foreach my $ID (0 .. $#mags) {
      next if $ID == $id;
      next if scalar(grep /^$ID$/, @{ $mag->{To} }); # Already connected.
      my $MAG = $mags[$ID];
      next unless trace($map, @{ $mag->{At} }, @{ $MAG->{At} });
      push @{ $mag->{To} }, $ID;
      push @{ $MAG->{To} }, $id;
    }
  }

  $map->{Magnets} = \@mags;
}

sub voronoi {
  my $map = shift;
  my @colors = ("red", "green", "Blue", "Red", "Green", "yellow", "purple",
                "cyan", "blue", "Cyan");
  foreach my $y (1 .. $map->height - 1) {
    foreach my $x (1 .. $map->width - 1) {
      next unless $map->{Map}[$y][$x]{_} eq ".";
      # Which wallmagnet are we closest to?
      my $best = [];
      my @ls;
      foreach my $magid (0 .. $#{ $map->{Magnets} }) {
        my $mag = $map->{Magnets}[$magid]{At};
        my $dist = euclid(@$mag, $y, $x);
        push @ls, [$dist, $magid];
      }
      my @newls = sort { $a->[0] <=> $b->[0] } @ls;
      foreach my $id (@newls) {
        my $magnet = $map->{Magnets}[ $id->[1] ]{At};
        # Is this magnet reachable from node ($y, $x)?
        next unless trace($map, $y, $x, @$magnet);
        $map->{Map}[$y][$x]{Ref} = $id->[1];
        $map->mod($y, $x, { color => $colors[ $id->[1] ] });
        last;
      }
    }
  }
}

sub trace {
  my ($map, $y, $x, $y2, $x2) = @_;
  1;
  while (1) {
    my $stuck = 0;
    if ($y > $y2 and $map->{Map}[$y-1][$x]{_} eq ".") {
      $y--;
    } elsif ($y < $y2 and $map->{Map}[$y+1][$x]{_} eq ".") {
      $y++;
    } else {
      $stuck++;
    }
    if ($x > $x2 and $map->{Map}[$y][$x-1]{_} eq ".") {
      $x--;
    } elsif ($x < $x2 and $map->{Map}[$y][$x+1]{_} eq ".") {
      $x++;
    } else {
      $stuck++;
    }
    return 1 if $y == $y2 and $x == $x2;
    return if $stuck == 2;
  }
}

42;