六角形のグリッドパス検索（AS3）

この記事は、六角形グリッドでA *アルゴリズムを使用してパス検索を実装するHexaPathコンポーネントの説明です。 ネットワーク上で、正方格子の例と特定の数の実装を使用して、アルゴリズムの多数の記述を見つけましたが、六角形格子の単一の言及は見つかりませんでした。 そして、実装を作成しました。 ソースを広めます。 突然、誰かがこれを必要としますが、自分で書くのは面倒です。

コンポーネントの説明

実際、これは1つのクラスではなく、いくつかのクラスです。

• NumberPoint.as -Pointクラスの簡略化された類似物
• PathList.as-リストの実装（オープンおよびクローズ）。 これは何ですか、アルゴリズムの説明を参照してください。
• HexaGrid.as-六角形のグリッドを使用します（セル座標で近傍を見つける、その座標で中心座標とセル角度を見つけるなど）
• HexaPath.asは、アルゴリズム自体の実装です。

何らかの理由で、私はこのセル配置を選択しました：







グリッド自体は、セルの値がこのセルへの「遷移のコスト」である通常の2次元配列によって定義されます。 遷移コストがHexaGrid.MAX_AVAILABLE以上の場合、セルは通過不能と解釈されます。



コンポーネントの操作は難しくありません。 まず、「移行コスト」が入力された2次元配列が必要です。 このような配列は、たとえば次のように作成できます。



HexaGrid.init(width, height);







これにより、各セルに値1の配列が作成されます。



セルに「値」を入力する手順は次のとおりです。



HexaGrid.grid[x][y]=value;







作成した配列をHexaPathクラスにフィードします



var res:Boolean=HexaPath.setMap(HexaGrid.grid);







この関数は配列を分析し、すべてが正常であれば、trueを返します。

これでパスをリクエストできます：



var result:Object=HexaPath.createPath(source:Point, target:Point);







結果変数の構造は次のとおりです。

result['status']:int;

result['path']:Array;







result ['status'] =パスが正常に計算された場合は1、何かが発生した場合は-1。

そして、これは起こる可能性があります：

• 開始座標または終了座標が配列を超えている
• 開始または終了の座標は、通過できないセルにあります。

result ['status'] = 1の場合、変数result ['path']にはパスセルの座標の生成された配列があります。 配列の各セルで、セル座標がcoordsプロパティにあるObject型の変数。 混乱した？ 次に、コードについてコメントします。



var result:Object=HexaPath.createPath(new Point(0, 0), new Point(5, 5));

var path:Array= result['path'];

var first_cell:Point=path[0]['coords'];





などなど。



それは本質的にすべてです。 実装は非常に軽快でした。

デモはこちらからご覧いただけます 。

ソースはここからスイングします 。



誰かが私の仕事を役に立つと思うことを願っています...



UPD。 ilyaplotは、このアルゴリズムの実装をPHPで書き直しました。 こちらからダウンロードできます。