java
/
jMonkeyEngine-wiki
mirror da https://github.com/jMonkeyEngine/wiki.git


			
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205
							<!DOCTYPE html><html lang="en"><head><meta charset="UTF-8"><!--[if IE]><meta http-equiv="X-UA-Compatible" content="IE=edge"><![endif]--><meta name="viewport" content="width=device-width, initial-scale=1.0"><meta name="generator" content="Asciidoctor 1.5.4"><title>Recast Navigation for JME</title><link rel="stylesheet" href="./asciidoctor.css">
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/4.5.0/css/font-awesome.min.css">
<link rel="stylesheet" href="./coderay-asciidoctor.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/docsearch.js/2/docsearch.min.css"><link rel="stylesheet" href="/home/travis/build/jMonkeyEngine/wiki/build/asciidoc/html5/jme3/advanced/twemoji-awesome.css"></head><body class="article toc2 toc-left"><div id="header"><div id="toolbar"><a href="https://github.com/jMonkeyEngine/wiki/edit/master/src/docs/asciidoc/jme3/advanced/recast.adoc"><i class="fa fa-pencil-square" aria-hidden="true"></i></a><a href="https://github.com/jMonkeyEngine/wiki/new/master/src/docs/asciidoc/jme3/advanced/"><i class="fa fa-plus-square" aria-hidden="true"></i></a><input dir="auto" style="position: relative; vertical-align: top;" spellcheck="false" autocomplete="off" class="searchbox__input aa-input" id="doc-search" name="search" placeholder="Search in the doc" required="required" type="search"></div><h1>Recast Navigation for JME</h1><div class="details"><span class="author" id="author"></span><br><span id="revnumber">version ,</span> <span id="revdate">2016/03/17 20:48</span></div><div id="toc" class="toc2"><div id="toctitle">Table of Contents</div><ul class="sectlevel1"><li><a href="#what-is-recast-navigation">What is Recast Navigation</a><ul class="sectlevel2"><li><a href="#recast">Recast</a></li><li><a href="#detour">Detour</a></li></ul></li><li><a href="#jnavigation">jNavigation</a></li><li><a href="#example">Example</a></li><li><a href="#how-to-get-jnavigation">How to get jNavigation</a><ul class="sectlevel2"><li><a href="#plugin">Plugin</a></li><li><a href="#developmental-project">Developmental project</a></li><li><a href="#questions-suggestions">Questions &amp; Suggestions</a></li><li><a href="#source">Source</a></li></ul></li></ul></div></div><div id="content"><div class="sect2"><h3 id="what-is-recast-navigation">What is Recast Navigation</h3><div class="paragraph"><p>Recast Navigation is C++ library for path-finding in 3D, continuous space. Recast has two big modules:</p></div>
<div class="olist arabic"><ol class="arabic"><li><p>Recast</p></li><li><p>Detour</p></li></ol></div>
<div class="sect2"><h3 id="recast">Recast</h3><div class="paragraph"><p>Recast is state of the art navigation mesh construction tool set for games.</p></div>
<div class="ulist"><ul><li><p>It is automatic, which means that you can throw any level geometry at it and you will get robust mesh out</p></li><li><p>It is fast which means swift turnaround times for level designers</p></li><li><p>It is open source so it comes with full source and you can customize it to your heart&#8217;s content.</p></li></ul></div></div>
<div class="sect2"><h3 id="detour">Detour</h3><div class="paragraph"><p>Recast is accompanied with Detour, path-finding and spatial reasoning toolkit. You can use any navigation mesh with Detour, but of course the data generated with Recast fits perfectly.</p></div>
<div class="paragraph"><p>Detour offers simple static navigation mesh which is suitable for many simple cases, as well as tiled navigation mesh which allows you to plug in and out pieces of the mesh. The tiled mesh allows you to create systems where you stream new navigation data in and out as the player progresses the level, or you may regenerate tiles as the world changes.</p></div></div></div>
<div class="sect1"><h2 id="jnavigation">jNavigation</h2><div class="sectionbody"><div class="paragraph"><p>jNavigation is port Java library for <a href="https://github.com/memononen/recastnavigation">Recast navigation</a>. jNavigation is the project in progress, and currently it enables building <a href="http://en.wikipedia.org/wiki/Navigation_mesh">Navigation meshes</a> and path-finding for one agent (bot).</p></div></div></div>
<div class="sect1"><h2 id="example">Example</h2><div class="sectionbody"><div class="paragraph"><p>In next code is described how the user should build navigation mesh, and query for it.</p></div>
<div class="listingblock"><div class="content"><pre class="CodeRay highlight"><code data-lang="java"><span class="comment">// Step 1. Initialize build config.</span>
Config config = <span class="keyword">new</span> Config();

