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

Implement pathfinding #12

Closed
Tracked by #246
Indy2222 opened this issue Mar 28, 2022 · 1 comment
Closed
Tracked by #246

Implement pathfinding #12

Indy2222 opened this issue Mar 28, 2022 · 1 comment

Comments

@Indy2222
Copy link
Collaborator

Indy2222 commented Mar 28, 2022

After #11 is implemented adapt it to proper object movement.

There are several requirements:

  • Do not go across terrain obstacles.
  • Avoid all solid object, static and movable.

Research available algorithms. Plain A* won't work.

@Indy2222
Copy link
Collaborator Author

Indy2222 commented May 26, 2022

After doing a bit more research, I decided to go with a version of NavMesh in the first iteration:

  1. compute rectangular bounding box around all static obstacles
  2. erode map boundaries & dilate the bounding boxes
  3. compute constrained Delaunay triangulation
  4. create edge visibility graph from -- edges which are part of the same triangle are neighbors in the graph
  5. build an R-tree for use in search for initial and target edges neighboring from/to points
  6. find shortest paths with a modified A* combined with gradual funnel algorithm

Indy2222 added a commit that referenced this issue May 31, 2022
Will be used by path finding plugin.

Relates to #12.
Indy2222 added a commit that referenced this issue May 31, 2022
Indy2222 added a commit that referenced this issue May 31, 2022
Indy2222 added a commit that referenced this issue May 31, 2022
Indy2222 added a commit that referenced this issue May 31, 2022
Indy2222 added a commit that referenced this issue May 31, 2022
Indy2222 added a commit that referenced this issue May 31, 2022
Indy2222 added a commit that referenced this issue May 31, 2022
Indy2222 added a commit that referenced this issue May 31, 2022
@Indy2222 Indy2222 changed the title Implement Proper Object Movement Implement pathfinding May 31, 2022
Indy2222 added a commit that referenced this issue May 31, 2022
Indy2222 added a commit that referenced this issue May 31, 2022
Indy2222 added a commit that referenced this issue May 31, 2022
Indy2222 added a commit that referenced this issue May 31, 2022
Indy2222 added a commit that referenced this issue May 31, 2022
Indy2222 added a commit that referenced this issue May 31, 2022
Indy2222 added a commit that referenced this issue May 31, 2022
Indy2222 added a commit that referenced this issue May 31, 2022
Indy2222 added a commit that referenced this issue Jun 4, 2022
Indy2222 added a commit that referenced this issue Jun 4, 2022
Indy2222 added a commit that referenced this issue Jun 4, 2022
Indy2222 added a commit that referenced this issue Jun 4, 2022
Indy2222 added a commit that referenced this issue Jun 4, 2022
Indy2222 added a commit that referenced this issue Jun 4, 2022
Indy2222 added a commit that referenced this issue Jun 4, 2022
Indy2222 added a commit that referenced this issue Jun 4, 2022
Indy2222 added a commit that referenced this issue Jun 4, 2022
Indy2222 added a commit that referenced this issue Jun 5, 2022
Indy2222 added a commit that referenced this issue Jun 5, 2022
Indy2222 added a commit that referenced this issue Jun 5, 2022
Indy2222 added a commit that referenced this issue Jun 5, 2022
Indy2222 added a commit that referenced this issue Jun 5, 2022
Indy2222 added a commit that referenced this issue Jun 5, 2022
Indy2222 added a commit that referenced this issue Jun 5, 2022
Indy2222 added a commit that referenced this issue Jun 5, 2022
Indy2222 added a commit that referenced this issue Jun 5, 2022
Indy2222 added a commit that referenced this issue Jun 5, 2022
Indy2222 added a commit that referenced this issue Jun 5, 2022
Indy2222 added a commit that referenced this issue Jun 5, 2022
Indy2222 added a commit that referenced this issue Jun 5, 2022
Indy2222 added a commit that referenced this issue Jun 5, 2022
Indy2222 added a commit that referenced this issue Jun 5, 2022
Indy2222 added a commit that referenced this issue Jun 5, 2022
Indy2222 added a commit that referenced this issue Jun 5, 2022
@Indy2222 Indy2222 closed this as completed Jun 6, 2022
@Indy2222 Indy2222 mentioned this issue Nov 15, 2022
83 tasks
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