My goal was to come out of this weekend with a pathfinding algorithm visualizer. I maneged to get the A* Search algorithm done. I used pygame to to visualize the algorithm. The window was broken up into column and rows, with each square representing Node.
The A* searching algorithm, further explained here
It uses concepts from Eulerian graph theory. The basics of this algorithms :
f(n)=g(n)+h(n)
where
f(n) = total estimated cost of path through node n
g(n) = cost so far to reach node n
h(n) = estimated cost from nn to goal. This is the heuristic part of the
cost function, so it is like a guess.
h(n) can be calculated different ways, but these are the main 2
Manhattan Distance Heuristic abs(x_start - x_end) + abs(y_start - y_end)
Euclidean Distance Heuristic sqrt((x_start - x_end)^2 + (y_start - y_end
)^2)
Manhattan Distance Heureistic is quicker to calculate, but the Euclidean
Distance Heuristic created more realistic paths, so I went with the latter
- Tech with Tim
- Brilliant's A* Search page
- A plethora of frantic google searches
- Coffee