Mesh mesh = ((Geometry) scene.getChild(<span class="string"><span class="delimiter">&quot;</span><span class="content">terrain</span><span class="delimiter">&quot;</span></span>)).getMesh();

Vector3f minBounds = RecastBuilder.calculateMinBounds(mesh);
Vector3f maxBounds = RecastBuilder.calculateMaxBounds(mesh);

config.setMaxBounds(maxBounds);
config.setMinBounds(minBounds);
config.setCellSize(<span class="float">0.3f</span>);
config.setCellHeight(<span class="float">0.2f</span>);
config.setWalkableSlopeAngle(<span class="integer">45</span>);
config.setWalkableClimb(<span class="integer">1</span>);
config.setWalkableHeight(<span class="integer">2</span>);
config.setWalkableRadius(<span class="integer">2</span>);
config.setMinRegionArea(<span class="integer">8</span>);
config.setMergeRegionArea(<span class="integer">20</span>);
config.setBorderSize(<span class="integer">20</span>);
config.setMaxEdgeLength(<span class="integer">12</span>);
config.setMaxVerticesPerPoly(<span class="integer">6</span>);
config.setDetailSampleMaxError(<span class="float">1f</span>);
config.setDetailSampleDistance(<span class="integer">6</span>);

RecastBuilder.calculateGridWidth(config);
RecastBuilder.calculatesGridHeight(config);

<span class="comment">// Step 2. Rasterize input polygon soup.</span>

<span class="comment">//context is needed for logging that is not yet fully supported in native library.</span>
<span class="comment">//It must NOT be null.</span>
<span class="predefined-type">Context</span> context = <span class="keyword">new</span> <span class="predefined-type">Context</span>();

<span class="comment">// Allocate voxel heightfield where we rasterize our input data to.</span>
Heightfield heightfield = <span class="keyword">new</span> Heightfield();
<span class="keyword">if</span> (!RecastBuilder.createHeightfield(context, heightfield, config)) {
    <span class="predefined-type">System</span>.out.println(<span class="string"><span class="delimiter">&quot;</span><span class="content">Could not create solid heightfield</span><span class="delimiter">&quot;</span></span>);
    <span class="keyword">return</span>;
}

<span class="comment">// Allocate array that can hold triangle area types.</span>

<span class="comment">// In Recast terminology, triangles are what indices in jME is. I left this,</span>

<span class="comment">// Find triangles which are walkable based on their slope and rasterize them.</span>
<span class="type">char</span><span class="type">[]</span> areas = RecastBuilder.markWalkableTriangles(context, config.getWalkableSlopeAngle(), mesh);
RecastBuilder.rasterizeTriangles(context, mesh, areas, heightfield, <span class="integer">20</span>);


<span class="comment">// Step 3. Filter walkables surfaces.</span>
<span class="comment">// Once all geometry is rasterized, we do initial pass of filtering to</span>
<span class="comment">// remove unwanted overhangs caused by the conservative rasterization</span>
<span class="comment">// as well as filter spans where the character cannot possibly stand.</span>
RecastBuilder.filterLowHangingWalkableObstacles(context, config.getWalkableClimb(), heightfield);
RecastBuilder.filterLedgeSpans(context, config, heightfield);
RecastBuilder.filterWalkableLowHeightSpans(context, config.getWalkableHeight(), heightfield);


