Golang 2D网格库实现：高效路径查找与地图导入导出

下面我将介绍一个基于数据导向设计的2D网格库实现，包含高效的路径查找算法(A*)以及地图的导入导出功能。

核心数据结构

package tile

import (
	"encoding/json"
	"errors"
	"math"
)

// 定义瓦片类型
type TileType int

const (
	Empty TileType = iota
	Wall
	Water
	Forest
	Road
)

// 网格单元
type Cell struct {
	Type       TileType
	Weight     float64 // 移动权重(用于路径查找)
	X, Y       int     // 坐标
	Passable   bool    // 是否可通行
	Properties map[string]interface{}
}

// 2D网格地图
type Grid struct {
	Width, Height int
	Cells         [][]*Cell
}

// 新建网格
func NewGrid(width, height int) *Grid {
	grid := &Grid{
		Width:  width,
		Height: height,
		Cells:  make([][]*Cell, height),
	}

	for y := 0; y < height; y++ {
		grid.Cells[y] = make([]*Cell, width)
		for x := 0; x < width; x++ {
			grid.Cells[y][x] = &Cell{
				X:          x,
				Y:          y,
				Type:       Empty,
				Weight:     1.0,
				Passable:   true,
				Properties: make(map[string]interface{}),
			}
		}
	}
	return grid
}

A*路径查找实现

// A*算法节点
type aStarNode struct {
	cell      *Cell
	parent    *aStarNode
	gScore    float64 // 从起点到当前节点的成本
	hScore    float64 // 启发式估计到终点的成本
	fScore    float64 // gScore + hScore
	heapIndex int     // 在堆中的索引
}

// 实现优先队列接口
type priorityQueue []*aStarNode

func (pq priorityQueue) Len() int { return len(pq) }

func (pq priorityQueue) Less(i, j int) bool {
	return pq[i].fScore < pq[j].fScore
}

func (pq priorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].heapIndex = i
	pq[j].heapIndex = j
}

func (pq *priorityQueue) Push(x interface{}) {
	n := len(*pq)
	node := x.(*aStarNode)
	node.heapIndex = n
	*pq = append(*pq, node)
}

func (pq *priorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	node := old[n-1]
	node.heapIndex = -1
	*pq = old[0 : n-1]
	return node
}

// A*路径查找
func (g *Grid) FindPath(startX, startY, endX, endY int) ([]*Cell, error) {
	if !g.isValid(startX, startY) || !g.isValid(endX, endY) {
		return nil, errors.New("invalid start or end position")
	}

	startCell := g.Cells[startY][startX]
	endCell := g.Cells[endY][endX]

	if !startCell.Passable || !endCell.Passable {
		return nil, errors.New("start or end cell is not passable")
	}

	openSet := make(priorityQueue, 0)
	heap.Init(&openSet)

	// 初始化起始节点
	startNode := &aStarNode{
		cell:   startCell,
		gScore: 0,
		hScore: heuristic(startCell, endCell),
		fScore: heuristic(startCell, endCell),
	}
	heap.Push(&openSet, startNode)

	// 记录所有访问过的节点
	cameFrom := make(map[*Cell]*aStarNode)
	gScore := make(map[*Cell]float64)
	gScore[startCell] = 0

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

		if current.cell == endCell {
			return reconstructPath(cameFrom, current), nil
		}

		// 检查所有相邻节点
		for _, neighbor := range g.getNeighbors(current.cell.X, current.cell.Y) {
			if !neighbor.Passable {
				continue
			}

			tentativeGScore := gScore[current.cell] + neighbor.Weight

			if existingGScore, ok := gScore[neighbor]; !ok || tentativeGScore < existingGScore {
				cameFrom[neighbor] = current
				gScore[neighbor] = tentativeGScore

				h := heuristic(neighbor, endCell)
				f := tentativeGScore + h

				// 检查节点是否已经在开放集中
				found := false
				for _, node := range openSet {
					if node.cell == neighbor {
						found = true
						node.gScore = tentativeGScore
						node.hScore = h
						node.fScore = f
						heap.Fix(&openSet, node.heapIndex)
						break
					}
				}

				if !found {
					newNode := &aStarNode{
						cell:   neighbor,
						gScore: tentativeGScore,
						hScore: h,
						fScore: f,
					}
					heap.Push(&openSet, newNode)
				}
			}
		}
	}

	return nil, errors.New("path not found")
}

