Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

What is the more common practice in commercial games; path lookup tables or real time searches?

I've read that in many games path lookup tables are pre-calculated and baked into each map, so to speak, then steering behaviour is used to handle dynamic obstacles.

or is it better practice to use optimised hierarchical A* searches? I understand the pro's and cons of each, I'm just curious as to what is most often used in the industry.

share|improve this question

4 Answers 4

up vote 4 down vote accepted

Seeing as how I've done this a few times in the industry, here's my rule of thumb:

Always, always implement dynamic "on-demand" pathfinding first, because it's simpler, faster to code, is much (MUCH) easier to debug, is more flexible, and has fewer moving parts (doesn't require changes to file formats, makes fewer demands on the data pipeline, etc).

I'm currently working on a commercial racing game which has fixed but branching tracks. Even though each track might only have four or five possible routes to reach the finish line, each car (8+ of them) is dynamically generating its own path from the starting point to the finish line, independently from the other cars. You might call it a waste for the cars to generate these same paths over and over again. But it's not -- it's simply faster and easier for me to code it this way than to bother with doing it as a pre-process, which means I can spend more of my time on things which actually will be noticed and valued by the end-user. Or to put it differently; we're trading a vanishingly small amount of CPU time for a whole lot of my time.

Pre-building paths is a form of code optimisation, and as such, you really shouldn't be thinking about it at all until profiling has shown that the dynamic approach is actually having a measurable impact on performance. In many (most?) cases, it doesn't. And so the fast-to-implement and flexible "dynamic, on demand" approach should always be preferred, until concrete profiling shows otherwise.

share|improve this answer

That's entirely dependent on the type of game and the requirements. In a game where there are lots of entities and therefore lots of path-finding queries, a lookup-table will come in handy.

In highly dynamic worlds or worlds with lots of possible paths, lookup-tables are either useless or not practicable (as they would potentially consume huge amounts of memory).

Albeit my insight into "the industry" is quite limited, I think it's common sense to use the tool that's best suited for the job. In some cases this might be a lookup table, in other cases real-time search is the way to go.

share|improve this answer
    
and in some cases they may use both, for example lookup-table when between far places, and A* between near ones. it will result in something like what I saw in oblivion. –  Ali.S Nov 19 '11 at 15:37

Precalculate whatever you can. Do real-time searches through the rest.

To look at it one way, almost every single implementation has a bit of both - you can't perform an A* search without a graph, so someone had to create the graph, usually as part of the level design process. And even if you do A* searches, for pretty much everything but turn-based strategy games you still have to move smoothly from one node to the next, meaning some sort of steering operation is going on (even if it's a trivial linear interpolation).

Also, don't assume everybody is using hierarchical A* for searches. Often just a plain A* is fine, and sometimes forming a decent hierarchy is difficult. Sometimes people use different variations on A*, such as IDA*.

share|improve this answer

Use the simplest-to-implement approach that you can afford to use.

  • If, for example, your game has preset maps, and it's easier for you to bake paths in while creating the map asset, do so.
  • If it has preset maps, but you have eg. only one artist and one coder, and the artist has a lot of work to do already, the coder can write in a dynamic pathfinder.
  • If your game has only procedurally generated maps, then obviously pathing has to be calculated at runtime, but runtime here could mean either precalculating paths before play begins, but after the map is generated, or it could mean simply calculating pathing during play.

Keep it simple inasmuch as possible, unless you have a pressing need to make things more complex.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.