dynamic

Documentation

Overview

Package dynamic provides incremental heuristic graph path finding functions.

Index

• type DStarLite
  • func NewDStarLite(s, t graph.Node, g graph.Graph, h path.Heuristic, m WorldModel) *DStarLite
  • func (d *DStarLite) Here() graph.Node
  • func (d *DStarLite) MoveTo(n graph.Node)
  • func (d *DStarLite) Path() (p []graph.Node, weight float64)
  • func (d *DStarLite) Step() bool
  • func (d *DStarLite) UpdateWorld(changes []graph.Edge)
• type WorldModel

Types

type DStarLite

type DStarLite struct {
	// contains filtered or unexported fields
}

DStarLite implements the D* Lite dynamic re-planning path search algorithm.

doi:10.1109/tro.2004.838026 and ISBN:0-262-51129-0 pp476-483

func NewDStarLite

func NewDStarLite(s, t graph.Node, g graph.Graph, h path.Heuristic, m WorldModel) *DStarLite

NewDStarLite returns a new DStarLite planner for the path from s to t in g using the heuristic h. The world model, m, is used to store shortest path information during path planning. The world model must be an empty graph when NewDStarLite is called.

If h is nil, the DStarLite will use the g.HeuristicCost method if g implements path.HeuristicCoster, falling back to path.NullHeuristic otherwise. If the graph does not implement graph.Weighter, path.UniformCost is used. NewDStarLite will panic if g has a negative edge weight.

func (*DStarLite) Here

func (d *DStarLite) Here() graph.Node

Here returns the current location.

func (*DStarLite) MoveTo

func (d *DStarLite) MoveTo(n graph.Node)

MoveTo moves to n in the world graph.

func (*DStarLite) Path

func (d *DStarLite) Path() (p []graph.Node, weight float64)

Path returns the path from the current location to the goal and the weight of the path.

func (*DStarLite) Step

func (d *DStarLite) Step() bool

Step performs one movement step along the best path towards the goal. It returns false if no further progression toward the goal can be achieved, either because the goal has been reached or because there is no path.

func (*DStarLite) UpdateWorld

func (d *DStarLite) UpdateWorld(changes []graph.Edge)

UpdateWorld updates or adds edges in the world graph. UpdateWorld will panic if changes include a negative edge weight.

type WorldModel

type WorldModel interface {
	graph.WeightedBuilder
	graph.WeightedDirected
}

WorldModel is a mutable weighted directed graph that returns nodes identified by id number.