7
\$\begingroup\$

When NP-Hard problems arise in game development, how are such problems dealt with? Through heuristics or solvers or a combination of both?

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Did you search various game development related sites such as here, Reddit, gamedev.net? Asking for lists here is off-topic, unfortunately, and I suppose the other question you ask will depend on the situation. \$\endgroup\$
    – Vaillancourt
    Commented Sep 1, 2022 at 15:35
  • 1
    \$\begingroup\$ I've edited the question in an attempt to bring it on-topic, though I'll be the first to admit the current form is still very broad. I'd invite community edits to further target the question, or votes to close if community members consider the revised form to still be off-topic. \$\endgroup\$
    – DMGregory
    Commented Sep 1, 2022 at 17:34
  • 1
    \$\begingroup\$ Counterpoint to @House: a lot of NP-Hard problems are fun, in the sense that many common game mechanics turn out to be NP-Hard. Sokoban, Sliding block puzzles, navigating levels in Mario, Zelda, Pokémon, or Metroid and more have been proven to fall in this complexity class (or worse). But in those cases, the instances that show up in games are usually small enough to be trivially computable, even if they're exponential-time or worse in the general case. \$\endgroup\$
    – DMGregory
    Commented Sep 1, 2022 at 21:24
  • 2
    \$\begingroup\$ I was a business software developer for 5 years, and I've done a little bit of game development too, and in that whole time, no NP-hard problem ever arose. I can't think of an NP-hard problem that is likely to arise when writing a video game (unless the game is specifically about some NP-hard problem). So I suspect that for most video game developers, the answer is "that never happens." \$\endgroup\$ Commented Sep 2, 2022 at 10:48
  • 2

1 Answer 1

18
\$\begingroup\$

In my experience, the main way NP-Hard problems are solved in game development involves relying on the fact that our instances tend to be quite small.

We usually don't need to solve NP-Hard problems involving millions of customers or billions of rows in a "Big Data" style database, where the complexity class hits hardest.

When the problems are player-facing, ie. the gameplay challenge depends on a human figuring out the solution, then the problem sizes are implicitly bounded by the limits on human reasoning and working memory.

If your \$n\$ is on the order of a couple dozen, then it doesn't matter if the best known algorithm for a problem is \$O(e^n)\$, and you may even be able to brute force exact solutions to some problems with \$O(n!)\$ complexity.

A recent example I encountered was in developing a solver routine as part of a level generator for a deductive puzzle game - to ensure the puzzles it generated could be successfully completed without guessing. The rules of the puzzle game make it a Boolean satisfiability problem equivalent to 3-SAT, and so NP-Hard. But taking into account limits on human reasoning, I limit my search to deductions that involve at most a dozen variables and a dozen clauses (or so). That keeps the search for a deducible solution pruned tightly enough that even a very naïve exponential algorithm can solve a full puzzle in milliseconds.

When the problem is not meant to be player-solvable, we still have other factors that can mitigate the difficulty.

If the problem is in decision-making by AI agents...

  • There are usually only a few sophisticated agents in a single game scene, like a handful of AI opponents in a strategy game, or a few dozen enemy combatants in a shooter. An expensive AI routine isn't too bad if you only need to run it a few times.

    Games with large numbers of AI agents tend to have them follow simpler logic like swarming, using steering behaviours or flow fields, rather than complex optimization routines.

  • It's often OK if those agents make decisions on human-perceivable time scales. We don't need them to react to a change in game state within a single frame - in fact, a delay proportional to human reaction and decision-making speeds can make the AI appear more realistic and fair than one that always reacts instantaneously. So we can afford to offload a heavy optimization calculation to a background thread, or time-slice our processing of it, so each agent only computes a new optimal move every few seconds, using simpler reflex behaviours in between strategic updates.

  • We often don't care if the AI makes the very best decision possible. In fact, sometimes a solution that's too clever/thinking too many steps ahead can look to the player like a bug, or like the AI is behaving randomly. Often we prefer predictable and obviously-explainable behaviour over optimal behaviour. That lets us apply a relaxation and solve a simpler version of the problem, use heuristics, or apply bounded reasoning to trade-off optimality for computation speed and memory efficiency.

If the problem arises in procedural generation of content, this is often work that can be done on a background thread while the player is playing previously-generated content, so it's OK if it takes some time to finish.

We'll also frequently use chunking techniques to reduce the density of data points our algorithms need to act on - say replacing a fine grid of the game map with a navmesh consisting of a much smaller number of much larger polygonal nodes, and solving spatial problems on this reduced graph. This again can trade off exact optimality for time and memory savings, but the player often won't know what's exactly optimal anyway, or we can disguise/explain-away sub-optimal behaviour using the game's fiction and art (eg. this unit sometimes looks a bit awkward trying to get into the best attack position according to its complex evaluation function? Make its model/sprite and animations look lumbering and clumsy so that's part of its character!)

That last point touches on a great get-out-of-jail-free card we have in game development: our worlds are made up. If the design of a particular game rule demands solving a computationally intractable problem, rather than inventing a revolutionary algorithm to solve it, we can just change the rules to something simpler to compute. That's a liberty that folks working in real-world domains like scientific computing, high-frequency trading, etc. don't have such easy access to. 😉

\$\endgroup\$
1
  • 3
    \$\begingroup\$ Re changing the rules: Along that vein, there's also the simple reality that the AI can follow different rules to the player, although you can expect players to get quite annoyed if they notice such a thing. \$\endgroup\$
    – Kevin
    Commented Sep 2, 2022 at 5:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .