engine: azul3d.org/engine/dstarlite

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

### 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 (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.