- ベストアンサー
オンラインゲームのオートランのアルゴリズムは？
オンラインゲームには、マウスでクリックした地点に移動する方式が数多く見られます。マップ上の１点をクリックすれば、「障害物を避けながら最短のルートで」そこにたどり着くことがわかります。 いったいこのアルゴリズムはどうなっているのでしょうか？ 特に「グラナドエスパダ」というゲームではそのアルゴリズムが完璧で、途中でどこかにひっかかったりするのを見たことがありません。 どこに立ってどこをクリックすればどの方向に行く、というマップごとにちまちまと割り当てられた命令があるのか、それともどんなマップでも一律して通用する複雑なアルゴリズムがあるのか。 このマウス移動の中身がどうなっているのか教えていただけないでしょうか。
- sanato
- お礼率72% (170/236)
- その他（プログラミング・開発）
- 回答数2
- ありがとう数2
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
「障害物が移動しない」という前提なら、動的計画法（Dynamic Programming; DP）と呼ばれる手法がありますね。 スタート地点から一歩目で行けるところを判断し、一歩目で行けるところから一歩で行けるところを二歩目とし、二歩目から一歩で行けるところを三歩目とし、・・・と続けていくと、目的地へ何歩で行けるかが分かります。そしてゴール地点からn-1歩目のマス、n-2歩目のマス、n-3歩目のマス、・・・と辿っていくと、スタート地点からの最短経路を見つけることができます。 これ動的計画法のひとつです。 移動速度に地形ごとの違いがあっても（砂の上を歩くスピードは草原と比較して遅いなど）距離に重みをつければよいだけなので、やることは変わりません。 重みをつけたらだいたいダイクストラ法と呼ばれるものになるはず。 動的計画法じたいは、部分最適解を重ねていくことで最終的なゴールを見つけ出す手法とされています。言い方を変えると、部分最適解以外を無視することで計算を減らせる手法ということでもあります。 最短距離の例で言えば、あらゆるルートを考えるのでは計算量が爆発しますし、なにより「これが最短だ」という保証がありません。動的計画法の考え方を用いると、ある地点までの最短距離が保証されていれば、その次のステップの最短距離も保証されることになり、最短距離以外のルートを通ってきたものを考える必要がなくなるわけです。 ただまあ、計算量がO(n^2)であることは変わりないので、単純にこれ実装しただけだとマップの細かさ次第では使えたものではありません。大きな移動のときは粒度を粗くして目的地近くでまた細かくするなどのがんばりはあるでしょうね。
その他の回答 (1)
- STICKY2006
- ベストアンサー率29% (1536/5269)
こんちくは。 正直、完璧な正解なら、開発者さんに聞いてね。のレベルになっちゃうので、 経験上、まぁ、こんなもんだろ。的な回答でも。 >>「障害物を避けながら最短のルートで」 え～と。 単純に、クリックした箇所に向かって直線移動。 途中、障害物があったら、ぶつかるけどもそれを気にせず突き進み、最終的にクリック先の箇所にたどり着く。 ですよね？？ そのゲームやった事ないので、アレなんですが。。 さすがに、キャラクターが勝手にカーブをすむ～ずに曲がって、建物の裏のポイントまでたどり着く。。。 ような、MMORPGは見たことないので。。。（汗 単純に。。。 Ａ地点（キャラが今いるところ）から、Ｂ地点（クリック先）へ、キャラの座標移動するようなプログラムがある。 ＡからＢへの直線上に、障害物があったら、キャラと障害物の当たり判定が発生して、座標がズレる。 ズレたところがＡ地点になって、そこから再度Ｂ地点へ移動計算。 多分、障害物接触中は、んな計算がガリガリされてて、キャラクターが「がくがくがくがく」動いてんじゃないかと。。。 でもって、最終的に、障害物との当たり判定が無くなるところまで座標移動したら、またＢに向かって直進。 んなもんですかねぇ。。。 。。。言葉で説明しただけで、アルゴリズムとしてはダメだな（汗（笑 >>どこに立ってどこをクリックすればどの方向に行く、というマップごとにちまちまと割り当てられた命令があるのか 単純に、 「Ａ地点からＢ地点へ移動する」処理 と 「キャラと障害物の当たり判定」を行なう処理 のようなもんを、どこのＭＡＰでも使っているかと。 「ＡからＢへ移動すること」と「障害物にあたったらちょっと避けること」自体は、どこのマップであろうとも共通処理ですから。
お礼
回答ありがとうございます。 おもっきり遠くの地点をクリックしても、最短経路でそこにたどり着きます。無駄な動きは一切なく。 いつか僕もそんなアルゴリズムを完成させたいです。
関連するQ&A
- オンラインゲームについて。
当方は片手しか使えなく、片手で操作が出来るオンラインゲームを探しています。 現状ではマウスでターゲットをとり、キーボードやゲーム内のスキルウィンドウなどをクリックしたりして・・というオンラインゲームがほとんどです。 それなりに操作が早いほうなので、それなりのプレイが出来るのですが、かなり疲労感があります。 理想はキーボードで近くの敵をターゲットすることが出来て、スキルもキーボードで出来たら・・と。移動はマウスでも構いませんが。。 なかなか見つからなくて知ってる方がいれば宜しくお願いします。
- 締切済み
- オンラインゲーム
- インターネットオンラインゲームについて
今日友達がこんな事を言ってきました。よくゲームセンターに全国オンラインのゲームがありますよね？あの中のゲームで「三国志大戦」のゲームをパソコンで再現することは出来ないのか？と・・・カードを動かしてリアルタイムで移動させる技術はマウスの原理と同じだと思うので出来ないことは無いと自分では思っています。問題はこの後です。パソコンがそれ以外の複雑な動き、例えば急な方向転換やカウンターなどの機能を異常なしに出来るでしょうか。あと、攻撃する時のダメージ計算も必要になってきます。果たしてこの思いつきは可能でしょうか・・・
- 締切済み
- その他([技術者向] コンピューター)
- フラッシュゲームを探しています！
このゲームを探しています！町を見つけながらクエストするゲームです。マップ上をマウスでクリックして町などを探して行くゲームで、敵と出会います。そして敵と戦います。勝ったら装備が貰えて負けたら装備が全部消えます。このゲームはどんな名前でどこでプレイできるのかを教えてください。
- 締切済み
- その他(ゲーム)
- ゲームコントローラーについて
教えてください。 オンラインゲームでゲームコントローラーを使用したいと思い購入しました。 設定するソフトもフリーでインストールしたのですが・・・。 マウスのように微妙な動きをしてくれません。（ボタン割当は最高^^） 設定画面でマウスカーソル移動量など調節したのですが、 移動量を増やすとカーソル移動が早くなりますが、クリックしたい場所への 微妙な動きができずあわせるの大変。移動量減らすと動きがめっちゃおそい。 これってなんとかできないものでしょうか？（早く細かく動かしたいです。） それと、上記のような状態はゲームコントローラー自体の 性能にもよるものなのでしょうか？（高いのもありますが・・。） アナログ・デジタルってのも・・・？アナログスティック付のほうがいいのかな？ もしそうなら買換えも考えてるんですが、おすすめあったら一緒に教えてください。 とにかくゲームコントローラーで快適なマウス同様の操作をしたいのです。 詳しい方いましたら是非教えてください。 長文すみません。
- ベストアンサー
- その他(PCパーツ・周辺機器)
- androidでゲーム中カーソル消す方法
androidで無線マウスをつないでpupgなどのfpsgゲームをやるときに試合中画面にずっとカーソルが表示されて左クリックしながらじゃないと視点を変えれないなど非常に不便です。どうやって試合中マウスカーソルをけして動かすだけで視点移動できるようにするにはどうしたらいいのでしょうか
- 締切済み
- スマホゲーム
- ゲームパッドでマウス操作ができるフリーソフト
こんにちは 最近ゲームパッドを買い、 マウスが使いにくいと感じていたので、 ゲームパッドをマウスの代わりに使いたいのですが、 ゲームパッドのスティックをマウスポインタの移動にしたり かつ、ボタンを左右のクリックやスクロールや キーボードのキーに割り振れ、 その設定をいくつか保存できるようなフリーソフトを探しています。 (例ゲームパッドの1ボタン→Ｚキーなど) 設定が簡単で使いやすいフリーソフトを教えてください
- ベストアンサー
- その他(PCパーツ・周辺機器)
- Ｇｏｏｇｌｅマップで標高を表示する方法
以前のパソコンでグーグルアースを利用していたのですが、その時は目標地点にマウスのポインターを合わせるとその地点の標高が表示されていました。久しぶりにＧｏｏｇｌｅマップを利用してみると標高の表示が出ないので、メニューの「地形」をクリックしてみると「地形、標高を表示します」の表示は出ますが、目標地点の標高は表示されません。何か特別の操作が必要なのでしょうか？
- 締切済み
- 地理学
- YOLPのマーカークリックでリンク先に飛ぶには？
Yahoo! JavaScriptマップAPIを使い、日本地図に複数のマーカーに吹き出しを付けて以下の形にしました。 このマーカーをダブルクリックしたときに、それぞれ指定したリンク先に飛ぶようにしたいのですが、どのようにすればよいのでしょうか。 また、現在のところマーカーのマウスホバーで吹き出しが表示されるのですが、これをマウスクリック（タップ）で表示するにはどうすればよいでしょうか。さらに別のマーカーをクリックするとそれまで開いていた吹き出しが消えて、クリック先の吹き出しに切り替わるようにしたいと考えています。 ご教示お願いいたします。 window.onload = function(){ var ymap = new Y.Map("map"); ymap.drawMap(new Y.LatLng(35.68132732438393,139.76650149843817), 6,"map"); var markers = []; markers.push( new Y.Marker(new Y.LatLng(35.674756131624456,139.73189027331),{title: "赤坂A地点"})); markers.push( new Y.Marker(new Y.LatLng(35.67024139121164,139.72727687380439),{title: "赤坂B地点"})); markers.push( new Y.Marker(new Y.LatLng(35.63223075430667,139.88597781679755),{title: "浦安A地点"})); ymap.addFeatures( markers ); }
- ベストアンサー
- JavaScript
- c言語マップ探査ゲーム プログラミング
学校の課題で、5×5のマス目を移動するマップ探査ゲームというものをプログラミングします。 プログラミングは超初心者なので簡単な命令で、できれば軽く解説してもらえると嬉しいです。 プレイヤーは移動方向を選択し、それぞれのマス目で通過か探査を選びます。 探査を選ぶとランダムで２～９のgoldを手に入れ獲得goldはメッセージで知らされます。 マップの表し方は 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 未探査のマスを0、プレイヤーを１、探査済のマスを獲得gold２～９で表します。 左上をスタートとし右下をゴールとします。 その他の条件として １、スタート地点は探査は行えず、ゴール地点は必ず探査を行うようにします。 ２、マス目から外れたところには、行けないようにします。（現在地を変化させない） ３、適当な位置に所持goldが半分もしくは、全額失うマス目を二ヶ所作ります。半額は少数切り上げ で、goldを失ったこととその数をメッセージで知らせ、マップには-１と表示します。 ４、マップ上ではプレイヤーを優先して表示します。 ５、マスは自由に移動可能だが、探査済のマスは再探査できない。 ６、ゴール地点を探査した時点でゲーム終了となり、43～47gold入手してる場合は"You wins!"それ以外は、"You lost!"と表示しゲームを終了する。 例として #include <stdio.h> #include <stdlib.h> #include <time.h> int main(void) { int movex = 0, movey = 0, gold = 0, getm; int direction, scanp; srand(time(NULL)); while (1) { printf("Input, where you going ? (Up:1, Down:2, Left:3, Right:4): "); scanf("%d", &direction); switch (direction) { case 1: movey--; break; case 2: movey++; break; case 3: movex--; break; case 4: movex++; break; } printf("Input, Check or Through ? (Check:1, Through:0) : "); scanf("%d", &scanp); if(scanp == 1 ) { getm = rand() % 8 + 2; printf("You get %d gold.\n", getm); gold = gold + getm; } } exit(0); } が与えられています。 これを参考に作ってもらえるとありがたいです。
- 締切済み
- C・C++・C#
お礼
回答ありがとうございます。 かなり複雑な地形でも重くならないのを見ると、いろいろな工夫がなされているようです。 動的計画法というものを調べてみようと思います。