[問題] 小精靈遊戲裡, 如何決定Ghost的路徑

[Racci (Another Day...)]

As title,

先簡單介紹這個遊戲, 英文是叫做PacMan, 也就是大家俗稱的小精靈遊戲
在迷宮裡, 有
1. PacMan: 即User本身
2. Jewel: 放在迷宮裡的寶物
3. Ghost: 在迷宮裡四處移動的怪物, 如果PacMan碰到鬼, 就Game Over了..

我已經做的差不多, 是StandAlone版..
但是有一個很蠢的Bug..
Ghost移動時, 很容易跑一跑就陷入某各程度的loop, 不斷循環的跑某各區域
先承認我現在做的路徑判斷很爛..
大致就是 看現在的位置 上下左右 哪各可以走 就往哪邊走
可能是因為上下左右判斷的順序一下  所以才會讓Ghost跑一跑就開始循環

在網路上找過一些資料
有些人是說, 必須要找出Ghost跟PacMan之間的最短路徑
但是我一直不懂.. 所謂的最短路徑怎麼找出來

舉例來說:

##########
#        #
# p### # #
# ##   # #
#     ## #
#####    #
# g #  ###
# # ##   #
# #    # #
##########

從Ghost怎麼直接找shortest path去抓PacMan?
在我的想法裡, 不是每走一步, 才知道接下來要走哪各位置嗎?
在上面的例子裡, PacMan在上方, 可是上面是牆, 只有左右可以走
Ghost怎麼知道要走左邊好 還是右邊比較好?

問題有點複雜, 謝謝大家看完 :)


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 75.7.19.19
推 zupi:A* search algorithm? XD
推 PsMonkey:建議轉 Prob_Solve 或是 GameDesign 版
推 WPC001:我倒是覺得以前的人工AI做得很笨, 走到路口不是用最短路徑
→ WPC001:而是一個簡單的路徑長度, 然後用機率的方式來取捨
→ WPC001:路徑短的機率較高而已... 沒有複雜的演算法