mirror of
https://github.com/orange-cpp/omath.git
synced 2026-02-13 07:03:25 +00:00
Orange
95c0873b8c
Adds documentation for the `omath::ViewAngles` struct, clarifying its purpose, common usage patterns, and the definition of the types of pitch, yaw and roll. Also, adds short explanations of how to use ViewAngles and what tradeoffs exist between using raw float types and strongly typed Angle<> types.
114 lines
3.9 KiB
Markdown
114 lines
3.9 KiB
Markdown
# `omath::pathfinding::NavigationMesh` — Lightweight vertex graph for A*
|
||
|
||
> Header: your project’s `pathfinding/navigation_mesh.hpp`
|
||
> Namespace: `omath::pathfinding`
|
||
> Nodes: `Vector3<float>` (3D points)
|
||
> Storage: adjacency map `unordered_map<Vector3<float>, std::vector<Vector3<float>>>`
|
||
|
||
A minimal navigation mesh represented as a **vertex/edge graph**. Each vertex is a `Vector3<float>` and neighbors are stored in an adjacency list. Designed to pair with `Astar::find_path`.
|
||
|
||
---
|
||
|
||
## API
|
||
|
||
```cpp
|
||
class NavigationMesh final {
|
||
public:
|
||
// Nearest graph vertex to an arbitrary 3D point.
|
||
// On success -> closest vertex; on failure -> std::string error (e.g., empty mesh).
|
||
[[nodiscard]]
|
||
std::expected<Vector3<float>, std::string>
|
||
get_closest_vertex(const Vector3<float>& point) const noexcept;
|
||
|
||
// Read-only neighbor list for a vertex key.
|
||
// If vertex is absent, implementation should return an empty list (see notes).
|
||
[[nodiscard]]
|
||
const std::vector<Vector3<float>>&
|
||
get_neighbors(const Vector3<float>& vertex) const noexcept;
|
||
|
||
// True if the graph has no vertices/edges.
|
||
[[nodiscard]]
|
||
bool empty() const;
|
||
|
||
// Serialize/deserialize the graph (opaque binary).
|
||
[[nodiscard]] std::vector<uint8_t> serialize() const noexcept;
|
||
void deserialize(const std::vector<uint8_t>& raw) noexcept;
|
||
|
||
// Public adjacency (vertex -> neighbors)
|
||
std::unordered_map<Vector3<float>, std::vector<Vector3<float>>> m_vertex_map;
|
||
};
|
||
```
|
||
|
||
---
|
||
|
||
## Quick start
|
||
|
||
```cpp
|
||
using omath::Vector3;
|
||
using omath::pathfinding::NavigationMesh;
|
||
|
||
// Build a tiny mesh (triangle)
|
||
NavigationMesh nav;
|
||
nav.m_vertex_map[ {0,0,0} ] = { {1,0,0}, {0,0,1} };
|
||
nav.m_vertex_map[ {1,0,0} ] = { {0,0,0}, {0,0,1} };
|
||
nav.m_vertex_map[ {0,0,1} ] = { {0,0,0}, {1,0,0} };
|
||
|
||
// Query the closest node to an arbitrary point
|
||
auto q = nav.get_closest_vertex({0.3f, 0.0f, 0.2f});
|
||
if (q) {
|
||
const auto& v = *q;
|
||
const auto& nbrs = nav.get_neighbors(v);
|
||
(void)nbrs;
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
## Semantics & expectations
|
||
|
||
* **Nearest vertex**
|
||
`get_closest_vertex(p)` should scan known vertices and return the one with minimal Euclidean distance to `p`. If the mesh is empty, expect an error (`unexpected` with a message).
|
||
|
||
* **Neighbors**
|
||
`get_neighbors(v)` returns the adjacency list for `v`. If `v` is not present, a conventional behavior is to return a **reference to a static empty vector** (since the API is `noexcept` and returns by reference). Verify in your implementation.
|
||
|
||
* **Graph invariants** (recommended)
|
||
|
||
* Neighbor links are **symmetric** for undirected navigation (if `u` has `v`, then `v` has `u`).
|
||
* No self-loops unless explicitly desired.
|
||
* Vertices are unique keys; hashing uses `std::hash<Vector3<float>>` (be mindful of floating-point equality).
|
||
|
||
---
|
||
|
||
## Serialization
|
||
|
||
* `serialize()` → opaque, implementation-defined binary of the current `m_vertex_map`.
|
||
* `deserialize(raw)` → restores the internal map from `raw`.
|
||
Keep versioning in mind if you evolve the format (e.g., add a header/magic/version).
|
||
|
||
---
|
||
|
||
## Performance
|
||
|
||
Let `V = m_vertex_map.size()` and `E = Σ|neighbors(v)|`.
|
||
|
||
* `get_closest_vertex`: **O(V)** (linear scan) unless you back it with a spatial index (KD-tree, grid, etc.).
|
||
* `get_neighbors`: **O(1)** average (hash lookup).
|
||
* Memory: **O(V + E)**.
|
||
|
||
---
|
||
|
||
## Usage notes
|
||
|
||
* **Floating-point keys**: Using `Vector3<float>` as an unordered_map key relies on your `std::hash<omath::Vector3<float>>` and exact `operator==`. Avoid building meshes with numerically “close but not equal” duplicates; consider canonicalizing or using integer IDs if needed.
|
||
* **Pathfinding**: Pair with `Astar::find_path(start, end, nav)`; the A* heuristic can use straight-line distance between vertex positions.
|
||
|
||
---
|
||
|
||
## Minimal test ideas
|
||
|
||
* Empty mesh → `get_closest_vertex` returns error; `empty() == true`.
|
||
* Single vertex → nearest always that vertex; neighbors empty.
|
||
* Symmetric edges → `get_neighbors(a)` contains `b` and vice versa.
|
||
* Serialization round-trip preserves vertex/edge counts and neighbor lists.
|