algor

Documentation

Overview

Package algor provides multiple algorithm that implements algor interface

Index

• Constants
• Variables
• type AStar
  • func (a *AStar) Search(start state.State) *state.State
  • func (a *AStar) Steps() int
• type Algor
• type Bfs
  • func (b *Bfs) Search(start state.State) *state.State
  • func (b *Bfs) Steps() int
• type Dfs
  • func (d *Dfs) Search(start state.State) *state.State
  • func (d *Dfs) Steps() int
• type HillClimbing
  • func (hc *HillClimbing) Search(start state.State) *state.State
  • func (hc *HillClimbing) Steps() int
• type NoAlgor
  • func (a *NoAlgor) Search(start state.State) *state.State
  • func (a *NoAlgor) Steps() int

Constants

const (
	UP    = "u"
	DOWN  = "d"
	LEFT  = "l"
	RIGHT = "r"
)

Keyboard input keys for algor.NoAlgor

Variables

var (
	NoFunc = func(s *state.State) *int {
		return nil
	}
	//GH1 sums up the cost to s and the manhattan distance from all unsolved boxes
	//to the nearest unsolved goal.
	GH1 = func(s *state.State) *int {
		unsolvedBoxes := make([][2]int, 0)
		unsolvedGoals := make([][2]int, 0)
		for i, a := range s.Tiles {
			for j, v := range a {
				if v == state.BOX {
					unsolvedBoxes = append(unsolvedBoxes, [2]int{i, j})
				}
				if v == state.GOAL {
					unsolvedGoals = append(unsolvedGoals, [2]int{i, j})
				}
			}
		}
		heuristic := 0
		for _, g := range unsolvedGoals {
			minDist := math.MaxInt
			for _, b := range unsolvedBoxes {
				minDist = int(math.Min(float64(minDist), float64(manhattanDist(g, b))))
			}
			heuristic += minDist
		}
		heuristicNCost := heuristic + s.Moves
		return &heuristicNCost
	}
	//GH2 sums up the cost to s, the manhattan distance from all unsolved boxes
	//to the nearest unsolved goal, and the manhattan distance from the player to
	//the nearest unsolved box.
	GH2 = func(s *state.State) *int {
		unsolvedBoxes := make([][2]int, 0)
		unsolvedGoals := make([][2]int, 0)
		for i, a := range s.Tiles {
			for j, v := range a {
				if v == state.BOX {
					unsolvedBoxes = append(unsolvedBoxes, [2]int{i, j})
				}
				if v == state.GOAL {
					unsolvedGoals = append(unsolvedGoals, [2]int{i, j})
				}
			}
		}
		heuristic := 0
		for _, g := range unsolvedGoals {
			minDist := math.MaxInt
			for _, b := range unsolvedBoxes {
				minDist = int(math.Min(float64(minDist), float64(manhattanDist(g, b))))
			}
			heuristic += minDist
		}

		player := s.Pos()

		minDist := math.MaxInt

		for _, b := range unsolvedBoxes {
			minDist = int(math.Min(float64(minDist), float64(manhattanDist(player, b))))
		}

		heuristic += minDist
		heuristicNCost := heuristic + s.Moves
		return &heuristicNCost
	}
	//H1 sums up the manhattan distance from all unsolved boxes
	//to the nearest unsolved goal.
	H1 = func(s *state.State) *int {
		unsolvedBoxes := make([][2]int, 0)
		unsolvedGoals := make([][2]int, 0)
		for i, a := range s.Tiles {
			for j, v := range a {
				if v == state.BOX {
					unsolvedBoxes = append(unsolvedBoxes, [2]int{i, j})
				}
				if v == state.GOAL {
					unsolvedGoals = append(unsolvedGoals, [2]int{i, j})
				}
			}
		}
		heuristic := 0
		for _, g := range unsolvedGoals {
			minDist := math.MaxInt
			for _, b := range unsolvedBoxes {
				minDist = int(math.Min(float64(minDist), float64(manhattanDist(g, b))))
			}
			heuristic += minDist
		}
		return &heuristic
	}
	//H2 sums up the manhattan distance from all unsolved boxes
	//to the nearest unsolved goal, and the manhattan distance from the player to
	//the nearest unsolved box.
	H2 = func(s *state.State) *int {
		unsolvedBoxes := make([][2]int, 0)
		unsolvedGoals := make([][2]int, 0)
		for i, a := range s.Tiles {
			for j, v := range a {
				if v == state.BOX {
					unsolvedBoxes = append(unsolvedBoxes, [2]int{i, j})
				}
				if v == state.GOAL {
					unsolvedGoals = append(unsolvedGoals, [2]int{i, j})
				}
			}
		}
		heuristic := 0
		for _, g := range unsolvedGoals {
			minDist := math.MaxInt
			for _, b := range unsolvedBoxes {
				minDist = int(math.Min(float64(minDist), float64(manhattanDist(g, b))))
			}
			heuristic += minDist
		}

		player := s.Pos()

		minDist := math.MaxInt

		for _, b := range unsolvedBoxes {
			minDist = int(math.Min(float64(minDist), float64(manhattanDist(player, b))))
		}

		heuristic += minDist
		return &heuristic
	}
)

Cost functions.

var (
	PROMPT = strings.Join([]string{UP, DOWN, LEFT, RIGHT}, ", ") + ">"
)

On screen prompt when using algor.NoAlgor

Types

type AStar

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

AStart implements a heuristic-agnostic A* algorithm.

func (*AStar) Search

func (a *AStar) Search(start state.State) *state.State

func (*AStar) Steps

func (a *AStar) Steps() int

type Algor

type Algor interface {
	Steps() int
	Search(start state.State) *state.State
}

Algor is an interface for sokoban solving algorithms Search method is the core of the interface, it takes the start state as start and returns the final state. Steps returns the number of steps the algorithms had to take to get to the returned state.

type Bfs

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

Bfs implements BFS algorithm.

func (*Bfs) Search

func (b *Bfs) Search(start state.State) *state.State

func (*Bfs) Steps

func (b *Bfs) Steps() int

type Dfs

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

Dfs implements the DFS algorithm.

func (*Dfs) Search

func (d *Dfs) Search(start state.State) *state.State

func (*Dfs) Steps

func (d *Dfs) Steps() int

type HillClimbing

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

HillClimbing implements itself.

func (*HillClimbing) Search

func (hc *HillClimbing) Search(start state.State) *state.State

func (*HillClimbing) Steps

func (hc *HillClimbing) Steps() int

type NoAlgor

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

NoAlgor is used for actual human input. it implements algor algorithm so it can be used the same as other algorithms.

func (*NoAlgor) Search

func (a *NoAlgor) Search(start state.State) *state.State

func (*NoAlgor) Steps

func (a *NoAlgor) Steps() int