Navigation Mesh
The Navigation Mesh is a graph structure that is used to represent the walkable area. Currently there exist a simple prototype in Windstille that is available from the main menu under Navigation Test.
A Navigation Mesh is a graph and consists of edges and nodes, the file that is used for the Navigation Test can be found at data/navigation.nav, the syntax is like this:
(navigation
(nodes
(node (id 1) (pos 100 200))
(node (id 2) (pos 300 400))
(node (id 3) (pos 444.861 410.437))
(node (id 4) (pos 534.858 436.132))
(node (id 5) (pos 615.372 436.622))
(node (id 6) (pos 681.084 263.793))
(node (id 7) (pos 597.783 288.682))
(node (id 8) (pos 491.216 288.682))
(node (id 9) (pos 421.02 285.146))
(node (id 10) (pos 332.645 268.294))
(node (id 11) (pos 362.944 159.5))
(node (id 12) (pos 436.191 163.735))
(node (id 13) (pos 513.665 163.235))
(node (id 14) (pos 594.374 162.168))
(node (id 15) (pos 132.505 83.9459))
(node (id 16) (pos 193.368 83.9459))
(node (id 17) (pos 161.409 177.94))
(node (id 18) (pos 283.341 177.94))
)
(segments
(segment (node1 1) (node2 2) (properties 0))
(segment (node1 2) (node2 3) (properties 0))
(segment (node1 3) (node2 4) (properties 0))
(segment (node1 4) (node2 5) (properties 0))
(segment (node1 5) (node2 6) (properties 0))
(segment (node1 10) (node2 9) (properties 0))
(segment (node1 9) (node2 8) (properties 0))
(segment (node1 8) (node2 7) (properties 0))
(segment (node1 11) (node2 12) (properties 0))
(segment (node1 12) (node2 13) (properties 0))
(segment (node1 13) (node2 14) (properties 0))
(segment (node1 15) (node2 16) (properties 0))
(segment (node1 17) (node2 18) (properties 0))
)
)
A node is an object that has a position and an id by which it can be identified, in addition it shall have a symbolic name by which scripts can access and manipulate it.
class Node
{
int id; // unique id
string name; // symbolic name
Vector2f pos; // position in the world
};
An segment or edge is an object connecting two nodes. Segments can have properties, which is currently implemented as bitmask.
class Segment
{
Node node1; // node to which the segment is connected
Node node2; // node to which the segment is connected
uint32 properties; // list of properties
};
The SegmentPosition is used to connect to the graph and move around on it.
Functions that can be applied to the navigation mesh include:
- adding/removing nodes
- adding/removing segments
- casting a ray (start_pos, end_pos) and return where it collides with the navigation mesh
- connection something to the graph and let it work
- trigger script function when positions on the graph are passed over