frapa / nav2d

2d navigation meshes with pathfinding and funneling
MIT License
30 stars 5 forks source link

Wrong path #26

Closed kukumberman closed 11 months ago

kukumberman commented 1 year ago

Just playing in editor (if you move 2nd node on the path a little bit it will find correctly)

Coords

555 95
-15 611

Polygon

[[{"x":72,"y":79},{"x":78,"y":252},{"x":974,"y":230},{"x":990,"y":453},{"x":625,"y":684},{"x":197,"y":383},{"x":-77,"y":616},{"x":-33,"y":658},{"x":249,"y":437},{"x":618,"y":762},{"x":975,"y":509},{"x":1128,"y":545},{"x":1032,"y":450},{"x":1010,"y":318},{"x":1135,"y":303},{"x":1149,"y":228},{"x":1032,"y":259},{"x":1011,"y":210},{"x":1069,"y":70},{"x":470,"y":93},{"x":954,"y":109},{"x":944,"y":172},{"x":389,"y":177},{"x":378,"y":110}]]

Screenshot_1

frapa commented 1 year ago

Thanks for the report! Usually this does not happen, but there might be some numerical bugs in the algorithm that cause this in certain situations!

recoshet commented 1 year ago

I also found a stably repeating error if I draw 2 holes

696 -16
395 84

Polygon:

[[{"x":401,"y":-7},{"x":490,"y":-11},{"x":496,"y":88},{"x":418,"y":87},{"x":366,"y":124},{"x":536,"y":122},{"x":538,"y":-43},{"x":354,"y":-54}],[{"x":418,"y":87},{"x":401,"y":-7},{"x":354,"y":-54},{"x":366,"y":124}],[{"x":584,"y":-11},{"x":667,"y":-20},{"x":656,"y":84},{"x":585,"y":80},{"x":536,"y":122},{"x":695,"y":125},{"x":734,"y":-62},{"x":538,"y":-43}],[{"x":585,"y":80},{"x":584,"y":-11},{"x":538,"y":-43},{"x":536,"y":122}]]

image

frapa commented 11 months ago

Thanks @recoshet and @kukumberman for reporting this. I fixed these in version 1.4.0 and added regression tests based on your examples. It took me a while, but at least it's there!