A navigation mesh is an abstract structure used by pathfinding algorithms to compute shortest path in space. It is often used in video game AI to set objects trajectory. Game Engine such as Unity uses navigation meshes for instance to control non-player characters (NPC’s).

Currently working on crowd simulation, we have been using game engine to model crowd movement within our cities.

This include of course the use of navigation meshes for our pedestrian to walk on.

In this article, we are going to showcase how to produce naviation meshes using `python`

and the Basisregistratie Grootschalige Topografie (BGT) dataset from the Dutch Kadaster, especially the * wegdeel* (road section) table that describes landuses (see below).

## Query BGT

The first step has been to query the BGT dataset. For that, we stored BGT data locally in a PostgreSQL spatial database (to do so an open framework, nlextract, exist).

We first retrieve the relevant ways using geometries and land type.

```
WITH subset AS (
/* Create a subset of the data within the bounding box for further use */
SELECT
bgt_functie,
bgt_fysiekvoorkomen,
relatievehoogteligging,
geometrie_vlak as geom
FROM
bgt.wegdeel a
WHERE
ST_Intersects(a.geometrie_vlak, ST_MakeEnvelope(202463.2722222761, 502554.4648402039, 203467.14590116503, 503221.6040946483,28992)) -- fill in bounding box of the area of interest
AND
bgt_functie IN ('voetpad','voetgangersgebied','voetpad op trap','parkeervlak','overweg') -- <-- Change this to the types you need. You can find all types on: https://imgeo.geostandaarden.nl/def/imgeo-object/wegdeel
AND
relatievehoogteligging = 0
)
```

Then we use this subset and tesselate the terrain geometry to obtain triangles. This way, we get closer to an actual mesh just like navigation meshes.

```
,triangles AS (
SELECT
ST_MakePolygon(ST_ExteriorRing((ST_Dump( --This is a workaround to get polygons instead of a TIN, remove if a TIN is what you want
ST_Tesselate( -- The actual triangulation per polygon
ST_SimplifyVW( -- Simplify to avoid to reduce vertices in corners
ST_CurveToLine(a.geom) -- Change bezier curves (original format in BGT) to geometries
,1)
)
)).geom)) geom
FROM subset a
)
SELECT * FROM triangles;
```

Using `python`

and `Geopandas`

, we can run the previous query:

```
import geopandas as gpd
import psycopg2
# enter your DB connection details
conn = psycopg2.connect(host=host, port='5432',dbname=dbname,user='postgres',password=password)
sql_pede = your_query # the above query
pedestrian = gpd.GeoDataFrame.from_postgis(sql_pede, conn, geom_col='geom' )
pedestrian = pedestrian.explode() #explode geometry collections
pedestrian
```

Output

geom | ||
---|---|---|

0 | 0 | POLYGON ((202661.558 502554.353, 202668.355 50... |

1 | 0 | POLYGON ((202661.558 502554.353, 202664.387 50... |

2 | 0 | POLYGON ((202635.005 503159.084, 202635.379 50... |

3 | 0 | POLYGON ((202635.728 503162.523, 202635.379 50... |

... | ... | ... |

8261 | 0 | POLYGON ((203140.913 502945.655, 203145.984 50... |

8272 | 0 | POLYGON ((203142.266 502945.109, 203145.984 50... |

8273 | 0 | POLYGON ((203142.812 502944.937, 203145.984 50... |

8274 rows × 1 columns

## Generate mesh

In order to be used in a game engine, our mesh coordinates need to be reprojected into a relative coordinates system where the bottom left corner will be considered as the origin. For that, we simply use a translation provided by the `shapely`

library

```
from shapely import affinity
from shapely.geometry import Point
def repro(poly,pivot):
local_poly = affinity.translate(poly, xoff=-pivot.x, yoff=-pivot.y, zoff=0.0)
local_poly = local_poly.simplify(0.01, preserve_topology=False) #to ensure simple and valid geometries
return local_poly
pivot_pnt = Point((202500, 502500)) #set the origin point
pedestrian['geom'] = pedestrian['geom'].apply(lambda x: repro(x,pivot_pnt)) #reproject each geometries
```

The only step left is now to actually produce the navigation mesh into a format recognisable by game engines. We use `trimesh`

, a library for loading and using triangular meshes with an emphasis on watertight surfaces. Full doumentation can be found here.

```
import trimesh
import numpy as np
meshes = []
#for each triangle in the pedestrian table
for triangle in pedestrian.geom:
if not triangle.is_empty: # empty triangle can appears, especially is a simplification has been ran
# The following line creates triangles from a polygon.
# In meshes objects, triangle are represented in term of vertices and faces, the two being linked by IDs
# In the present case, the polygons are already triangles so the vertices will simply repeat the one
# of the polygons. However, we still call that function in order to get faces with a consistent labelling
vertices, faces = trimesh.creation.triangulate_polygon(triangle, engine='earcut')
# Here we had a Z value to our vertices.
vertices = np.column_stack((vertices, np.zeros(len(vertices))))
# Of course if the data were 3D, one could simply use the following:
# vertices = np.array(triangle_3D.exterior)
# The two following line are specific to the Unity Game Engine where
# y and z axes are swaped.
#vertices = vertices.dot([[-1,0,0],[0,1,0],[0,0,1]])
#vertices[:,[1, 2]] = vertices[:,[2, 1]]
# Generate mesh from polygon
mesh = trimesh.Trimesh(vertices=vertices, faces=faces)
meshes.append(mesh)
#Concatenate all meshes to form the final navigation mesh
mesh = trimesh.util.concatenate(meshes)
```

## Export as OBJ file for game engine

Finally, we can ouput some 3D OBJ file using `trimesh`

function like so:

```
obj = trimesh.exchange.obj.export_obj(
mesh,
include_normals=True,
include_color=False,
include_texture=False,
return_texture=False,
write_texture=False,
resolver=None,
digits=8,
)
with open("navmesh.obj", 'w') as file:
file.write(obj)
```

## Final words

Here we have it. A navigation mesh that can be directly used in game engine such as Unity fully generated from open source solutions. The feature is useful for city digital twin and AR apps.