Finding Jump Conncetions for a Navigation Mesh
Members - Reputation: 106
Posted 24 January 2012 - 07:25 AM
I'm interested in information about how to find jump connections between nodes of a navigation mesh and how to store them.
To find jump connection does not mean to test for free jump space, in my opinion it is more about, where should I look for possible jump connections. For example if there is a box on a plane so there are at least 5 nodes in the navigation mesh and if I just concentrate at one node from the plane and the node from the top of the box, there are jumps from the edges of the plane node and from the center of this node to the top of the box. Is it usefull to just look for jumps from edges of nodes to edges of other nodes or what are useful restrictions to look for jump connections?
One jump can be described as a parabel, which is defined by a strength and an angle. Is there a way to describe several jumps form a line to another line, if it is usefull to look for jump connections just between edges of the navigation mesh nodes?
I tried hard to find any solid papers or anything addressing this topic. I would really appreciate any reference to good resources on that topic, because i feel like i am missing something (like totally missing the magic search keyword )
Crossbones+ - Reputation: 4132
Posted 13 February 2012 - 11:54 PM
finally, after the nodes have been mapped with jumping, you can assign "jump paths" to a higher value in the heuristic for determing pathing, so that if it can walk between the nodes, objects won't keep jumping between nodes. and then you can do normal pathing techniques, and simply approach the "jump paths" as requiring a diffrent action to get between nodes.
the draw back to this method is a higher memory cost,(although the second pass could be done at run-time, it'd defiantly benefit far more to do it at initialization time.), and it would be harder to coordinate multiple agents with several path maps in use.
anyway, that's my two cents on the subject
Members - Reputation: 2027
Posted 14 February 2012 - 09:11 AM
Members - Reputation: 106
Posted 06 April 2012 - 06:15 AM
Thank you for your feedback!
I think you are right about the two passes, the jump connection calculation should be done after the navigation-mesh/waypoint-graph generation, because it greatly benefits from the knowledge where a character is even able to move to.
The best i could find on practical implementation is what Mikko Mononen did for Killzone 3. He postet on his blog about it (where he also released the source code) and talked about his implementation at the Paris Game/AI Conference 2011. The Slides are available, but without the speech they are just hints about what he talked, i would love to hear that speech, probably very helpful for me.
Mikko's blog entry with source code:
Yeah, recast is amazing, already found it and the jump code from mikko. But thx anyways, recast totally deserves infinite google ranking points ;)