Python實(shí)現(xiàn)迷宮自動(dòng)尋路實(shí)例

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

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

背景

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

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

預(yù)處理

設(shè)計(jì)一個(gè)迷宮自動(dòng)尋路算法并不難，但是對(duì)于當(dāng)下這個(gè)任務(wù)而言，第一個(gè)棘手的地方在于，如何把這個(gè)迷宮變成計(jì)算機(jī)認(rèn)識(shí)的樣子，也就是迷宮圖片的矩陣化。

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

尋路算法

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

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

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

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

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

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

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

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

接下來(lái)，讓算法具備自動(dòng)回退的能力。我們想象一個(gè)簡(jiǎn)單情景：

這個(gè)圖不準(zhǔn)確，不滿足本文的優(yōu)先級(jí)設(shè)定，但也足以表意

遇到這樣的死胡同，假如進(jìn)來(lái)的時(shí)候足跡把出去的路給封死了，那么這個(gè)點(diǎn)就沒(méi)辦法再出來(lái)了。一旦我們發(fā)現(xiàn)這個(gè)點(diǎn)陷入了絕境，哪里都不能走了，這時(shí)候我們就得讓它原路返回。實(shí)迷途其未遠(yuǎn)，回到上一個(gè)路口也很簡(jiǎn)單，無(wú)非就是刪掉這一段路線。方法就是把path列表里的最后一個(gè)元素逐一彈出列表，由于我們有footprint記錄，所有它走過(guò)的地方都不能再走第二遍，所以只要這條錯(cuò)誤的路沒(méi)有完全退出去，退到哪一步都是四個(gè)方向都不能走的，因?yàn)楦浇急凰哌^(guò)了。這樣它就會(huì)一直退到我們期望的那個(gè)地方，也就是它誤入歧途的那個(gè)路口。

測(cè)試

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

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

優(yōu)化

我們考慮如下一種簡(jiǎn)單情況：

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

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

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