|
发表于 2010-2-4 20:47:13
|
显示全部楼层
基于A*算法的房间寻路过程,地图格式如前面。
--city城市表,sid起始房间编号,did目的房间编号
local openlist={}
local closedlist={}
--主函数
function getroompath(city,sid,did)
local bestroom,temproom
if sid==did then return "" end
table.insert(openlist,createnode(sid,0,"",nil,nil))
while table.getn(openlist)~=0 do
table.sort(openlist,function(a,b) return a.g
bestroom=openlist[1]
if bestroom.key==0 then
print("房间"..bestroom.prevnode.."有出口指向0,请查证")
return ""
end
table.remove(openlist,1)
if not checkclosedlist(bestroom.key) then closedlist[bestroom.key]=bestroom end
if bestroom.key==did then return getpathfromlist(sid,did) end
for k,v in pairs(city[bestroom.key].roomexists) do
if not checkopenlist(v) then
if not checkclosedlist(v) then table.insert(openlist,createnode(v,bestroom.g+1,k,bestroom.key,nil)) end
end
end
end
end
--创建节点
function createnode(key,g,path,prevnode,nextnode)
return {key=key,g=g,path=path,prevnode=prevnode,nextnode=nextnode}
end
--检查
function checkopenlist(key)
for k,v in pairs(openlist) do
if key==v.key then return true end
end
return false
end
--检查
function checkclosedlist(key)
if closedlist[key]~=nil then
return true
else
return false
end
end
--获取路径
function getpathfromlist(sid,did)
local tmp
local path=""
tmp=closedlist[did]
path=tmp.path
while tmp.prevnode~=sid do
tmp=closedlist[tmp.prevnode]
path=tmp.path..";"..path
end
return path
end
[ 本帖最后由 sauron 于 2010-2-4 09:18 PM 编辑 ] |
|