search

vleue / polyanya

Pathfinding using Polyanya
Apache License 2.0
283 stars 20 forks source link

Per-layer cost coefficients #78

Closed 0x0539 closed 1 week ago

0x0539 commented 3 weeks ago

Adds support for per-layer cost coefficients.

For the heuristic, I used min-layer-cost as this should be both admissible and backwards-compatible, though I'm sure better heuristics are possible.

I need this functionality for my own use, though I see it's a commonly-requested feature, e.g. https://github.com/vleue/polyanya/issues/35, https://github.com/vleue/vleue_navigator/issues/66, and https://github.com/vleue/vleue_navigator/issues/46

I saw in the docs that layer.scale can be used as a cost-coefficient, but I found it hard to work with, due to some unwanted interaction with mesh scaling and obstacle scaling. This cost coefficient should be more straightforward to use.

0x0539 commented 1 week ago

Actually, it doesn't work. I've identified a few problems:

1) "Polygons should not be reentrant" is no longer valid. Imagine that starting point and ending point are both in the same high-cost polygon, but the surrounding region is low-cost.

2) Locating the target polygon during a search should not terminate the search. Imagine that your target is in the far end of a high-cost central region that you have to walk around.

3) Finding the turning point before the goal no longer seems to work properly. Not sure why, honestly.

4) Heuristic may no longer be valid. This has an easy solution but, when I tried it, it didn't magically fix everything.

I'm going to close this PR. I will open a new one if I'm able to find a solution.

mockersf commented 4 days ago

the scale field of the layer should be usable to define cost per layer

at the moment the "best" place where it's documented is this test: https://github.com/vleue/polyanya/blob/d1102969b3bb98af303f94c8eec64baa7ab926f6/src/stitching.rs#L899C8-L899C34

Could you give more info about the issues you had?

0x0539 commented 3 days ago

Yeah I saw the comment but when I tried scale it had a bunch of undesirable side-effects like increasing the size of the layer. It might be good to have an example of traversal cost, seeing as it's a fairly often requested feature. Maybe then I could see what I did wrong.