Well, if you are interested in navmesh generation, take a look here:
I've seen his site before...and that's where I found JPS. Is this something that's good for dynamic environments that can change frequently?
Well, if you are interested in navmesh generation, take a look here:
I've seen his site before...and that's where I found JPS. Is this something that's good for dynamic environments that can change frequently?
JPS in a grid yes, grid implementations are the easier and fastest updatable struct you can use for changing envirnoment as all you need to do is mark the point as open or closed (and recalculate the path, but you would need to do that with pretty much any representation).
That being said, notice that grid implementations are likely be slower than navmeshs and consume much more memory.
I made a comparassion not long ago of a small A* study I made, you can see how much faster the JPS is: http://www.gamedev.net/topic/651968-binary-heap-vs-list-a-my-humble-performance-comparison-updated-with-jps/
Ok I'm going to say a little more on my implementation of my game so people know how things are running under the hood:
In THIS case, I'm looking at how this scales, and if I need to generate any type of navigational mesh. Obviously the path points I set for the NPC is every block; maybe I can save some memory with spreading out points (JPS may help with this) using an optimized navigation mesh? Terrain data takes up almost 256Mb data in memory, and re-meshing chunks takes a bit of time too. I need to balance time and memory for AI navigation.
What I've seen so far is that I can limit the number of queries an NPC makes based on two things: frame length and number of NPC's. Maybe only navigate 1 zone at a time (or possibly something a little larger, since NPC's are 1x1x2 voxels in size and a zone is 16x16 on it's top face so...maybe 2x2 or 4x4 zones at a time...?) to save processing power. How would this scale, though, to large castle, city walls, etc...? Would the NPC be forced then to follow the side of the wall all the way around...?
Maybe I'll have to play with this some more, and I'm just over-thinking this right now.
I don't think a navmesh is the way to go for terrain that constantly changes, and is already in a grid.
You could try to keep track of entrances/exits to Zones. You can then split your pathing up into a local within a Zone traversal, and a macro zone-to-zone traversal. Granted, I'm not sure how expensive it will be to keep track of entrances/exits to zones for your game, it could be more overhead than it's worth.
I think you have the right idea that it's best to start simple,and optimize only if you need it, as it may turn out your satisfied with the simple solution.
I think you have the right idea that it's best to start simple,and optimize only if you need it, as it may turn out your satisfied with the simple solution.
I think you're right. I'm just going to use A* with JPS and calculate per-frame for NPC's. They'll also have a limit to their search so their path list doesn't get too long :P But 32-64 path-points per NPC should be good for now.
@studentTeacher
It is dangerous to go alone. Take this:
https://github.com/Yonaba/Jumper/blob/master/jumper/search/jps.lua