3
\$\begingroup\$

This is a generalized A* pathfinder in Go. I am new to the language and am eager for advice about best practices.

In particular, I am not sure if the type assertion I make in Heuristic is the correct way to bind the implementation to the interface.

I have stolen the PriorityQueue type from the package documentation for container/heap.

Implementation

package pathing

import (
    "container/heap"
)

type Node interface {
    Neighbors() []Edge
    Heuristic(goal Node) float64
    Success(goal Node) bool
}

type Action string

type Edge struct {
    dest   Node
    action Action
}

func AStar(start Node, goal Node) []Action {
    seen := make(map[Node]bool)
    openHeap := make(PriorityQueue, 0)
    heap.Init(&openHeap)
    cameFrom := make(map[Node]Edge)
    gScore := make(map[Node]float64)
    fScore := make(map[Node]float64)
    gScore[start] = 0
    fScore[start] = gScore[start] + start.Heuristic(goal)
    heap.Push(&openHeap, &Item{node: start, priority: fScore[start]})
    seen[start] = true
    for {
        node := heap.Pop(&openHeap).(*Item).node
        if node.Success(goal) {
            return reconstructPath(cameFrom, node)
        }
        for _, edge := range node.Neighbors() {
            adj := edge.dest
            action := edge.action
            if seen[adj] {
                continue
            }
            seen[adj] = true
            // reverse the edge for reconstruction
            cameFrom[adj] = Edge{dest: node, action: action}
            // adjacency cost is based on a constant step
            gScore[adj] = gScore[node] + 1
            hScore := adj.Heuristic(goal)
            fScore[adj] = gScore[adj] + hScore
            heap.Push(&openHeap, &Item{node: adj, priority: fScore[adj]})
        }
    }
}

func reconstructPath(cameFrom map[Node]Edge, node Node) []Action {
    if edge, ok := cameFrom[node]; ok {
        return append(reconstructPath(cameFrom, edge.dest), edge.action)
    }
    return make([]Action, 0)
}

Test

package pathing

import (
    "math"
    "testing"
)

type GridNode struct {
    x int8
    y int8
}

const (
    UP    Action = "up"
    DOWN  Action = "down"
    LEFT  Action = "left"
    RIGHT Action = "right"
)

// orthogonal movement
func (node GridNode) Neighbors() []Edge {
    return []Edge{
        Edge{
            dest:   GridNode{node.x + 1, node.y},
            action: "right",
        },
        Edge{
            dest:   GridNode{node.x - 1, node.y},
            action: "left",
        },
        Edge{
            dest:   GridNode{node.x, node.y + 1},
            action: "up",
        },
        Edge{
            dest:   GridNode{node.x, node.y - 1},
            action: "down",
        }}
}

// euclidean norm
func (node GridNode) Heuristic(goal Node) float64 {
    gridGoal := goal.(GridNode)
    return math.Sqrt(math.Pow(float64(gridGoal.x)-float64(node.x), 2) +
        math.Pow(float64(gridGoal.y)-float64(node.y), 2))
}

func (node GridNode) Success(goal Node) bool {
    return node == goal
}

func TestAStar(t *testing.T) {
    start := GridNode{x: 0, y: 0}
    goal := GridNode{x: 4, y: 4}
    path := AStar(start, goal)
    expectedLength := 8
    if len(path) != expectedLength {
        t.Errorf(
            "Expected length %d, was length %d.",
            expectedLength,
            len(path))
    }
}
\$\endgroup\$
  • \$\begingroup\$ I haven't looked it all over yet, but for now since you asked about Heuristic I'll say that the type assertion looks fine (I think there may be ways of structuring this that wouldn't require that but maybe not or it might not be any better). In particular, the two value version of the type assert isn't wanted/needed here because (IMO) you want it to cause a run-time panic if a program error allows for a non-GridNode Node to get there. \$\endgroup\$ – Dave C Jun 21 '15 at 3:42
  • 1
    \$\begingroup\$ Oh, and I also noticed that it might be better to do math.Hypot(float64(gridGoal.x-node.x), float64(gridGoal.y-node.y)). In general if I want to square or cube an integer type I just do x*x or x*x*x rather than math.Pow(float64(x), 2). \$\endgroup\$ – Dave C Jun 21 '15 at 3:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.