Gridless movement region ranges over navmesh

Highlight reachable areas on navmesh for turn based game based off movement allowance

Potential castable polygons

Project out a sphere with radius representing the available movement distance allowance from current position. All navmesh polygons within this sphere are marked as “potentiallyr reachable”. Note that if the turn-based movement allowance is too great, this algorithm might be too heavy to undertake.

Start projecting movement arcs over potential polygons

For all these navmesh polygons fully visible from current position (ie. all points on polygon reachable via straight line through portal edges), mark them as already “visited”, and do a arc coverage projetion on them with the movement circle directly, from start position to determine to what extent they are traversible. Polygons fully covered by circle are highlighted completely and no further processing is needed.

For all other polygons that aren’t directly reachable , do a shortest path to reach navmesh polygon calculation with initial straight line raycast test along to see if can go through all portals to lead up to that closest polygon edge intersection… else find actual corriddor path through portals leading up to that closest polygon edge intersection via your pathfinding query for your navmesh).

Distance costs for path (whether straight or not..) is a 3D calculation. For a straight line path or segment leading up across a set of non-coplanar polygons through their portals, remember to calculate distance based off the resultant gradient slopes at each junction. (ie. additional “junctions” for each portal intersection is required if the slope changes), thus requiring you to individually add up distance across multiple line segments for different gradients. Likewise, specific navmesh regions with custom distance cost multipliers, would require breaking your line into different segments to calculate the costs accordingly.

Arc coverage projection on navmesh polygons

Form remaining arc by (remaining distance from intersection + distance from last corridoor path junction) clamped by left/right portals’ visiblity frustum (if any) along corridoor towards closest point on target polygon edge originating from last junction. If arc (clamped by any occluding portals) fully covers polygon, then polygon is fully traversible and no further processing is needed. If arc doesn’t touch polygon, then polygon is deemed not reachable.
For any clamps on left/right portals respectively (if found), form remaining arc by (remaining ditance from intersection) only, but not clamped by left/right portals, as if originating the arc from the corners of the portals itself.

Regarding accruacy

Note that using this approach is subjected to the accruacy of the pathfinding query itself and regularity of the navmesh geometry itself, and may not give 100% accruate results if the corridoor used wasn’t the best. However, since the nature of the movement allowance for the turn based game is to mimic that of the actual path provided by the pathfinding query, which uses the same corridoor, (and assuming you are restricted to selecting only a single target location for whatever path (no matter how non-ideal) the game gives you), then the highlighted regions gives the “accruate” matching result for that case.

Regarding practicality

In many cases, using a standard fine grid (eg. at radius of unit) over navmesh surface to determine movement range may still be a better option, and would actually often give better results with regards to graphs due to the “fineness/regularity” of the grid itself. However, this is just an article to present a case where “gridless freeform 3D” is the absolute requirement.