engine: azul3d.org/engine/dstarlite Index | Files | Directories

package dstarlite

import "azul3d.org/engine/dstarlite"

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

Package Files

dstarlite.go key.go priorityqueue.go valuemap.go

type Data Uses

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 Uses

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

Planner plans an path through DSL Data.

func New Uses

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 Uses

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 Uses

func (s *Planner) Goal() State

Goal returns the goal state, as it is currently.

func (*Planner) Plan Uses

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 Uses

func (s *Planner) Start() State

Start returns the start state, as it is currently.

func (*Planner) UpdateStart Uses

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 Uses

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.

Directories

PathSynopsis
gridPackage grid implements D* Lite grid-based pathfinding.

Package dstarlite imports 3 packages (graph) and is imported by 2 packages. Updated 2017-02-19. Refresh now. Tools for package owners.