CODEWITHSUNDEEP
algorithmgeometryshortest-pathpath-finding
user128409235
user128409235

Reputation: 249

Shortest path between two points in coordinates system

I have two points A and B. I want to find the shortest path from A to B, but there are N (up to 200) rectangles and the path cannot intersect any of those rectangles. Path and rectangles can intersect only at vertices of rectangles and at sides of rectangle. What is the length of the shortest path? Rectangles cannot intersect. They can share point or a side. So if there are two of them sharing a side then you can pass between them.

Upvotes: 0

Views: 1300

Answers (1)

Saeid
Saeid

Reputation: 4255

Usually the best algorithm for this kind of problems is A* using a simple heuristic like Manhattan Distance. But first you should find the illegal points. Illegal points are the ones that you can't enter them in this problem the points that are inside a rectangle are illegal (points that are located on the sides of the rectangles are legal since you can pass through them). After finding these points just implement an A* algorithm to find the shortest path between A and B.

Note that because there is no edge weight in this problem you can simply run a BFS to find the shortest path but it won't be as fast as A*.

If your search space is very big and you run out of memory using A*, you should consider using IDA* which consumes less memory but explores nodes more than once.

Upvotes: 2

Related Questions