Overview
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) it may have input issues. Firefox works great.