2dトップダウンスムーズなパス検索libGDX

Question

私はプレイヤー（あなたによって制御されている）の後ろに仲間を作ろうとしていますが、それは動作しますが、衝突検出機能を追加すると、バディは障害物に当たる。私はちょうどaiの動きを滑らかにするための最良のアプローチ（たぶんa *アルゴリズムの実装のようなもの）が何であり、それが障害を回避するのだろうかと思っていましたか？

public void update() { 

    setBounds(getX(), getY(), getWidth(), getHeight()); 

    float xDiff = Math.abs(player.getX() - getX()); 
    float yDiff = Math.abs(player.getY() - getY()); 

    if (player.getX() > getX() && xDiff > buddyDistance) { 
     setX(getX()+speed); 
    } 
    else if (player.getX() < getX() && xDiff > buddyDistance) { 
     setX(getX()-speed); 
    } 

    if (player.getY() > getY() && yDiff > buddyDistance) { 
     setY(getY()+speed); 
    } 
    else if (player.getY() < getY() && yDiff > buddyDistance) { 
     setY(getY()-speed); 
    } 

} 

Answer 1

実装が容易で、障害物のあなたのタイプに応じて、働くかもしれない解決策は、潜在的なフィールドの使用です： はここに私のバディクラスの現在の更新方法です。

アイデアは簡単です：プレイヤーは、バディを彼の方に引き寄せるマグネットのように振る舞います。同時に、障害物は、バディがそれらを避けるようにバディを撃退する。

私は、読みやすさのために、Javaの代わりに最初に説明するためにベクトルを使用します。

たとえば、bはバディの位置で、pのプレイヤーとo_1, ... o_kは障害物の位置です。

各b, p, o_1, ..., o_kは、xおよびyの座標を有する2次元ベクトルである。

そして、ベクトル(p-b)は、バディからプレイヤーを指すベクトルです。また、障害物iからバディーを指すベクトル(b-o_i)が必要です。さらに、ベクトル(p-b),(b-o_i)を直接使用する代わりに、最初に正規化します。

次に、normalized(p-b)は、すでにプレイヤーにバディを引き出すために必要なすべてです。

障害物から仲間を追い払うために、仲間が近くにいる場合は強く、友だちが遠い場合は小さい（またはゼロ）にしてください。そのため、われわれが望む方向、つまりnormalized(b-o_i)を1/|b-o_i|とすると、明らかな選択肢があります。ベクトルのノルムを示します。

今、私たちは単純にして、これらすべての「磁力」を混在させることができます：

w = normalized(p-b) + normalized(b-o_1)/|b-o_1| + ... + normalized(b-o_l)/|b-o_k| 

このベクターwは一般プレーヤーの方にポイントが、バディが障害物に近い時はいつでもある、そこからはじかれますまさにあなたが望むものです。

しかし、どのようにしてバディーが適切なスピードで動くようにすることができますか？ これは簡単です。我々はwを標準化して、速度でスケールします。反発の

• さまざまな種類が働くかもしれない：

  public void update() { 
  
      setBounds(getX(), getY(), getWidth(), getHeight()); //I kept this from your code, but I don't actually know what it does 
  
      float dx = player.getX() - getX(); //note: I removed abs 
      float dy = player.getY() - getY(); 
  
      float norm = Math.sqrt(dx*dx + dy*dy); 
  
      //normalization: 
      float wx = dx/norm; 
      float wy = dy/norm; 
  
      for (obstacle o : obstacles) { //assuming obstacles is an iterable datastructure containing instances of the class obstacle 
       //note, it suffices to iterate over close by obstacles 
       dx = getX() - o.getX(); 
       dy = getY() - o.getY(); 
  
       norm = Math.sqrt(dx*dx + dy*dy); 
  
       //normalization: 
       float ox = dx/norm; 
       float oy = dy/norm; 
  
       //add scaling to get the repulsion force we want 
       wx += ox/norm; 
       wy += oy/norm; 
      } 
  
      float norm_of_w = Math.sqrt(wx*wx + wy*wy); 
      float vx = speed * wx/norm_of_w; 
      float vy = speed * wy/norm_of_w; 
  
      setX(getX() + vx); 
      setY(getY() + vy); 
  } 
  

  は残念ながら、考慮すべきいくつかの事柄があります：それは私たちの最終的な速度ベクトルは、これは簡単にあなたのコードに追加することができますv = speed*w/|w|

  で、あります例えば1/| b-o_i |^2のように、1/| b-o_i |より良い。

• cの異なる値（つまり、ox = c*dx/norm;など）に対して、c*(b-o_i)/|b-o_i|を試してみるなど、力をつけて遊ぶのが役に立ちます。 cが小さすぎると、バディはある程度まで障害物に移動します。cが非常に大きい場合は、遠く離れているときに既にそれらを避けるでしょう。さまざまな障害物の大きさに異なるcの値を使用すると、より良い結果が得られる場合もあります。
• 障害物が円形であり、2つの障害物の間に十分な空間がある場合、障害物回避は最も効果的です。さもなければ、バディはローカル最適状態に詰め込まれ、プレイヤーはバディをローカル最適状態から引き離す場所に移動することによって彼を「救助」しなければならない。
• 障害物が素晴らしい円形ではなく大きいポリゴンである場合、ポリゴンの大部分（非常に大きな障害物であるc）をカバーする非常に大きな反発力を試すことができます。利点は、バディーが障害物を避けることができるということです。残念ながら、それを近くに移動したい場合は、強力な反発のために単純に拒否します。
• 友だちと障害物が近い場合は1/|b-o_i|が大きいことに注意することが重要です。それらが同じ位置にある場合、プログラムはゼロで分割しようとします。あなたはこのケースをチェックし、それを避けたいかもしれません。それだが、それは通常、潜在的な分野で、アイデアは、障害物のための目標と正電荷のために負の電荷を使用することであることは注目に値するかもしれない

---

、すなわち

w = -|p-b| + 1/|b-o_1| + ... + 1/|b-o_k| 

。なお、ここでwはベクトルではなくスカラーだけです。次に、勾配降下が適用されてゴールに向かって移動します。これは、b.x、b.yに関するwの勾配が計算されることを意味する。この勾配は、障害物を避けながらプレーヤーに到達する方向に向いています。これは私があなたに提案したものより良いアプローチですが、より多くの数学の知識が必要です。これがあなたが望むものかどうか試してみてください。

---

最も可能性の高い、最良の答えの障害物は、任意の形状と極小値を持っている場合は、ファンネルアルゴリズムと組み合わせるドロネー三角形分割を使用することであるために受け入れられません。あなたについてもっと読むことができますhttps://www.aaai.org/Papers/AAAI/2006/AAAI06-148.pdf

しかし、あなたは実装が簡単なものを好むと思います。