オンラインゲームのオートランのアルゴリズムは？

質問

オンラインゲームには、マウスでクリックした地点に移動する方式が数多く見られます。マップ上の１点をクリックすれば、「障害物を避けながら最短のルートで」そこにたどり着くことがわかります。

いったいこのアルゴリズムはどうなっているのでしょうか？
特に「グラナドエスパダ」というゲームではそのアルゴリズムが完璧で、途中でどこかにひっかかったりするのを見たことがありません。

どこに立ってどこをクリックすればどの方向に行く、というマップごとにちまちまと割り当てられた命令があるのか、それともどんなマップでも一律して通用する複雑なアルゴリズムがあるのか。

このマウス移動の中身がどうなっているのか教えていただけないでしょうか。

回答No.2

beefisdead · ベストアンサー

「障害物が移動しない」という前提なら、動的計画法（Dynamic Programming; DP）と呼ばれる手法がありますね。

スタート地点から一歩目で行けるところを判断し、一歩目で行けるところから一歩で行けるところを二歩目とし、二歩目から一歩で行けるところを三歩目とし、・・・と続けていくと、目的地へ何歩で行けるかが分かります。そしてゴール地点からn-1歩目のマス、n-2歩目のマス、n-3歩目のマス、・・・と辿っていくと、スタート地点からの最短経路を見つけることができます。
これ動的計画法のひとつです。

移動速度に地形ごとの違いがあっても（砂の上を歩くスピードは草原と比較して遅いなど）距離に重みをつければよいだけなので、やることは変わりません。
重みをつけたらだいたいダイクストラ法と呼ばれるものになるはず。

動的計画法じたいは、部分最適解を重ねていくことで最終的なゴールを見つけ出す手法とされています。言い方を変えると、部分最適解以外を無視することで計算を減らせる手法ということでもあります。
最短距離の例で言えば、あらゆるルートを考えるのでは計算量が爆発しますし、なにより「これが最短だ」という保証がありません。動的計画法の考え方を用いると、ある地点までの最短距離が保証されていれば、その次のステップの最短距離も保証されることになり、最短距離以外のルートを通ってきたものを考える必要がなくなるわけです。

ただまあ、計算量がO(n^2)であることは変わりないので、単純にこれ実装しただけだとマップの細かさ次第では使えたものではありません。大きな移動のときは粒度を粗くして目的地近くでまた細かくするなどのがんばりはあるでしょうね。

お礼

回答ありがとうございます。
かなり複雑な地形でも重くならないのを見ると、いろいろな工夫がなされているようです。
動的計画法というものを調べてみようと思います。

回答No.1

STICKY2006

こんちくは。

正直、完璧な正解なら、開発者さんに聞いてね。のレベルになっちゃうので、
経験上、まぁ、こんなもんだろ。的な回答でも。

>>「障害物を避けながら最短のルートで」

え～と。

単純に、クリックした箇所に向かって直線移動。
途中、障害物があったら、ぶつかるけどもそれを気にせず突き進み、最終的にクリック先の箇所にたどり着く。

ですよね？？

そのゲームやった事ないので、アレなんですが。。

さすがに、キャラクターが勝手にカーブをすむ～ずに曲がって、建物の裏のポイントまでたどり着く。。。
ような、MMORPGは見たことないので。。。（汗

単純に。。。
Ａ地点（キャラが今いるところ）から、Ｂ地点（クリック先）へ、キャラの座標移動するようなプログラムがある。
ＡからＢへの直線上に、障害物があったら、キャラと障害物の当たり判定が発生して、座標がズレる。
ズレたところがＡ地点になって、そこから再度Ｂ地点へ移動計算。
多分、障害物接触中は、んな計算がガリガリされてて、キャラクターが「がくがくがくがく」動いてんじゃないかと。。。

でもって、最終的に、障害物との当たり判定が無くなるところまで座標移動したら、またＢに向かって直進。
んなもんですかねぇ。。。

。。。言葉で説明しただけで、アルゴリズムとしてはダメだな（汗（笑

>>どこに立ってどこをクリックすればどの方向に行く、というマップごとにちまちまと割り当てられた命令があるのか

単純に、
「Ａ地点からＢ地点へ移動する」処理
と
「キャラと障害物の当たり判定」を行なう処理
のようなもんを、どこのＭＡＰでも使っているかと。

「ＡからＢへ移動すること」と「障害物にあたったらちょっと避けること」自体は、どこのマップであろうとも共通処理ですから。

お礼

回答ありがとうございます。

おもっきり遠くの地点をクリックしても、最短経路でそこにたどり着きます。無駄な動きは一切なく。
いつか僕もそんなアルゴリズムを完成させたいです。