Archive for the ‘programming’ Category

Pathfinding Woes

December 2, 2009

Having wrote an optimized (by my standards) A* pathfinding library to be used for my planned game, I was excited to see how it would perform on the Xbox 360. Its performance on the PC is rather satisfactory, at an average of 1ms for searching a 40×40 grid on my Intel 2.8GHz CPU. However, when I ran the same code on the 360, the results were totally shocking. In a bad way.

It took the Xbox 1 second just to perform 100 iterations, where 1000 iterations could be performed on my PC! After verifying that the pathfinding code was indeed heap-allocation-free, I concluded that the Xbox’s CPU just can’t run branch-intensive code as well as on the PC, so something else had to be done. There’s no way I can allocate about 10ms of my precious 16ms game-cycle just for a single game entity to find its stupid path around the map. That’s when I remember that the 360 has 2 additional cores for me to tap into.

After fiddling with the Thread.SetProcessorAffinity method and the WaitHandle class, I’ve came up with a consumer-producer thread architecture which I could actually dump my pathfinding requests to. The only remaining issue is that it still takes about 2 game cycles (33ms) to find paths for 3 entities on a 40×40 grid, unless I allocate another hardware thread for a second pathfinder. That’s not too big an issue though, and it might get ironed out if I get lucky at being able to optimize the pathfinding code even further.

I won’t be uploading my pathfinding library onto Skydrive, but if anyone happens to be interested, leave me a comment.

Advertisements