package dynamic

import "gonum.org/v1/gonum/graph/path/dynamic"

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.

Source Files ¶

doc.go dstarlite.go