// Copyright ©2015 The Gonum Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package testgraphs

import (
	"math"
	"reflect"
	"testing"

	"gonum.org/v1/gonum/graph"
	"gonum.org/v1/gonum/graph/simple"
)

type changes struct {
	n graph.Node

	new, old []simple.WeightedEdge
}

var limitedVisionTests = []struct {
	g        *Grid
	radius   float64
	diag     bool
	remember bool

	path []graph.Node

	want []changes
}{
	{
		g: NewGridFrom(
			"*..*",
			"**.*",
			"**.*",
			"**.*",
		),
		radius:   1,
		diag:     false,
		remember: false,
		path:     []graph.Node{node(1), node(2), node(6), node(10), node(14)},

		want: []changes{
			{
				n: node(1),
				new: []simple.WeightedEdge{
					{F: simple.Node(0), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(2), W: 1},
					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(1), W: 1},
					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
				},
				old: nil,
			},
			{
				n: node(2),
				new: []simple.WeightedEdge{
					{F: simple.Node(1), T: simple.Node(2), W: 1},
					{F: simple.Node(2), T: simple.Node(1), W: 1},
					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(6), W: 1},
					{F: simple.Node(3), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(2), W: 1},
				},
				old: nil,
			},
			{
				n: node(6),
				new: []simple.WeightedEdge{
					{F: simple.Node(2), T: simple.Node(6), W: 1},
					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(2), W: 1},
					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(10), W: 1},
					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(6), W: 1},
				},
				old: nil,
			},
			{
				n: node(10),
				new: []simple.WeightedEdge{
					{F: simple.Node(6), T: simple.Node(10), W: 1},
					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(6), W: 1},
					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(14), W: 1},
					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(10), W: 1},
				},
				old: nil,
			},
			{
				n: node(14),
				new: []simple.WeightedEdge{
					{F: simple.Node(10), T: simple.Node(14), W: 1},
					{F: simple.Node(13), T: simple.Node(14), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(10), W: 1},
					{F: simple.Node(14), T: simple.Node(13), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(15), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(14), W: math.Inf(1)},
				},
				old: nil,
			},
		},
	},
	{
		g: NewGridFrom(
			"*..*",
			"**.*",
			"**.*",
			"**.*",
		),
		radius:   1.5,
		diag:     false,
		remember: false,
		path:     []graph.Node{node(1), node(2), node(6), node(10), node(14)},

		want: []changes{
			{
				n: node(1),
				new: []simple.WeightedEdge{
					{F: simple.Node(0), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(0), T: simple.Node(4), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(2), W: 1},
					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(1), W: 1},
					{F: simple.Node(2), T: simple.Node(6), W: 1},
					{F: simple.Node(4), T: simple.Node(0), W: math.Inf(1)},
					{F: simple.Node(4), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(4), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(2), W: 1},
					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
				},
				old: nil,
			},
			{
				n: node(2),
				new: []simple.WeightedEdge{
					{F: simple.Node(1), T: simple.Node(2), W: 1},
					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(1), W: 1},
					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(6), W: 1},
					{F: simple.Node(3), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(3), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(2), W: 1},
					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
				},
				old: nil,
			},
			{
				n: node(6),
				new: []simple.WeightedEdge{
					{F: simple.Node(1), T: simple.Node(2), W: 1},
					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(1), W: 1},
					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(6), W: 1},
					{F: simple.Node(3), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(3), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(2), W: 1},
					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(10), W: 1},
					{F: simple.Node(7), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(6), W: 1},
					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
				},
				old: nil,
			},
			{
				n: node(10),
				new: []simple.WeightedEdge{
					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(10), W: 1},
					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(13), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(6), W: 1},
					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(14), W: 1},
					{F: simple.Node(11), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(15), W: math.Inf(1)},
					{F: simple.Node(13), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(13), T: simple.Node(14), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(10), W: 1},
					{F: simple.Node(14), T: simple.Node(13), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(15), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(14), W: math.Inf(1)},
				},
				old: nil,
			},
			{
				n: node(14),
				new: []simple.WeightedEdge{
					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(13), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(14), W: 1},
					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(15), W: math.Inf(1)},
					{F: simple.Node(13), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(13), T: simple.Node(14), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(10), W: 1},
					{F: simple.Node(14), T: simple.Node(13), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(15), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(14), W: math.Inf(1)},
				},
				old: nil,
			},
		},
	},
	{
		g: NewGridFrom(
			"*..*",
			"**.*",
			"**.*",
			"**.*",
		),
		radius:   1,
		diag:     false,
		remember: true,
		path:     []graph.Node{node(1), node(2), node(6), node(10), node(14)},

		want: []changes{
			{
				n: node(1),
				new: []simple.WeightedEdge{
					{F: simple.Node(0), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(2), W: 1},
					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(1), W: 1},
					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
				},
				old: nil,
			},
			{
				n: node(2),
				new: []simple.WeightedEdge{
					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(6), W: 1},
					{F: simple.Node(3), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(2), W: 1},
					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
				},
				old: []simple.WeightedEdge{
					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(2), W: 1},
					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(1), W: 1},
				},
			},
			{
				n: node(6),
				new: []simple.WeightedEdge{
					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(10), W: 1},
					{F: simple.Node(7), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(6), W: 1},
				},
				old: []simple.WeightedEdge{
					{F: simple.Node(2), T: simple.Node(1), W: 1},
					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(6), W: 1},
					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(2), W: 1},
					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
				},
			},
			{
				n: node(10),
				new: []simple.WeightedEdge{
					{F: simple.Node(9), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(14), W: 1},
					{F: simple.Node(11), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(10), W: 1},
				},
				old: []simple.WeightedEdge{
					{F: simple.Node(6), T: simple.Node(2), W: 1},
					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(10), W: 1},
					{F: simple.Node(10), T: simple.Node(6), W: 1},
				},
			},
			{
				n: node(14),
				new: []simple.WeightedEdge{
					{F: simple.Node(13), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(13), T: simple.Node(14), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(13), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(15), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(14), W: math.Inf(1)},
				},
				old: []simple.WeightedEdge{
					{F: simple.Node(10), T: simple.Node(6), W: 1},
					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(14), W: 1},
					{F: simple.Node(14), T: simple.Node(10), W: 1},
				},
			},
		},
	},
	{
		g: NewGridFrom(
			"*..*",
			"**.*",
			"**.*",
			"**.*",
		),
		radius:   1.5,
		diag:     false,
		remember: true,
		path:     []graph.Node{node(1), node(2), node(6), node(10), node(14)},

		want: []changes{
			{
				n: node(1),
				new: []simple.WeightedEdge{
					{F: simple.Node(0), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(0), T: simple.Node(4), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(2), W: 1},
					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(1), W: 1},
					{F: simple.Node(2), T: simple.Node(6), W: 1},
					{F: simple.Node(4), T: simple.Node(0), W: math.Inf(1)},
					{F: simple.Node(4), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(4), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(2), W: 1},
					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
				},
				old: nil,
			},
			{
				n: node(2),
				new: []simple.WeightedEdge{
					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(3), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(3), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
				},
				old: []simple.WeightedEdge{
					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(2), W: 1},
					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(1), W: 1},
					{F: simple.Node(2), T: simple.Node(6), W: 1},
					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(4), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(2), W: 1},
					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
				},
			},
			{
				n: node(6),
				new: []simple.WeightedEdge{
					{F: simple.Node(5), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(10), W: 1},
					{F: simple.Node(7), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(6), W: 1},
					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
				},
				old: []simple.WeightedEdge{
					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(2), W: 1},
					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(1), W: 1},
					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(6), W: 1},
					{F: simple.Node(3), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(3), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(4), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(2), W: 1},
					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
				},
			},
			{
				n: node(10),
				new: []simple.WeightedEdge{
					{F: simple.Node(9), T: simple.Node(13), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(14), W: 1},
					{F: simple.Node(11), T: simple.Node(15), W: math.Inf(1)},
					{F: simple.Node(13), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(13), T: simple.Node(14), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(10), W: 1},
					{F: simple.Node(14), T: simple.Node(13), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(15), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(14), W: math.Inf(1)},
				},
				old: []simple.WeightedEdge{
					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(4), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(2), W: 1},
					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(10), W: 1},
					{F: simple.Node(7), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(6), W: 1},
					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
				},
			},
			{
				n:   node(14),
				new: nil,
				old: []simple.WeightedEdge{
					{F: simple.Node(9), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(13), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(6), W: 1},
					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(14), W: 1},
					{F: simple.Node(11), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(15), W: math.Inf(1)},
					{F: simple.Node(13), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(13), T: simple.Node(14), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(10), W: 1},
					{F: simple.Node(14), T: simple.Node(13), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(15), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(14), W: math.Inf(1)},
				},
			},
		},
	},
	{
		g: NewGridFrom(
			"*..*",
			"**.*",
			"**.*",
			"**.*",
		),
		radius:   1,
		diag:     true,
		remember: false,
		path:     []graph.Node{node(1), node(2), node(6), node(10), node(14)},

		want: []changes{
			{
				n: node(1),
				new: []simple.WeightedEdge{
					{F: simple.Node(0), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(0), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(2), W: 1},
					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(1), W: 1},
					{F: simple.Node(2), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(0), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(2), W: math.Inf(1)},
				},
				old: nil,
			},
			{
				n: node(2),
				new: []simple.WeightedEdge{
					{F: simple.Node(1), T: simple.Node(2), W: 1},
					{F: simple.Node(1), T: simple.Node(6), W: math.Sqrt2},
					{F: simple.Node(2), T: simple.Node(1), W: 1},
					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(6), W: 1},
					{F: simple.Node(3), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(3), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(1), W: math.Sqrt2},
					{F: simple.Node(6), T: simple.Node(2), W: 1},
					{F: simple.Node(6), T: simple.Node(3), W: math.Inf(1)},
				},
				old: nil,
			},
			{
				n: node(6),
				new: []simple.WeightedEdge{
					{F: simple.Node(2), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(6), W: 1},
					{F: simple.Node(2), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(2), W: 1},
					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(10), W: 1},
					{F: simple.Node(7), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(6), W: 1},
					{F: simple.Node(10), T: simple.Node(7), W: math.Inf(1)},
				},
				old: nil,
			},
			{
				n: node(10),
				new: []simple.WeightedEdge{
					{F: simple.Node(6), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(10), W: 1},
					{F: simple.Node(6), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(14), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(6), W: 1},
					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(14), W: 1},
					{F: simple.Node(11), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(14), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(10), W: 1},
					{F: simple.Node(14), T: simple.Node(11), W: math.Inf(1)},
				},
				old: nil,
			},
			{
				n: node(14),
				new: []simple.WeightedEdge{
					{F: simple.Node(10), T: simple.Node(13), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(14), W: 1},
					{F: simple.Node(10), T: simple.Node(15), W: math.Inf(1)},
					{F: simple.Node(13), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(13), T: simple.Node(14), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(10), W: 1},
					{F: simple.Node(14), T: simple.Node(13), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(15), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(14), W: math.Inf(1)},
				},
				old: nil,
			},
		},
	},
	{
		g: NewGridFrom(
			"*..*",
			"**.*",
			"**.*",
			"**.*",
		),
		radius:   1.5,
		diag:     true,
		remember: false,
		path:     []graph.Node{node(1), node(2), node(6), node(10), node(14)},

		want: []changes{
			{
				n: node(1),
				new: []simple.WeightedEdge{
					{F: simple.Node(0), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(0), T: simple.Node(4), W: math.Inf(1)},
					{F: simple.Node(0), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(2), W: 1},
					{F: simple.Node(1), T: simple.Node(4), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(6), W: math.Sqrt2},
					{F: simple.Node(2), T: simple.Node(1), W: 1},
					{F: simple.Node(2), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(6), W: 1},
					{F: simple.Node(4), T: simple.Node(0), W: math.Inf(1)},
					{F: simple.Node(4), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(4), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(0), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(4), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(1), W: math.Sqrt2},
					{F: simple.Node(6), T: simple.Node(2), W: 1},
					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
				},
				old: nil,
			},
			{
				n: node(2),
				new: []simple.WeightedEdge{
					{F: simple.Node(1), T: simple.Node(2), W: 1},
					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(6), W: math.Sqrt2},
					{F: simple.Node(2), T: simple.Node(1), W: 1},
					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(6), W: 1},
					{F: simple.Node(2), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(3), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(3), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(3), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(1), W: math.Sqrt2},
					{F: simple.Node(6), T: simple.Node(2), W: 1},
					{F: simple.Node(6), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
				},
				old: nil,
			},
			{
				n: node(6),
				new: []simple.WeightedEdge{
					{F: simple.Node(1), T: simple.Node(2), W: 1},
					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(6), W: math.Sqrt2},
					{F: simple.Node(2), T: simple.Node(1), W: 1},
					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(6), W: 1},
					{F: simple.Node(2), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(3), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(3), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(3), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(1), W: math.Sqrt2},
					{F: simple.Node(6), T: simple.Node(2), W: 1},
					{F: simple.Node(6), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(10), W: 1},
					{F: simple.Node(6), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(6), W: 1},
					{F: simple.Node(10), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
				},
				old: nil,
			},
			{
				n: node(10),
				new: []simple.WeightedEdge{
					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(10), W: 1},
					{F: simple.Node(6), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(13), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(14), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(6), W: 1},
					{F: simple.Node(10), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(13), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(14), W: 1},
					{F: simple.Node(10), T: simple.Node(15), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(14), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(15), W: math.Inf(1)},
					{F: simple.Node(13), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(13), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(13), T: simple.Node(14), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(10), W: 1},
					{F: simple.Node(14), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(13), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(15), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(14), W: math.Inf(1)},
				},
				old: nil,
			},
			{
				n: node(14),
				new: []simple.WeightedEdge{
					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(13), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(14), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(13), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(14), W: 1},
					{F: simple.Node(10), T: simple.Node(15), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(14), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(15), W: math.Inf(1)},
					{F: simple.Node(13), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(13), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(13), T: simple.Node(14), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(10), W: 1},
					{F: simple.Node(14), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(13), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(15), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(14), W: math.Inf(1)},
				},
				old: nil,
			},
		},
	},
	{
		g: NewGridFrom(
			"*..*",
			"**.*",
			"**.*",
			"**.*",
		),
		radius:   1,
		diag:     true,
		remember: true,
		path:     []graph.Node{node(1), node(2), node(6), node(10), node(14)},

		want: []changes{
			{
				n: node(1),
				new: []simple.WeightedEdge{
					{F: simple.Node(0), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(0), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(2), W: 1},
					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(1), W: 1},
					{F: simple.Node(2), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(0), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(2), W: math.Inf(1)},
				},
				old: nil,
			},
			{
				n: node(2),
				new: []simple.WeightedEdge{
					{F: simple.Node(1), T: simple.Node(6), W: math.Sqrt2},
					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(6), W: 1},
					{F: simple.Node(3), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(3), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(1), W: math.Sqrt2},
					{F: simple.Node(6), T: simple.Node(2), W: 1},
					{F: simple.Node(6), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
				},
				old: []simple.WeightedEdge{
					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(2), W: 1},
					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(1), W: 1},
					{F: simple.Node(2), T: simple.Node(5), W: math.Inf(1)},
				},
			},
			{
				n: node(6),
				new: []simple.WeightedEdge{
					{F: simple.Node(2), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(10), W: 1},
					{F: simple.Node(7), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(6), W: 1},
					{F: simple.Node(10), T: simple.Node(7), W: math.Inf(1)},
				},
				old: []simple.WeightedEdge{
					{F: simple.Node(2), T: simple.Node(1), W: 1},
					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(6), W: 1},
					{F: simple.Node(5), T: simple.Node(0), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(1), W: math.Sqrt2},
					{F: simple.Node(6), T: simple.Node(2), W: 1},
					{F: simple.Node(6), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
				},
			},
			{
				n: node(10),
				new: []simple.WeightedEdge{
					{F: simple.Node(6), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(14), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(14), W: 1},
					{F: simple.Node(11), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(14), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(10), W: 1},
					{F: simple.Node(14), T: simple.Node(11), W: math.Inf(1)},
				},
				old: []simple.WeightedEdge{
					{F: simple.Node(6), T: simple.Node(1), W: math.Sqrt2},
					{F: simple.Node(6), T: simple.Node(2), W: 1},
					{F: simple.Node(6), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(10), W: 1},
					{F: simple.Node(10), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(6), W: 1},
					{F: simple.Node(10), T: simple.Node(7), W: math.Inf(1)},
				},
			},
			{
				n: node(14),
				new: []simple.WeightedEdge{
					{F: simple.Node(10), T: simple.Node(13), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(15), W: math.Inf(1)},
					{F: simple.Node(13), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(13), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(13), T: simple.Node(14), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(13), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(15), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(14), W: math.Inf(1)},
				},
				old: []simple.WeightedEdge{
					{F: simple.Node(10), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(6), W: 1},
					{F: simple.Node(10), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(14), W: 1},
					{F: simple.Node(14), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(10), W: 1},
					{F: simple.Node(14), T: simple.Node(11), W: math.Inf(1)},
				},
			},
		},
	},
	{
		g: NewGridFrom(
			"*..*",
			"**.*",
			"**.*",
			"**.*",
		),
		radius:   1.5,
		diag:     true,
		remember: true,
		path:     []graph.Node{node(1), node(2), node(6), node(10), node(14)},

		want: []changes{
			{
				n: node(1),
				new: []simple.WeightedEdge{
					{F: simple.Node(0), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(0), T: simple.Node(4), W: math.Inf(1)},
					{F: simple.Node(0), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(2), W: 1},
					{F: simple.Node(1), T: simple.Node(4), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(6), W: math.Sqrt2},
					{F: simple.Node(2), T: simple.Node(1), W: 1},
					{F: simple.Node(2), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(6), W: 1},
					{F: simple.Node(4), T: simple.Node(0), W: math.Inf(1)},
					{F: simple.Node(4), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(4), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(0), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(4), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(1), W: math.Sqrt2},
					{F: simple.Node(6), T: simple.Node(2), W: 1},
					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
				},
				old: nil,
			},
			{
				n: node(2),
				new: []simple.WeightedEdge{
					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(3), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(3), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(3), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
				},
				old: []simple.WeightedEdge{
					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(2), W: 1},
					{F: simple.Node(1), T: simple.Node(4), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(6), W: math.Sqrt2},
					{F: simple.Node(2), T: simple.Node(1), W: 1},
					{F: simple.Node(2), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(6), W: 1},
					{F: simple.Node(5), T: simple.Node(0), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(4), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(1), W: math.Sqrt2},
					{F: simple.Node(6), T: simple.Node(2), W: 1},
					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
				},
			},
			{
				n: node(6),
				new: []simple.WeightedEdge{
					{F: simple.Node(5), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(10), W: 1},
					{F: simple.Node(6), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(4), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(6), W: 1},
					{F: simple.Node(10), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
				},
				old: []simple.WeightedEdge{
					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(2), W: 1},
					{F: simple.Node(1), T: simple.Node(4), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(1), T: simple.Node(6), W: math.Sqrt2},
					{F: simple.Node(2), T: simple.Node(1), W: 1},
					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(2), T: simple.Node(6), W: 1},
					{F: simple.Node(2), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(3), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(3), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(3), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(0), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(4), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(1), W: math.Sqrt2},
					{F: simple.Node(6), T: simple.Node(2), W: 1},
					{F: simple.Node(6), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
				},
			},
			{
				n: node(10),
				new: []simple.WeightedEdge{
					{F: simple.Node(9), T: simple.Node(13), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(14), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(13), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(14), W: 1},
					{F: simple.Node(10), T: simple.Node(15), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(14), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(15), W: math.Inf(1)},
					{F: simple.Node(13), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(13), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(13), T: simple.Node(14), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(10), W: 1},
					{F: simple.Node(14), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(13), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(15), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(14), W: math.Inf(1)},
				},
				old: []simple.WeightedEdge{
					{F: simple.Node(5), T: simple.Node(0), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(4), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(5), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(1), W: math.Sqrt2},
					{F: simple.Node(6), T: simple.Node(2), W: 1},
					{F: simple.Node(6), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(6), T: simple.Node(10), W: 1},
					{F: simple.Node(6), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(2), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(3), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(7), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(4), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(6), W: 1},
					{F: simple.Node(10), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
				},
			},
			{
				n:   node(14),
				new: nil,
				old: []simple.WeightedEdge{
					{F: simple.Node(9), T: simple.Node(4), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(13), W: math.Inf(1)},
					{F: simple.Node(9), T: simple.Node(14), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(5), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(6), W: 1},
					{F: simple.Node(10), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(13), W: math.Inf(1)},
					{F: simple.Node(10), T: simple.Node(14), W: 1},
					{F: simple.Node(10), T: simple.Node(15), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(6), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(7), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(14), W: math.Inf(1)},
					{F: simple.Node(11), T: simple.Node(15), W: math.Inf(1)},
					{F: simple.Node(13), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(13), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(13), T: simple.Node(14), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(9), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(10), W: 1},
					{F: simple.Node(14), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(13), W: math.Inf(1)},
					{F: simple.Node(14), T: simple.Node(15), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(10), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(11), W: math.Inf(1)},
					{F: simple.Node(15), T: simple.Node(14), W: math.Inf(1)},
				},
			},
		},
	},
}

