首页 > 代码库 > A*算法实现
A*算法实现
1.A*基本流程图
2.扩展节点方法
3.A*最短路径条件
代码：
1.main.lua
require "Lib"
--create scene
local gameScene = cc.Scene:create()
gameScene:addChild(GameLayer:create())2.Lib.luarequire "src/GameLayer" require "src/Cube" require "src/Constant"3.Constant.lua
CubeSplit = 3 CellWidth = cc.Director:getInstance():getWinSize().width/10 CellHeight = cc.Director:getInstance():getWinSize().height/10 CubeWidth = CellWidth - CubeSplit --格子宽 CubeHeight = CellHeight - CubeSplit --格子高4.Cube.lua
--地图方格
Cube = class("Cube", function ()
return cc.Node:create()
end)
Cube.CUBE_TYPE_WALL = 1 --墙
Cube.CUBE_TYPE_START = 2 --起点格子
Cube.CUBE_TYPE_DESTANATION = 3 --目标地格子
Cube.CUBE_TYPE_AVIABLE = 4 --可以行走的格子
function Cube:create(row, col, type)
local view = Cube:new()
view:__init(row, col, type)
return view
end
function Cube:__init(row, col, type)
self.row = row
self.col = col
self.type = type
self:addBgByType()
end
function Cube:addBgByType()
local layerColor = nil
local lblDesp = nil
local fontSize = 15
local color = {
black = cc.c3b(0,0,0),
red = cc.c3b(255,0,255),
yellow = cc.c3b(255,255,0),
white = cc.c3b(255,255,255),
blue = cc.c3b(0,0,255),
green = cc.c3b(0,255,127)
}
if self.type == Cube.CUBE_TYPE_WALL then
layerColor = cc.LayerColor:create(color.blue, CubeWidth, CubeHeight) --黑色
lblDesp = cc.Label:createWithSystemFont("墙","Arial",fontSize)
elseif self.type == Cube.CUBE_TYPE_START then
layerColor = cc.LayerColor:create(color.red, CubeWidth, CubeHeight) --紫红
lblDesp = cc.Label:createWithSystemFont("起始点","Arial",fontSize)
elseif self.type == Cube.CUBE_TYPE_DESTANATION then
layerColor = cc.LayerColor:create(color.yellow, CubeWidth, CubeHeight) --黄
lblDesp = cc.Label:createWithSystemFont("终点","Arial",fontSize)
elseif self.type == Cube.CUBE_TYPE_AVIABLE then
layerColor = cc.LayerColor:create(color.white, CubeWidth, CubeHeight) --白
else
layerColor = cc.LayerColor:create(color.green, CubeWidth, CubeHeight) --白
layerColor:setOpacity(100)
end
layerColor:ignoreAnchorPointForPosition(false)
self:addChild(layerColor)
if lblDesp then
lblDesp:setColor(cc.c3b(0,0,0))
self:addChild(lblDesp)
end
end
function Cube:getPositionByRowCol()
return cc.p( CellWidth * (self.col-0.5), CellHeight * (self.row-0.5))
end
5.GameLayer.luaGameLayer = class("GameLayer",function()
return cc.Layer:create()
end)
function GameLayer:create()
local view = GameLayer.new()
view:__init()
return view
end
function GameLayer:__init()
self:addMap()
end
--是否出界
function GameLayer:checkIsInSide(cube)
return cube.row >= 1 and cube.row <= 10 and cube.col >= 1 and cube.col <= 10 and not self:checkIsInSide(cube)
end
--判断2个格子是否一样
function GameLayer:isEqual(cube1, cube2)
return cube1.row == cube2.row and cube1.col == cube2.col
end
--背景格子
function GameLayer:initBg()
for row = 1, 10 do
for col = 1, 10 do
local cube = Cube:create(row, col, Cube.CUBE_TYPE_AVIABLE)
cube:setPosition(cube:getPositionByRowCol())
self:addChild(cube)
end
end
end
--是否可以行走
function GameLayer:checkIsCanGo(cube)
if cube.row <= 0 or cube.row > 10 or cube.col <= 0 or cube.col > 10 then
return false
end
for _, cubeTmp in ipairs(self.mapList) do
if cube.row == cubeTmp.row and cube.col == cubeTmp.col and cubeTmp.type == Cube.CUBE_TYPE_WALL then
return false
end
end
return true
end
--开始点
function GameLayer:initStart()
self.startCube = Cube:create(3, 4, Cube.CUBE_TYPE_START)
self.startCube:setPosition(self.startCube:getPositionByRowCol())
self:addChild(self.startCube)
table.insert(self.mapList, self.startCube)
end
--结束点
function GameLayer:initDestination()
self.desCube = Cube:create(3, 9, Cube.CUBE_TYPE_DESTANATION)
self.desCube:setPosition(self.desCube:getPositionByRowCol())
self:addChild(self.desCube)
table.insert(self.mapList, self.desCube)
end
--墙
function GameLayer:initWall()
math.randomseed(os.time())
for i = 1, 60 do
local row = math.random(1,10)
local col = math.random(1,10)
local cube = Cube:create(row, col, Cube.CUBE_TYPE_WALL)
if not self:isEqual(cube, self.startCube) and not self:isEqual(cube, self.desCube) then
cube:setPosition(cube:getPositionByRowCol())
self:addChild(cube)
table.insert(self.mapList, cube)
end
end
end
function GameLayer:clearMap()
self:removeAllChildren()
self.mapList = {}
end
--480 * 320
--格子大小 48 * 32
function GameLayer:addMap()
self:clearMap()
self:initBg()
self:initStart()
self:initDestination()
self:initWall()
self:findAStarPath()
end
function GameLayer:tableInclude(cubeList, cube)
local isResult = false
for i = 1, #cubeList do
if self:isEqual(cube, cubeList[i]) then
isResult = true
break
end
end
return isResult
end
function GameLayer:tableRemove(cubeList, cube)
for i = 1, #cubeList do
if self:isEqual(cube, cubeList[i]) then
table.remove(cubeList, i)
break
end
end
end
function GameLayer:findValueInTable(cubeList, cube)
for i = 1, #cubeList do
if self:isEqual(cube, cubeList[i]) then
return cubeList[i]
end
end
end
function GameLayer:findAStarPath()
--以左下角为起点，顺时针转一圈
local dirList = {
{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1}
}
self.openList = {}
self.closeList = {}
table.insert(self.openList, self.startCube)
self.startCube.g = 0
self.startCube.h = self:getManhattonDis(self.startCube)
self.startCube.f = self.startCube.g + self.startCube.h
while true do
if #self.openList == 0 then
print("Fail, not find !!!")
break
else
local firstCubeInOpenList = self.openList[1]
table.remove(self.openList, 1)
table.insert(self.closeList, firstCubeInOpenList)
if self:isEqual(firstCubeInOpenList, self.desCube) then
self.desCube.parent = firstCubeInOpenList
print("Success, find !!!")
self:printPath()
break
else
for i = 1, 8 do
local dir = dirList[i]
local tmpCube = Cube:create(firstCubeInOpenList.row + dir[1], firstCubeInOpenList.col + dir[2], self.startCube.type)
if not self:checkIsCanGo(tmpCube) then
elseif not self:tableInclude(self.openList, tmpCube) and not self:tableInclude(self.closeList, tmpCube) then
self:getOrGetAndSetCubeFGH(firstCubeInOpenList, tmpCube, i)
table.insert(self.openList, tmpCube)
elseif self:tableInclude(self.openList, tmpCube) then
local newFTmp = self:getOrGetAndSetCubeFGH(firstCubeInOpenList, tmpCube, i, true)
if newFTmp < self:findValueInTable(self.openList, tmpCube).f then
self:getOrGetAndSetCubeFGH(firstCubeInOpenList, tmpCube, i)
end
elseif self:tableInclude(self.closeList, tmpCube) then
local newFTmp = self:getOrGetAndSetCubeFGH(firstCubeInOpenList, tmpCube, i, true)
if newFTmp < self:findValueInTable(self.closeList, tmpCube).f then
self:tableRemove(self.closeList, tmpCube)
table.insert(self.openList, tmpCube)
self:getOrGetAndSetCubeFGH(firstCubeInOpenList, tmpCube, i)
end
end
end
end
--按照f值升序排列openList
local sortFunction = function(cube1, cube2)
return cube1.f < cube2.f
end
table.sort(self.openList, sortFunction)
-- self:printOpenList(self.openList)
end
end
end
--打印开放列表
function GameLayer:printOpenList(openList)
print("==========================================")
for i = 1, #openList do
local cube = openList[i]
print("row:"..cube.row.." col:"..cube.col.." f:"..cube.f.." g:"..cube.g.." h:"..cube.h)
end
end
--回溯打印路径
function GameLayer:printPath()
local parentCube = self.desCube
local resultPath = {}
while parentCube.parent ~= nil do
parentCube = parentCube.parent
local row = parentCube.row
local col = parentCube.col
local cube = Cube:create(row, col)
cube:setPosition(cube:getPositionByRowCol())
self:addChild(cube)
end
end
--1.isOnlyGetFValue 为true: 只返回curCube的可能设置的临时f值
--2.isOnlyGetFValue为nil或false: 设置curCubed的f,g,h并且返回节点的f值
function GameLayer:getOrGetAndSetCubeFGH(srcCube, curCube, i, isOnlyGetFValue)
if isOnlyGetFValue then
local g
if i == 1 or i == 3 or i == 5 or i == 7 then
g = srcCube.g + 14
else
g = srcCube.g + 10
end
local h = self:getManhattonDis(curCube)
local f = g + h
return f
else
if i == 1 or i == 3 or i == 5 or i == 7 then
curCube.g = srcCube.g + 14
else
curCube.g = srcCube.g + 10
end
curCube.h = self:getManhattonDis(curCube)
curCube.f = curCube.g + curCube.h
curCube.parent = srcCube
return curCube.f
end
end
--得到一个节点的曼哈顿距离
function GameLayer:getManhattonDis(cube)
local value = http://www.mamicode.com/math.abs(self.desCube.row - cube.row) + math.abs( self.desCube.col - cube.col)>具体代码详见我github工程:https://git.oschina.net/jianan/AStar/tree/master
截图实例:
说明：在随机生成的墙壁中，给定开始点和结束点，浅绿色部分为A*算法计算出来的最短路径。
1.
2.
3.
总结：当估价函数h选定后，就可以让A*是最优算法，在此处采用的是曼哈顿距离！
其它A*入门视频：
http://m.blog.csdn.net/article/details?id=17187239
http://www.jiangzhongyou.net/forum-40-1.html
A*算法实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。