pathfind

README

Pathfind

Currently offers generic unweighted A* and BFS algorithm.

CLI Usage

Reading from file:

go run cmd/main.go -filename examples/small.txt

Reading from stdin:

cat examples/small.txt | go run cmd/main.go

Overriding symbols

go run cmd/main.go \
    -filename="examples/emoji.txt" \
    -symbolNonWalkable="🔥" \
    -symbolWalkable="⬜" \
    -symbolStart="🟢" \
    -symbolFinish="🏁" \
    -symbolPath="🚗"

See examples:

examples/example.sh <small|emoji>

Library usage

T.B.D

License

MIT

Documentation

Index

• type Adapter
• type Algorithm
• type Event
• type EventCandidateAdded
• type EventCandidateVisited
• type EventFinishReached
• type EventMaxCostReached
• type EventUnsolvable
• type FuncAdapter
  • func (a *FuncAdapter[T]) CostToFinish(c T) int
  • func (a *FuncAdapter[T]) IsFinish(c T) bool
  • func (a *FuncAdapter[T]) Neighbours(c T) []T
• type SolveContext
• type Solver
  • func NewSolver[T comparable](algorithm Algorithm, start T, adapter Adapter[T]) Solver[T]
  • func (s *Solver[T]) EventLog() []Event
  • func (s *Solver[T]) Walk() []T
• type Walker

Types

type Adapter

type Adapter[T comparable] interface {
	// to return the next reachable steps from the given T
	Neighbours(T) []T

	// to return the estimated cost to reach the finish from the given T.
	// this function is currently only used when using the astar algorithm
	CostToFinish(T) int

	// indicating whether the given T is the finish or not
	IsFinish(T) bool
}

type Algorithm

type Algorithm int

const (
	AlgorithmBFS Algorithm = iota
	AlgorithmAStar
)

type Event

type Event interface {
	// contains filtered or unexported methods
}

type EventCandidateAdded

type EventCandidateAdded[T comparable] struct {
	CandidateID T
}

type EventCandidateVisited

type EventCandidateVisited[T comparable] struct {
	CandidateID T
}

type EventFinishReached

type EventFinishReached[T comparable] struct {
	Path []T
}

type EventMaxCostReached

type EventMaxCostReached struct{}

type EventUnsolvable

type EventUnsolvable struct{}

type FuncAdapter

type FuncAdapter[T comparable] struct {
	NeighboursFn   func(T) []T
	CostToFinishFn func(T) int
	IsFinishFn     func(T) bool
}

func (*FuncAdapter[T]) CostToFinish

func (a *FuncAdapter[T]) CostToFinish(c T) int

func (*FuncAdapter[T]) IsFinish

func (a *FuncAdapter[T]) IsFinish(c T) bool

func (*FuncAdapter[T]) Neighbours

func (a *FuncAdapter[T]) Neighbours(c T) []T

type SolveContext

type SolveContext[T comparable] struct {
	MaxCost int

	Publish   func(Event)
	Adapter   func() Adapter[T]
	IsVisited func(T) bool
	Visit     func(T)
}

type Solver

type Solver[T comparable] struct {

	// some runtime options
	MaxCost int
	// contains filtered or unexported fields
}

func NewSolver

func NewSolver[T comparable](algorithm Algorithm, start T, adapter Adapter[T]) Solver[T]

func (*Solver[T]) EventLog

func (s *Solver[T]) EventLog() []Event

func (*Solver[T]) Walk

func (s *Solver[T]) Walk() []T

type Walker

type Walker[T comparable] interface {
	Walk(SolveContext[T]) []T
}