Doors, Pathfinding


There is a system in place to handle doors and other objects that block. The problem is that as NPCs walk around they need to be able to open/close doors in order to get from place to place. Moreover, it would be nice to allow some NPCs to go through some doors, e.g., the butcher Kenrich should be able to enter the freezer but the player can only get there by knowing the combination. Or animals, for instance, can't go through doors.

*** SOLUTION 1 ***

Suppose I need to get from place A to place B. We do an A* path find, checking blocks. First, though, we tell all objects to prepare for pathfinding, and they will flag blocks as "requirement" blocks. So a door will flag the blocks that are solid when it's closed as requiring "door".

The first thing we do is pathfind with the assumption that all requirements can be met. We do this by passing a list of requirements that CANT be met to the pathfinder. But as the pathfinder walks over a "requirement" block, it will store that value in a list so that when we have built the path, we know it's only a valid path if the given requirement list can be met.

Then we can pathfind a few more times, this time with the assumption that certain requirements can't be met; there are a few variations on this idea, but the main thrust is to produce a bunch of paths from point A to point B, matched with lists of requirements. The obvious (but perhaps overkill) solution is to include ever possible combination of requirements. Since often these will be only 1 or 2, this maybe isn't a big deal.

When we are searching for a path, we pass in what requirements we are able to meet, and get back a path that we know we can solve. The NPC logic itself then knows to open doors as it comes across them, or whatnot.

*** SOLUTION 2 ***

This is similar to the above in terms of having blocks flagged as requirements, but instead what we do is flag each step as an action. So for instance, to get through a closed door, we know we have to do the "open" action, so that gets put into the path.

*** CONCLUSION ***

Solution 2 is a bit cleaner, in some respects, since it results in a list of actions to take to get from point A to point B (walk to (2,2), walk to (2,3), open door, walk to (2,4), etc.) but it's not bi-directional. As well, it might require more modification to the existing stuff for pathfinding. So I think I will go with Solution 1, even though it's a little bit dirtier.

2007-10-31


◀ Back