4 replies to this topic

[sam101981]

Hi,

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 )

[sam101981]

Knowing that there actually are no documents on this topic would be just as satisfying for me

Is anybody adequately sure that there is no solid info about automatic jump point calculation out there?

[slicer4ever]

i personally know of no documentations on pathing jumpable objects, but what i'd suggest is to do a two pass system when creating your path map, and pre-calculate the jump point's in the second path for a given jumpable height. then store the map for each object that has x height. so, in the first pass, you'd create a regular navigation nodes, and each node would contain how to transverse to it's surrounding nodes. during the second pass, take each node, and get the maximum distance that jumper can move at full speed, and highest jump. find all the nodes that are within this distance to the center node. from thier, check if the jump would be legal for reaching each node(i.e. find the height of the landing position, and check to make sure it aligns with the arc of the jumper, as well to make sure he wouldn't hit any other nodes while jumping, and make sure to also assign the required forward momentum to achieve such a jump.)

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

[et1337]

Check out Recast. In the editor tool they provide, you can specify different parameters that determine which places are jumpable and whatnot. Here's a quick article I wrote that might be helpful if you choose to go this route.

[sam101981]

@slicer4evr
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:
http://digestingduck...slides-and.html

Slides:
http://www.guerrilla...m/publications/
http://www.guerrilla...ons/PGAIC11.pdf

@et1337
Yeah, recast is amazing, already found it and the jump code from mikko. But thx anyways, recast totally deserves infinite google ranking points ;)