SMS Pathfinding code

[Chebmaster]

I think the subject is better discussed on an evolutionary biology forum or some such place

I mean, ape what mother nature does and use similar hacks.

1. Cache it! If a
NPC finds a route between two points once, it memorizes it and then re-uses it without invoking pathfinding, using simple right/left hand algorithm to go around mobile obstacles. Only large deviation/delay to follow the route causes the actor to reset its cache and perform pathfinding again
Each NPC has a weighed route cache. Or all units of the same type do, in case of RTS.

2. Lazy pathfinding
Use direct movement towards the goal with right/left hand obstacle avoidance first, fill a request for the pathfinding manager that may fulfill it several ticks later
This evens out CPU load.

3. If a crowd of adjacent NPCS searches for a path to the same target, do it once. Select the closest NPC as the leader and make all others follow him. Use pathfinding again only if some NPCs have little progress.

4. Use a crude approximation first, before invoking A*:
- cast a virtual collider on a direct route to target using left|right hand to go around obstacles
- if it does reach the target, try smoothing the path out by casting virual colliders between points of the path 10..15 mob diameters apart.
- if it doesn't, use A*
You can even make a *tree* of paths, branching every time your collider collides with a new obstacle, one goes left other goes right.

I mean, I used pretty dumb mechanics in my 1998 FPS but it worked surprisingly well. I'll try describing what I did:

1. Levels were object soup, up to two thousand cylindrical colliders placed haphazardly on a flat plain sorted into a primitive grid to reduce the O^N. Buildings were made of sprites, physically the same cylindrical colliders

2. There was manually created graph of nav-zones to allow navigating bridges and other difficult places. The nav-zones wre cylindrical, of different width (often quite wide)

3. There was nothing like A*. Monsters periodically performed passability checks to see if they can reach their target directly. It was a costly operation consisting of casting a virtual collider along direct path, simulating all drops from ledges and checking for deadly hazards like water or lava. Only one monster per physics tick could do this.

4. All MOBs kept track of the last nav-zone they visited which was used to find path to target. The algorithm was simple:
Is my last visited nav-zone the same as as the target?
YES: move towards the target using left/right hand obstacle avoidance when colliding with something
NO: find path through the nav-zones graph, set the next nav-zone as my next destination.

Coupled with 3, this proved to be amazingly efficient. Monsters only had problems with crudely made stairs where I, the player, had to jump to get unstuck, or with narrow bridges, congesting them and slowing to a crawl.
Other than that... They surely proved to be more proactive than DooM monsters. See player? Go a roundabout way crossing two bridges over a river and then !surprise! him. Silly player, hiding in a hut. Left/right hand along the walls until entrance, oh there is no wall... Surprise!
They were, in fact, very good at appearing !suddenly! as if from nowhere.

All of that with a dozen or so nav-zones placed by hand.

I suppose in modern times your tools auto-build a sparse nav-mesh for your level in offline mode.
But do not discard the left/right hand. It's a powerful tool.