A_算法Lua实现

一.寻路

--3个任务
local class = require "middleclass"
Point = class('Point')
function Point:initialize(x,y)
    self.x = x
    self.y = y
end
function Point:__tostring()
    return 'Point:[' .. tostring(self.x) .. ',' .. tostring(self.y) .. ']'
end
--从图中建造数据模型
aStar = {
--0表示可走
--1表示不可走
{0,0,0,0,0,0,0},
{0,0,0,1,0,0,0},
{0,0,0,1,0,0,0},
{0,0,0,1,0,0,0},
{0,0,0,0,0,0,0},
}
startPoint = Point(3,2)
endPoint = Point(3,6)
local openTab,closeTab = {},{}
function openTab:__tostring() 
    local ret = ""
     for k = 1 ,#self do
        ret = ret ..  tostring(self[k]) 
     end
      return ret
end 
setmetatable(openTab,openTab)
function nextPos(aStar,point)
    --遍历上下左右添加到开启表
    local tmp = {Point(point.x,point.y - 1),Point(point.x,point.y + 1),
    Point(point.x - 1 ,point.y ),Point(point.x + 1,point.y)
    }
    if point.x == endPoint.x and point.y == endPoint.y then
        --print("结束")
        openTab[#openTab + 1] = point
        if #openTab < 10 then
            print(openTab)
        end 
        table.remove(openTab)
        return
    else    
        for i = 1,4 do
            --处于边界内并且可走
            if tmp[i].x >= 1 and tmp[i].x <= 5 and tmp[i].y >= 1 and tmp[i].y <= 7 and  aStar[tmp[i].x][tmp[i].y] == 0 then
                aStar[point.x][point.y] = 1 --当前位置设置不可走
                openTab[#openTab + 1] = point
                nextPos(aStar,tmp[i]) --选择下一个位置
                table.remove(openTab)
                aStar[point.x][point.y] = 0
            else
                -- 不可走的舍弃,裁枝
            end  
        end 
    end
end
nextPos(aStar,startPoint)