0


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 *"や "Dijkstraのアルゴリズム"のような方法を指定しないでください。私はまた、優れた発見的方法で助けを必要とします。

3 回答


4


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

  1. あなたは短いものより長いストレートランを好みますか? この嗜好をどのように定量化しますか? (検索アルゴリズムを収束させるには、スコアリング関数が非線形であるとより簡単になります。)

  2. 目的地に直行したくない場合は、メインラインから外れているステップに報酬を与えたいと思うかもしれません。 たとえば、AからBへの経路上で各点を検討し、次に3つのステップを実行して点間の方向を計算します。 その方向とAからBの方向の差の余弦を計算します。 それを否定しなさい。 直線上のステップはあなたに対して-1をカウントし、垂直ステップは中立であり、直線からのステップはあなたのために1をカウントします。

ここにいくつかの良い次のステップがあります:

  • さらにいくつかの得点のアイデアを考えてください。

  • 手でダースパスを描き、あなたがそれらをどれだけ好きかによってランク順に並べてください。

  • パスごとに、手作業でいくつかの小さなバリエーションを作成します。

  • すべてのパスでスコアリング機能を実行します。 あなたが好きなものが好きな得点関数を得るまで、いじってください。

検索アルゴリズムについて考える準備ができました。


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単位右に押します。


0


これがアイデアです---

Aから始めて、ランダムな方向(左、上、または下)に移動します。 各移動の後、あなたが向きを変えるかどうかを確認するために乱数を振ります。 あなたが同じ方向に旅行し続ける時間の75%、そしてあなたが曲がる時間の25%を言うことができます。 あなたが向きを変えるときは、常にBに近づく方向に向けてください。 つまり、左または右に移動している場合は上に移動する必要があり、上に移動している場合は現在の目標の右または左にどれだけ離れているかに基づいて右または左を選択します。 。 また、あなたが世界の境界の1つに当たったならば、向きを変えてください!

コーディングするのがそれほど難しくないはずです。 必要以上に複雑にしているだけなのですが…