ZDoom Pathfinding

Robust navigation mesh pathfinding for ZDoom.

Contents

• Prerequisites
• PK3 Structure
• ZNav API
  • ZLevelHandler
  • ZNavHandler
  • ZNavNode
  • ZNavMesh
  • ZNavAgent

Prerequisites

First, generate nav mesh JSON with zdoom-navmesh-generator.

An example of basic movement is provided, but you will likely need to tailor your movement code to suit your specific needs. The best way to learn is to see how it all works in the provided example file.

PK3 Structure

YOUR_GAME_OR_MOD.PK3/
├── MODELS/       
│   └─ NAV/             #place your navigation meshes in here
│       ├─ map01.json
│       └─ e1m1.json
├── ZSCRIPT/
│   ├─ ZNAV/            #zdoom-pathfinding zscripts here (included)
│   └─ ZJSON/           #ZJSON here (included)
└── MAPINFO.txt         #load event handlers here

In-Depth

Here's how this all works. The nav mesh app generates a 3D model from the TEXTMAP lump. This 3D model is then fed into Recast, which generates a navigation mesh from the model. The nav mesh is stored as a JSON file, which is parsed by ZJSON when the level is loaded.

Agents use the navigation mesh mesh to determine the best way to move towards their target. The navigation mesh is defined by a set of interconnected nodes. Each node is described by a centroid, a list of adjacent nodes, a list of shared borders between nodes ('portals'), and a list of vertices which define the outer borders of the node.

Agents use the A* algorithm to get a list of connected nodes between their position and their desired position. Once a list of nodes is created, agents use a funnel algorithm to get a route, a smooth path from the agent to its intended destination. Agents move towards each point on the route and advance to the next each time they reach one.

Agents have the ability to move to their targets without getting stuck on obstacles. This behavior can be extended to craft more sophisticated AI capable of better problem-solving.

API

ZLevelHandler

A base class for event handlers

ZNavHandler

This class runs when a map is loaded, looks for a navigation mesh in the /MODELS/NAV directory sharing the same name as the current map

ZNavNode

A node is a polygon area defined by a set of vertices, portals and a centroid.

Properties

• groupID Int Index of ZNavGroup to which this node belongs
• Centroid vector3 The mean position of all vertices in the node.
• vertexIDs array<Int> List of indices of vertices used to define the polygon.
• neighborIDs array<Int> List of indices of ZNavNodes sharing edges with this polygon.
• portals array<ZNavPortal> List of ZNavPortals, pairs of vertexIDs which define edges shared by neighboring nodes.

ZNavGroup

A group is a collection of interconnected nodes. It is always possible to move between two nodes so long as they are in the same group.

ZNavMesh

Class containing navigation mesh data, which includes all nodes and groups.

getVertex

Parameters

• vertexID Int Index of vertex.

Returns Vector3 Position of Mesh vertex at index.

FindPath

Parameters

• groupID Int Group of nodes to search for paths.
• startPos Vector3 Start Positions.
• endPos Vector3 Destination.
• route ZNavRoute Reference to instance of ZNavRoute, this countains a list of points which define a path.

Returns boolean Whether or not it could find a path to destination.

ZNavAgent

Base class for pathfinding actors.

A_MoveToEx

Move towards actor goal ( the actor's goal, by default ).

ZNavRoute

An object which contains paths composed of points (Vector3).

get

Parameters

• index Int Get a vertex from list

Returns Vector3 Point from a list of points.

shift

Returns Vector3 Returns the first point in the route and removes it from the route.

pop

Returns Vector3 Returns the last point in the route and removes it from the route.

push

Parameters

• point Vector3 Adds a point to the route.

clear

Remove all points from route

Special Thanks

• Ricardo Luis
• Nash Muhandes