Jumper(v1.8.1)

• Index

Contents

• Functions

Modules

• jumper.core.bheap
• jumper.core.heuristics
• jumper.core.node
• jumper.core.path
• jumper.grid
• jumper.grid
• jumper.pathfinder

Scripts

• jumper.search.astar
• jumper.search.bfs
• jumper.search.dfs
• jumper.search.dijkstra
• jumper.search.jps
• jumper.search.thetastar

Module jumper.core.heuristics

Heuristics for the search algorithm.

A heuristic provides an estimate of the optimal 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 built-in heuristics available.

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(dx, dy)
   -- function body
 end
 

Jumper features some built-in distance heuristics, named MANHATTAN, EUCLIDIAN, DIAGONAL, CARDINTCARD. You can also supply your own heuristic function, using the template given above.

Usage:

  -- Example
  local Distance = require ('jumper.core.heuristics')
  local Grid = require ("jumper.grid")
  local Pathfinder = require ("jumper.pathfinder")
  local walkable = 0
  -- Placeholder: local map = {...}
  local grid = Grid(map)
  local myFinder = Pathfinder('ASTAR', grid, walkable)

  -- Use Euclidian heuristic to evaluate distance
  myFinder:setHeuristic('EUCLIDIAN')
  -- etc ...

Info:

• Copyright: 2012-2013
• License: MIT
• Author: Roland Yonaba

Functions

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

Functions

Heuristics.MANHATTAN (dx, dy)

Manhattan distance.
This heuristic is the default one being used by the pathfinder object.
Evaluates as distance = |dx|+|dy|

Parameters:

• dx int the difference endX-startX
• dy int the difference endY-startY

Returns:

number the distance from location startX, startY to location endX, endY

 -- First method
 pathfinder:setHeuristic('MANHATTAN')

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

Heuristics.EUCLIDIAN (dx, dy)

Euclidian distance.
Evaluates as distance = squareRoot(dx*dx+dy*dy)

Parameters:

• dx int the difference endX-startX
• dy int the difference endY-startY

Returns:

number the distance from location startX, startY to location endX, endY

 -- First method
 pathfinder:setHeuristic('EUCLIDIAN')

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

Heuristics.DIAGONAL (dx, dy)

Diagonal distance.
Evaluates as distance = max(|dx|, abs|dy|)

Parameters:

• dx int the difference endX-startX
• dy int the difference endY-startY

Returns:

number the distance from location startX, startY to location endX, endY

 -- First method
 pathfinder:setHeuristic('DIAGONAL')

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

Heuristics.CARDINTCARD (dx, dy)

Cardinal/Intercardinal distance.
Evaluates as distance = min(dx, dy)*squareRoot(2) + max(dx, dy) - min(dx, dy)

Parameters:

• dx int the difference endX-startX
• dy int the difference endY-startY

Returns:

number the distance from location startX, startY to location endX, endY

 -- First method
 pathfinder:setHeuristic('CARDINTCARD')

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