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).
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;
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
|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
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
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)
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.