討論區快速選單
知識庫快速選單
網路投保旅行平安險 網路投保旅行平安險
[ 回上頁 ] [ 討論區發言規則 ]
如何求出避過物件的最短路徑?
更改我的閱讀文章字型大小
作者 : kagaya(kagaya) VC++優秀好手C++優秀好手貼文超過1000則人氣指數超過30000點
[ 貼文 1601 | 人氣 38709 | 評價 4610 | 評價/貼文 2.88 | 送出評價 115 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2010/1/8 下午 04:41:51
假設畫面上散布一些矩形物件
然後有A和B兩個點
用線將兩個點連接起來
線只能走水平或垂直兩個方向
而且要避開散落在A和B之間的矩形
轉彎次數愈少和路徑愈短愈好
不知有沒有什麼好的算法可以參考?
謝謝
作者 : ozzy123(ozzy) VC++優秀好手資訊類作業求救卓越專家C++卓越專家貼文超過4000則人氣指數超過30000點
[ 貼文 4498 | 人氣 37262 | 評價 11100 | 評價/貼文 2.47 | 送出評價 49 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
主題發起人kagaya註記此篇回應為很有道理 2010/1/10 上午 09:38:16
no shortest path , just reduce times you turn right or left.

you can use a n by m array to simulate above conditions. this algorithm is easy
作者 : kagaya(kagaya) VC++優秀好手C++優秀好手貼文超過1000則人氣指數超過30000點
[ 貼文 1601 | 人氣 38709 | 評價 4610 | 評價/貼文 2.88 | 送出評價 115 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2010/1/10 下午 10:19:43
感謝回覆
n by m array....
我再找找看
作者 : jawa560(Snaking) Java Script優秀好手貼文超過1000則人氣指數超過30000點
[ 貼文 1154 | 人氣 32593 | 評價 4630 | 評價/貼文 4.01 | 送出評價 168 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
主題發起人kagaya註記此篇回應為很有道理 2010/1/11 上午 01:42:12
剛好想試試春源兄介紹的 Raphael (http://www.programmer-club.com.tw/showsametitleN/javascript/8947.html),於是寫了個範例,不知這是不是你想要的東西?
http://www.sailing.org.tw/tutorial/cross_blocks.htm
打包下載:
http://www.sailing.org.tw/tutorial/cross_blocks.rar

說明:
1.建議用Firefox 執行會比較沒問題.
2.試作類似資料表關聯的路徑.
3.矩形可拖拉,路徑兩邊控制點也可拖拉.
4.會自動決定走下面還是走上面.
4.計算上還不是很完美,僅供參考.
作者 : kagaya(kagaya) VC++優秀好手C++優秀好手貼文超過1000則人氣指數超過30000點
[ 貼文 1601 | 人氣 38709 | 評價 4610 | 評價/貼文 2.88 | 送出評價 115 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2010/1/11 上午 09:40:04
大大真是高手啊
能夠用網頁做出這樣的效果
不過試用發現一些小問題
線會從物件之中穿過去
還有會繞遠路 幾乎都是從外圍繞回去
但其實目視是有轉彎更少更近的路徑的
不過我會拜讀您的原碼
希望能夠從中獲得啟發
非常感謝
作者 : jawa560(Snaking) Java Script優秀好手貼文超過1000則人氣指數超過30000點
[ 貼文 1154 | 人氣 32593 | 評價 4630 | 評價/貼文 4.01 | 送出評價 168 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2010/1/11 上午 10:38:36
不知你有沒有弄錯,第一個連結是春源兄的一個範例,第二個連結才是針對本CASE 的範例.
一切都要感謝春源兄引薦好東西,他才是高手 ^^!
作者 : kagaya(kagaya) VC++優秀好手C++優秀好手貼文超過1000則人氣指數超過30000點
[ 貼文 1601 | 人氣 38709 | 評價 4610 | 評價/貼文 2.88 | 送出評價 115 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2010/1/11 下午 01:24:41
大大您好
我應該是沒弄錯 我是下載.rar回來執行
執行結果如下
http://kagaya98.myweb.hinet.net/01.jpg
但是照理說它應該會跑出下面的結果(下面那張是我用小畫家畫出來的)
http://kagaya98.myweb.hinet.net/02.jpg
也就是說
第一張圖它沒有選擇從中間走 而是選擇從外圍繞遠路過去
而它對外圍的定義方式 應該是算出能包容這四個矩形的一個大矩形
然後依據這個大矩形來走的樣子
這樣一來 不但路徑長 也多了一些不必要的轉角
不知我的理解是否有誤?
謝謝
作者 : jawa560(Snaking) Java Script優秀好手貼文超過1000則人氣指數超過30000點
[ 貼文 1154 | 人氣 32593 | 評價 4630 | 評價/貼文 4.01 | 送出評價 168 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2010/1/11 下午 11:09:31
對不起,看不到你的圖!
我目前的算法是很粗淺的,的確是完全避過所有中間方塊. 如果不符合您的需求,那麼就要用複雜許多的演算法!
我接下來幾天會很忙,可能沒空來試做這個 CASE. 但仍然好奇您的需求到底是什麼,所以若方便的話,可否將圖片發到我信箱?
jawa560小老鼠ms5點hinet點net,謝謝!
作者 : kagaya(kagaya) VC++優秀好手C++優秀好手貼文超過1000則人氣指數超過30000點
[ 貼文 1601 | 人氣 38709 | 評價 4610 | 評價/貼文 2.88 | 送出評價 115 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2010/1/12 上午 09:34:34
大大您好
不好意思麻煩您花寶貴的時間說
所以我還是決定用自己的方法
用迴圈去把它算出來
雖然我覺得這個方法是最差的方法=.=
各位大大若有好方法也歡迎提供
謝謝
作者 : jason680(Jsn) 貼文超過200則
[ 貼文 209 | 人氣 1 | 評價 810 | 評價/貼文 3.88 | 送出評價 4 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
主題發起人kagaya註記此篇回應為很有道理 2010/1/13 下午 12:48:42
看了01.jpg,與02.jpg
這都是其中一個解

要找出最佳解,就是走完所有的解(或者用高深理論求出解---我不知道,所以稱其高深...),
然後比較誰的最好.

真正的解(步數同02.jpg,但轉角最少)應該是
1.先往上
2.往右
3.再往上
轉兩次,距離同02.jpg(02.jpg共轉三次)

作者 : kagaya(kagaya) VC++優秀好手C++優秀好手貼文超過1000則人氣指數超過30000點
[ 貼文 1601 | 人氣 38709 | 評價 4610 | 評價/貼文 2.88 | 送出評價 115 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2010/1/13 下午 02:30:51
感謝回覆
你說的沒錯 不過我那張只是示意圖而已
其實兩個點相連會有四個方向
左上 右上 左下 右下
用迴圈往它的方向推應該就可以推出答案來
只是想說應該有更好的方法?
作者 : alexlyblue(Aber)
[ 貼文 90 | 人氣 0 | 評價 380 | 評價/貼文 4.22 | 送出評價 13 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
主題發起人kagaya註記此篇回應為很有道理 2010/1/13 下午 04:23:51
我有點忘了所以只能說個大概
1. 要找最短路徑, 必須全部路徑走完
2. 給個值讓每次轉彎遞加
3. 切成多條平行線 ( 因為你要左右轉 )
4. 在同一平行線上尋找該值之最小值
以上是避開的方法, 同理最短路徑, 也就是垂直線, 用的方式也跟上面差不多
最後 簡單來說 你就把它看成簡單的二元樹就好, 應該是這樣.. 很久以前作的有點忘記了

... 最近連打個字都會Delay ... 老是打錯字
作者 : dragon229(程式入門中)
[ 貼文 3 | 人氣 0 | 評價 10 | 評價/貼文 3.33 | 送出評價 0 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2010/1/15 下午 04:38:28
http://blog.minstrel.idv.tw/2004/12/star-algorithm.html

不知這個能不能幫到你

最少轉角的部份應該把找出的路線能合併的角都合併起來應該就行了
作者 : jawa560(Snaking) Java Script優秀好手貼文超過1000則人氣指數超過30000點
[ 貼文 1154 | 人氣 32593 | 評價 4630 | 評價/貼文 4.01 | 送出評價 168 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2010/1/19 下午 11:00:47
更新了最新實作在:
http://www.sailing.org.tw/tutorial/cross_blocks_V4.htm
(請使用FireFox 觀看)

可以說是花了九牛二虎之力,但還是沒全部完成. 若有人有興趣, 再來談演算邏輯.
 板主 : 小朱
 > 高手過招區 - 討論區
 - 最近熱門問答精華集
 - 全部歷史問答精華集
 - 高手過招區 - 知識庫
  ■ 全站最新Post列表
  ■ 我的文章收藏
  ■ 我最愛的作者
  ■ 全站文章收藏排行榜
  ■ 全站最愛作者排行榜
  ■  月熱門主題
  ■  季熱門主題
  ■  熱門主題Top 20
  ■  本區Post排行榜
  ■  本區評價排行榜
  ■  全站專家名人榜
  ■  全站Post排行榜
  ■  全站評價排行榜
  ■  全站人氣排行榜
 請輸入關鍵字 
  開始搜尋
 
Top 10
評價排行
高手過招區
1 冼鏡光 410 
2 長長 350 
3 eBoy 290 
4 Benson 280 
5 速定 260 
6 HKLN.net 240 
7 青衫 210 
8 ozzy 190 
9 冷眼 150 
10 John 150 
高手過招區
  專家等級 評價  
  一代宗師 10000  
  曠世奇才 5000  
  頂尖高手 3000  
  卓越專家 1500  
  優秀好手 750  
Microsoft Internet Explorer 6.0. Screen 1024x768 pixel. High Color (16 bit).
2000-2019 程式設計俱樂部 http://www.programmer-club.com.tw/
0.078125