The OpenD Programming Language

pathfind

Implements the A* path finding algorithm on a grid.

pathfind
(,,,
scope bool delegate isPassable
,
scope int delegate d = null
,
scope int delegate h = null
)

Parameters

start Point

starting point on the grid

goal Point

destination point on the grid

size Size

size of the grid

isPassable bool delegate

used to determine if the tile at the given coordinates are passible

d int delegate

weight function to the A* algorithm. If null, assumes all will be equal weight. Returned value must be greater than or equal to 1.

h int delegate

heuristic function to the A* algorithm. Gives an estimation of how many steps away the goal is from the given point to speed up the search. If null, assumes "taxicab distance"; the number of steps based solely on distance without diagonal movement. If you want to disable this entirely, pass p => 0.

Return Value

Type: Point[]

A list of waypoints to reach the destination, or null if impossible. The waypoints are returned in reverse order, starting from the goal and working back to the start.

So to get to the goal from the starting point, follow the returned array in backwards.

The waypoints will not necessarily include every step but also may not only list turns, but if you follow them you will get get to the destination.

Bugs

The current implementation uses more memory than it really has to; it will eat like 8 MB of scratch space RAM on a 512x512 grid.

It doesn't consider wraparound possible so it might ask you to go all the way around the world unnecessarily.

Meta

History

Added May 2, 2020.