astar

README

astar

astar is a visual representation of the A* algorithm for finding the shortest path between two nodes.

Installation

This project uses a 2d game library called ebiten. Follow the instructions for installing ebiten for your platform which covers installing:

• Go
• C compiler (for certain platforms)
• Dependencies

CLI

The tool supports several command line options:

• -h <N>, -height <N> the height of the graph
• -w <N>, -width <N> the width of the graph
• -f <N>, -frequency <N> how often to render the graph solution

Example invocation: go run ./cmd/ -h 20 -w 20 -f 5

Usage

When the grid opens there will be no walls. The following actions are supported:

• Left-Click on a cell to flip it from wall to empty or vice-versa
• Right-Click anywhere to randomly add 10 cells to the grid
• Press Enter to start running the algorithm
• Press R to stop the algorithm and reset the grid

Legend

Color	Meaning
Orange	Start or End node
Black	Wall
White	Unexplored node
Red	Closed Node - full explored
Green	Open Node - fringe - potential node to explore
Blue	Shortest path to currently exploring node

The value printed in each cell is its f(n) value - which is an estimate of the cost to extend that node to the End.

Examples

Description	Example
Direct path
Path with walls
No path - exhaustive search

Documentation

Index

• Constants
• Variables
• func FloatPtr(f float64) *float64
• type AStarGraph
  • func NewAStarGraph(b *Board) *AStarGraph
  • func (a *AStarGraph) MarkPath()
  • func (a *AStarGraph) Neighbors(tile *Tile) []*EdgeTo
  • func (a *AStarGraph) Step()
• type Board
  • func NewBoard(height, width int) (*Board, error)
  • func (b *Board) Coord(index int) (int, int)
  • func (b *Board) Draw(boardImage *ebiten.Image)
  • func (b *Board) End() *Tile
  • func (b *Board) Index(x, y int) int
  • func (b *Board) IsOnBoard(x, y int) bool
  • func (b *Board) Size() (int, int)
  • func (b *Board) Start() *Tile
  • func (b *Board) TileAt(x, y int) *Tile
  • func (b *Board) Update(input *Input)
• type EdgeTo
• type Game
  • func NewGame(h, w, movesPerSecond int) (*Game, error)
  • func (g *Game) Draw(screen *ebiten.Image)
  • func (g *Game) Layout(outsideWidth, outsideHeight int) (screenWidth, screenHeight int)
  • func (g *Game) Update() error
• type Input
  • func (i *Input) CopyAndReset() *Input
  • func (i *Input) Update()
• type TableEntry
  • func (te *TableEntry) F() float64
• type Tile
  • func NewTile(x, y int) *Tile
  • func (t *Tile) Color() color.RGBA
  • func (t *Tile) Draw(boardImage *ebiten.Image)
  • func (t *Tile) HeuristicDistanceFrom(other *Tile) float64
  • func (t *Tile) SetKind(kind TileType)
  • func (t *Tile) Text() string
  • func (t *Tile) TryFlipWall()
• type TileType

Constants

const (
	ScreenWidth  = 1600
	ScreenHeight = 1000
)

const (
	TileSize   = 40
	TileMargin = 2
)

Variables

var (
	BackgroundColor = color.RGBA{0xfa, 0xf8, 0xef, 0xff}
	FrameColor      = color.RGBA{0xbb, 0xad, 0xa0, 0xff}
	White           = color.RGBA{0x00, 0x00, 0x00, 0x00}
	Black           = color.RGBA{0x13, 0x13, 0x13, 0xff}
	Green           = color.RGBA{0x1e, 0x82, 0x4c, 0xff}
	Red             = color.RGBA{0x96, 0x28, 0x1b, 0xff}
	Orange          = color.RGBA{0xff, 0xa5, 0x00, 0xff}
	LightBlue       = color.RGBA{0xad, 0xd8, 0xe6, 0xff}
)

Functions

func FloatPtr

func FloatPtr(f float64) *float64

Types

type AStarGraph

type AStarGraph struct {
	Board   *Board
	Entries map[*Tile]*TableEntry

	OpenNodes   map[*Tile]struct{}
	ClosedNodes map[*Tile]struct{}
	CurrentNode *Tile
}

func NewAStarGraph

func NewAStarGraph(b *Board) *AStarGraph

func (*AStarGraph) MarkPath

func (a *AStarGraph) MarkPath()

MarkPath resets the isPath value for every tile in the grid. It then paints the path to the CurrentNode in our graph traversal. This is very inefficient, and not necessary ffor solving A*. Instead we do this to give the user a visual representation of what the algorithm is "doing".

