Classic A-Star path finding

For more information about A-Star itself, the folks over at Red Blob Games put together a very comprehensive introduction:

http://www.redblobgames.com/pathfinding/a-star/introduction.html

Types

Distance = int | float: Distance is used for two things:
To measure cost of moving between nodes

To represent the heuristic that determines how close a point is to the goal
Graph = concept g ## The graph being traversed. ## * `nieghbors`: Iterates over the neighbors of a node in the graph ## * `cost`: Returns the price for moving between two nodes var node: Node for neighbor in g.neighbors(node): typeof(neighbor) is Node cost(g, node, node) is Distance
Node = concept n ## Represents a node stored within a graph. ## * `==`: Nodes must be comparable so we know when we reach the goal ## * `hash`: Nodes are used as keys in a table, so they need to be ## hashable `==`(n, n) is bool hash(n) is Hash
Point = concept p ## An X/Y Coordinate. This isn't used by the A-Star algorithm itself, ## but by the built in heuristic procs. p.x is Distance p.y is Distance

Procs

proc asTheCrowFlies[P: Point](node, goal: P): float {.inline.}

A convenience function that measures the exact distance between two points. This is meant to be used as the heuristic when creating a new AStar instance.

proc chebyshev[P: Point; D: Distance](node, goal: P): D {.inline.}

A convenience function that measures the chebyshev distance between two points. This is also known as the diagonal distance. This is meant to be used as the heuristic when creating a new AStar instance.

proc manhattan[P: Point; D: Distance](node, goal: P): D {.inline.}

A convenience function that measures the manhattan distance between two points. This is meant to be used as the heuristic when creating a new AStar instance.

proc onLineToGoal[P: Point; D: Distance](node, start, goal: P): D {.inline.}

Computes the cross-product between the start-to-goal vector and the current-point-to-goal vector. When these vectors don't line up, the result will be larger. This allows you to give preference to points that are along the direct line between the start and the goal.

For example, you could define a heuristic like this:

proc heuristic(grid: Grid, node, start, goal, parent: Point): float =
    return 1.5 * onLineToGoal[Point, float](node, start, goal) +
        asTheCrowFlies(node, goal)

proc straightLine[P: Point; D: Distance](weight: D; node: P;
    grandparent: Option[P]): D

Returns the given weight if a node doesn't have any turns. Otherwise, returns 1. You can multiply the result of a different heuristic to give preference to straight paths.

For example, you could define a heuristic like this:

proc heuristic(
    grid: StraightLineGrid,
    node, start, goal, parent: XY,
    grandparent: Option[XY]
): float =
    straightLine[XY, float](1.2, node, grandparent) *
        manhattan[XY, float](node, goal)

Iterators

iterator path[G: Graph; N: Node; D: Distance](graph: G; start, goal: N): N: Executes the A-Star algorithm and iterates over the nodes that connect the start and goal

src/astar

Types

Procs

Iterators