Re: [Adonthell-devel] Pathfinding in 3rd dimension
On Mon, Aug 6, 2012 at 10:33 PM, Kai Sterker kai.ster...@gmail.com wrote: 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. Did more of the same. Going up stairs also works now, although not perfectly. Much better now. From the little testing I did yesterday, it seemed that the NPC can now reach every goal on the path-test map, with only few exceptions. (One goal would require a jump, which is not implemented yet and in rare cases, the path search would require more iterations than allowed). 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. That was actually so simple that I didn't even consider it. Only when I had the node search visualization in place did I notice what the problem is: to check if the character became stuck, we store the last position on the map at the end of the move and compare that with the position at the end of the next move. The problem is that this position is pixel-based, but movement can be less than a pixel for slow characters or when collisions occur, like when going up the stairs. Changed the code to wait for 5 frames before deciding that a character is stuck and everything is good :-). 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/ Did not look further into that yet. But it might help with those instances where searching the path takes too long with the current approach. Looking at the node search visualization (which is turned off in the code I pushed), one can see that it searches towards the goal first, but when the goal is on a different level, it starts spreading out from the point beneath (or above) the code in a ever growing circle, until it discovers a stair that brings it closer to the level of the goal. With the test map, that only has narrow paths to walk this isn't so much an issue (except when search starts on the ground level), but on actual maps it could be pretty wasteful. 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. That's the next point on my list. That probably means building a better Waste's Edge map first, to test with that. Kai ___ Adonthell-devel mailing list Adonthell-devel@nongnu.org https://lists.nongnu.org/mailman/listinfo/adonthell-devel
Re: [Adonthell-devel] Pathfinding in 3rd dimension
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
Re: [Adonthell-devel] Pathfinding in 3rd dimension
On Monday, July 23, 2012, Kai Sterker wrote: On Mon, Jul 23, 2012 at 10:09 AM, Josh Glover jmg...@gmail.comjavascript:; wrote: You can use it, but worldtest might be the better option for now. Ok, makes sense. How would the adonthell program differ from worldtest? Just by not hard-coding the loading of the player and NPC? --Josh -- Cheers, Josh ___ Adonthell-devel mailing list Adonthell-devel@nongnu.org https://lists.nongnu.org/mailman/listinfo/adonthell-devel
Re: [Adonthell-devel] Pathfinding in 3rd dimension
On Mon, Jul 23, 2012 at 10:24 AM, Josh Glover jmg...@gmail.com wrote: Ok, makes sense. How would the adonthell program differ from worldtest? Just by not hard-coding the loading of the player and NPC? I thought a bit about the possible options we have and I see two ways how it could work in principle. The givens are that we have a data directoy that can contain a number of games compatible with the engine. We can either have a single program that can run each game (a global engine executable, like v0.3) or we could allow/require a custom executable specific to each game. In the first case, we'd have the code as part of the engine package (much like worldtest), in latter case it would live in the game package instead (snd a lot of code might have to be duplicated for each game.) In either case, the main loop should be kept inside the engine. Best place for that would be the main package, as that is the one module that has access to all other modules (and inside the adonthell::app class also knows which modules are actually initialized/used). For the main program, this leaves the task of initialization (of course without any hardcoded loading) and a call to a game-specific Python script that can do game-specific setup and will at one point have to start the main loop, at which point control remains within the engine, until the player exits the game. The idea behind the game-specifc init script is also that it sets up global key listeners (to show in-game menus for example) and it needs to have access to adonthell::app to start and stop the main loop. It also has access to any other part of the engine, of course. Kai ___ Adonthell-devel mailing list Adonthell-devel@nongnu.org https://lists.nongnu.org/mailman/listinfo/adonthell-devel
Re: [Adonthell-devel] Pathfinding in 3rd dimension
On Monday, July 23, 2012, Kai Sterker wrote: On Mon, Jul 23, 2012 at 1:37 PM, Josh Glover jmg...@gmail.comjavascript:; wrote: I like the idea of a global executable. Yeah, it's probably the better solution. There's still room for customization in the Python script that gets called. Cool! I'll start working on this, though progress will be slow. Heading off to Germany on Thursday for 10 days! :) --Josh -- Cheers, Josh ___ Adonthell-devel mailing list Adonthell-devel@nongnu.org https://lists.nongnu.org/mailman/listinfo/adonthell-devel
Re: [Adonthell-devel] Pathfinding in 3rd dimension
On Sun, Jul 8, 2012 at 4:34 PM, Kai Sterker kai.ster...@gmail.com wrote: Committed my first changes to the pathfinding code. It's basically some code cleanup, better test and a few small improvements to get it working with the test map. To see stuff in action, run ./path_test -g ../../adonthell/test/ path Press 'p' to assign a new goal to the NPC (out of a list of three). You should see the path drawn on top of everything and hopefully the NPC will reach the goal. Added a real z-coordinate to the pathfinding, and that alone allows a character to find its way down to a lower level. Up does not work yet, as the collision check cannot distinguish between a stair and other blocking objects. There's another problem, however, that needs to be solved first. Since a path can now be found on different levels, the number of iterations allowed to calculate the path is too small. Simply increasing it doesn't seem to be a good idea either. One way to further tweak the result is finding a proper heuristic for the remaining distance to the goal for a given point. The most likely candidates should have the smallest distance, as those are checked first. This worked well on a plane, but when the final path might go up and down and back and forth it's not so simple any more. Ideas certainly welcome. I found one instance where the NPC will get stuck for no obvious reason. Not sure what happens there, haven't debugged yet. Fixed. It's also possible for the player to get stuck under the higher level paths. Levels are exactly 80px above each other and the character is 80px tall. There seems to be certain positions where the collision detection will report a collision, even though things should just fit. Haven't debugged that either. Sort of fixed, but not sure if this is the right thing to do. See https://github.com/ksterker/adonthell/commit/14cc8a407b630046cb4a1f9d7bc9bf2b376d7879 Kai ___ Adonthell-devel mailing list Adonthell-devel@nongnu.org https://lists.nongnu.org/mailman/listinfo/adonthell-devel
[Adonthell-devel] Pathfinding in 3rd dimension
Y'all, having finally warmed up, I'll be looking into one of the remaining issues needed for WE: making pathfinding aware of the 3rd dimension. So far it only works for ground level pathing, but Redwyne Inn will have cellar, first and second floor at least, with NPCs walking around on either (and sometimes between). So I would cut the task into 3 phases, hoping to complete at least the first two. 1. Pathfinding on levels other than 0. Simple. Introduce a z-coordinate other than 0 into the pathfinding system, so characters can walk around on their respective level. 2. Level changing using stairs/slopes. Not quite so simple any more. Need to figure out where levels can be safely changed by walking up/down stairs or slopes. Am not even sure how to best go about this, but preferably it should work without having to explicitly point out to the pathfinder what is a stair and what isn't. 3. Jumping/climbing/falling Probably quite hard. Maybe could be divided even further. Jumping across gaps, jumping up to a higher level. Dropping down to a lower level. The few thoughts I had about this is that jumping should generally have (much) higher costs, to encourage NPCs to use bridges, stairs and natural slopes instead of cutting straight through difficult terrain. Also would suggest to make the grid used for pathfinding larger in Z-space as it is on the ground. At least as large as a character can jump, which is about 40px - 50px. The current pathfinding code already checks for holes and obstacles. This seems to be a good place to try and see whether a jump/climb/drop would work there. This might cover actually finding a path that includes jumping/climbing/falling, but more work needs to be done when finally executing that path. I guess during the pathfinding stage, special commands could be stored in those nodes where a jump is required. But I guess we'd also need checks if we're still on the correct path or if the jump/fall took us somewhere where we didn't expect to end up. In that case, we'd have to update or recalculate the path to our goal. Comments welcome. As today is my last day off, things will go more slowly from now on. But I should find time on the weekend at least. Kai ___ Adonthell-devel mailing list Adonthell-devel@nongnu.org https://lists.nongnu.org/mailman/listinfo/adonthell-devel
