A算法详解（go实现）

四、go语言代码实现

package main

import (
	"fmt"
	"math"
	"sort"
	"strings"
)

var openlist []*open
var closelist []*pos

func isIncloselist(x, y int) bool {
	for _, pos := range closelist {
		if pos.y == y && pos.x == x {
			return true
		}
	}
	return false
}

func isInopenlist(x, y int) (*open, bool) {
	for _, o := range openlist {
		if o.pos.y == y && o.pos.x == x {
			return o, true
		}
	}
	return nil, false
}

type open struct {
	parent *open
	pos    *pos
	f      int
	g      int
	h      int
}

type pos struct {
	x    int
	y    int
	view string
}

type maps struct {
	with   int
	height int
	zones  []*pos
}

// findAstarPaths A星寻路算法获取地图中起始点至终点的路径
func (m *maps) findAstarPaths(startX, startY, endX, endY int) []*pos {
	defer func() {
		openlist = nil
		closelist = nil
	}()

	startPos := m.getpos(startX, startY)
	endPos := m.getpos(endX, endY)
	if startPos == nil || endPos == nil || endPos.view == "X" || startPos.view == "X" {
		return nil
	}
	if startPos.x == endPos.x && startPos.y == endPos.y {
		return []*pos{startPos}
	}

	openlist = append(openlist, &open{pos: startPos})
	var lastopen *open
	for len(openlist) > 0 {
		// 找到最小的F值的点
		sort.Slice(openlist, func(i, j int) bool { return openlist[i].f < openlist[j].f })
		minopen := openlist[0]
		openlist = openlist[1:]
		closelist = append(closelist, minopen.pos)

		// 1、找到F点周围的点（八个方向）如果是墙或在closelist中或超出地图范围则跳过
		// 2、如果在openlist中则判断G值是否比之前大，如果是则不处理，否则更新这个点的父亲节点为当前节点并重新计算F值
		// 3、如果终点已经在openlist中说明已经找到最优路径，退出查找
		/** 上 **/
		lastopen = m.findLastOpen(minopen, minopen.pos.x, minopen.pos.y-1, endX, endY, 10)
		if lastopen != nil {
			break
		}

		/** 下 **/
		lastopen = m.findLastOpen(minopen, minopen.pos.x, minopen.pos.y+1, endX, endY, 10)
		if lastopen != nil {
			break
		}

		/** 左 **/
		lastopen = m.findLastOpen(minopen, minopen.pos.x-1, minopen.pos.y, endX, endY, 10)
		if lastopen != nil {
			break
		}

		/** 右 **/
		lastopen = m.findLastOpen(minopen, minopen.pos.x+1, minopen.pos.y, endX, endY, 10)
		if lastopen != nil {
			break
		}

		/** 左上 **/
		lastopen = m.findLastOpen(minopen, minopen.pos.x-1, minopen.pos.y-1, endX, endY, 14)
		if lastopen != nil {
			break
		}

		/** 左下 **/
		lastopen = m.findLastOpen(minopen, minopen.pos.x-1, minopen.pos.y+1, endX, endY, 14)
		if lastopen != nil {
			break
		}

		/** 右上 **/
		lastopen = m.findLastOpen(minopen, minopen.pos.x+1, minopen.pos.y-1, endX, endY, 14)
		if lastopen != nil {
			break
		}

		/** 右下 **/
		lastopen = m.findLastOpen(minopen, minopen.pos.x+1, minopen.pos.y+1, endX, endY, 14)
		if lastopen != nil {
			break
		}
	}

	if lastopen == nil {
		return nil
	}

	var paths []*pos
	for lastopen != nil {
		if len(paths) == 0 {
			paths = append(paths, lastopen.pos)
		} else {
			tmp := make([]*pos, len(paths)+1)
			tmp[0] = lastopen.pos
			copy(tmp[1:], paths)
			paths = tmp
		}
		lastopen = lastopen.parent
	}
	return paths
}

func (m *maps) print() {
	for y := 0; y < m.height; y++ {
		for x := 0; x < m.with; x++ {
			fmt.Print(" " + m.getpos(x, y).view + " ")
		}
		fmt.Println()
	}
}

func (m *maps) getpos(x, y int) *pos {
	if x < 0 || y < 0 || x >= m.with || y >= m.height {
		return nil
	}
	for _, pos := range m.zones {
		if pos.y == y && pos.x == x {
			return pos
		}
	}
	return nil
}

func (m *maps) updateView(x, y int, view string) {
	p := m.getpos(x, y)
	if p != nil {
		p.view = view
	}
}

func (m *maps) findLastOpen(minopen *open, findX, findY, endX, endY int, gval int) *open {
	if findX == endX && findY == endY {
		return &open{pos: m.getpos(endX, endY), parent: minopen}
	}

	findPos := m.getpos(findX, findY)
	if findPos == nil || findPos.view != "O" || isIncloselist(findX, findY) {
		return nil
	}

	currentopen := &open{
		pos: findPos,
		g:   minopen.g + gval,
	}
	currentopen.h = int(math.Abs(float64(endY-currentopen.pos.y))*10 + math.Abs(float64(endX-currentopen.pos.x)*10))
	currentopen.f = currentopen.h + currentopen.g
	currentopen.parent = minopen

	// 判断是否在opendlist中
	open, b := isInopenlist(findX, findY)
	if b {
		if open.g > currentopen.g {
			open.parent = minopen
			open.g = currentopen.g
			open.f = open.g + open.h
		}
	} else {
		openlist = append(openlist, currentopen)
	}
	return nil
}

func newMaps(arr []string) *maps {
	m := &maps{
		with:   len(strings.Split(arr[0], " ")),
		height: len(arr),
	}
	for y := 0; y < m.height; y++ {
		viewArr := strings.Split(arr[y], " ")
		for x := 0; x < m.with; x++ {
			m.zones = append(m.zones, &pos{x, y, viewArr[x]})
		}
	}

	return m
}

func main() {
	arr := []string{
		"O X O O X",
		"O O O X O",
		"O X X O O",
		"O X O X O",
		"O X O X O",
	}
	m := newMaps(arr)
	m.print()

	fmt.Println("----------- 寻路结果 ----------")

	paths := m.findAstarPaths(0, 0, 4, 4)

	if len(paths) == 0 {
		fmt.Println("没有合适的路径")
		return
	}

	for i, pos := range paths {
		if i == 0 {
			m.updateView(pos.x, pos.y, "S")
		} else if i == len(paths)-1 {
			m.updateView(pos.x, pos.y, "E")
		} else {
			m.updateView(pos.x, pos.y, "*")
		}
	}

	m.print()
}

参考文章：A星寻路算法解析 | Rico’s Blog

路径规划（五）-A-Star算法 | 学步

使用GO语言实现A星寻路算法 - OSCHINA - 中文开源技术交流社区

后面将会开源坦克动荡go语言版的，包括超强人机（寻路就是使用a*实现的）和联机功能，也鼓励大家使用该算法实现一些有趣的项目