Documentation
¶
Index ¶
- type Maze
- type Problem
- func (p Problem) Discard(image.Point)
- func (p Problem) Finish(c image.Point) ([]image.Point, error)
- func (p *Problem) Initialize(out []image.Point) ([]image.Point, error)
- func (p Problem) Next(c image.Point, out []image.Point) ([]image.Point, error)
- func (p Problem) OptimisticLess(a, b image.Point) bool
- func (p Problem) PessimisticLess(a, b image.Point) bool
- func (p Problem) Solved(c image.Point) bool
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Maze ¶
type Maze struct {
Size image.Rectangle
Start, End image.Point
// contains filtered or unexported fields
}
func Make ¶
Make creates a new maze of the given size, using the given random number generator.
If r is nil, the default random number generator will be used.
func (Maze) Down ¶
Returns true if you can move down from the given point.
func (Maze) Draw ¶
Returns a drawing of the maze, mostly for debugging purposes. An optional path can be drawn on top of the maze.
func (Maze) Left ¶
Returns true if you can move to the left from the given point.
func (Maze) Right ¶
Returns true if you can move to the right from the given point.
type Problem ¶
type Problem struct {
// contains filtered or unexported fields
}
A Problem is intended to be used by the Solve function to find a path through a maze.
This is more of a demonstration of how to use the Solve function, a dedicated maze solving algorithm would more efficient. In particular, the solver manages a max heap for discarding states when at capacity, which a maze solver would not need - a maze has a finite number of cells, which for our purposes represent a state, and we'd never exceed (and thus need to keep track of and discard) that many states.
func NewProblem ¶
func NewProblem(size image.Rectangle, start, end image.Point, rightTest func(image.Point) bool, downTest func(image.Point) bool) *Problem
NewMazeProblem creates a new maze problem with the given size, start and end points, and well as two functions that test if movement to the right and down is allowed from a given point.
func (Problem) Discard ¶
This function would be used to release any resources associated with a given search state, but since a state for this problem is just a point, and all the actual state information is stored in the cells slice, there's nothing to do here.
func (Problem) Finish ¶
Converts the given position, the one that passed the Solved test above, into a list of points that form a path from the start to the end.
func (*Problem) Initialize ¶
Initializes the maze search problem, and appends the start point to the given slice.
func (Problem) Next ¶
Appends the next positions to consider from the given position.
func (Problem) OptimisticLess ¶
Returns true if state a should be explored before b.
func (Problem) PessimisticLess ¶
Similar to OptimisticLess, but we scale the heuristic to penalize uncertainty about the actual remaining distance.
Note that the solver uses this with a max heap to determine which states to prune when at capacity.
This will typically be similar to OptimisticLess, but with a penalty for uncertainty.
For our purposes, we're just going to use the same heuristic as OptimisticLess. Assuming that you give the solver a capacity equal to the number of cells in the maze, it won't need to prune any states.
Source Files