A*寻路算法lua实现

前言：并在相当长的时间没有写blog该，我觉得有点“颓废”该，最近认识到各种同行，也刚刚大学毕业，我认为他们是优秀的。认识到与自己的间隙，有点自愧不如。我没有写blog当然，部分原因是由于工作。最初体验上有点欠缺，，原本国庆回去就要把这个寻路的功能改进一下，结果第一次去女朋友家了就没碰电脑，回上海来的第一个夜晚满脑子全是心事。早上凌晨四点就在床上辗转睡不着了，这个月随着项目的进行感觉压力也越来越大，上班时期天天六点多就醒了睡不着，希望挺过这段适应期。

关于寻路问题。在几个月之前一次面试就碰到。面试官叫我上机写出这个算法。由于之前没看过A*，仅仅是有这个概念，所以仅仅能凭着自己的思路来暂时编写。最后憋出了一段后来主动跟面试官说名能够用A*算法来实现，最后还是我的坚持打动了面试官。今天又碰到相同的问题，也让我纠结了一两天，再次写下寻路的学习心得。

一、问题概述

游戏中有敌我两方，有四十个方格。当轮到我方武将行动的时候，要先显示出我方武将能够行动的方位，这个就涉及到我方武将的行动力的大小来决定，预先做出路径的预算。这里还要考虑敌方以及地标(比如:炸弹、势头)的阻挡，以及特殊方格对武将行动力的消耗以及敌方的间隔阻挡规则。

当碰到这个问题的时候，问老大选择用什么寻路算法。他推荐的是Dijstra算法。但我看了之后感觉还不是非常适合我的需求。第一：我认为Dijstra算法是有向图的最佳路径选择。节点之间路径长度必须先知晓，但我这里四十个方格假设要两两制定感觉略微复杂，而且随着武将的移动，地图还是时时变化的，感觉更复杂。第二：Distra算法没有阻挡考虑。当然也能够记录若干路径然后考虑阻挡选择最优路径，我感觉也稍复杂。

然而我的第一反应该需求A*算法挺接近的，然后咨询老大，老大说A*方格之间距离必须要均等不然比較复杂。然后再咨询公司其它稍有经验同事，当然各有个的说法，什么深度、广度遍历，感觉没一个确定的说法。

让我选择就纠结了一天，不敢轻易选择，假设稍有考虑不慎。说不定就要做几天白用工，但最后我还是坚持自己的想法用A*来实现。

二、关于A*

A*通用的计算公式F=G+H

G:表示从起点A移动到网格上指定方格的移动耗费(我这里没考虑斜方向移动),也可理解为节点的权重

H:表示从制定方格移动到终点B的估计耗费,这里一般就是计算距离*系数

三、寻路思想

1.从起点A開始。把它加入到"开启列表"

2.寻找A点可到到的周围四个点，这里可到达是指没有阻挡而且已经不再关闭列表中的节点。并把他们加入进开启列表。并设置他们的父节点为A

3.从开启列表中删除A点并加入进关闭列表中，关闭列表就是存放的不须要检測的方格节点

4.检查它全部相邻而且合一到达的方格，假设这些方格还不再开启列表里的话就把他们加入开启列表。计算这些方格的GHF值并设置它的父节点

5.假设某个相邻方格 D 已经在 "开启列表" 里了, 检查假设用新的路径 (就是经过C 的路径) 到达它的话, G值是否会更低一些, 假设新的G值更低, 那就把它的 "父方格" 改为眼下选中的方格 C, 然后又一次计算它的 F 值和 G 值 (H 值不须要又一次计算, 由于对于每一个方块, H 值是不变的). 假设新的 G 值比較高, 就说明经过 C 再到达 D 不是一个明智的选择, 由于它须要更远的路, 这时我们什么也不做

6.当发现开启列表中有终点目标方格的时候则说明路径已经找到。

关于具体的图解能够參考其它网友的具体解释，我这里就不具体写了。

四、找回路径

我们找到最后一个点的时候然后层层往之前找到他的父节点迭代到最后不为空结束

五、数据结构

Point类

module('Point', package.seeall)
-- require("script/battle/BattleCommon")
--计算F值
function CalcF( point )
	point.F = point.G + point.H
end

function create( posId )
	local point = {}
	point.parentPoint = {}
	point.step = 1 --用于计算h值
	local x,y = BattleCommon.convertPosIdToCoord(posId)
	point.F = 0
	point.G = 0
	point.H = 0
	point.X = y            --point.X范围[1,5]
	point.Y = x            --point.Y范围[1,8]
	point.posId = posId
	point.CalcF = CalcF
	
	return point
end

return Point

地形(Maze)结构

--依据一个table创建一个地形
function create( tb )
	local maze = {}
	maze.step = 1 --格子与格子的基本距离,用于计算H值
	maze.mazeArray = tb
	maze.openList = TabledArray.create() --开启列表
	maze.closeList = TabledArray.create() --关闭列表
	maze.findPath = findPath
	return maze
end

六、主要代码

module('Maze', package.seeall)
require("script/battle/TabledArray")
require("script/battle/BattleCommon")
require ("script/battle/Point")

-- --获取列表中F值最小的点
function getMinPoint( pointsList )
	local minPoint = pointsList.tbl[1]
	for i = 1,pointsList:getSize() do
		if minPoint.F > pointsList.tbl[i].F then
			minPoint = pointsList.tbl[i]
		end
	end
	return minPoint