<span class="comment">// Step 4. Partition walkable surface to simple regions.</span>
<span class="comment">// Compact the heightfield so that it is faster to handle from now on.</span>
<span class="comment">// This will result more cache coherent data as well as the neighbours</span>
<span class="comment">// between walkable cells will be calculated.</span>
CompactHeightfield compactHeightfield = <span class="keyword">new</span> CompactHeightfield();

<span class="keyword">if</span> (!RecastBuilder.buildCompactHeightfield(context, config, heightfield, compactHeightfield)) {
    <span class="predefined-type">System</span>.out.println(<span class="string"><span class="delimiter">&quot;</span><span class="content">Could not build compact data</span><span class="delimiter">&quot;</span></span>);
    <span class="keyword">return</span>;
}

<span class="keyword">if</span> (!RecastBuilder.erodeWalkableArea(context, config.getWalkableRadius(), compactHeightfield)) {
    <span class="predefined-type">System</span>.out.println(<span class="string"><span class="delimiter">&quot;</span><span class="content">Could not erode</span><span class="delimiter">&quot;</span></span>);
    <span class="keyword">return</span>;
}

<span class="comment">// Partition the heightfield so that we can use simple algorithm later to triangulate the walkable areas.</span>
<span class="comment">// There are 3 martitioning methods, each with some pros and cons:</span>
<span class="comment">// 1) Watershed partitioning</span>
<span class="comment">//   - the classic Recast partitioning</span>
<span class="comment">//   - creates the nicest tessellation</span>
<span class="comment">//   - usually slowest</span>
<span class="comment">//   - partitions the heightfield into nice regions without holes or overlaps</span>
<span class="comment">//   - the are some corner cases where this method creates produces holes and overlaps</span>
<span class="comment">//      - holes may appear when a small obstacles is close to large open area (triangulation can handle this)</span>
<span class="comment">//      - overlaps may occur if you have narrow spiral corridors (i.e stairs), this make triangulation to fail</span>
<span class="comment">//   * generally the best choice if you precompute the nacmesh, use this if you have large open areas</span>
<span class="comment">// 2) Monotone partioning</span>
<span class="comment">//   - fastest</span>
<span class="comment">//   - partitions the heightfield into regions without holes and overlaps (guaranteed)</span>
<span class="comment">//   - creates long thin polygons, which sometimes causes paths with detours</span>
<span class="comment">//   * use this if you want fast navmesh generation</span>
<span class="predefined-type">String</span> partitionType = <span class="string"><span class="delimiter">&quot;</span><span class="content">Sample partition watershed</span><span class="delimiter">&quot;</span></span>;

<span class="keyword">if</span> (partitionType.equals(<span class="string"><span class="delimiter">&quot;</span><span class="content">Sample partition watershed</span><span class="delimiter">&quot;</span></span>)) {
    <span class="keyword">if</span> (!RecastBuilder.buildDistanceField(context, compactHeightfield)) {
        <span class="predefined-type">System</span>.out.println(<span class="string"><span class="delimiter">&quot;</span><span class="content">Could not build distance field</span><span class="delimiter">&quot;</span></span>);
        <span class="keyword">return</span>;
    }
    <span class="keyword">if</span> (!RecastBuilder.buildRegions(context, compactHeightfield, config)) {
        <span class="predefined-type">System</span>.out.println(<span class="string"><span class="delimiter">&quot;</span><span class="content">Could not build watershed regions</span><span class="delimiter">&quot;</span></span>);
        <span class="keyword">return</span>;
    }
}

<span class="keyword">if</span> (partitionType.equals(<span class="string"><span class="delimiter">&quot;</span><span class="content">Sample partition monotone</span><span class="delimiter">&quot;</span></span>)) {
    <span class="keyword">if</span> (!RecastBuilder.buildRegionsMonotone(context, compactHeightfield, config)) {
        <span class="predefined-type">System</span>.out.println(<span class="string"><span class="delimiter">&quot;</span><span class="content">Could not build monotone regions</span><span class="delimiter">&quot;</span></span>);
        <span class="keyword">return</span>;
    }
}