func (*AStarGraph) Neighbors

func (a *AStarGraph) Neighbors(tile *Tile) []*EdgeTo

Neighbors returns all neighbors to the tile that are not a wall or closed. Neighbors in cardinal directions have a cost of 1 (Lef, Right, Up, Down). Neighbors in corners have a cost of sqrt2 (TopRight, TopLeft, BotRight, BotLeft). Walls and closed (fully visited) nodes are not returned.

func (*AStarGraph) Step

func (a *AStarGraph) Step()

Step explores the next "Open" node with the lowest F-value. If that node is End, then we have reached the end and found the shortest path.

type Board

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

Board represents the game board.

func NewBoard

func NewBoard(height, width int) (*Board, error)

NewBoard generates a new Board with giving a size.

func (*Board) Coord

func (b *Board) Coord(index int) (int, int)

Coord returns the 2-d coordinates for an array index. Board stores the grid as a 1-d array.

func (*Board) Draw

func (b *Board) Draw(boardImage *ebiten.Image)

Draw draws the board to the given boardImage.

func (*Board) End

func (b *Board) End() *Tile

End returns the bottom right tile in thee board, which is our destination.

func (*Board) Index

func (b *Board) Index(x, y int) int

Index returns the position in the array for a coordinate. Board stores the grid as a 1-d array, so this helper computes the 1-d index based on the 2-d coordinates.

func (*Board) IsOnBoard

func (b *Board) IsOnBoard(x, y int) bool

IsOnBoard reeturns true if the coordinate is on the board. This is the relative x and y coordiantes of the mouse, not the cell in the grid.

func (*Board) Size

func (b *Board) Size() (int, int)

Size returns the board size.

func (*Board) Start

func (b *Board) Start() *Tile

Start returns the top left tile in the board which is our starting point.

func (*Board) TileAt

func (b *Board) TileAt(x, y int) *Tile

TileAt returns the tile at the x and y position on the board. This is the position of the mouse, not the x and y coordinates of the grid.

func (*Board) Update

func (b *Board) Update(input *Input)

Update updates the board state.

type EdgeTo

type EdgeTo struct {
	Tile *Tile
	Cost float64
}

EdgeTo represents the edge from a tile to its valid neighbors.

type Game

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

Game represents a game state.

func NewGame

func NewGame(h, w, movesPerSecond int) (*Game, error)

NewGame generates a new Game object.

func (*Game) Draw

func (g *Game) Draw(screen *ebiten.Image)

Draw draws the current game to the given screen.

func (*Game) Layout

func (g *Game) Layout(outsideWidth, outsideHeight int) (screenWidth, screenHeight int)

Layout implements ebiten.Game's Layout.

func (*Game) Update

func (g *Game) Update() error

Update updates the current game state.

type Input

type Input struct {
	LeftMousePressed  bool
	RightMousePressed bool
	MouseX            int
	MouseY            int
	EnterPressed      bool
	ResetPressed      bool
}

func (*Input) CopyAndReset

func (i *Input) CopyAndReset() *Input

func (*Input) Update

func (i *Input) Update()

type TableEntry

type TableEntry struct {
	Node *Tile
	// Distance from start.
	G *float64
	// Heuristic distance from end.
	H float64
	// For tracking the path to how we got here.
	PreviousVertex *Tile
}

TableEntry is a row in the A* table.

func (*TableEntry) F

func (te *TableEntry) F() float64

F is the A* distance function - g() + h().

type Tile

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

Tile contains the information necssary to render a tile on the board. The color and contents are determined based on the kind.

func NewTile

func NewTile(x, y int) *Tile

NewTile creates a new Tile object.

func (*Tile) Color

func (t *Tile) Color() color.RGBA

func (*Tile) Draw

func (t *Tile) Draw(boardImage *ebiten.Image)

Draw draws the current tile to the given boardImage.

func (*Tile) HeuristicDistanceFrom

func (t *Tile) HeuristicDistanceFrom(other *Tile) float64

HeuristicDistanceFrom is the h() function for A*. Here we use the pythagorean distance.

func (*Tile) SetKind

func (t *Tile) SetKind(kind TileType)

func (*Tile) Text

func (t *Tile) Text() string

func (*Tile) TryFlipWall

func (t *Tile) TryFlipWall()

type TileType

type TileType int

TileType is used to dtermine how to render the tile. Some types are immutable - like TypeStart and TypeEnd. SetKind() should be used to change a Tile's Type.

const (
	TypeBlank TileType = iota
	TypeStart
	TypeEnd
	TypeWall
	TypeOpen
	TypeClosed
)