The flight graph is stored as a series of delta elements at 1m resolution and a list of nodes. Both lists share the same buffer. Each delta element takes up 2 bytes or sometimes 6 bytes if the delta is large. The path can consist of multiple disconnected segments, in which case the gaps are stored as delta elements with a jump-bit set.
Once in a while or when required the graph is consolidated, which means:
- Points that lie roughly in a line are replaced by a single line
- Points that lie close to previously recorded lines are pruned
- For lines that pass close to each other a node element is created
Furthermore:
- The graph is recorded at a higher precision closer to home
- If the graph becomes full, the overall precision is reduced and the whole graph is re-consolidated
- If the graph becomes full once more, all data is removed except for the shortest path home at that moment. One of these actions is repeated at each subsequent fill-up.
Path finding information is generated/refreshed on demand and stored in the nodes. During return-to-home, the best direction to home is continuously evaluated by using the information stored in the nodes.
The graph recording and path finding is implemented in navigator/tracker.cpp.
The graph based return-to-home is implemented in navigator/smart_rtl.cpp.
