3

ゲームのアルゴリズムを機能させるのに問題があり、ここの誰かが私を助けてくれることを願っています。ほとんどのソリューションは完全なタイルで機能するため、Googleはあまり役に立たなかったようです。

ゲームでは、ユニットはタイル内のさまざまな位置を占めることができます。つまり、左上隅、中央、右下、...タイルの位置（2/3）、つまり（2.2 / 3.1）、（2.5 / 3.5）に配置できます。 ）、（2.8 / 3.9）。

それらが位置（2.2 / 3.1）から（5.7 / 4.1）に移動する場合、パスに障害物があるかどうかを確認する必要があります。

私の現在のアルゴリズムは次のとおりです。

  1. （2.2 / 3.1）から
  2. 動きの角度を計算します（つまり70度）
  3. その方向に0.1ステップ移動します
  4. 私がいるタイルを確認してください（floor（pX）/ floor（pY））
  5. 2から繰り返す

このアルゴリズムは機能しますが、障害物はタイルの一部ではなく完全なタイルにしかなり得ないため、私にはあまり効率的に見えません（ユニットは衝突しません）。ステップサイズを大きくすると、わずかに交差するだけのタイルを見逃し始めます（つまり、左下隅のみを交差します）。ステップサイズが0.1の場合でも、障害物を見逃す可能性があります。

サブマップ（角のあるすべてのタイル（floor（start.X）/ floor（start.Y））と（ceil（start.X）/ ceil（start.Y））を取得するための解決策を見つけようとしました。すべてのタイルを調べて、交差するかどうかを数学的にチェックします。悲しいことに、このチェックに必要な数学の知識が不足しているようです。

私の最後のアイデアは、タイルの4つの境界線すべてを線として取り、線線交叉を行うことでしたが、それは私の元のアプローチよりも遅いようです。

ヒントはありますか？

ありがとう。

4

1 に答える 1

5

線に沿ってステップすることによってパスをトレースする代わりに、次の可能なタイル（境界線）に直接ジャンプします。これはかなり簡単に計算できます。上記のサンプル番号を使用します。

  1. ラインeqnを計算します（y = .286x + 2.471）
  2. タイル2,3から始めて、タイル5,4に向かって移動しています。したがって、xが3（すぐ右側のタイルの境界）になったときのy値を計算します。3.329です。
  3. 次に、yが4（すぐ上のタイルの境界）になったときのx値を計算します。5.346です。
  4. 2,3から始まり、右に移動すると3,3.329になります。上に移動すると5.346,4になります。右側で交差します（xで2-> 3を移動しても、yでタイルは移動しません）。xのタイル5に到達するまで、上で交差しません。
  5. 4で計算されたタイルが、新しい比較（3,3）になります。手順2から繰り返します。

このプロセスでは、移動したタイルごとに1回の計算のみが発生し（精度やタイルの大きさに関係なく）、正確です。計算された値は、両方の交差点を盲目的に何度も計算する代わりに、保存して再利用できることに注意してください。上記では、x = 5になるまでタイルを上に移動しないことがわかります（ステップ4）。したがって、パス全体を別の計算なしで推測できます（2,3-> 3,3-> 4,3-> 5,3-> 5,4）。

すべてのトランジションを段階的に実行する代わりに事前計算することもできますが、これは常にパス全体が必要な場合にのみ有益です（障害物を見つけたら処理を停止したいので必要ありません）。

2つの警告。標識と線の方向に注意してください。負の勾配に細心の注意を払わないと、多くのバグが発生します。また、実数を使用すると、対角線上で交差することはほとんどありません（一度に2つの境界線）が、念のために注意する必要があります（コードで処理します）。

このメソッドには名前がありますが、頭のてっぺんから思い出せません。それはゲームプログラミングジェムシリーズからのものかもしれないと思いますが、おそらく他の誰かがより良いリファレンスを提供することができます。

于 2010-05-06T13:39:27.223 に答える