所有代码都在 Lua / 伪代码中
我正在尝试编写 A* 探路者。但是，我似乎遇到了一些错误。我不确定我的程序是否正确...
local function AStar(Start, Goal)
Start["GScore"] = 0 -- Distance from start.
Start["HScore"] = Heuristic(Start,Goal) -- Estimated Distance from Goal
Start["FScore"] = Start.GScore + Start.HScore -- The Final Score
我认为上面的代码是正确的......
现在......我正在使用的数据结构是一个“节点”数组，其中包含一个表：
- X
- 是
- 源（指向另一个节点的指针）
- 评分
- 高分
- 分数
我有一张预先组装好的地图，里面有...
- X
- 是
- 邻居表（X/Y 格式，但没有 Source、GScore 等）。
尝试减少计算。
启发式
我用的heusticis是...
function Heuristic(Start, Goal)
return math.sqrt(((Start.X-Goal.X)^2) + ((Start.Y-Goal.Y)^2))
end
欧几里得距离，虽然我试图使用切比雪夫距离。我认为这行得通，但我不能确定，所以我改用我认为的“故障安全”启发式方法，直到我认为它行得通......但是你得到......
S = Start
E = End
S
***
*****
***
E
寻路时，在哪里...
S
**O
****O
**O
E
技术上可能是正确的路径。我不确定您是否有任何解决方法。我在做....
function HeuristicDiagonal(Start, Goal)
return min(abs(Start.X-Goal.X), abs(Start.Y-Goal.Y))
end
function HeuristicStraight(Start, Goal)
return abs(Start.X-Goal.X) + abs(Start.Y - Goal.Y)
end
function Heuristic(Start, Goal)
local HD = HeuristicDiagonal(Start, Goal)
return ((HD*1.414) + ((HeuristicStraight(Start, Goal) - (2*HD))))*1.01
end
但它似乎降级为最佳搜索。
代码/算法的基础
我正在尝试遵循以下说明：
OPEN = priority queue containing START
CLOSED = empty set
while lowest rank in OPEN is not the GOAL:
current = remove lowest rank item from OPEN
add current to CLOSED
for neighbors of current:
cost = g(current) + movementcost(current, neighbor)
if neighbor in OPEN and cost less than g(neighbor):
remove neighbor from OPEN, because new path is better
if neighbor in CLOSED and cost less than g(neighbor): **
remove neighbor from CLOSED
if neighbor not in OPEN and neighbor not in CLOSED:
set g(neighbor) to cost
add neighbor to OPEN
set priority queue rank to g(neighbor) + h(neighbor)
set neighbor's parent to current
reconstruct reverse path from goal to start
by following parent pointers
(**) This should never happen if you have an monotone admissible heuristic. However in games we often have inadmissible heuristics.
从这个来源 [ http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html#sketch ]
不幸的是，对于这个**，我得到了这个，我很确定我使用的启发式方法很好，因为它是距离公式....
我的代码的基本轮廓是......
Define Functions / Variables (Openset, etc)
While No Goal and OpenSet > Value do
If NOT the goal
Get the Lowest Ranked Items in OpenSet
Add to closed set
For each neighbor pulled from premade calculated stuff do
Calculate FScore, GScore, HScore
If Neighbor in OpenSet and Cost less then the GScore of the item in open // In this case, the item in open is the one identified
Remove it from open
If Neighbor in Closed and Cost loss then the GScore of the item in closed
Remove it from Closed
**Thing that should not happen, but does anyway... :(
If the Neighbor is not in Closed or Open
Add it to open
Else it is the Goal
Say found Goal (Stop loop)
Reconstruct path
实际代码
local function AStar(Start, Goal)
print("AStar start")
Start["GScore"] = 0 -- Distance from start.
Start["HScore"] = Heuristic(Start,Goal) -- Estimated Distance from Goal
Start["FScore"] = Start.GScore + Start.HScore -- The Final Score
local OpenSet = {Start} -- The OpenSet is the set of nodes that need to be check. In each repetition, it pulls out the smallest 'Scoring' one, and checks it.
local ClosedSet = {} -- The ClosedSet is the set of nodes that have already been visited
local Continue = true -- Until the Goal is found, continue will be true.
local LowestNode, IndexVal
local Reps = 0
local function GetLowestRankInOpen()
local LowestRanks = {}
local LowestNode, IndexVal;
local CurrentNodeFScore = math.huge
print("OpenSet has :"..#OpenSet.." options")
for Index, Node in pairs(OpenSet) do
if Node.FScore < CurrentNodeFScore then
CurrentNodeFScore = Node.FScore
LowestNode = Node
IndexVal = Index;
LowestRanks = {}
LowestRanks[#LowestRanks+1] = {Node = Node,Index = Index}
elseif Node.FScore == CurrentNodeFScore then
LowestNode = Node
IndexVal = Index;
LowestRanks[#LowestRanks+1] = {Node = Node,Index = Index}
end
end
return LowestRanks--LowestNode, IndexVal;
end
local function NodeIsTransversable(NodeX, NodeY)
local MapX = Map[NodeX] -- Node out of bounds?
if not MapX then
print("Node out of bounds")
return false
end
local MapXY = MapX[NodeY] -- Node out of bounds?
if not MapXY then
print("Node out of bounds")
return false
end
return MapXY.Transversable
end
function NodeIsInOpenSet(NodeX, NodeY)
for Index, Node in pairs(OpenSet) do
if ((Node.X == NodeX) and (Node.Y == NodeY)) then
return true, Node, Index
end
end
return false
end
function NodeIsInClosedSet(NodeX, NodeY)
for Index, Node in pairs(ClosedSet) do
if ((Node.X == NodeX) and (Node.Y == NodeY)) then
return true, Node, Index
end
end
return false
end
local function ReconstructPath(Node, Tab)
Tab = Tab or {}
table.insert(Tab, Node)
return Node.Source and ReconstructPath(Node.Source, Tab) or Tab;
end
local function Check(Num) -- Basically just debugging... Not sure if it worked too well...
for _, Node in pairs(OpenSet) do
if Node.FScore <= Num then
print("failed @ "..Node.FScore)
end
end
end
local SourceNode
while ((#OpenSet > 0) and Continue) do
LowestNodes = GetLowestRankInOpen()
for _, TheNode in pairs(LowestNodes) do
SourceNode = TheNode
local LowestNode = TheNode.Node
local IndexVal = TheNode.Index
Reps = Reps + 1
print("Loop #: "..Reps.." | Open #: "..#OpenSet)
print(LowestNode and "Lowest node is there" or "Lowest node is not there")
print("X: "..LowestNode.X.." Y: "..LowestNode.Y)
local LowestNodeX = LowestNode.X
local LowestNodeY = LowestNode.Y
print("FScore: "..LowestNode.FScore)
Check(LowestNode.FScore)
wait(0.1)
if not ((LowestNodeX == Goal.X) and (LowestNodeY == Goal.Y)) then
ClosedSet[#ClosedSet+1] = LowestNode
OpenSet[IndexVal] = nil
if OpenSet[IndexVal] then
print("Hack")
end
RenderNiceBrick(LowestNodeX, LowestNodeY, BrickColor.new("Mid gray"))
for _, NeighborNode in pairs(Map[LowestNodeX][LowestNodeY].Neighbors) do
local NeighborNodeX = NeighborNode.X -- Speed things up
local NeighborNodeY = NeighborNode.Y
if NodeIsTransversable(NeighborNodeX, NeighborNodeY) then
local NeighborGScore = LowestNode.GScore + Heuristic(LowestNode, NeighborNode)
local NeighborHScore = Heuristic(NeighborNode, Goal)*1.01
local NeighborFScore = NeighborHScore + NeighborGScore
local NodeIsInOpen, OpenNode, OpenIndex = NodeIsInOpenSet(NeighborNodeX, NeighborNodeY)
local NodeIsInClosed, ClosedNode, ClosedIndex = NodeIsInClosedSet(NeighborNodeX, NeighborNodeY)
if NodeIsInOpen and NeighborGScore < OpenNode.GScore then
RenderNiceBrick(NeighborNodeX,NeighborNodeY, BrickColor.new("Bright orange"), NeighborFScore)
OpenSet[OpenIndex] = nil
end
if NodeIsInClosed and NeighborHScore < ClosedNode.GScore then
RenderNiceBrick(NeighborNodeX,NeighborNodeY, BrickColor.new("Bright red"), NeighborFScore)
ClosedSet[ClosedIndex] = nil
end
if not NodeIsInClosed and not NodeIsInOpen then
RenderNiceBrick(NeighborNodeX,NeighborNodeY, BrickColor.new("Bright blue"), NeighborFScore)
local NewNode = {}
NewNode.X = NeighborNodeX
NewNode.Y = NeighborNodeY
NewNode["GScore"] = NeighborGScore
NewNode["HScore"] = NeighborHScore
NewNode["FScore"] = NeighborFScore
NewNode.Source = LowestNode
OpenSet[#OpenSet+1] = NewNode
end
else
RenderNiceBrick(NeighborNodeX,NeighborNodeY, BrickColor.new("Hot pink"))
print("Can't walk on dat")
end
end
else
RenderNiceBrick(LowestNode.X,LowestNode.Y, BrickColor.new("Bright yellow"))
Continue = false
print("Found goal")
end
end
end
print("Done with A*")
return true, ReconstructPath(SourceNode, {});
end
输出
输出看起来像......（来自我正在为其编写的游戏） http://youtu.be/MNnWHRU7NtU
注释 - 数字是 FScore - 红色 = 完成 - 绿色 = 开始
实际输出示例：
failed @ 59.430702270978
OpenSet has :102 options
Loop #: 156 | Open #: 102
Lowest node is there
X: 160 Y: -13
FScore: 59.424070168796
failed @ 59.424070168796
OpenSet has :104 options
Loop #: 157 | Open #: 104
Lowest node is there
X: 159 Y: -12
FScore: 59.417896359916
failed @ 59.417896359916
OpenSet has :106 options
Loop #: 158 | Open #: 106
Lowest node is there
X: 158 Y: -11
FScore: 59.412223982381
failed @ 59.412223982381
OpenSet has :108 options
Loop #: 159 | Open #: 108
Lowest node is there
X: 157 Y: -10
FScore: 59.407101745211
failed @ 59.407101745211
OpenSet has :110 options
Loop #: 160 | Open #: 110
Lowest node is there
X: 156 Y: -9
FScore: 59.402584854429
failed @ 59.402584854429
OpenSet has :112 options
Loop #: 161 | Open #: 112
Lowest node is there
X: 155 Y: -8
FScore: 59.398736129429
failed @ 59.398736129429
OpenSet has :114 options
Loop #: 162 | Open #: 114
Lowest node is there
X: 154 Y: -7
FScore: 59.395627356727
failed @ 59.395627356727
OpenSet has :116 options
Loop #: 163 | Open #: 116
Lowest node is there
X: 153 Y: -6
FScore: 59.393340941897
failed @ 59.393340941897
OpenSet has :118 options
Loop #: 164 | Open #: 118
Lowest node is there
X: 152 Y: -5
FScore: 59.391971938836
failed @ 59.391971938836
OpenSet has :120 options
Loop #: 165 | Open #: 120
Lowest node is there
X: 151 Y: -4
FScore: 59.391630560343
failed @ 59.391630560343
OpenSet has :122 options
Loop #: 166 | Open #: 122
Lowest node is there
X: 150 Y: -3
FScore: 59.392445307867
failed @ 59.392445307867
OpenSet has :124 options
Loop #: 167 | Open #: 124
Lowest node is there
X: 149 Y: -2
FScore: 59.39456690506
failed @ 59.39456690506
OpenSet has :127 options
Loop #: 168 | Open #: 127
Lowest node is there
X: 148 Y: -1
FScore: 59.398173284976
failed @ 59.398173284976
OpenSet has :128 options
Loop #: 169 | Open #: 128
Lowest node is there
X: 163 Y: -11
FScore: 59.484589358667
failed @ 59.484589358667
OpenSet has :205 options
Loop #: 170 | Open #: 205
Lowest node is there
X: 164 Y: -12
FScore: 59.498131722924
failed @ 59.498131722924
OpenSet has :204 options
Loop #: 171 | Open #: 204
Lowest node is there
X: 165 Y: -13
FScore: 59.511707387983
failed @ 59.511707387983
OpenSet has :206 options
Loop #: 172 | Open #: 206
Lowest node is there
X: 166 Y: -14
FScore: 59.525313655834
failed @ 59.525313655834
OpenSet has :207 options
Loop #: 173 | Open #: 207
Lowest node is there
X: 167 Y: -15
FScore: 59.53894811221
failed @ 59.53894811221
OpenSet has :208 options
Loop #: 174 | Open #: 208
Lowest node is there
X: 168 Y: -16
FScore: 59.552608590246
failed @ 59.552608590246
如果你们发现我的程序或逻辑有任何问题，请告诉我。我确定这是我忽略的一些愚蠢的事情。
谢谢！