A* Pathfinding project
C++ implementation of A* on a 2D grid.
A junior level class 2 week assignment.
This was my favorite assignment from a class I’ve taken because it had a speed contest. The top 4 students from the class that had the fastest implementation could go on a tour of the Nintendo campus in Washington. I was trying really hard for this, and spent many hours experimenting and reading up on possible optimizations. Unfortunately, I came in 5th, as it was very competitive and people were spending upwards of 40 hours just on this contest. But the speed aspect really got me interested in optimizations in game coding, and was a good learning experience. A little of my work can be seen on the code snippets page.
My experience
I got started on this project really early, as I was gunning for top 4, in a class of 100+ students. The base implementation was easy, and most of my time was dedicated to researching and trying out different ideas for optimization. The list of stored nodes was something that I spent a lot of time experimenting with, I dug through some papers written on the speeds of different data structures, and tried out a d-ary heap, binary trees, lists and finally settled on an array of bucketed arrays.
Cache locality was something else that I was determined to optimize as much as possible. My grid nodes needed to store some data, such as it’s given and final costs, and as we were allowed to preprocess the nodes, I also wanted it to store it’s neighbors so that I can skip calculations if the adjacent node is a wall. I made use of bit shifting to store the 8 neighbours in a 1 byte char, and reducing the class size as much as possible, aligning the struct size to maximize optimization gains.
Other things I did included testing out SIMD, I used it to load in the costs of the 8 neighbors and do the calculation all at once, but this did not offer any gains, so I scrapped it. I also tested out the new C++20 attributes such as likely/unlikely, which did lead to some gains. I picked up some C++20 knowledge from watching talks on youtube from cppcon, so I was glad I could apply the knowledge. I wanted to experiment with lookup tables, having each possible configuration stored with the right function pointer to calculate that exact configuration’s neighbors, but I didn’t have time to try it.