在RPG游戲中我們經(jīng)常會(huì)看到一些迷宮，我之前玩仙劍一的時(shí)候就經(jīng)常在幾個(gè)迷宮里繞來繞去也繞不出來，玩仙三由于游戲視角可以轉(zhuǎn)，更是費(fèi)勁。這里我們使用深度優(yōu)先算法達(dá)到遍歷一個(gè)迷宮的目的。

?? 首先定義一個(gè)有序元組A:{左，上，右，下}表示遍歷的順序，這個(gè)順序?qū)⒂脕砩伤阉鳂涞淖庸?jié)點(diǎn)，當(dāng)然順序是可以變的，如果地圖是45度角的，也可以定義非正方向，總之能表示一個(gè)順序就好。

?? 然后針對(duì)每個(gè)分叉節(jié)點(diǎn)，定義候選方向?yàn)锽:{x|x∈A ∩x方向有路可走∩ x≠當(dāng)前方向}，算法每次得到按照A排序的B集合，然后從B中取第一個(gè)方向進(jìn)行，一直到B=Φ。當(dāng)B=Φ時(shí)回溯到上一個(gè)節(jié)點(diǎn)，然后得到當(dāng)前節(jié)點(diǎn)的B集，從中選擇優(yōu)先級(jí)低于當(dāng)前方向的方向繼續(xù)前進(jìn).如此可以遍歷整個(gè)迷宮。

?? 本算法的問題在于迷宮必須是非成環(huán)的，像仙劍三到大渡口的迷宮就是有環(huán)的，所形成的就不是搜索樹而是搜索圖，另一個(gè)問題是如果完全執(zhí)行算法最后會(huì)停在入口的位置，所以見到出口您就出吧，見好就收。

?? 舉一個(gè)例子。

?? 如上圖所示的迷宮A集合{左，上，右，下}，B集合依次如下所示：

{右}

{下}

{右}

{右，下}選則右

{上}

{右}回退一個(gè)

{上}回退一個(gè)

{右，下}選擇下

{右}

{下}見好就收吧，出迷宮去嘍

?? 搜索樹如圖所示，每個(gè)子節(jié)點(diǎn)集合就是B

??????? 右

??????? |

??????? 下

??????? |

??????? 右

?????? /? \

????? 右?? 下

????? |??? |

????? 上?? 右

????? |??? |

????? 右?? 下

?? 當(dāng)然實(shí)際的迷宮構(gòu)成的搜索樹會(huì)很復(fù)雜,但是深度優(yōu)先的思路還是一致的.

轉(zhuǎn)載于:https://www.cnblogs.com/sdqxcxh/archive/2010/08/13/1798995.html

總結(jié)

以上是生活随笔為你收集整理的深度优先搜索算法在RPG游戏迷宫中的应用的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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