This will be a brief overview of how I created the visualization, not detailed
explanation of the A* algorithm. If you want that check out either this video
by Polylog. Going into this project I had only heard of A* before. I knew it
existed from watching Polylog's youtube video about 6 months before. In my
Data Structures and Algorithms class from my previous university semester, one
of my homework assignments was implementing Dijkstra's Algorithm, so I have
had some familliarity with implementing pathfinding algorithms. I knew
implementing A* would be similar so I wanted to do it.
I decided to use Unity for this project to simplify the creation of the visualization
and interactability of the demo I wanted to make. I created an Empty 2D scene, a
prefab for the grid tiles, and a empty GameObject called “GridManager” to spawn
in the grid on runtime. The tile prefab contained a couple sprite overlays that
I could enable or disable to change the color of the tile, indicating the state
of the tile. Each tile can either be normal, a wall, the start, the end, or a path.
When the position of the start and the end tile's are tracked in the GridManager
so that there can only be one goal and start at any time.
At start, the GridManager generates a 16:9 grid of tiles and positions the camera
in the center of them. After that, every frame the GridManager checks the valid
neighbors of each tile and calls execution of the A* script. The A* script first
clears its auxilarry data structures, which include a List with the path to from
the start to the goal, and a Dictionary with the tiles that have been checked as
the key, and the cost as the value. The Start and Goal are spawned at the bottom
left and top right respectively. After the data structures are cleared, the main
pathfinding function is called. When it's done the List containing the path from
the start to the goal is fully updated and all of the tiles have their sprites overlayed
to show the path on screen.
*If your browser supports gestures (mouse dragging) this web build may have input issues. Firefox
works great.