This week, I optimized the simulated shot algorithm and worked on our final presentation slides. For the simulated shot algorithm, I added more concrete vectorization for pocket detection and wall collisions. Additionally, I optimized ball collision checks by using scipy.spatial.cKDTree, which is an optimized form of the spatial hashing class I implemented earlier. Now, instead of using vectorized numpy checks with spatial hashing, which was in O(n), we use the cKDTree (a binary tree representing different locations on the board) to find nearest balls in O(log n). Additionally, SciPy uses underlying C code for the cKDTree implementation, which further optimizes the runtime. With these fixes, I was able to improve the shot simulation runtime by almost 600%.
Before Optimizations
After Optimizations
I will be spending this next week working on the final presentation, final report, and getting everything ready for the final demo. I am still on schedule.