Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Path finding inside convex areas #97

Open
4 tasks
Tracked by #246
Indy2222 opened this issue Jun 2, 2022 · 0 comments
Open
4 tasks
Tracked by #246

Path finding inside convex areas #97

Indy2222 opened this issue Jun 2, 2022 · 0 comments

Comments

@Indy2222
Copy link
Collaborator

Indy2222 commented Jun 2, 2022

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

@Indy2222 Indy2222 added this to the Version 0.1 milestone Jun 2, 2022
Indy2222 added a commit that referenced this issue Jun 15, 2022
Indy2222 added a commit that referenced this issue Jun 15, 2022
Indy2222 added a commit that referenced this issue Jun 15, 2022
Indy2222 added a commit that referenced this issue Jun 15, 2022
Indy2222 added a commit that referenced this issue Jun 16, 2022
@Indy2222 Indy2222 mentioned this issue Nov 12, 2022
83 tasks
@Indy2222 Indy2222 modified the milestones: Version 1.0, Run 2 Sep 26, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Development

No branches or pull requests

1 participant