Description
Currently, objects cannot be sent from/to non-occupied concave area around a static object.
The reason is that convex hull of each object ichnography is considered to be an exclusion area. This issue gets more pronounced for clusters of mutually intersecting objects (their offsetted ichnographies) because convex hull of the cluster of polygons is used as the exclusion area.
Convexivity of the polygons simplifies path finding, because shortest path never goes through a concave area. It is an issue solely when the starting or target point is located inside this concave area.
The following modification to the path finding algorithm would solve the issue:
- Make static object ichnography an arbitrary polygon (currently, it has to be convex polygon)
- Store ichnography, offsetted ichnography & offsetted ichnography convex hull separately in some mapping
- working with concave polygons will be more CPU intensive, it is better to avoid frequent re-computation (currently offset is computed again for every object during every path finder update)
- all ichnographies are cloned and passed to a separate thread during path finder update -> it is much cheaper to copy only GlobalTranform-s and object types (Pre-load & cache map objects #128)
- All instances of the same object type have the same ichnography -> storing it only once saves some memory and increases CPU cache hit
- Force both convex hull edges and concave polygon edges (after merging intersecting polygons) to the Constrained Delaunay Triangulation.
- Give each concave cluster (merger of multiple intersecting convex hulls) and ID
- Each indexed triangle inside the path finder has its parent cluster ID so source and target cluster IDs (if any) are known
- Each edge of the convex hull and all edges inside the hull have this ID
- During A* graph traversal, only edges:
- without such ID are expanded
- with ID equal to source or target cluster ID are expanded
Blockers
This issue depends on concave polygon offsetting. AFAIK there is no suitable concave polygon offsetting implementation in the Rust ecosystem. Thus has to either be implemented as part of #129, or a PR must be prepared to an existing library (ideally Parry which is already used).
I have already submitted convex polygon offsetting to Parry, dimforge/parry#83.
There seems to be desire to have this functionality in geo: georust/geo#641