func TestLimitedVisionGrid(t *testing.T) {
	t.Parallel()
	for i, test := range limitedVisionTests {
		l := &LimitedVisionGrid{
			Grid:         test.g,
			VisionRadius: test.radius,
			Location:     test.path[0],
		}
		if test.remember {
			l.Known = make(map[int64]bool)
		}
		l.Grid.AllowDiagonal = test.diag

		x, y := l.XY(test.path[0].ID())
		nodes := graph.NodesOf(l.Nodes())
		for _, u := range nodes {
			uid := u.ID()
			ux, uy := l.XY(uid)
			uNear := math.Hypot(x-ux, y-uy) <= test.radius
			for _, v := range nodes {
				vid := v.ID()
				vx, vy := l.XY(vid)
				vNear := math.Hypot(x-vx, y-vy) <= test.radius
				if u.ID() == v.ID() && l.HasEdgeBetween(uid, vid) {
					t.Errorf("unexpected self edge: %v -- %v", u, v)
				}
				if !uNear && !vNear && !l.HasEdgeBetween(uid, vid) && couldConnectIn(l, uid, vid) {
					t.Errorf("unexpected pessimism: no hope in distant edge between %v and %v for test %d",
						u, v, i)
				}
				if (uNear && vNear) && l.HasEdgeBetween(uid, vid) != l.Grid.HasEdgeBetween(uid, vid) {
					t.Errorf("unrealistic optimism: disagreement about edge between %v and %v for test %d: got:%t want:%t",
						u, v, i, l.HasEdgeBetween(uid, vid), l.Grid.HasEdgeBetween(uid, vid))
				}
			}
		}

		var got []changes
		for _, n := range test.path {
			new, old := l.MoveTo(n)
			got = append(got, changes{n: n, new: asConcreteEdges(new, l), old: asConcreteEdges(old, l)})
		}
		if !reflect.DeepEqual(got, test.want) {
			t.Errorf("unexpected walk for test %d:\ngot: %+v\nwant:%+v", i, got, test.want)
		}
	}
}

func asConcreteEdges(changes []graph.Edge, in graph.Weighted) []simple.WeightedEdge {
	if changes == nil {
		return nil
	}
	we := make([]simple.WeightedEdge, len(changes))
	for i, e := range changes {
		we[i].F = e.From()
		we[i].T = e.To()
		w, ok := in.Weight(e.From().ID(), e.To().ID())
		if !ok && !math.IsInf(w, 1) {
			panic("unexpected invalid finite weight")
		}
		we[i].W = w
	}
	return we
}

func couldConnectIn(l *LimitedVisionGrid, uid, vid int64) bool {
	if uid == vid {
		return false
	}

	ur, uc := l.RowCol(uid)
	vr, vc := l.RowCol(vid)
	if abs(ur-vr) > 1 || abs(uc-vc) > 1 {
		return false
	}
	if (ur != vr || uc != vc) && !l.Grid.AllowDiagonal {
		return false
	}

	if !l.Known[uid] && !l.Known[vid] {
		return true
	}
	if l.Known[uid] && !l.Grid.HasOpen(uid) {
		return false
	}
	if l.Known[vid] && !l.Grid.HasOpen(vid) {
		return false
	}

	return true
}