Hexagonal mesh path search (AS3)

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

Component Description

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

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

For some reasons, I chose this arrangement of cells:



The grid itself is defined by an ordinary two-dimensional array in which the values ​​of the cells are the “cost of transition” 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 a component is not difficult. First you need to have a two-dimensional array with filled "transition costs." Such an array can be created for example like this:

HexaGrid.init(width, height);

This will create an array with a value of 1 in each cell.

Filling the cells with “values” is done like this:

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

Feed the created array to the HexaPath class .

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

The function will analyze the array and if everything is fine, it will return true.
Now you can request the path: the

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

structure of the result variable is as follows: result ['status'] = 1 if the path was calculated successfully, -1 if something happened. And this can happen:
result['status']:int;
result['path']:Array;

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

If result ['status'] = 1 , then in the variable result ['path'] there is a generated array of coordinates of the path cells. In each cell of the array, a variable of type Object , for which the cell coordinates are in the coords property . Confused? Now I will comment on the code: and so on. That's essentially all. The implementation turned out quite frisky. The demo can be seen here . Sources swing from here . I hope someone will find my work useful ... UPD. ilyaplot rewrote the implementation of this algorithm in php. You can download it here .

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'];