六角形のグリッドパス検索(AS3)

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


コンポーネントの説明


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


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

画像

グリッド自体は、セルの値がこのセルへの「遷移のコスト」である通常の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で書き直しました。 こちらからダウンロードできます。

Source: https://habr.com/ru/post/J115689/


All Articles