Search for a path in a hexagonal grid (AS3)

This article is a description of the HexaPath component that implements the search for a path using the A * algorithm in a hexagonal grid. I found a large number of descriptions of the algorithm in the network using the example of a square grid and a number of implementations, but not a single mention of the hexagonal grid. And I wrote my implementation. I spread source codes. Suddenly, someone will need it, but it will be too lazy to write.

Component Description

In fact, this is not one class, but several:

• NumberPoint.as is a stripped-down version of the Point class
• PathList.as - list implementation (open and closed). What it is, see the description of the algorithm.
• HexaGrid.as - working with a hexagonal grid (finding neighbors in the cell coordinates, finding the center coordinates and angles of the cell in its coordinates, etc.)
• HexaPath.as - directly the implementation of the algorithm itself.

')
For some reasons, I chose the following arrangement of cells:



The grid itself is defined by a conventional two-dimensional array, in which the cell values ​​are the “transition cost” to this cell. If the “transition cost” is greater than or equal to HexaGrid.MAX_AVAILABLE , then the cell is interpreted as impassable.

Working with the component is not difficult. First you need to have a two-dimensional array with filled “transition costs”. Such an array can be created like this:

HexaGrid.init(width, height);

This will create an array, in each cell which will be the value 1.

Filling the cells with “costs” is performed as follows:

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

Feed the created array to the HexaPath class

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

The function will parse the array and if everything is normal, it returns true.
Now you can request the path:

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

The structure of the result variable is:
result['status']:int;
result['path']:Array;

result ['status'] = 1, if the path was calculated successfully, -1 - if something happened.
And it can happen like this:

• the coordinates of the beginning or end go beyond the array
• the coordinates of the beginning or end are in impassable cells.

If result ['status'] = 1 , then the variable result ['path'] contains the generated array of coordinates of the path cells. In each cell of the array, a variable of type Object , in which the coordinates of the cell are in the coord property. Messy? Now I will comment on the code:

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'];
and so on.

That is essentially all. The implementation was pretty frisky.
You can see the demo here .
Source codes swing from here .

I hope someone my work will come in handy ...

UPD. ilyaplot rewrote php implementation of this algorithm. You can download it here .