noam-c/EDEn — Issue #1: Add obstacle detection for moving NPCs.
Author: noam-c
Created: 2011-11-25 18:34:34+00:00
State: open

The current movement behaviour for NPCs simply ignores and walks through obstacles or other NPCs. If another NPC, or the player, walks in the way of a walking NPC, then the walking NPC should take a new best path that goes around the obstacle.

Currently, NPC pathfinding is performed using the Roy-Floyd-Warshall algorithm, which determines a best path for any given pair of tiles in the map. This algorithm is run when the map is first loaded, and does not take into account the fact that the best path might be blocked.
The path could be blocked if a script event adds a new obstacle to the map or if one NPC moves into the path that another NPC is currently walking.

If the path of an NPC is blocked at some point during its walk, then the NPC should use the Pathfinder to get a fallback path using A* (the matrix created by the RFW algorithm could be used as an accurate heuristic function, which would make A* run in linear time).