module DragonSkeleton::Pathfinding

Contains pathfinding algorithms.

Graphs are represented as hashes where keys are nodes and values are arrays of edges. Edges are hashes with keys :to and :cost. :to is the node the edge leads to and :cost is the cost of traversing the edge.

Nodes can be any kind of data, usually coordinates on a grid with additional pathfinding related data.

Example:

graph = {
  { x: 0, y: 0 } => [
    { to: { x: 1, y: 0 }, cost: 1 },
    { to: { x: 0, y: 1 }, cost: 1 }
  ],
  { x: 1, y: 0 } => [
    { to: { x: 0, y: 0 }, cost: 1 },
    { to: { x: 0, y: 1 }, cost: 1.5 }
  ],
  { x: 0, y: 1 } => [
    { to: { x: 0, y: 0 }, cost: 1 },
    { to: { x: 1, y: 0 }, cost: 1.5 }
  ]
}