> Pathfinding is actually a murderously complex programming challenge—one that, depending on the path, might be NP-complete. > The "eureka!" moment came when C

> Pathfinding is actually a murderously complex programming challenge—one that, depending on the path, might be NP-complete. > The "eureka!" moment came when Castle and team realized they didn't have to build perfect—or even really great—pathfinding. Rather, they had to build pathfinding that didn't look stupid to the player. > The most interesting thing, at least to me, is that pathfinding is still a difficult problem even for modern games, and simply throwing more CPU power at the problem doesn't really help that much—such is the curse of NP-complete problems. It reminds me of my experience of some pathfinding bugs in OpenRA (free and open source Command & Conquer clone): one day I was playing OpenRA on Linux, and I find the game was running extremely slowly like a snail, the more I played the more slow it was. So I decided to check GitHub, it turned out that AI has built a huge number of soldiers, but unfortunately, due to geography features of the map and the battles, a lot of them have trapped inside "islands" with no available path connected to the rest of the world, or they want to attack targets inside "islands". One example is isolated waterways, another is land with destroyed bridges. But edge cases like these were still not handled well in the OpenRA engine, the AI would keep ordering those units to move and attack. OpenRA uses a variant of the A* algorithm, and those AI orders will force the engine to run a huge number of A* pathfinding attempts on every second and exhaust most of your CPU time. The solution should make the AI to detect these endless attempts and "bail out". The developers have already fixed some of those edge cases, but there are still a few to hunt down. * https://github.com/OpenRA/OpenRA/issues/12435 https://github.com/OpenRA/OpenRA/issues/12435 * https://github.com/OpenRA/OpenRA/issues/7694 https://github.com/OpenRA/OpenRA/issues/7694 * https://github.com/OpenRA/OpenRA/issues/12938 https://github.com/OpenRA/OpenRA/issues/12938 * https://github.com/OpenRA/OpenRA/issues/12435 https://github.com/OpenRA/OpenRA/issues/12435 * https://github.com/OpenRA/OpenRA/issues/10860 https://github.com/OpenRA/OpenRA/issues/10860