... astar.go to preserve optimality

Moved the check for goal state out of the neighbour expansion loop.

This patch was designed to fix https://github.com/beefsack/go-astar/issues/1

Basic idea is to implement bidirectional a-star, which can (or not) depending on the problem, be more efficient. So there are two priority queues. I thought it would be a nice addition to this package.

However:

• unlike one-directional, it is not guaranteed to find the exact optimal path. this makes it harder to test
• it is solving some tests nicely, but I am still getting some unexpected results, still debugging

The "Found a path to the goal" condition is checked when expanding neighbours. But to be optimal, this condition should be checked for a node freshly popped from the priority queue instead.

Its taking me longer than Id like to produce a failing testcase, but I can show a simple thought experiment that illustrates the problem. It's not as easy to illustrate in the grid world (and Im not even certain I could illustrate it in that world, because it does not use Edge weights), but your algorithm appears to be designed to be more general that just solving the grids.

Consider a world with Nodes and Edges, Edges each having a cost

      E
    /  |
  /    |
S---- M

S=Start E=End M=Middle

Edges: S-E is a giant chasm, cost: 10000 S-M and M-E are paved roads. cost: 1

Currently, astar.go would do this. -Push S onto the Queue -Pop S -Expand neighbors of S using Edges -Neighbor E found. END.

Resulting solution would be S-E cost 10000. But optimal solution is S-M-E, cost 2.

In the example in the README, the methods on Tile use the English spelling of "Neighbour", whereas the interface Pather requires the methods to spell it "Neighbor".

Hi, beefsack. I think the closed and open fields are a bit of a contradiction, so I try to keep it simple. And I removed the head.Remove method, which gave a slight performance improvement.

Benchmark

Original

$ go test -benchmem -benchtime 3s  -bench . astar
goos: windows
goarch: amd64
pkg: astar
cpu: Intel(R) Core(TM) i5-9600KF CPU @ 3.70GHz
BenchmarkLarge-6            2955           1188135 ns/op          542940 B/op       6652 allocs/op
PASS
ok      astar   3.669s

After

$ go test -benchmem -benchtime 3s  -bench . astar
oos: windows
goarch: amd64
pkg: astar
cpu: Intel(R) Core(TM) i5-9600KF CPU @ 3.70GHz
BenchmarkLarge-6            3030           1157325 ns/op          516254 B/op       6652 allocs/op
PASS
ok      astar   3.665s

While defined as func Path(from, to Pather) ..., the resulting path actually starts at to node and ends at from.

This can be seen using this patch to pather_test.go:

diff --git pather_test.go pather_test.go
index b9d78bd..331ee0d 100644
--- pather_test.go
+++ pather_test.go
@@ -159,18 +159,19 @@ func (w World) RenderPath(path []Pather) string {
                return ""
        }
        height := len(w[0])
-       pathLocs := map[string]bool{}
-       for _, p := range path {
+       pathLocs := map[string]rune{}
+       for i, p := range path {
                pT := p.(*Tile)
-               pathLocs[fmt.Sprintf("%d,%d", pT.X, pT.Y)] = true
+               nr := []rune("0123456789abc")[i%12] // "clever" rendering of node index in path.
+               pathLocs[fmt.Sprintf("%d,%d", pT.X, pT.Y)] = nr
        }
        rows := make([]string, height)
        for x := 0; x < width; x++ {
                for y := 0; y < height; y++ {
                        t := w.Tile(x, y)
                        r := ' '
-                       if pathLocs[fmt.Sprintf("%d,%d", x, y)] {
-                               r = KindRunes[KindPath]
+                       if nr := pathLocs[fmt.Sprintf("%d,%d", x, y)]; nr != 0 {
+                               r = nr
                        } else if t != nil {
                                r = KindRunes[t.Kind]
                        }

which renders 0 on T and 9 on F:

=== RUN   TestStraightLine
    path_test.go:14: Input world
        .....~......
        .....MM.....
        .F........T.
        ....MMM.....
        ............
    path_test.go:19: Resulting path
        .....~......
        .....MM.....
        .9876543210.
        ....MMM.....
        ............
--- PASS: TestStraightLine (0.01s)