文档章节

Golang实现A星路径搜索算法

路人甲777
 路人甲777
发布于 2016/03/29 11:36
字数 813
阅读 32
收藏 0
package main

import (
   "fmt"
   "math/rand"
   "time"
)

type block struct {
   //编号
   id int32
   //是否障碍
   isHinder bool
   //父节点
   parent *block
   //G值 H值  F = G + H
   gValue int32
   hValue int32
}

// 总共格子数
var GRID_NUM int32 = 5000

// 行数
var ROW_NUM int32 = 50

// 列数
var COL_NUM int32 = 100

// 地图map
var Map map[int32]*block

// 生成地图 10*10 大小
func GenerateMap() {
   Map = make(map[int32]*block)
   for i := int32(1); i <= GRID_NUM; i++ {
      bk := &block{
         id:       i,
         isHinder: false,
      }
      Map[i] = bk
   }
   // 随机生成障碍物
   //var tem int32 = 25
   for j := 1; j < 500; j++ {
      rand, _ := GetRandNumDown(1, GRID_NUM)
      block, fd := Map[rand]
      if fd {
         block.isHinder = true
      }
      //tem += 10
   }
}

// 计算给出的位置在哪一行哪一列
func GetRowCol(point int32) (int32, int32) {
   row := point/COL_NUM + 1
   col := point % COL_NUM
   return row, col
}

// 找到相邻格子
func FindNeighbor(point int32) []int32 {
   neighbor := make([]int32, 0)
   if point < 1 || point > GRID_NUM {
      return neighbor
   }
   // 上
   up := point - COL_NUM
   if up > 0 {
      neighbor = append(neighbor, up)
   }
   // 下
   down := point + COL_NUM
   if down <= GRID_NUM {
      neighbor = append(neighbor, down)
   }
   // 左
   left := point - 1
   if left > 0 && left%COL_NUM != 0 {
      neighbor = append(neighbor, left)
      // 左上
      leftup := left - COL_NUM
      if leftup > 0 {
         neighbor = append(neighbor, leftup)
      }
      // 左下
      leftdown := left + COL_NUM
      if leftdown <= GRID_NUM {
         neighbor = append(neighbor, leftdown)
      }
   }
   // 右
   right := point + 1
   if right <= GRID_NUM && point%COL_NUM != 0 {
      neighbor = append(neighbor, right)
      // 右上
      rightup := right - COL_NUM
      if rightup > 0 {
         neighbor = append(neighbor, rightup)
      }
      // 右下
      rightdown := right + COL_NUM
      if rightdown <= GRID_NUM {
         neighbor = append(neighbor, rightdown)
      }
   }
   return neighbor
}

// 计算B点 G H 值
func CountGH(pointA, pointB, pointC *block) {
   if pointB.isHinder {
      return
   }
   rowB, colB := GetRowCol(pointB.id)
   rowC, colC := GetRowCol(pointC.id)
   h1 := rowB - rowC
   h2 := colB - colC
   if h1 < 0 {
      h1 = -h1
   }
   if h2 < 0 {
      h2 = -h2
   }
   pointB.hValue = (h1 + h2) * 10
   if pointA.id-COL_NUM == pointB.id || pointA.id+COL_NUM == pointB.id || pointA.id+1 == pointB.id || pointA.id-1 == pointB.id {
      pointB.gValue = 10
   } else {
      pointB.gValue = 15
   }
}

//地图寻路 传入起点 终点
func FindRoad(start, end int32) []int32 {
   road := make([]int32, 0)

   if start == end {
      return road
   }
   //开放列表
   OpenList := make(map[int32]*block)
   //闭合列表
   CloseList := make(map[int32]*block)

   b_star, bfd := Map[start]
   if !bfd || b_star.isHinder {
      return road
   }

   b_end, efd := Map[end]
   if !efd || b_end.isHinder {
      return road
   }

   // 起点放入closelist
   CloseList[start] = b_star

   Run(b_star, b_end, OpenList, CloseList)
   /////////
   // 在开放列表中找最小值
   var count int32 = 0
   for {
      if count >= 100000 {
         fmt.Println("BREAK")
         break
      }
      count++
      if _, fd := OpenList[end]; fd {
         //找到了
         tail := b_end
         for {
            if tail.parent == nil {
               break
            }
            road = append(road, tail.id)
            tail = tail.parent
         }
         break
      }
      if len(OpenList) <= 0 {
         //找不到路
         break
      }
      var block_temp *block
      for _, val := range OpenList {
         if block_temp == nil {
            block_temp = val
         } else {
            if val.gValue+val.hValue < block_temp.gValue+block_temp.hValue {
               block_temp = val
            }
         }
      }
      // 找到后从开放列表中删除, 加入关闭列表
      if block_temp != nil {
         delete(OpenList, block_temp.id)
         CloseList[block_temp.id] = block_temp
      }
      Run(block_temp, b_end, OpenList, CloseList)
   }

   //road = append(road, start)
   return road
}

func Run(currentBlock, b_end *block, OpenList, CloseList map[int32]*block) {
   // 找出邻居
   neighbors := FindNeighbor(currentBlock.id)
   for _, id := range neighbors {
      block, ok := Map[id]
      if ok {
         // 已经在关闭列表,不考虑
         _, fd := CloseList[block.id]
         if fd {
            continue
         }
         // 是障碍 不考虑
         if block.isHinder {
            continue
         }
         //
         if _, fd := OpenList[block.id]; fd {
            // 已经在开放列表
            var g int32
            if block.id+1 == currentBlock.id || block.id-1 == currentBlock.id || block.id+COL_NUM == currentBlock.id || block.id-COL_NUM == currentBlock.id {
               g = 10
            } else {
               g = 15
            }
            if currentBlock.gValue+g < block.gValue {
               block.parent = currentBlock
               block.gValue = currentBlock.gValue + g
            }
         } else {
            // 计算每个相邻格子的gh值
            CountGH(currentBlock, block, b_end)
            // 放入开放列表
            OpenList[block.id] = block
            block.parent = currentBlock
         }
      }
   }
}

//获取[min, max)之间的随机数
func GetRandNumDown(min, max int32) (int32, error) {
   if min > max {
      return 0, fmt.Errorf("%d can not bigger than %d", min, max)
   }
   if min == max {
      return min, nil
   }
   r := rand.New(rand.NewSource(time.Now().UnixNano()))
   num := int32(r.Intn(int(max-min))) + min

   return num, nil
}

func DrawMap(road []int32) {
   if len(Map) != int(GRID_NUM) {
      return
   }
   for i := int32(1); i <= GRID_NUM; i++ {
      flag := false
      for _, id := range road {
         if i == id {
            fmt.Print("\x1b[31m@\x1b[0m")
            flag = true
         }
      }
      if !flag {
         block, _ := Map[i]
         if block.isHinder {
            fmt.Print("\x1b[33m#\x1b[0m")
         } else {
            fmt.Print("*")
         }
      }
      if i%COL_NUM == 0 {
         fmt.Print("\n")
      }
   }
}

func main() {
   road := make([]int32, 0)
   GenerateMap()
   fmt.Println("原地图")
   DrawMap(road)
   fmt.Println("==================")
   road = FindRoad(11, 4582)
   if len(road) <= 0 {
      fmt.Println("找不到路")
      return
   }
   fmt.Println("路线图")
   DrawMap(road)
   fmt.Println("==================")
   fmt.Printf("Road: %v", road)
}


© 著作权归作者所有

路人甲777
粉丝 0
博文 5
码字总数 2173
作品 0
郑州
私信 提问
A星路径搜索

摘要: 在人工智能中有一类问题是有确定解的,如路径、五子棋等,这样的问题非常适合使用搜索来解决。 路径搜索是一个很有趣的问题,在人工智能中算是很基础的问题。最近一直在读《Artificia...

晨曦之光
2012/06/07
645
0
A星寻路算法入门(Unity实现)

最近简单学习了一下A星寻路算法,来记录一下。 还是个萌新,如果写的不好,请谅解。 Unity版本:2018.3.2f1 A星寻路算法是什么 游戏开发中往往有这样的需求,让玩家控制的角色自动寻路到目标...

青空哲也
03/14
0
0
Python: Trie树实现字典排序

一般语言都提供了按字典排序的API,比如跟微信公众平台对接时就需要用到字典排序。按字典排序有很多种算法,最容易想到的就是字符串搜索的方式,但这种方式实现起来很麻烦,性能也不太好。T...

陈亦
2014/02/18
0
4
自动机器学习工具全景图:精选22种框架,解放炼丹师

构建一个典型的机器学习项目,一般分成以下步骤: 收集原始数据、合并数据源、清洗数据、特征工程、模型构建、超参数调优、模型验证和设备部署。 整个过程中,模型构建最能体现创造力,而最耗...

技术小能手
2018/08/22
0
0
用Golang写一个搜索引擎

用Golang写一个搜索引擎 猜你喜欢 golang入门-- 一个2D的图形库学习 golang入门--一个简单的http client golang的第一个deadlock LiteJob,一个Golang的本地任务调度器 再次自我黑客马拉松--不...

d_watson
2016/04/14
50
0

没有更多内容

加载失败,请刷新页面

加载更多

将博客搬至CSDN

https://blog.csdn.net/qq_38157006

Marhal
16分钟前
1
0
unicode Java中求字符串长度length()和codePointCount()的区别

在计算字符串长度时,Java的两种方法length()和codePointCount()一度让我困惑,运行书上例子得到的长度值是相等的,那为什么要设定两个方法呢? 对于普通字符串,这两种方法得到的值是一样的...

泉天下
16分钟前
2
0
uin-app 一、学习理由

选择uni-app 理由 别人的理由 1. 5+ 有HTML5+和Native.js技术,HTML5+包含常用的跨平台的几百个API,能满足常规开发需求,而Native.js把40w原生api映 射成js对象,这样js可以直接调原生。HTM...

轻轻的往前走
18分钟前
1
0
方括号及其在命令行中的不同用法介绍

通配 方括号最简单的用法就是通配。你可能在知道“ Globbing”这个概念之前就已经通过通配来匹配内容了,列出具有相同特征的多个文件就是一个很常见的场景,例如列出所有 JPEG 文件: ls *.j...

Linux就该这么学
24分钟前
1
0
vecty 基础

gopherjs 是把 go 编译为 js 的工具。 vecty 是基于 gopherjs 的一种类似 React 的开发框架。 安装 gopherjs 和 vecty go get -u github.com/gopherjs/gopherjsgo get -u github.com/gopher......

electricface
25分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部