I have been working on my main title “Unlox” for about a year now and have found that one of the most complex and frustrating areas of development (for me at least) on Roblox is with pathfinding.
I have found what I believe is an elegant solution and wanted to showcase it along with my game for feedback or improvements.
Pathfinding Use Case:
Static and user generated maps with multiple closed off doors and rooms, with NPC’s controlled by the default Roblox pathfinding system to find players.
Problem:
Complex static and user generated maps with doors behind doors can be easily created and quickly confuse the current pathfinding system especially as many doors are closed behind a skilled or fast-moving player.
Initial solution:
While the target player is moving or alive but cannot be ‘seen’ by the pathfinding system, the NPC will continue to follow the last set of waypoints it found, whilst recomputing new pathways in a separate thread in the hopes of finding the target again.
Issue:
After tinkering here and there for a while and finally getting it all working, I noticed that during a game a skilled player easily and sometimes without even trying could game the ‘chase pattern’ in and out of rooms and trap the NPC in a room. If the player is running and is now behind 5 doors and the NPC could only see up to the second or third door when the doors close and before the last compute, it will lose the path and become stuck.
I searched for other elegant solutions which would allow the pathfinder to ignore certain objects like a closed unlocked door, I tried various collision group configurations and considered another library, but nothing allowed the current pathfinder to ignore special objects and I did not really like the idea of a duplicate map with removed obstacles and inter-translating the coordinates.
My Solution:
My door and room configurations follow a predictable model design and the players uses these to create models of rooms etc so it is easy to design a recursive algorithm to chain a new pathfinder thread through the doors’ in-and-out patterns, and building a map of visible doors along the way, I can iterate these waypoints when the traditional pathfinder thread loses the target, I switch to room finding; although the waypoints are baked into the actual parts themselves in the workspace, these are also recomputed incrementally to account for dynamic changes to the model.
Desired outcome:
The NPC can now go through unlocked doors and find players that are hiding inside rooms easily. Performance was terrible in the first few iterations and after some sustained optimization and refactoring the algorithm can now find its way through rooms (n) deep for static and dynamic user generated maps, on average in under a second. This keeps the NPC chasing relentlessly!
Sorting doors by distance to target before the search, really helps.
