The Challenge of Efficient Path Finding on the XBOX360

Yesterday, a friend taking an AI course showed me his midterm exam, and I noticed that there was an A* related question.

This got me thinking about A* and after 6 hours of (trying to) make an SMT solver for CSC410 yesterday, I’ve shifted away from art mode to programming mode.

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.

2D path finding with diagonals. The path is fairly natural.

2D path finding without diagonals. A monster following this path in the naive way would turn down, right, down, right,... making it seem robotic.

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.


This entry was posted in DBP2011, XNA and tagged , , . Bookmark the permalink.

6 Responses to The Challenge of Efficient Path Finding on the XBOX360

  1. Evan says:

    I saw your link to this from CDF, interesting stuff … I have been challenged by implementing path finding on my own game as well. Right now it just uses plain A* but I am worried that it won’t scale well to hundreds of agents. I was interested by this research after seeing a cool video of it in action on a game, according to the paper it can simulate thousands of agents travelling to a goal and avoiding obstacles and each other in real time but the math is complicated enough that I’ve been putting off changing my implementation for now :P

  2. olhovsky says:

    That is really interesting Evan!
    Computing the set of potential fields might have a high overhead for large or few actors — I’m not sure because they don’t provide much data for small numbers of actors. They achieve 12fps with 10,000 actors which is pretty amazing. Assuming they used only one thread for the crowd computations, they have ~24-40x the computation power available to me on the XBOX for pathfinding. Still, it could be effective on the XBOX with say 100 actors.
    In any case, that looks like a serious undertaking to implement, but very interesting. I’ll definitely consider it for a future project, or for the future of this project — after the submission deadline.

  3. olhovsky says:

    And here’s another approach also using a continuum style method, with computation on the GPU in mind:
    https://a248.e.akamai.net/f/674/9206/0/www2.ati.com/misc/siggraph_asia_08/GPUCrowdSimulation_SLIDES.pdf
    They achieve 65000 actors at 20fps on the GPU.

  4. Pingback: Every day can’t be a game development day. | Olhovsky

  5. Pingback: Pathfinding: What would Kirk do? | Olhovsky

  6. I am going to at once learn your rss feed when i are unable to in discovering the e-mail subscription hyperlink or perhaps e-newsletter program. Do you have virtually any? Make sure you allow me know to ensure I could signed up. Thank you.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>