[問題] 演算法問題...

[骨頭]

請益 ,
如果我今天的已知的題目是這樣.


我假設有一個 100* 100的地圖,其上有障礙物. (以01代替)

00000
01010
01110
00000
類似這樣 1就是可以走的路 0就是不能走的路


而我今天假設是使用者帶著多隻寵物在逛地圖 ,
使用者移動的時候 , 寵物必須跟隨著使用者 , 但是不能同一格.

而且使用者和寵物有速度上的差別，可能越走就會越拉越遠。
(如果畫面距離超過20格就不追了)

以上是我碰到的難題啦...￣▽￣



暫且先不考慮寵物卡到寵物的問題 ,

由於人物的座標值是會常常變動的，所以我不能用老鼠迷宮的方式，
設訂一個固定的終點讓它去跑，而必須用追的.....


目前前人的作法是取得使用者的座標 以xy座標逐漸靠近的方式去前進，
這是最基本的想法嘛，但是只要一碰到障礙物就會被擋下來。


而且感覺上也是"笨笨的" orzorz
有沒有類似路徑追蹤的演算法可以用......


目前是找到一個螞蟻演算法 正在努力閱讀中￣▽￣

--
I am a person, and I am always thinking .
Thinking in love , Thinking in life ,
Thinking in why , Thinking in worth.
I can't believe any of what ,
I am just thinking then thinking ,
but worst of all , most of mine is thinking not actioning...

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.134.27.68

[!H45]

※ 引述《TonyQ (骨頭)》之銘言：
: 請益 ,
: 如果我今天的已知的題目是這樣.
: 我假設有一個 100* 100的地圖,其上有障礙物. (以01代替)
: 00000
: 01010
: 01110
: 00000
: 類似這樣 1就是可以走的路 0就是不能走的路
: 而我今天假設是使用者帶著多隻寵物在逛地圖 ,
: 使用者移動的時候 , 寵物必須跟隨著使用者 , 但是不能同一格.
: 而且使用者和寵物有速度上的差別，可能越走就會越拉越遠。
: (如果畫面距離超過20格就不追了)
: 以上是我碰到的難題啦...￣▽￣
: 暫且先不考慮寵物卡到寵物的問題 ,
: 由於人物的座標值是會常常變動的，所以我不能用老鼠迷宮的方式，
: 設訂一個固定的終點讓它去跑，而必須用追的.....
: 目前前人的作法是取得使用者的座標 以xy座標逐漸靠近的方式去前進，
: 這是最基本的想法嘛，但是只要一碰到障礙物就會被擋下來。
: 而且感覺上也是"笨笨的" orzorz
: 有沒有類似路徑追蹤的演算法可以用......
: 目前是找到一個螞蟻演算法 正在努力閱讀中￣▽￣

BFS 不行嗎...?

覺得廣度優先走訪太笨的話，就用 Best first search
其中的 A* algorithm 應該是最「聰明」的吧？ (當然有許多元素要自己定義)

再不然就採用 Reinforcement learning
放狗自己慢慢學著如何追人

不知道以上方案好不好？

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.205.85

[骨頭]

※ 引述《H45 (!H45)》之銘言：
: ※ 引述《TonyQ (骨頭)》之銘言：
: BFS 不行嗎...?
: 覺得廣度優先走訪太笨的話，就用 Best first search
: 其中的 A* algorithm 應該是最「聰明」的吧？ (當然有許多元素要自己定義)

嗯 後來採用A*

cost不高(距離是20格內的小地圖 , 每次約0~5 ms)
又很自然，是很不錯的東西。

貼上一點當時的參考資料和我的實作code

參考資料 (這兩篇其實是翻譯同一篇文章 不過對照著看有不同收穫)
http://www.roboticfan.com/college/knowledge/200606/147.shtml
http://swf.com.tw/?p=67

code實作
http://tony1223.no-ip.info:1223/bmore?Flyword&4646

(因為碼有點長，我直接貼我的webbs連結。
如果連結跑掉了可以來信跟我說T^T)


底下是一點點的心得 , 有錯的地方歡迎提出來討論 .(冏)


1.基本原理 g = 路徑成本 , h=到達目標的"估計"成本 , F=總成本(g+h)

它並不直接找出一條路徑，而是透過計算成本後指定前一格的方式。

當到達終點時，透過終點回推最低成本的路徑，
從終點的的前一格→前一格→前一格→起始格‧找到路徑。
有點類似LinkedList的那種串聯的概念...

這邊看起來還蠻抽象的T^Ta 失敗了三四次才成功

2.它的發展並不是就單一條線的發展
而是就目前的視野(openlist)
去找出以目前的視野底下成本最低的路徑(F值最低)

我一開始一直以為它是沿線尋找...所以把cango寫錯了...
這是蠢點1 orz


3.它的作法是建立一個大地圖的陣列(whichlist)，然後每次查詢給與不
同的onClose跟onOpen，感覺上是為了方便連續多次的查找的時候，
不會互相混淆。

不過我的case由於地圖本身座標值蠻高的，
幾百個地圖又沒有一個固定的size，所以建表法對我來講不實際。

我採用的是把xy先做hash , f(x,y) = x*最大長度 +y 的狀況，
(in my case f(x,y) = 50000*x+y)

把看過的點(onOpen and onClose) 建立在 allpoint 這個HashMap裡面。

只要透過查找Hash值就可以馬上知道這個點是不是已經存在，
而且也可以知道這個點是 onClose或onOpen 。(透過Node的type紀錄)

4.另外openList採用BinaryHeap維護 ... (minHeap)
降低查找最低F的成本 (這個增進效能非常多)

────────────────────────────────

3跟4 如果是用List再用 O(n) 的列舉法取做查找,效能差蠻多的
以底下的測資來說，我採用前者時是 106ms，採用後者時16 ms...￣▽￣

不過我前者的code沒留下來，所以可能也是我哪裡有沒寫好的地方...XD

另外影響這演算法的地方有兩個...
1.G值的計算, 會直接影響到取點的優先度...
在我的case是以角色為中心的八格損耗都一樣。
在參考文章的範例則是走斜角會加大損耗。

2.cango的地方可以決定哪些點是可以走的
另外 掃點的時候不見得要掃九宮格...
視case不同的情況而定

--
11001100111111110101
01001000001100011001
11010010100111101111
10011100000010100100
10111001011100100101
11101000111111100101
10001101000010000100
11110101010110000100
11101111100010011101
10111000101010011110
11001000011111001101
01101001110100010110
00111100101011111010
10001001110111110011
00001010111010010001
11111101001001101011
10010101111011111010
10111011010110110111
11101001101000011100
00011111001110011111

--
　▄▅▆▇███▇▆▅▄▃　　　　　　　　╰┼╯─╮ ╮　　　　　 　
　◥███████████◣　　　　　　　╰┼╯＝│=│　　　　　　　　 
◥██████───────◣　　　　＊．　╯　 ╯ ╯ 　物　語　．＊
　◥███████──────◣　～　◢◣　　　　　　　　　　　　 ◢◣
　◥██████───────◤　　　◥◤＊　　空白的世界．翼 ＊◥◤
 　◥██▁▂▃▄▅▆▇███▆▅▄▃▂▂～telnet://tony1223.no-ip.info

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.134.27.68