search

TyOverby / astar

DEPRICATED
32 stars 6 forks source link

no documentation exists #9

Open radix opened 7 years ago

radix commented 7 years ago

Hi, I'm evaluating pathfinding libraries. I like that this one seems to support caching of path analysis for multiple queries, but I can't figure out how to use the library.

For example, I have no idea what TwoDSearchProblem::get is supposed to return -- the only unit test returns None or Some(0), so I'm not sure what the effect of the u32 is.

Another thing I'd like to know is if there is any support for max distance in pathing. Without it, I believe that infinite loops would be trivial (by trying to path to an inaccessible location). Is there a way to limit the distance of a search?

TyOverby commented 7 years ago

Yeah... I should really get around to documenting this.

As for your questions:

I have no idea what TwoDSearchProblem::get is supposed to return.

get returns None if that block is impassable, or Some(weight) if the block has some weight associated with it.

is any support for max distance in pathing.

Not right now. It should be pretty easy to add though. I'll file a bug.

TyOverby commented 7 years ago

Also, I'm sorry to report that

this one seems to support caching of path analysis for multiple queries

is false. The ReusableSearchProblem trait indicates that it's the SearchProblem that is reusable, not that it is caching pathing routes. I'm unaware of any modifications to A* that would allow for path caching without destroying the running time. If this is important to your algorithm, then I'd recommend doing the caching of complete point->point paths yourself, and perhaps use them to provide very accurate heuristics implementations.

radix commented 7 years ago

@TyOverby ah, interesting. I'm actually not sure if it'll be necessary, but basically what I'm trying to do is render all accessible destinations from a starting point on a grid map, with a maximum distance limit. I figure it should be possible to avoid recalculating the path from (0, 0) to (0, 5) when calculating the route to (0, 6) (if I've already calculated (0,0) to (0, 5), that is).

radix commented 7 years ago

Also, I realized that I can at least put an overly generous upper limit on my pathfinding by adding a cost check to neighbors from the starting point. It could potentially return a lot of extraneous neighbors in the face of blocking terrain, but it at least avoids an exhaustive search of all of i32 x i32.

radix commented 7 years ago

By the way, I'll probably contribute some documentation if I can get something working, which I'm getting close to. :)

TyOverby commented 7 years ago

Also, on the point about looping infinitely by trying to path to an inaccessible location: this is possible, but only if you have an infinite search space.