Follow up on path search

  • 0

    The original question is: given an unbounded 2D map, we want to know if a robot can reach the destination (xd, yd) from starting position (xs, ys). An API is given: bool isPath(int x, int y), which tells you whether you can reach location (x, y). The robot can move in 8 directions. This question is easy to get using a two way BFS search.

    The follow up is where I haven't got a good idea. I was asked to simultaneously find K paths that are distinct from each other (paths do not intersect or share any segments). Of course K is less than 8.

    Any thoughts?

  • 0

    my thoughts towards 2D pathfinding:

    1. if you do start BFS from source and destination this is faster than just starting from start, how ever, you assume that the path is bidirectional, which is, in the case of maps and especially games not always true.
    2. The problem with BFS is, that it does spread in all directions, whereas most often if your target is south, you are much more likely to go south and only go north if an obstacle hinders you going south. That's where A* comes into play where you can place an heuristic function that will dramatically accelerate your path finding and exploited points...
    3. now, the followup question might be to run A* with different heuristics, one that goes directly to the target and others maybe approaching with an arch etc... similar like in soccer you do not always run directly to the goal but might trick your opponent etc.

    So, in this scenario, you could simultaneously run A* with different heuristics and avoid places that have already been visited or take this into the heuristics so it draws you away from visited places (kind of).

    but pathfinding in 2D is almost always something with A*, BFS is just to exhausting
    Amit's very good introduction to A* might clarify my thoughts

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.