Module core.heuristics

Heuristic functions for search algorithms.

A distance heuristic provides an estimate of the optimal distance cost from a given location to a target. As such, it guides the pathfinder to the goal, helping it to decide which route is the best.

This script holds the definition of some built-in heuristics available through jumper.

Distance functions are internally used by the pathfinder to evaluate the optimal path from the start location to the goal. These functions share the same prototype:

 local function myHeuristic(nodeA, nodeB)
   -- function body
 end

Jumper features some built-in distance heuristics, namely MANHATTAN, EUCLIDIAN, DIAGONAL, CARDINTCARD. You can also supply your own heuristic function, following the same template as above.

Functions

Heuristics.MANHATTAN (nodeA, nodeB) Manhattan distance.
Heuristics.EUCLIDIAN (nodeA, nodeB) Euclidian distance.
Heuristics.DIAGONAL (nodeA, nodeB) Diagonal distance.
Heuristics.CARDINTCARD (nodeA, nodeB) Cardinal/Intercardinal distance.


Functions

Heuristics.MANHATTAN (nodeA, nodeB)
Manhattan distance.
This heuristic is the default one being used by the pathfinder object.
Evaluates as distance = |dx|+|dy|

Parameters:

  • nodeA node a node
  • nodeB node another node

Usage:

     -- First method
     pathfinder:setHeuristic('MANHATTAN')
     -- Second method
     local Distance = require ('jumper.core.heuristics')
     pathfinder:setHeuristic(Distance.MANHATTAN)

Returns:

    number the distance from nodeA to nodeB
Heuristics.EUCLIDIAN (nodeA, nodeB)
Euclidian distance.
Evaluates as distance = squareRoot(dxdx+dydy)

Parameters:

  • nodeA node a node
  • nodeB node another node

Usage:

     -- First method
     pathfinder:setHeuristic('EUCLIDIAN')
     -- Second method
     local Distance = require ('jumper.core.heuristics')
     pathfinder:setHeuristic(Distance.EUCLIDIAN) 

Returns:

    number the distance from nodeA to nodeB
Heuristics.DIAGONAL (nodeA, nodeB)
Diagonal distance.
Evaluates as distance = max(|dx|, abs|dy|)

Parameters:

  • nodeA node a node
  • nodeB node another node

Usage:

     -- First method
     pathfinder:setHeuristic('DIAGONAL')
     -- Second method
     local Distance = require ('jumper.core.heuristics')
     pathfinder:setHeuristic(Distance.DIAGONAL)

Returns:

    number the distance from nodeA to nodeB
Heuristics.CARDINTCARD (nodeA, nodeB)
Cardinal/Intercardinal distance.
Evaluates as distance = min(dx, dy)*squareRoot(2) + max(dx, dy) - min(dx, dy)

Parameters:

  • nodeA node a node
  • nodeB node another node

Usage:

     -- First method
     pathfinder:setHeuristic('CARDINTCARD')
     -- Second method
     local Distance = require ('jumper.core.heuristics')
     pathfinder:setHeuristic(Distance.CARDINTCARD)

Returns:

    number the distance from nodeA to nodeB
generated by LDoc 1.2