<span class="comment">// Step 5. Trace and simplify region contours.</span>
<span class="comment">// Create contours.</span>
ContourSet contourSet = <span class="keyword">new</span> ContourSet();

<span class="keyword">if</span> (!RecastBuilder.buildContours(context, compactHeightfield, <span class="float">2f</span>, config.getMaxEdgeLength(), contourSet)) {
    <span class="predefined-type">System</span>.out.println(<span class="string"><span class="delimiter">&quot;</span><span class="content">Could not create contours</span><span class="delimiter">&quot;</span></span>);
    <span class="keyword">return</span>;
}

<span class="comment">// Step 6. Build polygons mesh from contours.</span>
<span class="comment">// Build polygon navmesh from the contours.</span>
PolyMesh polyMesh = <span class="keyword">new</span> PolyMesh();

<span class="keyword">if</span> (!RecastBuilder.buildPolyMesh(context, contourSet, config.getMaxVertsPerPoly(), polyMesh)) {
    <span class="predefined-type">System</span>.out.println(<span class="string"><span class="delimiter">&quot;</span><span class="content">Could not triangulate contours</span><span class="delimiter">&quot;</span></span>);
    <span class="keyword">return</span>;
}

<span class="comment">// Step 7. Create detail mesh which allows to access approximate height on each polygon.</span>
PolyMeshDetail polyMeshDetail = <span class="keyword">new</span> PolyMeshDetail();

<span class="keyword">if</span> (!RecastBuilder.buildPolyMeshDetail(context, polyMesh, compactHeightfield, config, polyMeshDetail)) {
    <span class="predefined-type">System</span>.out.println(<span class="string"><span class="delimiter">&quot;</span><span class="content">Could not build detail mesh.</span><span class="delimiter">&quot;</span></span>);
    <span class="keyword">return</span>;
}

<span class="comment">// (Optional) Step 8. Create Detour data from Recast poly mesh.</span>
<span class="comment">// The GUI may allow more max points per polygon than Detour can handle.</span>
<span class="comment">// Only build the detour navmesh if we do not exceed the limit.</span>
<span class="keyword">if</span> (config.getMaxVertsPerPoly() &gt; DetourBuilder.VERTS_PER_POLYGON()) {
    <span class="keyword">return</span>;
}
NavMeshCreateParams createParams = <span class="keyword">new</span> NavMeshCreateParams();
createParams.getData(polyMesh);
createParams.getData(polyMeshDetail);
<span class="comment">//setting optional off-mesh connections (in my example there are none)</span>
createParams.getData(config);
createParams.setBuildBvTree(<span class="predefined-constant">true</span>);

<span class="type">char</span><span class="type">[]</span> navData = DetourBuilder.createNavMeshData(createParams);

<span class="keyword">if</span> (navData == <span class="predefined-constant">null</span>) {
    <span class="predefined-type">System</span>.out.println(<span class="string"><span class="delimiter">&quot;</span><span class="content">Could not build Detour navmesh.</span><span class="delimiter">&quot;</span></span>);
    <span class="keyword">return</span>;
}

NavMesh navMesh = <span class="keyword">new</span> NavMesh();

<span class="keyword">if</span> (!navMesh.isAllocationSuccessful()) {
    <span class="predefined-type">System</span>.out.println(<span class="string"><span class="delimiter">&quot;</span><span class="content">Could not create Detour navmesh</span><span class="delimiter">&quot;</span></span>);
    <span class="keyword">return</span>;
}

Status status;
status = navMesh.init(navData, TileFlags.DT_TILE_FREE_DATA.value());
<span class="keyword">if</span> (status.isFailed()) {
    <span class="predefined-type">System</span>.out.println(<span class="string"><span class="delimiter">&quot;</span><span class="content">Could not init Detour navmesh</span><span class="delimiter">&quot;</span></span>);
    <span class="keyword">return</span>;
}

