I originally started the project in Python because it was easier to build a working prototype. I studied A* from various online resources including it's original research paper, but spent countless hours debugging by stepping through the code during runtime;
although it was repetitive and exhausting, this experience has given me a deeper understanding and appreciation for pathfinding algorithms.
Midway through the development process I noticed how the algorithm’s performance was lacking, originally I thought it was Python being slow, but further investigation led me to conclude that it was my lack of an optimized data structure.
A* needs to prioritize certain elements, but storing these elements while keeping track of priority was tricky. A naive attempt is to dump the elements in a list and search for the best one every time; this obviously had tremendous consequences
for the performance once the list gets enormous. Sorting the list everytime an element was added or removed also wasn’t going to be helpful because only a small partition would ever need to be reordered.
To solve this problem I had to use a Priority Queue -also known as a binary heap depending on its implementation- where elements are stored relative to their priority. The most favoured elements were located the front -or root, whereas
the least are near the back -or leaf. Removing the root element is as easy as swapping it with a leaf node and popping it. Insertion was also simple as the heap only had to operate on certain sub-heaps. This implementation had greatly increase my
A* calculation speed by a factor of 3x at minimum!