If video game pathfinding is something you’re curious about but feel intimidated by the scale of, it might be helpful to know that in one real sense it’s no more complicated than what you already know about sorting. Implementing A* is an easy and fun exercise, with plenty of obvious optimization opportunities with jump point searching, hierarchical grids, and so on.
But what’s unique to this domain is that your game might get worse as your pathfinding gets better. There’s an endlessly deep amount of fun to be had in limiting the local knowledge of your pathing agents, toying with local steering or flocking, and adding back in all the inefficiencies characteristic of organic behavior. That’s the hard part.
the only game im playing atm, its sooo good :) great multiplayer
As a tangent, Starcraft 1 (and its popular expansion Brood war) had very weird things going on with its pathfinding, some behaviors/side effects were made into features of the game by the players and professional map makers.
One example out of many, is that certain maps designed late in the game’s life, had harvestable mineral lines blocking the way to another player, but bringing to workers to mine on the same mineral and then spamming the move command would force one of the workers through, to continue its scouting of the enemy on the other side of the mineral line.
This blog is a fascinating read, with many nice articles on developing Starcraft: https://www.codeofhonor.com/blog/the-starcraft-path-finding-hack
Note that this new heuristic is not consistent – it will overestimate the distance of paths that cross more chunk boundaries. A* is only guaranteed to give an optimal path when used with a consistent heuristic. With the new heuristic, units will sometimes take suboptimal paths.
This performance improvement is probably still worth it though, because the gameplay doesn’t require units to have perfectly optimal pathing to be fun.
Related: Casey Muratomi has a couple of blog posts on some code for identifying what surfaces in The Witness are walkable.
https://caseymuratori.com/blog_0032 # Recording of conference talk, but the audio is real bad.