golang实现A*路径查找算法插件库go-astar的使用

go-astar简介

go-astar是一个用于Go语言的A路径查找算法实现。A算法是一种常用的路径查找算法，以其性能和准确性著称，常用于游戏开发等领域。

示例

图例说明

• . - 平地 (移动成本1)
• ~ - 河流 (移动成本2)
• M - 山脉 (移动成本3)
• X - 障碍物，无法通过
• F - 起点
• T - 终点
• ● - 计算出的路径

直线路径示例

.....~......      .....~......
.....MM.....      .....MM.....
.F........T.  ->  .●●●●●●●●●●.
....MMM.....      ....MMM.....
............      ............

绕过山脉示例

.....~......      .....~......
.....MM.....      .....MM.....
.F..MMMM..T.  ->  .●●●MMMM●●●.
....MMM.....      ...●MMM●●...
............      ...●●●●●....

路径被阻挡示例

............      
.........XXX
.F.......XTX  ->  无法找到路径
.........XXX
............

使用说明

导入包

import "github.com/beefsack/go-astar"

实现Pather接口

需要实现以下三个方法：

type Tile struct{}

// 返回相邻的路径节点
func (t *Tile) PathNeighbors() []astar.Pather {
	return []astar.Pather{
		t.Up(),
		t.Right(),
		t.Down(),
		t.Left(),
	}
}

// 计算到相邻节点的移动成本
func (t *Tile) PathNeighborCost(to astar.Pather) float64 {
	return to.MovementCost
}

// 估算到目标节点的成本(启发式函数)
func (t *Tile) PathEstimatedCost(to astar.Pather) float64 {
	return t.ManhattanDistance(to)
}

调用Path函数

// t1和t2是世界中的*Tile对象
path, distance, found := astar.Path(t1, t2)
if !found {
	log.Println("无法找到路径")
}
// path是一个Pather对象切片，可以转换回*Tile类型

完整示例

下面是一个完整的示例代码，展示如何使用go-astar库：

package main

import (
	"fmt"
	"github.com/beefsack/go-astar"
	"log"
)

// Tile实现Pather接口
type Tile struct {
	X, Y        int
	Kind        string
	MovementCost float64
}

// 定义地图
var world = [][]*Tile{
	{{Kind: "."}, {Kind: "."}, {Kind: "."}, {Kind: "."}, {Kind: "."}},
	{{Kind: "."}, {Kind: "X"}, {Kind: "X"}, {Kind: "X"}, {Kind: "."}},
	{{Kind: "F"}, {Kind: "."}, {Kind: "."}, {Kind: "T"}, {Kind: "."}},
	{{Kind: "."}, {Kind: "X"}, {Kind: "X"}, {Kind: "X"}, {Kind: "."}},
	{{Kind: "."}, {Kind: "."}, {Kind: "."}, {Kind: "."}, {Kind: "."}},
}

func init() {
	// 初始化地图坐标和移动成本
	for y, row := range world {
		for x, tile := range row {
			tile.X = x
			tile.Y = y
			switch tile.Kind {
			case ".":
				tile.MovementCost = 1.0
			case "X":
				tile.MovementCost = 0.0 // 不可通过
			case "F", "T":
				tile.MovementCost = 1.0
			}
		}
	}
}

// 实现Pather接口
func (t *Tile) PathNeighbors() []astar.Pather {
	var neighbors []astar.Pather
	for _, offset := range [][]int{
		{-1, 0}, {1, 0}, {0, -1}, {0, 1},
	} {
		if n := t.getTile(t.X+offset[0], t.Y+offset[1]); n != nil && n.MovementCost > 0 {
			neighbors = append(neighbors, n)
		}
	}
	return neighbors
}

func (t *Tile) PathNeighborCost(to astar.Pather) float64 {
	return to.(*Tile).MovementCost
}

func (t *Tile) PathEstimatedCost(to astar.Pather) float64 {
	toT := to.(*Tile)
	absX := toT.X - t.X
	if absX < 0 {
		absX = -absX
	}
	absY := toT.Y - t.Y
	if absY < 0 {
		absY = -absY
	}
	return float64(absX + absY)
}

func (t *Tile) getTile(x, y int) *Tile {
	if y < 0 || y >= len(world) || x < 0 || x >= len(world[y]) {
		return nil
	}
	return world[y][x]
}

func main() {
	// 查找起点和终点
	var from, to *Tile
	for _, row := range world {
		for _, tile := range row {
			switch tile.Kind {
			case "F":
				from = tile
			case "T":
				to = tile
			}
		}
	}

	// 查找路径
	path, distance, found := astar.Path(from, to)
	if !found {
		log.Fatal("无法找到路径")
	}

	// 打印路径
	fmt.Printf("路径长度: %.0f\n", distance)
	for _, p := range path {
		tile := p.(*Tile)
		fmt.Printf("(%d, %d) ", tile.X, tile.Y)
	}
}

这个示例创建了一个5x5的地图，设置了起点(F)和终点(T)，并使用A*算法找到它们之间的最短路径。