NavMeshQuery query = <span class="keyword">new</span> NavMeshQuery();
status = query.init(navMesh, <span class="integer">2048</span>);
<span class="keyword">if</span> (status.isFailed()) {
    <span class="predefined-type">System</span>.out.println(<span class="string"><span class="delimiter">&quot;</span><span class="content">Could not init Detour navmesh query</span><span class="delimiter">&quot;</span></span>);
    <span class="keyword">return</span>;
}</code></pre></div></div>
<div class="paragraph"><p>After this (if everything is successful) you can use methods in <code>query</code> that was created for path-finding purposes.</p></div></div></div>
<div class="sect2"><h3 id="how-to-get-jnavigation">How to get jNavigation</h3><div class="paragraph"><p>There is 2 ways to get jNavigation:</p></div>
<div class="ulist"><ul><li><p>as plugin form</p></li><li><p>as developmental project</p></li></ul></div>
<div class="sect2"><h3 id="plugin">Plugin</h3><div class="paragraph"><p>You can download “stable version from <a href="https://github.com/QuietOne/jNavigationPlugin/tree/master">repository</a></p></div></div>
<div class="sect2"><h3 id="developmental-project">Developmental project</h3><div class="paragraph"><p>Instructions for downloading and setting it up:</p></div>
<div class="ulist"><ul><li><p>Download C++ wrapper from <a href="https://github.com/QuietOne/jNavigation-native">jNavigationNative repository</a></p></li><li><p>Build downloaded project with C++ compiler</p></li><li><p>Download java library from <a href="https://github.com/QuietOne/jNavigation">jNavigation repository</a></p></li><li><p>In Java project in class <code>com.jme3.ai.navigation.utils.RecastJNI.java</code> change <abbr title="Uniform Resource Locator">URL</abbr> to where your build of C++ project is.</p></li></ul></div>
<div class="listingblock"><div class="content"><pre class="CodeRay highlight"><code data-lang="java"><span class="directive">static</span> {
    <span class="comment">// the URL that needs to be changed</span>
    <span class="predefined-type">System</span>.load(<span class="string"><span class="delimiter">&quot;</span><span class="content">.../jNavigationNative.dll</span><span class="delimiter">&quot;</span></span>);
}</code></pre></div></div>
<div class="paragraph"><p>If there is problem with building C++ project see <a href="../../jme3/advanced/building_recast.html">link</a>.</p></div></div>
<div class="sect2"><h3 id="questions-suggestions">Questions &amp; Suggestions</h3><div class="ulist"><ul><li><p>For suggestion and/or question on jNavigation post on <a href="http://hub.jmonkeyengine.org/forum/board/development/summer-of-code/">forum</a></p></li><li><p>For question on Recast (C++ library) ask on <a href="https://groups.google.com/forum/#!forum/recastnavigation">Google groups</a></p></li></ul></div></div>
<div class="sect2"><h3 id="source">Source</h3><div class="ulist"><ul><li><p><a href="https://github.com/QuietOne/jNavigationPlugin/tree/master">jNavigation plugin repository</a></p></li><li><p><a href="https://github.com/QuietOne/jNavigation">Developmental jNavigation repository</a></p></li><li><p><a href="https://github.com/QuietOne/jNavigation-native">Developmental jNavigationNative repository</a></p></li></ul></div>
<div class="sect3"><h4 id="useful-links">Useful links</h4><div class="ulist"><ul><li><p><a href="../../jme3/advanced/building_recast.html">How to build the native recast bindings</a></p></li><li><p><a href="http://www.critterai.org/projects/nmgen_study/">Study: Navigation Mesh Generation</a></p></li><li><p><a href="http://www.stevefsp.org/projects/rcndoc/prod/index.html">Documentation of C++ Recast library</a> It can be useful for tracing bugs.</p></li></ul></div></div></div></div></div><div id="footer"><div id="footer-text">Version <br>Last updated 2019-12-20 23:30:51 +00:00</div></div><script type="text/javascript" src="https://cdn.jsdelivr.net/docsearch.js/2/docsearch.min.js"></script><script>docsearch({
  apiKey: 'a736b6d93de805e26ec2f49b55013fbd',
  indexName: 'jmonkeyengine',
  inputSelector: '#doc-search',
  debug: false // Set debug to true if you want to inspect the dropdown
});</script></body></html>