AmProsius
Gorn's pathfinding in the Free Mine is abysmal
Describe the bug It's nearly impossible to have Gorn follow you through the whole Free Mine as he gets stuck quite easily.
Expected behavior Gorn doesn't get lost in the Free Mine as often as in vanilla Gothic.
NPC pathfinding follows "robust tracing" to find the direct route to the target position (largely ignoring height difference). The failing of robust tracing has a time-out. The "possibility of failing" increases over some time if reaching the target position is currently not possible (not sure what situations that entails). During this time period, however, the NPC is not standing still but continues to try to reach its target position. This results in the NPC running in circles or along the edge of a ledge or along walls. I am not sure whether that is intended. I assume it is necessary for the NPC to find/wiggle their way towards a possible path and around obstacles.
Only once robust tracing fails the waynet will be consulted. The route on the waynet is calculated using A*. Since the waynet, i.e. the ways connecting the waypoints, are designed by hand, routes on the waynet result in very reliable but very snappy/unnatural movement due to straight ways. The optimal route is calculated from nearest waypoint of the start position to the nearest waypoint of the end position. That means for regions sparse in waypoints (like the Free Mine), the start/end waypoints may be very far off, resulting in terrible routes. If, for example, the PC is on a ledge with the closest waypoint below, the follower NPC (whose robust tracing previously failed) would jump down to reach the waypoint only then to fail on robust tracing to get any closer.
In the context of the Free Mine, robust tracing does not seem to fail often - as far as I know - not even when Gorn is stuck on a platform and running in circles on its edge. I could imagine that additional height difference checks and consequently forcing waynet routes might help. Where robust tracing does fail in the Free Mine is mostly if Gorn is a level below the PC. In that case, he will run around aimlessly or in circles until the fail time-out is reached. (By that time, he might have run into a completely different direction.) In the ideal case, the route on the waynet will correctly direct him towards a ladder. However, if there is no waypoint close to the PC, the closest determined waypoint might be below the player. Gorn's waynet route would then have him run away from the ladder towards the waypoint below the PC.
How exactly robust tracing determines the next target position or if its really just a direct straight line towards the target NPC (maybe using backtracking?) I haven't looked at yet.
A first step in improving NPC pathfinding is to improve finding the nearest waypoint. I already tried penalizing the Y-distance to force waypoints at similar height. Instead of merely finding the nearsest waypoint based on the Euclidean distance, we should find the nearest accessible waypoint (that results in another pathfinding problem within this pathfinding problem!) and/or the nearest way (connection between two waypoints) if the waypoints are spaced widely.
