Python實現(xiàn)迷宮自動尋路實例

更新時間：2022年02月08日 14:16:14 作者：程序媛小本

大家好，本篇文章主要講的是Python實現(xiàn)迷宮自動尋路實例，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下

背景

我打開手機，發(fā)現(xiàn)有人在QQ空間里叫囂。

看他得意的樣子，顯然是在家里呆久了，已經(jīng)忘了天有多高。

預處理

設計一個迷宮自動尋路算法并不難，但是對于當下這個任務而言，第一個棘手的地方在于，如何把這個迷宮變成計算機認識的樣子，也就是迷宮圖片的矩陣化。

圖片的大小是397×390。先把四周的白邊裁掉，再把這幅圖中的每一個像素二值化，再根據(jù)顏色賦值，黑色用0表示，白色用1表示，建立一個0/1矩陣?？紤]到迷宮的邊界都是封閉的，為了防止由于圖片質(zhì)量問題導致某些看上去是0的地方其實是1，在之后走迷宮的過程中造成一些可預知的影響，比如列表的越界等，我們再把四條邊上的元素全部強制變成0。這時，對迷宮的預處理已經(jīng)基本完成，如果我們把1隱藏，把所有的0打印出來，經(jīng)過放縮之后，就得到了這樣的結(jié)果：

尋路算法

得到了這個迷宮矩陣之后，我們需要找到一條從左上角到右下角的路。

印象中我與有關(guān)走迷宮的方法有過一面之緣，那是在一節(jié)算法選修課上，老師在臺上深情地講著深度優(yōu)先搜索與廣度優(yōu)先搜索，我在臺下忘我地抄著大物實驗報告。至今，提起這兩個概念，我唯一的印象只有它倆的英文縮寫一個是D開頭一個是B開頭。

不過沒關(guān)系。當年陳刀仔他能用20塊贏到3700萬，我用for循環(huán)搞定這個小迷宮，沒有問題。

一般來說，迷宮的內(nèi)部是不封閉的，我從任意一個地方倒水，總能把整個迷宮填滿。因此，假定我們有一個小老鼠，把它放在起點，如果它能夠保證自動避障、不踩走過的路、遇死胡同回退，那么它總能找到終點。

因此，我們定義一個點(x,y)，初始位置為(1,1)，也就是邊界內(nèi)左上角的第一個點。

定義兩個列表，一個是path，用來存放它最終確定下來的路徑（也就是那個最終走到終點的路徑）中的每一個點；另一個是footprint，用來存放所有它走過的地方，包括它走的錯路。兩個列表形如[(1,1),(1,2),(2,2),......,(m,n)]。

再定義四種動作，分別是：向下走一步(y=y+1)，向右走一步(x=x+1)，向左走一步(x=x-1)和向上走一步(y=y-1)。我們每次讓這個點嘗試四種動作，如果能走就讓它走。判斷是否不能走是看下一步的坐標是否是墻或者是足跡。把新的點放進path和footprint里，成為新的足跡。

確定四個動作的優(yōu)先級，即下、右、左、上，能下則下，不能下則右，不能右則左，不能左則上。這樣它就不會在一個空地上平白無故地亂轉(zhuǎn)，而是具有一定方向性地探索。

接下來，讓算法具備自動回退的能力。我們想象一個簡單情景：

這個圖不準確，不滿足本文的優(yōu)先級設定，但也足以表意

遇到這樣的死胡同，假如進來的時候足跡把出去的路給封死了，那么這個點就沒辦法再出來了。一旦我們發(fā)現(xiàn)這個點陷入了絕境，哪里都不能走了，這時候我們就得讓它原路返回。實迷途其未遠，回到上一個路口也很簡單，無非就是刪掉這一段路線。方法就是把path列表里的最后一個元素逐一彈出列表，由于我們有footprint記錄，所有它走過的地方都不能再走第二遍，所以只要這條錯誤的路沒有完全退出去，退到哪一步都是四個方向都不能走的，因為附近都被它走過了。這樣它就會一直退到我們期望的那個地方，也就是它誤入歧途的那個路口。

測試

下面，我們讓它開始循環(huán)。只要它的坐標不等于終點的坐標，我們就一直讓它不斷地探索。運行結(jié)束后，我們得到了一條迂回的曲線，如圖（局部）。

程序成功得到了一條可以通往終點的路徑，但這條路徑過于冗雜，以上圖為例，所有寬度不為1的地方都是這個點繞來繞去所導致的。因此，該路徑還有待優(yōu)化。

優(yōu)化

我們考慮如下一種簡單情況：

在這條路線中，顯然4~9屬于沒有意義的兜圈，正確的路線應該是從3直接到10。

我們的優(yōu)化方法是：如果第n步在(x,y)，從第n+2步（也就是下一步的下一步），一直到最后一步，這中間只要有一步落在(x,y)一步之遙的地方，就把從第n+1步到這一步的所有路徑點都刪掉。拿上面這個例子來說，我們從第1步開始檢查。檢查到第3步時，我們從第5步開始看，一直看到第10步發(fā)現(xiàn)10落在3一步就能到達的地方，這時我們把中間的4-9全部刪掉，直接把10接在3的后面。

不過，考慮到后面可能還會有更優(yōu)的情況，比如說從12開始繼續(xù)繞，繞到20發(fā)現(xiàn)20剛好落在3的上面，那我們事實上應該直接把20接在3后面，12也要丟掉，之前的方法有些缺陷。因此，為了避免這種情況，我們逆著循環(huán)，對于第3步而言，我們從第20步往前循環(huán)，一直循環(huán)到第5步，看是否有3能直接到達的地方。這樣我們就能對這條路線進行最大優(yōu)化了。