Tasks:Path Finding

Back to Task List

Overview

The pathfinding engine has the responsibility of providing NPCs the capacity to move from one point to another in the map. To do so it first needs to find a path between those two points, and then handle the movement of the character trough the path.

Dependencies

Mapengine implementation

Requirements

• A perfect or near-perfect path has to be found, when possible, from one point to another. (done)
• It should be able to handle goals in different altitudes, handle the y axis. (done)
• It has to be quick and do not degrade the frame rate in older machines. (done)
• NPCs should be able to handle collision with other NPCs or objects that were not supposed to be in their path, ie. blocked the path after the search was done. (done)
• It should be able to load and save data so that it can reconstitute at least ongoing pathfinding searches in the current map, after a game save/load. (done)
• It has to allow the possibility of choosing which direction the NPC will face after finishing moving. (done)
• Support jumping and climbing.
• It has to be able to find items in the current map, as well as specific areas in the map (ex: "Redwyne Inn", or "Someone's House", etc), and other NPCs. (partially done)
• Each map tile should have a different interest value, so that different creatures/races can follow paths mostly composed of tiles they "like" and avoid tiles they "dislike". Ex: a human might choose a path consisting mostly of roads, avoiding forest and mountains, while a dwarvf might have a path consisting mostly of mountain tiles. This could also be taken to another level and each race could have different velocities according to the tile they are standing on, ex: water tiles would be slow for most races, humans would be fast on roads, slow on mountains, etc... (done)

References

• Adonthell 0.3 version of the pathfinding code in CVS
• Latest version of the pathfinding code in GIT
• Open Issues