自己寫的貪吃蛇（3）

A*算法網上很多介紹了，在此就不詳細介紹了。

首先是計算一個格子的（start）的相鄰4個方向上的G,F,H值等

每個格子有一個index屬性來辨別在cells數組中的位置

target表示要到達的目标格子

opened是要将要搜尋的數組

closed是已經搜尋了的數組

snakes看着障礙物

function SnakeGame:calculateCell(start, dir, target, opend, closed, snakes)
    local cell = nil
    local index = start.index
    local b = false
    if dir == SnakeGame.Dir.LEFT then
        cell = index - 
    elseif dir == SnakeGame.Dir.RIGHT then
        cell = index + 
    elseif dir == SnakeGame.Dir.UP then
        cell = index + self.column_num
    elseif dir == SnakeGame.Dir.DOWN then
        cell = index - self.column_num
    end
    if self.cells[cell] then
        for k, v in ipairs(closed) do 
            if cell == v.index then
                -- 已經在搜尋過了的路徑裡則不作處理
                b = true
                break
            end
        end
        if not b then
            for k, v in ipairs(snakes) do 
                if cell == v.index and v ~= target then
                    -- 障礙物
                    b = true
                    break
                end
            end            
        end
        if not b then
            -- 跳行的判斷
            if dir == SnakeGame.Dir.LEFT then
                b = self.cells[index].x > self.cells[cell].x
            elseif dir == SnakeGame.Dir.RIGHT then
                b = self.cells[index].x < self.cells[cell].x
            elseif dir == SnakeGame.Dir.UP then
                b = self.cells[index].y < self.cells[cell].y
            elseif dir == SnakeGame.Dir.DOWN then
                b = self.cells[index].y > self.cells[cell].y
            end
            if b then
                local G = start.G +  --G值是上一個的G+
                local H = math.abs(self.cells[target.index].x - self.cells[cell].x) / self.cell_width + math.abs(self.cells[target.index].y - self.cells[cell].y) / self.cell_width
                -- H是目前到目标的最短距離（其實就是橫向和豎向的直線距離和）
                local F = G + H
                for k, v in ipairs(opend) do 
                    if v.index == cell then
                        if F < v.F then
                            -- 如果在待搜尋的裡面并且F值更小則替換F值和parent
                            v.F = F
                            v.parent = start
                        end
                        return nil
                    end
                end
                -- 傳回dir方向上的搜尋
                return {index = cell, G = G, H = H, F = F, parent = start, dir = dir}
            end
        end
    end
    return nil
end
           

在opend裡找到最小F值的

function SnakeGame:findMinF(opend)
    local key = #opend
    for k, v in ipairs(opend) do 
        if k < #opend then
            if v.F <= opend[key].F then
                key = k
            end
        end
    end
    return key
end
           

搜尋一條最短的路徑

-- 傳回蛇的頭部到達target的最短路徑或者不存在
function SnakeGame:checkAWay(snakes, target)
    local opend = {}
    local closed = {}
    -- 用蛇的頭部作為搜尋的起點
    local start = {index = snakes[].index, G = }
    table.insert(closed, start)
    local left = self:calculateCell(start, SnakeGame.Dir.LEFT, target, opend, closed, snakes)
    local right = self:calculateCell(start, SnakeGame.Dir.RIGHT, target, opend, closed, snakes)
    local up = self:calculateCell(start, SnakeGame.Dir.UP, target, opend, closed, snakes)
    local down = self:calculateCell(start, SnakeGame.Dir.DOWN, target, opend, closed, snakes)

    -- 存在則插入到opend數組裡面
    if left then
        table.insert(opend, left)
    end
    if right then
        table.insert(opend, right)
    end
    if up then
        table.insert(opend, up)
    end
    if down then
        table.insert(opend, down)
    end
    local find_a_way = false
    while opend[] do
        local key = self:findMinF(opend)
        -- 最小F值的放入closed裡面
        table.insert(closed, opend[key])
        table.remove(opend, key)
        -- 到達目标則找到最短路徑
        if closed[#closed].index == target.index then     
            find_a_way = true       
            break
        end
        local left = self:calculateCell(closed[#closed], SnakeGame.Dir.LEFT, target, opend, closed, snakes)
        local right = self:calculateCell(closed[#closed], SnakeGame.Dir.RIGHT, target, opend, closed, snakes)
        local up = self:calculateCell(closed[#closed], SnakeGame.Dir.UP, target, opend, closed, snakes)
        local down = self:calculateCell(closed[#closed], SnakeGame.Dir.DOWN, target, opend, closed, snakes)
        if left then
            table.insert(opend, left)
        end
        if right then
            table.insert(opend, right)
        end
        if up then
            table.insert(opend, up)
        end
        if down then
            table.insert(opend, down)
        end

    end
    if find_a_way then        
        return closed
    else
        print("not find a way!")
        return nil
    end
end
           

在ctor裡面初始化一個數組self.targetLines = {} 用于放置最短路徑每一步的方向，即蛇移動的方向

function SnakeGame:doAI(target)
    if #self.targetLines > 0 then
        return
    end
    target = target or self.tail      
    local closed = self:checkAWay(self.snakes, target)
    if closed then
        self.targetLines = {}
        table.insert(self.targetLines, closed[#closed].dir)
        local parent = closed[#closed].parent
        local ii = 

        while parent and parent ~= closed[] do
            local index = parent.index            
            local x = self.cells[index]
            table.insert(self.targetLines, parent.dir)  
            parent = parent.parent
        end          
    else
        print("not find a way!")
    end
end
           

在generateBody末尾增加一個self:doAI()的調用，讓每次生成目标tail的時候生成最短路徑！

最後修改onEnter函數中的update讓它沿AI最短路徑跑起來

function SnakeGame:onEnter()
    local time1 = tsixi.THelper:currentMilliseconds()
    local update = function(dt)
        if not self.is_failed then
            local now = tsixi.THelper:currentMilliseconds()
            if not self.parse and (now - time1 >=  or self.must) then
                self.must = false
                time1 = now
                self.direction = self.targetLines[#self.targetLines]
                table.remove(self.targetLines)                  
                self:doMove()                
            end     
        end
    end
    self:scheduleUpdateWithPriorityLua(update, ) 
end
           

現在蛇可以自己去吃目标物了

現在這個AI還有很多問題，如果生成的紅塊在蛇本身的身體裡時就找不到，下一節再優化這個問題