Mesh Maps

Mesh file format .mesh

Stores a complete MCDT of a navigation mesh, with a distinction between a traversable face pathfinding can go over and non-traversable.

The file format is stored first as a list of 1-index vertices coordinates, followed by a list of n-edge 1-index faces. Items are assigned index numbeers based on their ordering, thus the first vertex listed is id-1, second id-2, ect.

The coordinate system has the x-axis increasing towards the right, and the y-axis increasing upwards.

The format is provided below, elements in [] are variables, // are comments

mesh
3
[vertices-n:int] [faces-n:int]
// foreach [vertices-n] lines: define vertex-i
[vertex-i-x:float] [vertex-i-y:float]
// foreach [faces-n] lines: define face-i
[face-i-trav:bool] [face-i-edges:int] [face-i-vertex-id:int] * [face-i-edges:int]
    [face-i-neighbour-id:int] * [face-i-edges:int]

We first describe the number of vertices [vertices-n] and number of faces [faces-n] in the mesh.

The next [vertices-n] lines describe each vertices x and y coordinate as floats, one per line. These are 1-indexed based on order.

The next [faces-n] lines describe all faces of the mesh, one per line.
First parameter [face-i-trav] is a boolean detailing if face is traversable (1) or non-traversable (0).
The next parameter [face-i-edges] details the number of edges and vertices each face has.
The next [face-i-edges] parameters detail the vertices by vertex-id in counter-clockwise order.
The next [face-i-edges] parameters detail connection status with the neighbouring faces that share the same two vertices. The jth parameter details neighbouring face to the edge comprised of the j-1th and jth vertices of the face. The connection status is express as an integer k with 3 considerations:

1. Positive: can traverse over the edge to neighbouring face-id k
2. Negative: cannot traverse over the edge to neighbouring face-id -k
3. Zero: Has no neighbouring face, only found on the edge of the mesh.

Example with comments:

mesh
3
5 4  // 5 vertices 4 faces
0 0   // vertex 1
0 10  // vertex 2
10 10 // vertex 3
10 0  // vertex 4
5 5   // vertex 5
0 3   4 1 5   -4 0 -2 // face 1, non-traversable, constrained along edge 5-4 and 1-5
1 3   1 2 5   -1 0 3  // face 2, traversable, constrained along edge 5-1
1 3   2 3 5   3 0 4   // face 3, traversable, both edges are non-constrained
1 3   3 4 5   3 0 -1  // face 4, traversable, constrained along edge 4-5

The Iron Harvest Benchmarks

Iron Harvest

Home of the Iron Harvest benchmarks. Using data from Iron Harvest, a recent real-time strategy game, we provide 35 distinct maps and 70,000 associated problem instances. Each map has three different representations: navigation mesh, obstacle map and grid. There are 2,000 co-feasible instances per map which allow comparisons across the different representations. We describe the benchmark, our instance generation approach and provide experimental results for some currently leading grid-based and mesh-based path planners.