問題タブ [path-finding]

パスファインディングのためにクリーンで一貫性のあるサンドボックスが必要な場合は、何を使用しますか？

幾何学的平面上の障害物の周りに仮想ユニット（ロボット）を送信して、さまざまなパスファインディングアルゴリズムを試してみたいと思います。

しかし、ゲームエンジンやFlashのような機能の過剰な機能は必要ありません。アニメーション化されたレポートと、ネイティブの衝突検出器だけです。

Pythonでスクリプト化することをお勧めしますが、JavaまたはC ++の代替手段がある場合は、それらもいただければ幸いです。

本当に驚いたのは、Windows から OS X に移行したときに、Finder にいくつかの重要な機能が欠けていることです。そのうちの 1 つは、アーカイブをフォルダーとして開く可能性です。つまり、ディレクトリ ツリーにとどまり、ドラッグ アンド ドロップできます。アーカイブからツリー、サイドバーなどのフォルダーへのファイル。

そのような機能を有効にするにはどうしますか?

アップデート

Path Finderはすばらしいシェアウェア アプリで、これを標準の Finder の代わりに使用する予定です (多くの Mac ユーザーがそうしています)。そのため、Path Finder でアーカイブを閲覧するためのプラグインに興味があります。パッケージを参照する可能性があるので (View Options をチェックしてください)、それをアーカイブに拡張することは可能だと思います。Path Finder 用のプラグインを作成するためのSDKもあります。唯一の質問 -苦労しているすべての人が最終的に幸せになるように、プラグインを作成する方法は?

都市建設ゲームを設計していて、問題が発生しました。

Sierra のCaesar IIIのゲーム メカニクスを想像してみてください。それぞれに 1 つの市場がある多くの都市地区があるとします。有向加重グラフで接続された距離にあるいくつかの穀倉地帯があります。違い: 人 (ここでは車) は交通渋滞を形成する単位です (ここではグラフの重みが続きます)。

注: Ceasar ゲーム シリーズでは、人々は食料を収穫していくつかの大きな穀倉に備蓄しましたが、多くの市場 (小さな店) は穀倉から食料を取り出して市民に届けました。

タスク: 各地区に食料をどこから調達すべきかを伝えると同時に、時間を最小限に抑え、都市の道路の混雑を最小限に抑えます。

マップの例

黄色の地区にはそれぞれ 7 個、7 個、4 個のリンゴが必要であるとします。青みがかった穀倉には、それに応じて 7 個と 11 個のリンゴがあります。

エッジの重みがそれらの長さに比例するとします。次に、解決策は、端に示されている灰色の数字のようなものになるはずです。たとえば、第 1 地区は第 1 穀倉から 4 個のリンゴを、第 2 穀倉からは 3 個のリンゴを取得しますが、最後の地区は第 2 穀倉からのみ 4 個のリンゴを取得します。

ここでは、最初に垂直道路が最大まで占有され、次に残りの労働者が斜めの経路に送られます。

質問

どの実用的で非常に高速なアルゴリズムを使用する必要がありますか? 輻輳ゲームについて説明している論文 ( Congestion Games: Optimization in Competitionなど) を見ていましたが、全体像をつかむことができませんでした。

または同様の言語のバージョン。2D だけでなく、すべてのタイプのマップに対応するものです。

一度に1文字ずつ変えて、有効な英語の単語だけを使って単語を変えようとする「ワードゲーム」を聞いたことがあると思います。私はそれを解決するためにA*アルゴリズムを実装しようとしています（A *の理解を具体化するためだけに）。必要なものの1つは、最小距離のヒューリスティックです。

つまり、任意の文字列aを別の文字列bに変換できるこれら3つの突然変異のうちの1つの最小数：1）1つの文字を別の文字に変更する2）任意の文字の前後の場所に1つの文字を追加する3）任意の文字を削除する

例

私は多くのアルゴリズムを試しました。毎回実際の答えを出すものが見つからないようです。実際、人間の推論でさえ最良の答えを見つけているかどうかわからないことがあります。

誰かがそのような目的のためのアルゴリズムを知っていますか？または多分私が1つを見つけるのを手伝うことができますか？

（明確にするために、私は、英語の妥当性を無視して、任意の文字列を他の文字列に変換できるアルゴリズムを求めています。）

これは私のノードのグリッドです:

A* パスファインディング アルゴリズムを使用して、その上でオブジェクトを移動しています。通常は問題なく動作しますが、時々間違った動作をします:

