0

私は（ごくわずかな）自由な時間にローグライクゲームに取り組んでいます。各レベルは基本的に、パスで接続されたいくつかの長方形の部屋になります。でも、部屋の間の小道は自然に見えて風が強いようにしたいと思います。たとえば、私は次の自然な見た目を考慮しません。

       B       
       X       
       X       
       X       
      XX       
     XX        
    XX         
  AXX

私は本当にこのようなものが欲しいです：

       B       
       X       
       XXXX    
          X    
          X    
          X    
          X    
  AXXXXXXXX

これらのパスは、いくつかのプロパティを満たす必要があります。

  1. 私はそれらが境界を定められている領域を指定できなければなりません、
  2. 私は彼らがどれほど風が強くて長いかをパラメータ化できなければなりません、
  3. 線は、一方のパスで開始し、もう一方のパスで終了したように見えるべきではありません。たとえば、上記の最初の例は、Aで始まり、Bで終わるように見えます。これは、基本的に、Bと並ぶまで方向を繰り返し変えてから、そこにまっすぐ進むためです。

A *を使用したいと思っていましたが、正直なところ、ヒューリスティックがどうなるかわかりません。遺伝的アルゴリズムの使用も検討しましたが、その方法がどれほど実用的かはわかりません。

私の質問は、私が望む結果を得るための良い方法は何ですか？「A*」や「ダイクストラのアルゴリズム」のような方法を指定するだけでなく、優れたヒューリスティックの支援も必要です。

4

3 に答える 3

4

パスを作成する方法を理解する前に、必要なものをより正確に表現する方法を理解する必要があります。これを行う1つの方法は、各パスにスコアを割り当ててから、スコアの高いパスを検索することです。考慮すべきいくつかの質問があります：

  1. あなたは短いものより長いまっすぐな走りを好みますか？この好みをどのように定量化しますか？（検索アルゴリズムを収束させるには、スコアリング関数が非線形である方が簡単です。）

  2. 目的地に直行したくない場合は、メインラインから外れたステップに報酬を与えることができます。たとえば、AからBへのパスで、各ポイントを検討し、3つのステップを実行して、ポイント間の方向を計算します。次に、その方向とAからBへの直線の方向の差の正弦を取ります。それを否定します。ラインカウントのステップはあなたに対して-1、垂直のステップはニュートラルであり、ラインカウントから離れるステップは+1です。

次のステップは次のとおりです。

  • さらにいくつかのスコアリングのアイデアを考えてみてください。
  • 手で十数本のパスを描き、好きなだけランク付けします。
  • パスごとに、手作業でいくつかの小さなバリエーションを作成します。
  • すべてのパスでスコアリング関数を実行します。好きなスコアリング関数が得られるまで、いじり続けてください。

これで、検索アルゴリズムについて考える準備が整います。

于 2009-04-25T23:18:29.333 に答える
1

ここでは、パスファインディングは間違った用語だと思います。通常、AからBへの有効なルートを見つける必要があります。問題は、そのルートを見つけることではなく、目的に合ったルートを作成することです。意図的に次善のパスを作成しているため、その品質を定量化するのは困難です。したがって、ヒューリスティックを使用した検索アルゴリズムが問題の最善の解決策になるとは思いません。1つの必須基準（作業パス）といくつかのあいまいで未定義の基準（自然に見えるものと曲がりくねったもの）がある場合は、必須要件を満たすことから始めて、他の要件に向けて変更することをお勧めします。そうすれば、常に機能するものが得られます。

直角に曲がる水平パスと垂直パスを好むように思われる場合は、AからBへの直線の2セグメントパスから始めることをお勧めします（マンハッタン距離ヒューリスティックを使用したA *でこれを見つけることができますが、それは同じです自分で簡単にステップアウトできます）。次に、2つのセグメントの1つとそのセグメントの2つの端点の1つに沿ってランダムな点を取り、線のそのサブセクションをそれ自体と平行にランダムな距離だけ移動します。次に、2つの線分を追加して、線の新しい位置を古い接続ポイントに結合します。2番目の例は、このアルゴリズムの1つの反復を示しています。Aが（0,0）で、Bが（5、7）の場合、2番目の線分（垂直線分）をランダムに選択し、（0,5）で端点を選択しました。 ）と（5,5）の中点で、そのセクションを3単位右に押してから、元に戻します。

于 2009-05-01T13:08:05.583 に答える
0

ここにアイデアがあります---

Aから開始し、ランダムな方向（左、上、または下）に移動します。移動するたびに、乱数をロールして、向きを変えるかどうかを確認します。同じ方向に移動し続ける時間の75％、方向転換する時間の25％としましょう。曲がるときは、常にBに近い方向に曲がってください。つまり、左または右に移動する場合は上に曲がる必要があり、上に移動する場合は右/左を選択する必要があります。あなたが現在ゴールの右または左にどれだけ離れているかに基づいています。また、世界の境界線にぶつかったら、向きを変えてください！

コーディングするのはそれほど難しいことではありません。これを必要以上に複雑にしようとしているような気がします...

于 2009-05-07T21:31:39.520 に答える