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-Clickon a cell to flip it from wall to empty or vice-versaRight-Clickanywhere to randomly add 10 cells to the grid- Press
Enterto start running the algorithm - Press
Rto 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
- type Board
- 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
- type Input
- type TableEntry
- type Tile
- 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 ¶
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 (*Board) Coord ¶
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) Index ¶
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 ¶
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.
type Game ¶
type Game struct {
// contains filtered or unexported fields
}
Game represents a game state.
func (*Game) Draw ¶
func (g *Game) Draw(screen *ebiten.Image)
Draw draws the current game to the given screen.
type Input ¶
type Input struct {
LeftMousePressed bool
RightMousePressed bool
MouseX int
MouseY int
EnterPressed bool
ResetPressed bool
}
func (*Input) CopyAndReset ¶
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.
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 (*Tile) Draw ¶
func (t *Tile) Draw(boardImage *ebiten.Image)
Draw draws the current tile to the given boardImage.
func (*Tile) HeuristicDistanceFrom ¶
HeuristicDistanceFrom is the h() function for A*. Here we use the pythagorean distance.
func (*Tile) TryFlipWall ¶
func (t *Tile) TryFlipWall()
Source Files
Directories