如何儘量不Search 到重覆的Branch - 拼圖

最近在玩一套Boardgame 叫Titan

他的戰鬥地圖可以在這邊找到 http://colossus.sourceforge.net/

就是由一堆六角形形成一個大六角形的地圖

目前我想做的事是當生物上戰場時, 用電腦找出他所有能走的路徑

我簡單講一下戰鬥的規則, 他大至上分為兩個phase

第一個 phase 是移動, 第二個 phase 是攻擊, 必須要全部移動完才進行攻擊

每隻生物的移動力不完全相同, 他可以選擇不動或是移動到某一個地方

每隻生物只能動一次, 但每次的移動都必須有合理的行徑路線

例如不會飛的生物甲, 他前方剛好有自己的同伴乙擋著他的路

他如果想前進, 就必須要先移走同伴乙, 然後自己再來移動, 或者是趬遠路

所以我的問題就是先移動甲再移動乙, 和先移動乙再移動甲可能會產生同樣的版面

在Search 這些路徑時, 如果能夠儘量不重覆Search 到同樣的版面

將可以節省大量的時間

請大家幫忙想看看囉

如果這問題不適合在這裡, 請版主不用客氣:)





--