search

roy-t / AStar

A fast 2D path finding library based on the A* algorithm. Works with both grids and graphs. Supports any .NET variant that supports .NETStandard 2.0 or higher. This library has no external dependencies. The library is licensed under the MIT license.
http://roy-t.nl
MIT License
338 stars 60 forks source link

Capping time spent searching #14

Closed mhughson closed 6 years ago

mhughson commented 6 years ago

Is there a good way to handle unreachable points? It appears that there is no way to early out of your path search, so an unreachable point will be very, very, expensive.

I would like a way to tell the GetPath function to exit early after either visiting N number of nodes, or after spending N amount of time. This way I can avoid huge hangs when an invalid search is requested.

This may have some overlap with https://github.com/roy-t/AStar/issues/10

roy-t commented 6 years ago

I see some overlap with #10, but this is considerably easier to implement. Especially if its 'good enough' when only looking at the number of nodes expanded (which will also give you fairly predictable time outcomes). Of course checking and incrementing a loop counter every time is going to be expensive on the hot path. But well worth it I guess.

roy-t commented 6 years ago

This feature was added in version 2.1.0, which should be available now on NuGet. Check the new GetPath overload. Note that I implemented this by duplicating a tiny bit of code. So the check does not effect the version that does not have an interationLimit.

mhughson commented 6 years ago

Tested and works, but slightly different than I expected. I was expecting that in a failure case (eg. when it hits the IterationLimit) it would return the "best" path it had found so far. Maybe returning PartiallyReconstructPath(grid, start, current, cameFrom); instead of null? I suppose it should also communicate that the path returned is not the full path (an out bool param?).