Yesterday, a friend taking an AI course showed me his midterm exam, and I noticed that there was an A* related question.
So today I refactored an A* search that I wrote about a year ago, and hooked it up to the in-game console to do some benchmarking on the XBOX360.
My vision is to have hundreds, or at least dozens, of monsters in the game world at any moment, each of which needs to be able to find it’s way from the darkness it spawned in to the player.
To see how close I am to having this many monsters so far, I did the following test on my PC (an Intel E5300 overclocked to 3.1 Ghz). Note that this code is written with XBOX in mind, not the PC.
This is done on a grid specified by the “world” parameter, so the grid is size 320x320x2 in the last test (~200k cells in total). Cells on the grid are randomly marked as obstacles, in these tests I made roughly 30% of the grid into obstacles.
So in this example, it would already takes 1.7 seconds for 5 monsters to find their way from one end of a 320x320x2 map to the other side. Since the XBOX tends to be about 5-10x slower than this PC, these results are looking grim.
On the XBOX360 I ran the exact same benchmarks, the results are:
Size Average time (ms) 40x40x2 46 80x80x2 188 160x160x2 897 320x320x2 5402
5.4 seconds for a single monster to find his way across a 320x320x2 map. Around 1 minute then, to spawn 10 monsters. And that would be if everything in the game was static — but obstacles move.
At this point, maybe we could have one monster in the game — certainly not dozens.
My plan is to use a heightmap in the game that will be at least 1024×1024, so we’re already using a fairly coarse approximation to the actual game geometry.
These tests have been on a 3D grid of height 2. This is because I was hoping to be able to place obstacles that float slightly above the ground. Only some monsters are affected by these, and perhaps I can just use a 2D grid, and treat some cells specially.
I’m also allowing for diagonals, including 3D diagonals (thus there are 26 possible directions to move at each cell). E.g. a move from (0, 0, 0) to (1,1,1) is legal, and tested. Switching to 2D leaves 8 directions of travel at each cell, and ignoring diagonals will leave only 4 directions.
Removing diagonals will make the paths look more robotic. In the following images, the blue block is the starting position, red is the ending position, and black blocks are obstacles.
Game Programming Gems 5 chapter 2.2 “Minimal Acceleration Hermite Curves” describe a way to generate curves between points that have minimal bendyness, which could smooth out the robotic looking paths.
I recently pulled up a presentation I read a while back about Left for Dead’s AI pathfinding. They essentially use a very coarse pathfinding grid and then use local detailed grids to allow for many (mostly slow moving zombies) to find their way around the environment. This approach could be fruitful. They apparently don’t use D*, and I’m not sure why that is. Probably for the same reason that I don’t want to use it — it could be very time consuming to implement!
I also vaguely remembered reading about Fringe search. So I pulled my copy of Game Programming Gems 7 off the shelf. I’ve been studying chapter 3.7 “Beyond A*: IDA and Fringe Search”, which might provide another route to improving the pathfinding speed.
Game Programming Gems 5 chapers 3.7 and 3.8, “Beyond A*” and “Advanced Pathfinding with Minimal Replanning Cost: Dynamic A Star (D*)” explore efficient approaches for pathfinding when the environment is changing or when multiple mobs spawn relatively close to each other — both of which are the case for me. Again though, implementing D* is significantly more work than the simple A* algorithm.
Studying lots of new material is not something that I have in the time budget for the 3 month duration of this project, so if anyone has a suggestion for which route to take, I’m all ears. In the meantime, I’m going to start studying this material more in-depth tonight, and either come to a decision and implement that tomorrow, or defer the completion of the path finding while I do more research.
The XBOX360 CPU is slow, and purely managed C# running on the compact .NET CLR is REALLY slow, and on top of that, XNA developers don’t have access to the vector processing unit on the XBOX CPU. As a result I’m doing all pathfinding using integers only — a luxury we don’t have for physics simulations, which is another difficult problem for another day.
This makes the path finding problem a tough one to solve in real time on the XBOX. Apparently more than just a couple of days work, especially if I’m going to have hordes of evil hellbeasts approaching you from all corners of the darkness.