No replies to this topic

[Uberi]

An optimised implementation of the A* search algorithm, a popular algorithm often used for finding the shortest path between a start location and a goal.

Its performance stems from usage of relevant data structures such as the binary min-heap for open list node selection and map fields for membership testing.

Usage:

Path := PathFind(Grid,StartX,StartY,EndX,EndY)
For Index, Node In Path
    MoveToPosition(Node.X,Node.Y)

NOTE: The grid is in the form Grid[X,Y], not Grid[Y,X]. If you use something like the following the rows and columns will be inverted:

Grid := [[0,0,0,0,0],
         [0,1,1,1,1],
         [0,0,0,0,0],
         [1,1,1,0,0],
         [0,0,0,0,0]]

This can be fixed through transposition:

NewGrid := []
For IndexY, Row In Grid
{
    For IndexX, Entry In Row
        NewGrid[IndexX,IndexY] := Entry
}

Download:

Script

A usage example is included at the top of the file.