cocos2dx之寻路 A星

–寻路

local MAX_ROW_NUM = 9 --行数
local MAX_COL_NUM = 9 --列数
local director = cc.Director:getInstance()
local visibleSize = director:getVisibleSize()

–小方块宽高

local ItemWidth  = visibleSize.width / MAX_COL_NUM
local ItemHeight = ItemWidth

–查找方向

local SEARCH_POS = {
cc.p(-1,0),--左边
cc.p(0,1),--上
cc.p(1,--右
cc.p(0,-1),--下
}

self.m_allItems = {}
for i=1,MAX_ROW_NUM do
    self.m_allItems[i] = {}
    for j=1,MAX_COL_NUM do
        local smallItem = smallItem:create(i,j)
        smallItem:setPosition((j - 1) * ItemWidth,(i - 1) * ItemHeight)
        self:addChild(smallItem)

        self.m_allItems[i][j] = smallItem
    end
end

–从（1， 1）找向（7， 7）

self:_AStar(cc.p(1,cc.p(7,7))

function TestLayer:_AStar(from,to)
    local queue = {from}
    --记录行走的路径
    local searchMap = {[from.x*MAX_ROW_NUM + from.y] = {from}}

    repeat
        local p = table.remove(queue,1)
        if(not p) then break end
        --将目前格子的周围相邻的格子压栈
        for _,point in ipairs(SEARCH_POS) do
            local x = point.x + p.x
            local y = point.y + p.y

            if x > 0 and x <= MAX_COL_NUM and y > 0 and y <= MAX_ROW_NUM then --格子有效范围内
                local pp = clone(searchMap[p.x*MAX_ROW_NUM + p.y])
                table.insert(pp,cc.p(x,y))
                if x == to.x and y == to.y then
                    --找到了
                    for _,point in pairs(pp) do
                        -- print("x,y: ",point.x,point.y)
                    end
                    return
                elseif not self.m_allItems[x][y]:_getIsMask() then --格子未寻过
                    self.m_allItems[x][y]:_setIsMask(true) --标记格子寻路过
                    table.insert(queue,y))
                    searchMap[x*MAX_ROW_NUM + y] = pp
                end
            end
        end
    until false
end