C語(yǔ)言是所有編程語(yǔ)言的基礎(chǔ)耸采，當(dāng)我們對(duì)C語(yǔ)言有足夠深入的理解后析命，就能輕松入門其他語(yǔ)言主卫，比如現(xiàn)在流行的Python。現(xiàn)在鹃愤，我將帶領(lǐng)大家看一個(gè)基于C語(yǔ)言經(jīng)典算法簇搅，使用Python編寫的塔防小游戲。
在塔防游戲中软吐，有許多敵人向著同一目標(biāo)前進(jìn)瘩将。在很多塔防游戲當(dāng)中，有一條或幾條事先預(yù)定好的路徑凹耙。在一些中姿现，比如經(jīng)典的《Desktop Tower Defense》，你可以將塔放在任何位置肖抱，它們充當(dāng)障礙影響敵人選擇的路徑备典。試一試，點(diǎn)擊地圖來(lái)移動(dòng)墻壁：
我們?nèi)绾蝸?lái)實(shí)現(xiàn)這種效果意述？
像A*這樣的圖搜索算法經(jīng)常被用來(lái)尋找兩點(diǎn)之間的最短路徑提佣。你可以用這個(gè)來(lái)為每一個(gè)敵人找到前往目標(biāo)的路徑。在這種類型的游戲當(dāng)中荤崇，我們有很多不同的圖搜索算法來(lái)拌屏。這是一些經(jīng)典方法
單源，單目標(biāo):
- 貪心搜索算法
- A*算法 – 在游戲當(dāng)中常用
單源多目標(biāo)或多源單目標(biāo)
- 廣度優(yōu)先算法-無(wú)加權(quán)邊
- Dijkstra算法-有加權(quán)邊
- Bellman-Ford算法-支持負(fù)權(quán)重
多源多目標(biāo)
- Floyd-Warshall算法
- Johnson’s算法
像《Desktop Tower Defense》這樣的游戲會(huì)有很多個(gè)敵人（源）和一個(gè)共同的目的地术荤。這使得它被歸為多源單目標(biāo)一類倚喂。我們可以執(zhí)行一個(gè)算法，一次算出所有敵人的路徑瓣戚，而不是為每個(gè)敵人執(zhí)行一次A*算法端圈。更好的是，我們可以計(jì)算出每個(gè)位置的最短路徑带兜，所以當(dāng)敵人擠在一塊或者新敵人被創(chuàng)建時(shí)枫笛，他們的路徑已經(jīng)被計(jì)算好了。
我們先來(lái)看看有時(shí)也被稱作“洪水填充法”（FIFO變種）的廣度優(yōu)先算法刚照。雖然圖搜索算法是適用于任何由節(jié)點(diǎn)和邊構(gòu)成的圖刑巧，但是我還是使用方形網(wǎng)格來(lái)表示這些例子。網(wǎng)格是圖的一個(gè)特例无畔。每個(gè)網(wǎng)格瓦片是圖節(jié)點(diǎn)啊楚，網(wǎng)格瓷磚之間的邊界是圖的邊。我會(huì)在另一篇文章當(dāng)中探討非網(wǎng)格圖浑彰。
廣度優(yōu)先搜索始于一個(gè)節(jié)點(diǎn)恭理，并訪問(wèn)鄰居節(jié)點(diǎn)。關(guān)鍵的概念是“邊界”郭变，在已探索和未開(kāi)發(fā)的區(qū)域之間的邊界颜价。邊界從原始節(jié)點(diǎn)向外擴(kuò)展涯保，直到探索了整張圖碗旅。
邊界隊(duì)列是一個(gè)圖節(jié)點(diǎn)(網(wǎng)格瓦片)是否需要被分析的列表/數(shù)組蒸健。它最開(kāi)始僅僅包含一個(gè)元素粗梭，起始節(jié)點(diǎn)柿究。每個(gè)節(jié)點(diǎn)上的訪問(wèn)標(biāo)志追蹤我們是否采訪過(guò)該節(jié)點(diǎn)僚纷。開(kāi)始的時(shí)候除了起始節(jié)點(diǎn)都標(biāo)志為FALSE授霸。使用滑塊來(lái)查看邊界是如何擴(kuò)展的：
這個(gè)算法是如何工作的伪煤？在每一步朵诫，獲得一個(gè)元素的邊界并把它命名為current寨腔。然后尋找current的每個(gè)鄰居速侈，next。如果他們還沒(méi)有被訪問(wèn)過(guò)的話迫卢，將他們都添加到邊界隊(duì)列里面倚搬。下面是一些python代碼：
Python
frontier = Queue()
frontier.put(start)
visited = {}
visited[start] = True
while not frontier.empty():
current = frontier.get()
for next in graph.neighbors(current):
if next not in visited:
frontier.put(next)
visited[next] = True
frontier = Queue()
frontier.put(start)
visited = {}
visited[start] = True
while not frontier.empty():
current = frontier.get()
for next in graph.neighbors(current):
if next not in visited:
frontier.put(next)
visited[next] = True
現(xiàn)在已經(jīng)看見(jiàn)代碼了，試著步進(jìn)上面的動(dòng)畫乾蛤。注意邊界隊(duì)列潭枣，關(guān)于current的代碼，還有next節(jié)點(diǎn)的集合幻捏。在每一步盆犁，有一個(gè)邊界元素成為current節(jié)點(diǎn)，它的鄰居節(jié)點(diǎn)會(huì)被標(biāo)注篡九，并且未被拜訪過(guò)的鄰居節(jié)點(diǎn)會(huì)被添加到邊界隊(duì)列谐岁。有一些鄰居節(jié)點(diǎn)可能已經(jīng)被訪問(wèn)過(guò)，他們就不需要被添加到邊界隊(duì)列里面了榛臼。
這是一個(gè)相對(duì)簡(jiǎn)單的算法伊佃，并且對(duì)于包括AI在內(nèi)的很多事情都是有用的。我有三種主要使用它的辦法：
1.標(biāo)識(shí)所有可達(dá)的點(diǎn)沛善。這在你的圖不是完全連接的航揉，并且想知道哪些點(diǎn)是可達(dá)的時(shí)候是很有用的。這就是我再上面用visited這部分所做的金刁。
2.尋找從一個(gè)點(diǎn)到所有其他點(diǎn)或者所有點(diǎn)到一個(gè)點(diǎn)的路徑帅涂。我在文章開(kāi)始部分的動(dòng)畫demo里面使用了它。
3.測(cè)量從一個(gè)點(diǎn)到所有其他點(diǎn)的距離尤蛮。這在想知道一個(gè)移動(dòng)中的怪物的距離時(shí)是很有用的媳友。
如果你正在生成路徑，你可能會(huì)想知道從每個(gè)點(diǎn)移動(dòng)的方向产捞。當(dāng)你訪問(wèn)一個(gè)鄰居節(jié)點(diǎn)的時(shí)候醇锚，要記得你是從哪個(gè)節(jié)點(diǎn)過(guò)來(lái)的。讓我們把visited重命名為came_from并且用它來(lái)保存之前位置的軌跡：
Python
frontier = Queue()
frontier.put(start)
came_from = {}
came_from[start] = None
while not frontier.empty():
current = frontier.get()
for next in graph.neighbors(current):
if next not in came_from:
frontier.put(next)
came_from[next] = current
frontier = Queue()
frontier.put(start)
came_from = {}
came_from[start] = None
while not frontier.empty():
current = frontier.get()
for next in graph.neighbors(current):
if next not in came_from:
frontier.put(next)
came_from[next] = current
我們來(lái)看看它看起來(lái)是怎樣的：
如果你需要距離坯临，你可以在起始節(jié)點(diǎn)講一個(gè)計(jì)數(shù)器設(shè)置為0焊唬，并在每次訪問(wèn)鄰居節(jié)點(diǎn)的時(shí)候?qū)⑺右涣抵纭Ｗ屛覀儼裿isitd重命名為distance，并且用它來(lái)存儲(chǔ)一個(gè)計(jì)數(shù)器：
Python
frontier = Queue()
frontier.put(start)
distance = {}
distance[start] = 0
while not frontier.empty():
current = frontier.get()
for next in graph.neighbors(current):
if next not in distance:
frontier.put(next)
distance[next] = 1 + distance[current]
frontier = Queue()
frontier.put(start)
distance = {}
distance[start] = 0
while not frontier.empty():
current = frontier.get()
for next in graph.neighbors(current):
if next not in distance:
frontier.put(next)
distance[next] = 1 + distance[current]
我們來(lái)看看它看起來(lái)是怎樣的：
如果你想同時(shí)計(jì)算路徑和距離赶促，你可以使用兩個(gè)變量焰雕。
這就是廣度優(yōu)先檢索算法。對(duì)于塔防風(fēng)格的游戲芳杏，我用它來(lái)計(jì)算所有位置到一個(gè)指定位置的路徑，而不是重復(fù)使用A*算法為每個(gè)敵人分開(kāi)計(jì)算路徑辟宗。我用它來(lái)尋找一個(gè)怪物指定行動(dòng)距離內(nèi)所有的位置爵赵。我也是用它來(lái)進(jìn)行程序化的地圖生成。Minecraft使用它來(lái)進(jìn)行可見(jiàn)性提出泊脐。由此可見(jiàn)這是一個(gè)不錯(cuò)的算法空幻。
下一步
我有python和c++代碼的實(shí)現(xiàn)。
如果你想要找到從一個(gè)點(diǎn)出發(fā)而不是到達(dá)一個(gè)點(diǎn)的路徑容客，只需要在檢索路徑的時(shí)候翻轉(zhuǎn)came_from指針秕铛。
如果你想要知道一些點(diǎn)而不是一個(gè)點(diǎn)的路徑，你可以在圖的邊緣為你的每個(gè)目標(biāo)點(diǎn)添加一個(gè)額外的點(diǎn)缩挑。額外的點(diǎn)不會(huì)出現(xiàn)在網(wǎng)格中但两，但是它會(huì)表示在圖中的目標(biāo)位置。
提前退出：如果你是在尋找一個(gè)到達(dá)某一點(diǎn)或從某一點(diǎn)出發(fā)供置，谨湘。我在A*算法的文章當(dāng)中描述了這種情況。
加權(quán)邊：如果你需要不同的移動(dòng)成本芥丧，廣度優(yōu)先搜索可以替換為為Dijkstra算法紧阔。我在A*算法的文章當(dāng)中描述了這種情況。
啟發(fā)：如果你需要添加一種指導(dǎo)尋找目標(biāo)的方法续担，廣度優(yōu)先算法可以替換為最佳優(yōu)先算法擅耽。我在A*算法的文章當(dāng)中描述了這種情況。
如果你從廣度優(yōu)先算法物遇，并且加上了提前退出乖仇，加權(quán)邊和啟發(fā)，你會(huì)得到A询兴。如你所想这敬，我在A算法的文章當(dāng)中描述了這種情況。
