Feature request: Add is_blocked() or similar function to BaseMap trait.

[BezPowell]

This one is related to my efforts to try and add a JPS algorithm, but I think would have uses outside of that. As far as I can see the only way to check if a given tile is traversable is via the get_available_exits function. It would be nice if it were possible to also check whether a arbitrary tile was blocked, without necessarily knowing the route to get there. Essentially passing in a idx value and getting a boolean back as to whether the tile can be moved into.

An example use case of this would be on the A* algorithm, having a quick check at the start to see whether the target tile is actually reachable and if not bailing out immediately without attempting to calculate a path (which would never complete, but pause execution of the thread).

The obvious disadvantage would be that anyone implementing the trait would need to add the logic for an additional function.

I'm happy to knock up a PR for this if it is considered that the advantage of adding it would outweigh the disadvantages.

P.S. Sorry for clogging up the issues with multiple feature requests. If there's a better place to discuss these things I'm happy to jump on there instead.

[waldoplus]

If I understand you right, you want to check the destination tile for a blocker before running a_star. Assuming you have a map object with a blocked: Vec<bool> field, just wrap your a_star request in an if !map.blocked[idx] { a_star call } or you can use a guard clause if map.blocked[idx] {return} before the a_star call. This requires that you update your blocked array each turn, of course. If you are just looking at tiles and don't care about other blockers, say entities, you can just write a function to check your maps tileType and return true if it's a blocking tile. Then that function will become your condition in the if statement.

[BezPowell]

I was primarily requesting it to be added to allow adding the Jump Point Search algorithm as an alternative to A*. JPS only works on uniform cost grids, and as a result assumes that direct routes to cells are faster that more roundabout routes to speed up path-finding. Because of this, instead of checking every neighbour of a given cell for potential exits, it jumps ahead and would need to check only whether a route between two different tiles was available.

When attempting to use get_available_exits the performance of JPS is actually worse than A* due to the extra computational overhead of checking all exits and then immediately discarding the results for most of them.

To add an implementation of JPS to the crate there would need to be a separate method on the BaseMap trait (or an additional AdvancedPathfinding trait or similar) that takes 2 tiles as arguments and returns a boolean indicating whether it is possible to pass from one to the other. Something similar to:

fn is_path_between(&self, start: usize, end: usize) -> bool {
    if self.blocked[start] || self.blocked[end] {
        return false;
    }

    true
}

Those wishing to use JPS could then write their own definition for the function taking into account which tiles are connected etc. Hopefully that makes some kind of sense?

I don't know how much interest there would be in adding additional path-finding algorithms to the crate, but thought JPS would be a good fit as it seems particularly well optimised for games.

EDIT: Added link to JPS algorithm on wikipedia for a more detailed explanation of how it works.