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