1

ゲームのプログラミングに挑戦します。私のゲームでは、従来のゲームグリッドでA*パスファインディングアルゴリズムを実行する必要があります。

たとえば、次のようになります：（S =開始、G =目標、X =壁）

-------------------------------
|  |  |  |  |  |  |  |  | G|  |
-------------------------------
|  |  |  |  |  |  |  |  |  |  |
-------------------------------
|  | X| X| X| X|  |  |  |  |  |
-------------------------------
|  |  |  |  | X|  |  |  |  |  |
-------------------------------
| S|  |  |  |  |  |  |  |  |  |
-------------------------------

A *を実装するには、任意のノードの「ネイバー」を取得できる必要があります。（たとえば、Startには3つのネイバー（Above、Diagonal、Right）があります。）

これをデータレイヤーにマッピングするために頭に浮かぶ方法は、2次元配列またはリンクリストです。

アレイは最もパフォーマンスが高く、簡単に外せるようです。したがって、もしそうなら、その隣人はS（右）、（上）、（対角）になります[0][4][0 + 1][4][0][4 - 1][0 + 1][4 - 1]

しかし、.NETアプリケーションの開発を数年間行ってきたので、基本的な配列は私には少し古い学校のように思えます。

そのため、その道を進む前に、グリッド（UIではなくデータレイヤー）をマップするために使用できる優れた.NETコレクションタイプがあるかどうかを尋ねると思いました。

4

2 に答える 2

3

グリッド全体をマップする必要はありません。はるかに簡単なのは、特定のノードのネイバーをオンデマンドで生成することです。つまり、ノード（x、y）のネイバーはになります{x-1, x, x+1} x {y-1, y, y+1} - (x, y)。これらのポイントのいずれかがグリッド寸法の外側にある場合、それらは考慮されません。これらの場所のいずれかに壁がある場合は、それらも無視します。したがって、ある場所の壁を効率的にチェックする方法を検討するだけで済みます。この特定の問題では、上記の方法でノードのネイバーを見つけることができるため、ここでは隣接リストや隣接行列は必要ないと思います。

編集：ある場所の壁をチェックするとき、私は座標から整数へのマッピングでそれを行っていました。すなわち(x, y) => x + y*MaxWidth。座標ごとに一意の整数を取得します。これで、効率的なルックアップのために、その整数を使用して壁の位置をハッシュテーブルなどに保存するだけで済みます。グリッドの次元がかなり大きい場合、このメソッドは2D配列表現に優先します。

于 2012-12-03T23:48:34.750 に答える
3

この場合、配列は正しい選択のように聞こえます。提供されるデータ構造のほとんどは、さまざまな機能を提供しようとしていることを忘れないでください。

必要な唯一の抽象メソッド（ネイバー）が迅速な実装であることを考えると、より複雑なものを基礎として使用する理由はありません。

于 2012-12-03T23:49:30.657 に答える