How do I implement A* search in Go?

A* search is a popular algorithm used in pathfinding and graph traversal. It finds the shortest path between nodes in a weighted graph. Below is a simple implementation of the A* search algorithm in Go.


package main

import (
    "container/heap"
    "fmt"
    "math"
)

// Node represents a single node in the graph
type Node struct {
    Position   [2]int
    G, H, F    float64
    Parent     *Node
}

// PriorityQueue implements heap.Interface
type PriorityQueue []*Node

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].F < pq[j].F }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }

func (pq *PriorityQueue) Push(x interface{}) {
    *pq = append(*pq, x.(*Node))
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[0 : n-1]
    return item
}

func heuristic(a, b [2]int) float64 {
    return math.Abs(float64(a[0]-b[0])) + math.Abs(float64(a[1]-b[1]))
}

func aStar(start, goal [2]int, grid [][]int) ([][2]int, error) {
    openSet := &PriorityQueue{}
    heap.Init(openSet)

    startNode := &Node{Position: start, G: 0, H: heuristic(start, goal), F: heuristic(start, goal)}
    heap.Push(openSet, startNode)

    closedSet := make(map[[2]int]bool)
    cameFrom := make(map[[2]int]*Node)

    directions := [][2]int{
        {1, 0}, {0, 1}, {-1, 0}, {0, -1},
    }

    for openSet.Len() > 0 {
        current := heap.Pop(openSet).(*Node)

        if current.Position == goal {
            path := make([][2]int, 0)
            for n := current; n != nil; n = n.Parent {
                path = append(path, n.Position)
            }
            // Reverse path
            for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
                path[i], path[j] = path[j], path[i]
            }
            return path, nil
        }

        closedSet[current.Position] = true

        for _, dir := range directions {
            neighborPos := [2]int{current.Position[0] + dir[0], current.Position[1] + dir[1]}
            if neighborPos[0] < 0 || neighborPos[0] >= len(grid) || neighborPos[1] < 0 || neighborPos[1] >= len(grid[0]) || grid[neighborPos[0]][neighborPos[1]] == 1 {
                continue // Skip walls or out of bounds
            }

            if closedSet[neighborPos] {
                continue // Skip already evaluated neighbors
            }

            gScore := current.G + 1
            neighborNode := &Node{Position: neighborPos, G: gScore, H: heuristic(neighborPos, goal), F: gScore + heuristic(neighborPos, goal)}
            if _, ok := cameFrom[neighborPos]; !ok {
                cameFrom[neighborPos] = current
                heap.Push(openSet, neighborNode)
            }
        }
    }
    return nil, fmt.Errorf("no path found")
}

func main() {
    grid := [][]int{
        {0, 0, 0, 0, 0},
        {0, 1, 1, 1, 0},
        {0, 0, 0, 1, 0},
        {0, 1, 0, 0, 0},
        {0, 0, 0, 0, 0},
    }
    start := [2]int{0, 0}
    goal := [2]int{4, 4}

    path, err := aStar(start, goal, grid)
    if err != nil {
        fmt.Println(err)
    } else {
        fmt.Println("Path found:", path)
    }
}

How do I implement A* search in Go?

Popular Topics

Recent Languages

How do I implement A* search in Go?

Related Questions

Popular Topics

Recent Languages