2019獨(dú)角獸企業(yè)重金招聘Python工程師標(biāo)準(zhǔn)>>>

■在A *方法總結(jié)

Summary of the A* Method

?

好了，現(xiàn)在你通過解釋已經(jīng)走了，讓我們奠定了一步一步的方法，在同一個(gè)地方：

Okay, now that you have gone through the explanation, let's lay out the step-by-step method all in one place:

?

添加開始方塊（或節(jié)點(diǎn)）到開啟列表。

Add the starting square (or node) to the open list.

?

重復(fù)以下操作：

Repeat the following:

?

a） 尋找開啟列表上最小F值的方塊。我們將此作為當(dāng)前方塊。

Look for the lowest F cost square on the open list. We refer to this as the current square

?

b） 切換到關(guān)閉列表。

Switch it to the closed list.

?

c）? 對(duì)于當(dāng)前方塊的8個(gè)方塊的每一個(gè)...

c) For each of the 8 squares adjacent to this current square …

?

如果不能走，或者如果它是關(guān)閉的名單上，忽略它。否則，請(qǐng)執(zhí)行以下操作。

If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.

?

如果不在開啟列表中，將其添加到開啟列表。使當(dāng)前方塊成為這個(gè)方塊的父。記錄的方塊F值，G值和H值。

If it isn't on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square.

?

如果在開啟列表了，檢查，看看這個(gè)路徑，該方塊是否是更好的，采用G值作為衡量。更低的G值意味著這是一個(gè)更好的路徑。如果是這樣，把方格的父改變當(dāng)前方塊，并重新計(jì)算方塊的G值和F值。如果你保持開啟列表排序F值，由于這個(gè)變化你可能需重存列表。

If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.

?

d）當(dāng)你停止：

d) Stop when you:

?

目標(biāo)方塊添加到關(guān)閉列表，在這種情況下，路徑已經(jīng)被發(fā)現(xiàn)（見下面的注），或無法找到目標(biāo)方塊，并且開啟列表是空的。在這種情況下，不存在路徑。

Add the target square to the closed list, in which case the path has been found (see note below), or Fail to find the target square, and the open list is empty. In this case, there is no path.

?

保存路徑。從目標(biāo)方塊往回走，從每個(gè)方塊移到其父，直到你到達(dá)開始方塊。這是你的路徑。

Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path.

?

注：在早期版本的文章中，有人建議，當(dāng)目標(biāo)方塊（或節(jié)點(diǎn)）已經(jīng)添加到開啟列表，而不是關(guān)閉的列表，你可以停下來。這樣做會(huì)更快，它幾乎總是會(huì)給你的最短路徑，但并非總是如此。有些情況下，這樣做可能產(chǎn)生差異當(dāng)從第二移動(dòng)到最后一個(gè)節(jié)點(diǎn)到最后的（目標(biāo)）節(jié)點(diǎn)的運(yùn)動(dòng)成本可能有明顯變化 -例如，如果在河流交叉在兩個(gè)節(jié)點(diǎn)之間的情況下。

Note: In earlier versions of this article, it was suggested that you can stop when the target square (or node) has been added to the open list, rather than the closed list. Doing this will be faster and it will almost always give you the shortest path, but not always. Situations where doing this could make a difference are when the movement cost to move from the second to the last node to the last (target) node can vary significantly -- as in the case of a river crossing between two nodes, for example.

?

■小咆哮

Small Rant

?

請(qǐng)原諒我的題外話，但值得指出的是，當(dāng)你在網(wǎng)上閱讀的A *路徑搜索，并在各類論壇上的各種討論時(shí)，你偶爾會(huì)看到有人提到某些代碼不是A *。對(duì)于A *使用方法，你需要包含上面討論到的元素 -- 特別是開放列表和關(guān)閉列表和路徑采用F值，G值和H值。有很多其他的路徑搜索算法，但是其它的通常被認(rèn)為是最好的方法不是A *。在這篇文章的末尾有布萊恩斯托特討論，包括他們的一些利弊引用的文章很多。有時(shí)替代品在某些情況下更好，但你應(yīng)該明白你正在進(jìn)入。好了，爽了。回到話題。

Forgive me for digressing, but it is worth pointing out that when you read various discussions of A* pathfinding on the web and in assorted forums, you will occasionally see someone refer to certain code as A* when it isn't. For the A* method to be used, you need to include the elements just discussed above -- specifically open and closed lists and path scoring using F, G, and H. There are lots of other pathfinding algorithms, but those other methods are not A*, which is generally considered to be the best of the lot. Bryan Stout discusses many of them in the article referenced at the end of this article, including some of their pros and cons. Sometimes alternatives are better under certain circumstances, but you should understand what you are getting into. Okay, enough ranting. Back to the article.

?

（待續(xù)）

轉(zhuǎn)載于:https://my.oschina.net/dubenju/blog/464443

總結(jié)

以上是生活随笔為你收集整理的再译《A *路径搜索入门》之四的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。