// 启发式函数(曼哈顿距离)
func heuristic(a, b *Cell) float64 {
	return math.Abs(float64(a.X-b.X)) + math.Abs(float64(a.Y-b.Y))
}

// 重建路径
func reconstructPath(cameFrom map[*Cell]*aStarNode, current *aStarNode) []*Cell {
	path := []*Cell{current.cell}
	for {
		prev, ok := cameFrom[current.cell]
		if !ok {
			break
		}
		path = append([]*Cell{prev.cell}, path...)
		current = prev
	}
	return path
}

// 获取相邻单元格
func (g *Grid) getNeighbors(x, y int) []*Cell {
	neighbors := make([]*Cell, 0, 8)
	directions := [8][2]int{
		{-1, -1}, {0, -1}, {1, -1},
		{-1, 0}, {1, 0},
		{-1, 1}, {0, 1}, {1, 1},
	}

	for _, dir := range directions {
		nx, ny := x+dir[0], y+dir[1]
		if g.isValid(nx, ny) {
			neighbors = append(neighbors, g.Cells[ny][nx])
		}
	}
	return neighbors
}

func (g *Grid) isValid(x, y int) bool {
	return x >= 0 && x < g.Width && y >= 0 && y < g.Height
}

地图导入导出

// 地图JSON结构
type gridJSON struct {
	Width  int            `json:"width"`
	Height int            `json:"height"`
	Cells  [][]cellJSON   `json:"cells"`
}

type cellJSON struct {
	Type       TileType               `json:"type"`
	Weight     float64               `json:"weight"`
	Passable   bool                  `json:"passable"`
	Properties map[string]interface{} `json:"properties"`
}

// 导出为JSON
func (g *Grid) ToJSON() ([]byte, error) {
	gridJSON := gridJSON{
		Width:  g.Width,
		Height: g.Height,
		Cells:  make([][]cellJSON, g.Height),
	}

	for y := 0; y < g.Height; y++ {
		gridJSON.Cells[y] = make([]cellJSON, g.Width)
		for x := 0; x < g.Width; x++ {
			cell := g.Cells[y][x]
			gridJSON.Cells[y][x] = cellJSON{
				Type:       cell.Type,
				Weight:     cell.Weight,
				Passable:   cell.Passable,
				Properties: cell.Properties,
			}
		}
	}

	return json.MarshalIndent(gridJSON, "", "  ")
}

// 从JSON导入
func FromJSON(data []byte) (*Grid, error) {
	var gridJSON gridJSON
	if err := json.Unmarshal(data, &gridJSON); err != nil {
		return nil, err
	}

	grid := NewGrid(gridJSON.Width, gridJSON.Height)

	for y := 0; y < grid.Height; y++ {
		for x := 0; x < grid.Width; x++ {
			cellJSON := gridJSON.Cells[y][x]
			cell := grid.Cells[y][x]
			cell.Type = cellJSON.Type
			cell.Weight = cellJSON.Weight
			cell.Passable = cellJSON.Passable
			cell.Properties = cellJSON.Properties
		}
	}

	return grid, nil
}

使用示例

func main() {
	// 创建10x10网格
	grid := NewGrid(10, 10)
	
	// 设置一些障碍物
	for i := 2; i < 8; i++ {
		grid.Cells[i][5].Type = Wall
		grid.Cells[i][5].Passable = false
	}
	
	// 查找路径
	path, err := grid.FindPath(0, 0, 9, 9)
	if err != nil {
		fmt.Println("Path not found:", err)
		return
	}
	
	fmt.Println("Path found with length:", len(path))
	
	// 导出地图
	jsonData, err := grid.ToJSON()
	if err != nil {
		fmt.Println("Export error:", err)
		return
	}
	
	// 导入地图
	newGrid, err := FromJSON(jsonData)
	if err != nil {
		fmt.Println("Import error:", err)
		return
	}
	
	fmt.Println("Imported grid size:", newGrid.Width, "x", newGrid.Height)
}

性能优化建议

1. 对象池：对于频繁创建/销毁的A*节点，可以使用对象池减少GC压力
2. 内存布局：将单元格数据改为连续内存布局(结构体数组而非指针数组)
3. 并行处理：对于大型地图，可以将地图分块并行处理路径查找
4. 缓存：缓存常用路径查找结果
5. 分层寻路：实现分层寻路(Hierarchical Pathfinding)减少计算量

这个实现提供了基本的2D网格功能，包括高效的A*路径查找和地图的序列化/反序列化。您可以根据需要扩展更多功能，如动态障碍物、区域标记等。