2dプラットフォームゲームでパスを検索したい、teeworlds。そこにいるプレイヤーは左右に移動したり、ジャンプしたり、フックを使用して壁を上に移動したり、天井の下を移動したりすることができます。まあ、通常のパスファインド、つまり*やbfsはここに存在しないので、難しいです。私はパスを見つける必要がありますbtw 2プレーヤーので、1つは2番目に行くことができます。 3種類のタイルがあり、衝突したり、フックしたり、何もしたりしません。私はフォーマットint map[w][h]の地図を持っています。ここでは0 =空気、1 =衝突、2 = nohookです。マップはゲーム時間全体にわたって修正されていません。プラットフォームゲームのC++での経路探索
私は完全にそれを行う方法はありません。あなたが私を助けることができれば、私は満足しています。
PS。質問はプラットフォームゲームに関する一般的なものですが、teeworldsはそのうちの1つだけです...
経路探索アルゴリズムの観点からは、登山可能な壁を通常の歩道であるかのように扱うことができるため、アルゴリズムはそこで停止しません。アルゴリズムは別のセルから一般
動きのグラフ上で動作
あなたはそれをもっと説明できますか？ –
あなたは、A *などのアルゴリズムが2D環境でパスを見つけることができると述べました。彼らが働く仕組みには本質的に2つのタイプの地形があります：通過可能かつ通過不可能（通過可能な地形に重さが異なる可能性があります。例えば平坦な土地は丘よりも簡単です）。これをあなたの環境に適用することができます。プレイヤーがプラットフォーム上に立っていて、左、右に移動して登ることができれば、アルゴリズムはツリーの可能なルートを見ています：左から1つ、右から1つ、上から1つ。 [cont] – Attila
[cont]アルゴリズムの観点から見ると、ここでの「上」は、2Dの別の方向です（左右に垂直）。あなたは本質的に（人間の立場から）「上向き」を「前進」と同等にすることによって、 – Attila
経路探索は、（4つの方向のインスタンスのために）二つのセル間の接続が存在することを意味します。しかし、他のセル（天井）にリンクすることもできます。
あなたのゲームの可能性を完全に理解しているとは思えません。しかし、これは一般的にどのように動作するのですか：
パス探索アルゴリズムはグラフ上で動作します（すべてのエッジのコストまたは等価コストは関係ありません）。あなたがしなければならないのは、あなたのゲームのルールに従ってグラフをモデリングすることだけです。私。フィールドiとjとの間の通常の方法がcost（i、j）= normalよりも唯一の場合、フックを使用する別の方法があれば、コスト（i、j）= min（フック、ノーマル）。等々。グラフを作成したら（あなたのゲームのために指示されなければならないと仮定します）、すべての通常のPathfindingアルゴリズムが機能します。
「あなたはn回だけフックを使用できます」という要件がある場合は、マルチラベルdijsktraが動作します。
*ここでも一般的な検索アルゴリズムとして使用できますが、一般的な検索の問題として、プラットフォームのゲームのパス発見問題を表現する方法を見つけるだけです。ですから、格子状の迷路を通る経路を見つけるアルゴリズムとしてA *を導入したかもしれませんが、これは一般的な探索問題の特定のケースです。
より一般的な場合は、エッジが移動またはアクションを表し、ノードが位置または状態を表すグラフです。あなたが言及したゲームのための*を使用する
一つの方法は、このInfinite Mario AIから例を取ることによってです。このA *の実装はローカルで動作し、正確な瞬間に最適なアクションを得るために毎回ダニを再実行します。これはマリオやゲームのようなペースが速いゲームには最適ですが、A *それは迷路を解決するために使用されます。その場合、パスは一度しか見つからず、最後まで追跡されるグローバルな計画のようです。ノードのペアを前処理
使用単純BFS方法。
FYI：ゲーム開発の質問のためのStackExchageサイトがあります：http：//gamedev.stackexchange。com – raveturned