fa icon indicating copy to clipboard operation
fa copied to clipboard

Introduce generated navigational mesh to interpret maps

Open Garanas opened this issue 3 years ago • 5 comments

Initial implementation as an alternative of markers. The goal is to allow AIs to properly read all maps that are reasonably sanely made. All queries towards the data structures and algorithms are guaranteed to be optimal and annotated. This will remove a large hurdle for AIs in terms of performance

Must haves:

  • [x] Is it possible to path from a to b? (yes / no answer)
  • [x] Generate a path from a to b (a path)
  • [ ] Generate a path from a to b, given a maximum amount of threat (a path)
  • [ ] Generate a path from a to b, while trying to avoid threat (a path)
  • [ ] Generate a path from a to b, while trying to seek threat (be attracted to it, like experimentals)
  • [ ] Generate a path from a to b, that doesn't wall hug (a path)

Should haves, likely future pull requests:

  • Square meters of an area
  • Number of resources of an area
  • A distance query from point a to b, over the graph

Garanas avatar Oct 14 '22 20:10 Garanas

Crag Dunes - 0.085876 seconds image

Bermuda Locket - 1.4 seconds image image

Craftious Max - 0.3 seconds image image

Garanas avatar Oct 14 '22 20:10 Garanas

image

We now have neighbor information stored per leaf of each quad tree. See the image, where the neighbours have an additional black square inside it. The white square is highlighted. With this, we can start doing path finding!

Garanas avatar Oct 15 '22 17:10 Garanas

image

Made a debugging tool for CanPathTo to make testing easier. There is both a visual representation of the status quo, and the answer (you'd get in code) is visible in the interface.

Garanas avatar Oct 16 '22 11:10 Garanas

image

Example of an air grid, along with a path 😄

Garanas avatar Oct 18 '22 12:10 Garanas

image

image

image

image

image

image

A few more examples of the output of the current status quo

Garanas avatar Oct 18 '22 12:10 Garanas