dstarlite

Documentation

Overview

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
http://pub1.willowgarage.com/~konolige/cs225b/dlite_tro05.pdf

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).

Index

• type Data
• type Planner
  • func New(data Data, start, goal State) *Planner
  • func (s *Planner) FlagChanged(u, v State, cOld, cNew float64)
  • func (s *Planner) Goal() State
  • func (s *Planner) Plan() (path []State)
  • func (s *Planner) Start() State
  • func (p *Planner) UpdateStart(s State)
• type State

Types

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.