end

-- --检測是否有阻挡,没有阻挡为true
function checkBlock( maze,x,y,roleFlag)              --x范围[1,5]  y范围[1,8]
	if roleFlag == BattleCommon.BATTLE_GROUP_ALLIES then --我方阵营
		if maze.mazeArray[x][y][1] == 0 or maze.mazeArray[x][y][1] == 1 then
			return true  --没有阻挡
		else
			return false   
		end
	elseif roleFlag == BattleCommon.BATTLE_GROUP_ENEMY then
		if maze.mazeArray[x][y][1] == 0 or maze.mazeArray[x][y][1] == 2 then
			return true  --没有阻挡
		else
			return false   
		end
	end
end

-- --列表中是否包括x,y的点
function existsXY( list,x,y )
	if list:getSize()>0 then
		for i,point in pairs(list.tbl) do
			if point.X == x and point.Y == y then
				return true
			end
		end
	end
	return false
end

--列表中是否包括某个点
function existsPoint( list,point )
	for i, p in pairs(list.tbl) do
		if (p.X == point.X) and (p.Y == point.Y) then
			return true
		end
	end
	return false
end


-- --检測能达到的点
function canReach( maze,startPoint,x,y,roleFlag)
	if (not checkBlock(maze,x,y,roleFlag)) or  existsXY(maze.closeList,x,y) then --关闭列表中包括这个点或者有阻挡
		return false
	else
		if (math.abs(x-startPoint.X)+math.abs(y-startPoint.Y) == 1 ) then
			return true
		end
	end
end

-- --获取相邻的点
function getSurroundPoints( maze,point,roleFlag )
	local surroundPoints = TabledArray.create()
	for i = point.X - 1 ,point.X + 1 do
		for j=point.Y - 1,point.Y + 1 do
			if i>0 and i<6 and j > 0 and j < 9 then  --排除超过表姐
				if BattleCommon.distanceFromTo(point.posId,BattleCommon.convertToPositionId(j-1,i-1)) < 2 then
					if canReach(maze,point,i,j,roleFlag) then
						surroundPoints:append(maze.mazeArray[i][j][2])
					end
				end
			end
		end
	end
	return surroundPoints   --返回point点的集合
end

-- --计算G值
function CalcG( point )
	local G = point.G
	local parentG = 0
	if point.parentPoint then
		parentG = point.parentPoint.G
	end
	return G + parentG
end

function foundPoint( tempStart,point )
	local G = CalcG(point)
	if G < point.G then
		point.parentPoint = tempStart
		point.G = G
		point:CalcF()
	end
end


function notFoundPoint( maze,tempStart,point )
	point.parentPoint = tempStart
	point.G = CalcG(point)
	point:CalcF()
	maze.openList:append(point)
end

function getPoint( list,data )
	for i,point in pairs(list.tbl) do
		if point.posId == data.posId then
			return point
		end
	end
	return nil
end

-- --寻找路径(起始路径)
local function findPath( maze,startPoint,endPoint,roleFlag)
	maze.openList:append(startPoint)
	while maze.openList:getSize() ~= 0 do
		--找出F的最小值
		local tempStart = getMinPoint(maze.openList)
		maze.openList:removeById(1)
		maze.closeList:append(tempStart)
		--找出它相邻的点
		local surroundPoints = getSurroundPoints(maze,tempStart,roleFlag)
		for i,point in pairs(surroundPoints.tbl) do
			if existsPoint(maze.openList,point) then
				--计算G值,假设比原来大,就什么都不做,否则设置他的父节点为当前节点,并更新G和F
				foundPoint(tempStart,point)
			else
				--假设他们不再開始列表里面,就加入,并设置父节点,并计算GHF
				notFoundPoint(maze,tempStart,point)
			end
		end
		--假设最后一个存在则返回
		if getPoint(maze.openList,endPoint) then
			return getPoint(maze.openList,endPoint)
		end
	end
	return getPoint(maze.openList,endPoint)
end


--依据一个table创建一个地形
function create( tb )
	local maze = {}
	maze.step = 1 --格子与格子的基本距离,用于计算H值
	maze.mazeArray = tb
	maze.openList = TabledArray.create() --开启列表
	maze.closeList = TabledArray.create() --关闭列表
	maze.findPath = findPath
	return maze
end


return Maze

调用方法

function printPath( presentPoint )
	local pathArray = TabledArray.create()
	while presentPoint do
		pathArray:preppend(presentPoint.posId)
		presentPoint = presentPoint.parentPoint
	end
	local startPoint = pathArray:get(2)
	local endPoint = pathArray:getLast()
	
	cclog(startPoint)
	cclog(endPoint)
	cclog("从"..startPoint.."到"..endPoint.."的路径是:")
	for i,p in pairs(pathArray.tbl) do
		cclog(p)
	end
end

	local array = battleBoard:createBoxPoints(cRole:getFlag(),40)
	local maze = Maze.create(array)
	local startPoint = Point.create(cRole:getPositionId())
	local endPoint = Point.create(40)
	local presentPoint = maze:findPath(startPoint,endPoint,cRole:getFlag())
	printPath(presentPoint)

七、执行效果

手机測试效果还能够。貌似在255*255规模的方格规模上採用A*还是不会很多效率。

假设需要交流请联系。

版权声明：本文博客原创文章，博客，未经同意，不得转载。