Recast Navigation hack for Long-Range Off-Mesh Connections

Detour_HACK_LongRangeOffMeshConnections.md

This is a drop-in hack for enabling long-range offmesh connections in an application using the unmodified Recast Navigation library. This avoids the need to maintain a fork of the library if your game features portals, trains, non-euclidean geometry or some such.

It works by injecting a private method into dtNavMesh, and relies on implementation details of the Detour library which may change in the future. However, the implementation details in question have been stable for three years so this is unlikely to happen any time soon.

The code is based on PR #645 by niji-k.

WARNING

This manual linking mechanism is brittle. If you are loading and unloading navmesh tiles at runtime you must take care to 'unconnect' any long-range links you create, or you may encounter null-pointer crashes when querying the navmesh.

Instructions

Any source files responsible for building the navmesh should #include "Detour_HACK_OffMeshLinks.h" before including DetourNavMesh.h. The easist way to do this is to include the hack at the top of the C++ files concerned.

After building any pair of navtiles sharing a long-range offmesh connection, call dtNavMesh::connectManualOffMeshLinks.

• This is unnecessary, but harmless, if the tiles are adjacent.
• You may convert dtTileRef to dtMeshTile* pointers by calling dtNavMesh::getTileByRef.
• It is usually necessary to call this function a second time with the order of the tiles swapped.
• As usual, make sure to create a zero-cost or low-cost area type if these long-range connections represent portals or high-speed transit.

Before unloading a navtile, go through any long-range neighbors and call dtNavMesh::unconnectManualOffMeshLinks.

• The first argument should be the neighboring tile and the second should be the one about to get unloaded.
• Don't do this if the neighboring tile is already unloaded.

Detour_HACK_OffMeshLinks.cpp

#include "Detour_HACK_OffMeshLinks.h"

/*
	Based on Recast Navigation PR #645 by niji-k.
	https://github.com/recastnavigation/recastnavigation/pull/645
*/

#include <Recast.h>
#include <DetourNavMeshBuilder.h>
#include <DetourNavMesh.h>
#include <DetourCommon.h>

#include <cmath>

// This duplicates the allocLink function in DetourNavMesh.cpp
#define allocLink copy_of_allocLink
inline static unsigned int copy_of_allocLink(dtMeshTile* tile)
{
	if (tile->linksFreeList == DT_NULL_LINK)
		return DT_NULL_LINK;
	unsigned int link = tile->linksFreeList;
	tile->linksFreeList = tile->links[link].next;
	return link;
}

void dtNavMesh::connectManualOffMeshLinks(const dtMeshTile * tile, const dtMeshTile * target)
{
	if (!tile || !target) return;

	// Do not link OMCs if tiles are adjacent; dtNavMesh does that automatically.
	if (std::abs(tile->header->x-target->header->x) <= 1 &&
		std::abs(tile->header->y-target->header->y) <= 1)
		return;

	/*
		This code is closely based on dtNavMesh::connectExtOffMeshLinks, except:
			- Checks for offmesh connection 'side' are skipped.
			- The dtLink::side of the resulting links are set to 0xFF.
			- We must const cast dtMeshTile to allocate links.
	*/
	for (int i = 0; i < target->header->offMeshConCount; ++i)
	{
		dtOffMeshConnection* targetCon = &target->offMeshCons[i];

		dtPoly* targetPoly = &target->polys[targetCon->poly];
		// Skip off-mesh connections which start location could not be connected at all.
		if (targetPoly->firstLink == DT_NULL_LINK)
			continue;

		const float halfExtents[3] = { targetCon->rad, target->header->walkableClimb, targetCon->rad };

		// Find polygon to connect to.
		const float* p = &targetCon->pos[3];
		float nearestPt[3];
		dtPolyRef ref = findNearestPolyInTile(tile, p, halfExtents, nearestPt);
		if (!ref)
			continue;
		// findNearestPoly may return too optimistic results, further check to make sure. 
		if (dtSqr(nearestPt[0] - p[0]) + dtSqr(nearestPt[2] - p[2]) > dtSqr(targetCon->rad))
			continue;
		// Make sure the location is on current mesh.
		float* v = &target->verts[targetPoly->verts[1] * 3];
		dtVcopy(v, nearestPt);

		// Link off-mesh connection to target poly.
		unsigned int idx = allocLink((dtMeshTile *)target);
		if (idx != DT_NULL_LINK)
		{
			dtLink* link = &target->links[idx];
			link->ref = ref;
			link->edge = (unsigned char)1;
			link->side = 0xff;
			link->bmin = link->bmax = 0;
			// Add to linked list.
			link->next = targetPoly->firstLink;
			targetPoly->firstLink = idx;
		}

		// Link target poly to off-mesh connection.
		if (targetCon->flags & DT_OFFMESH_CON_BIDIR)
		{
			unsigned int tidx = allocLink((dtMeshTile *)tile);
			if (tidx != DT_NULL_LINK)
			{
				const unsigned short landPolyIdx = (unsigned short)decodePolyIdPoly(ref);
				dtPoly* landPoly = &tile->polys[landPolyIdx];
				dtLink* link = &tile->links[tidx];
				link->ref = getPolyRefBase(target) | (dtPolyRef)(targetCon->poly);
				link->edge = 0xff;
				link->side = (unsigned char)(0xff);
				link->bmin = link->bmax = 0;
				// Add to linked list.
				link->next = landPoly->firstLink;
				landPoly->firstLink = tidx;
			}
		}
	}
}

Detour_HACK_OffMeshLinks.h

#pragma once

/*
	Include this header FIRST in source files where it is needed.

	This macro injects a member function definition into dtNavMesh,
		allowing us to extend it with one new public function.
		connectManualOffMeshLinks should be called on any pair of
		loaded tiles whose tx and/or ty position differ by two or more.
*/
#define connectExtOffMeshLinks(...) \
	/* void */    unimplementedPleaseIgnore(); \
	public:  void connectManualOffMeshLinks(const dtMeshTile * tile, const dtMeshTile * target); \
	inline void unconnectManualOffMeshLinks(const dtMeshTile * tile, const dtMeshTile * target) \
		{unconnectLinks((dtMeshTile*) tile, (dtMeshTile*) target);} \
	private: void connectExtOffMeshLinks(__VA_ARGS__)