Info
This post was originally intended for a Patreon audience.
Pathfinding Woes
Access has a pretty simple path-finding system for two reasons:
- Maps are simple, composed of static, rectangular rooms connected to each other via “doors”.
- Characters have a set of predetermined positions they can be.
I thought this was a pretty simple task and I decided to not use a make a fully-fledged path-finding system.
At first, the algorithm did the following steps:
- Take the character’s position.
- Find a series of doors that will take the character to the room they want to go to with the shortest distance possible.
- Pick one of the predetermined spots to stop at.
Here’s what that looked like:
Simple, right? Well, I quickly ran into a problem with this approach. Consider hallways:
As you can see, this would cause a character to walk though a wall, which is… not great. The characters in the story are not ghosts, after all! Well, not yet anyway. A pretty simple solution is to give each door an entry and exit point.
Great! Here’s what out algorithm looks like now (changes bolded):
- Take the character’s position.
- Find a series of doors that will take the character to the room they want to go to with the shortest distance possible. Use the assigned entry and exit points for that door.
- Pick one of the predetermined spots to stop at.
As it turns out, having an entry and exit point for each door is pretty useful and I use it often to account for furniture in the room, especially for furniture placed near a wall. We don’t want characters to walk through furniture either! By putting the exit and entry points in a place where characters can then make a straight-line path to any of the pre-determined positions in the room fixes that problem. So, here’s where I am now:
Here’s what’s going on in this picture:
- Green boxes are the “predetermined positions”
- The yellow line goes between the entry and exit points of the door
As you can see, the lowest-most point on the door is extended quite far into the room to account for the counter, but we also want to place a character behind the counter. Our current strategy, doesn’t know how to deal with this:
Whoops! That’s not allowed. This makes more sense:
- Take the character’s position.
- Find a series of doors that will take the character to the room they want to go to with the shortest distance possible. Find the closest point on the line between the entry and exit points for that door.
- Pick one of the predetermined spots to stop at.
This solution works surprisingly well:
And for other characters, it still behaves as expected!
If I run into even more problems and don’t find a satisfactory solution, I may have to consider using Unity’s built-in path-finding. I would like to avoid doing so since it would introduce a lot of complexity I think this game doesn’t need.