• 3 から 1 に移動するときは 2 を経由しますが、1 から 3 に移動するときは 4 を経由します。
• 3 と 5 の間を移動する場合、6 を経由する短い方法ではなく、いずれかの方向に 4 を経由します。

何が間違っている可能性がありますか？これが私のコードです（AS3）：

NodeGridNode::distanceTo()

私の同僚が、オンラインのジャッジ Web サイトから、小さな町の避難計画の問題をグラフで解くという演習を提案してくれました。

私は答えを必要としません（また、私はそれを望んでいません）、私はこの種の問題に少し慣れていないので、それを解決するための最良のアプローチについてのアドバイスが必要です。

問題は、核攻撃の場合の労働者と放射性降下物シェルターのある町の建物で構成されています。各建物の労働者を 1 つまたは複数の放射性降下物シェルターに割り当てるアルゴリズムを構築する必要がありますが、一部のシェルターが過密になりすぎず、他のシェルターはほとんど空のままになるようにする必要があります (そうでない場合は、労働者を最寄りのシェルターに移動させるだけです)。 .

問題はこれです：http://acm.timus.ru/problem.aspx?space=1&num=1237

オフラインの場合は、Google キャッシュ バージョンを参照してください。 kotov+避難+問題&cd=1&hl=pt-PT&ct=clnk&gl=pt

私がこれまでに行ったことは、各建物が最も近い避難所を取得し、その建物から避難所の容量に等しい数の労働者を移動させることです。その後、次の建物に移動します。しかし、時には労働者の数がシェルターの収容能力よりも多い場合があります。その場合、すべての建物を繰り返し処理した後、すべての建物に労働者が0人になるまで同じアルゴリズムを繰り返し適用します。問題は、これが最善の方法ではないことです。それを解決します。

どんなヒントでも大歓迎です。答えを求めているような気がしないでください。それを解決するための正しい方向へのアドバイスが欲しいだけです。

前もって感謝します。

このようなグリッドがあるとしましょう (ランダムに作成):

では、白いボックスの 1 つからランダムに出発する車があるとします。白いボックスのそれぞれを通過する最短経路は何でしょうか? 各ホワイト ボックスには何度でもアクセスできますが、ブラック ボックスを飛び越えることはできません。ブラックボックスは壁のようなものです。簡単に言えば、ホワイト ボックスからホワイト ボックスにのみ移動できます。

斜めにも、どの方向にも移動できます。

2 つのサブ質問:

1. 移動する前に、すべてのブラック ボックスの位置がわかっていると仮定します。
2. ブラック ボックスに隣接するホワイト ボックス内にいる場合にのみ、ブラック ボックスの位置を知っていると仮定します。

ここに D* に関するいくつかの論文へのリンクがありますが、私には少し数学的すぎます。初心者向けの D*/D* Lite に関する情報はありますか?

接続ノードグラフ用に作業しているゲームで、より高速なパスファインディングメカニズムを導入しようとしています。ノードは、「ネットワーク」と「ルーター」の2つのタイプに分類されます。

この図では、青い円はルーターと灰色の長方形のネットワークを表しています。

各ネットワークは、接続されているルーターのリストを保持し、その逆も同様です。ルーターは他のルーターに直接接続できず、ネットワークは他のネットワークに直接接続できません。

ネットワークは、接続されているルーターを一覧表示しますルーター



は同じことをします

送信元と宛先が同じネットワークであるパスを除く、可能な送信元と宛先のネットワークごとに、交差するネットワークの数で測定されるパスをマップするアルゴリズムを取得する必要があります。私は今1つ持っていますが、パスをマップするのに約2秒かかるため、接続されているすべてのプレーヤーにとって非常に目立ちます。

現在のアルゴリズムは、深さ優先のブルートフォース検索（パスキャッシングを機能させるために約1時間でまとめられたもの）であり、通過した順序でネットワークの配列を返します。これが、非常に遅い理由を説明しています。より効率的なアルゴリズムはありますか？

ちなみに、これらの例のグラフには4つのネットワークがありますが、実際のグラフには55のネットワークと約20のルーターが使用されています。不可能なパスも発生する可能性があり、ネットワーク/ルーターのグラフの地形が変化する可能性があるため、パスキャッシュを再構築する必要があります。

このタイプのグラフに最適な結果を提供する可能性のあるアプローチ/アルゴリズムはどれですか？