On Mon, Jul 23, 2012 at 8:58 AM, Kai Sterker <kai.ster...@gmail.com> wrote:
Pushed the latest pathfinding code, with a few open issues resolved and at least generally in a clean state. Still not done completely, though. > Going up stairs also works now, although not perfectly. There are > instances where the nodes falling on the stairs get skipped and even > if they are present, sometimes the character fails to follow them. > Latter might be a problem with the collision detection. Although right > now I do not understand why it works for the player, but sometimes not > for the NPC. Haven't really solved that issue yet. Seems I need to better understand in what order nodes on the path grid get evaluated. Adding a visualization to the pathfinding phase should help with that, so this will be the next thing on my list. > All in all, the allotted number of iterations for pathfinding needs to > be increased as well. But to allow that, the actual finding of the > path needs to be distributed over several frames (maybe allowing 1000 > iterations per frame(. This change shouldn't be too difficult, but it > will require to keep some data around that right now is only kept > locally. And we must ensure that multiple simultaneous pathfinding > operations each use their own set of data. Done. > Following along the path does not work well if the NPC deviates too > much from that path, i.e. due to being deflected by obstacles. Fixed. Also, if obstacles appear during the walking phase, not the complete path to the goal is recalculated. Instead, just a path from the current spot to the next unblocked part of the path is sought. I have also spend some time yesterday reading up on collision detection in general, and found one article that looks quite interesting: https://harablog.wordpress.com/2011/08/26/fast-pathfinding-via-symmetry-breaking/ Especially the Jump Point Search described there could be something very beneficial to us. As it appears to vastly reduce the number of nodes to search, it might offset the additional cost of finding paths across multiple levels. There's a lua implementation to take as a reference: https://github.com/Yonaba/Jumper/ Unfortunately, there isn't much information about multi-level pathfinding around. I still have not figured out what a good heuristic would be. Experimenting in that area will be easier with the visualization suggested above in place. Another bit for my todo list are doorways. Blocked node detection needs to be able to distinguish between solid walls and doors, which are basically just walls with a hole in them. Not too difficult, but needs to be done. Later we'd also need to accommodate for closed doors, allowing NPCs to open them. For locked doors, we also would have to check if the NPC possesses the matching key in its inventory. That's for after v0.4, though. Keep you updated once there is more progress. Getting visitors next weekend, so might take a little bit of time. Kai _______________________________________________ Adonthell-devel mailing list Adonthell-devel@nongnu.org https://lists.nongnu.org/mailman/listinfo/adonthell-devel