v0.0.0-...-793ea6c Latest Latest

This package is not in the latest version of its module.

Go to latest
Published: Oct 24, 2021 License: BSD-3-Clause Imports: 3 Imported by: 1



Package dstarlite implements the D* Lite pathfinding algorithm.

The Planner struct implements the optimized D* Lite pathfinding algorithm described on Page 8, Figure 9 in Sven Koenig and Maxim Likhachev's paper:

Fast Replanning for Navigation in Unknown Terrain

D* Lite is an incremental algorithm, as such updates to it are very fast (in comparison to other pathfinding algorithms like A* where the entire path must be recalculated).



This section is empty.


This section is empty.


This section is empty.


type Data

type Data interface {
	// Succ should return an slice of successors to the specified state.
	Succ(s State) []State

	// Pred should return an slice of predecessors to the specified state.
	Pred(s State) []State

	// Dist should return the distance between the two states. In actual use
	// the second vertex will always be the goal state.
	// It must follow these rules:
	//  Dist(a, a) == 0
	//  Dist(a, b) <= Cost(a, c) + Dist(c, b) (where a and c are neighbors)
	Dist(a, b State) float64

	// Cost should return the exact cost for the distance between two
	// neighboring states.
	// The result for non-neighboring states is undefined.
	// Note: Neighbors can be determined by the Pred() and Succ() functions.
	Cost(a, b State) float64

Data is the data that the DSL Planner struct will plan through.

See dstarlite/grid for example usage.

type Planner

type Planner struct {
	// contains filtered or unexported fields

Planner plans an path through DSL Data.

func New

func New(data Data, start, goal State) *Planner

Returns an new D* Lite Planner given the specified Data interface, start and end goal states.

func (*Planner) FlagChanged

func (s *Planner) FlagChanged(u, v State, cOld, cNew float64)

FlagChanged indicates that the cost of traversal from state u to state v has changed from cOld to cNew and needs to be replanned at the next iteration.

func (*Planner) Goal

func (s *Planner) Goal() State

Goal returns the goal state, as it is currently.

func (*Planner) Plan

func (s *Planner) Plan() (path []State)

Plan recomputes the lowest cost path through the map, taking into account changes in start location and edge costs.

If no path is found, nil is returned.

func (*Planner) Start

func (s *Planner) Start() State

Start returns the start state, as it is currently.

func (*Planner) UpdateStart

func (p *Planner) UpdateStart(s State)

UpdateStart changes the start location post-initialization. Use this to cheaply move along the path (I.e. this does not need to replan the entire path).

type State

type State interface {
	// Equals should simply tell if they're equal (useful for pointer types, etc)
	Equals(other State) bool

State represents an single DSL state.


Path Synopsis
Package grid implements D* Lite grid-based pathfinding.
Package grid implements D* Lite grid-based pathfinding.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL