Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!
Not quite sure how to name the topic.
Heres what i have a 2D rect that defines movable area, and set of 2D rects that define obstacles Now i would like to find a safe passage from point A to B.
I can't pit that into 2D grid, its a math problem i either use points or planes to define obstacles.
Any references or ideas?
11 minutes ago, _WeirdCat_ said:I can't pit that into 2D grid, its a math problem i either use points or planes to define obstacles.
I would use BSP tree or motorcycle graph to divide the area into convex polygons (or rectangles), and then use standard Dijkstra / A* pathfinding algorithm on the resulting graph, and finally smooth the path if necessary.
Edit: Motorcycle graph can be built in almost linear time if you use a regular grid as acceleration structure (In case you need it to be fast. Otherwise BSP is a bit easier to do.)
Actually all i need is to define clear pathways as separated rects.
I failed to imagine that thats why i asked.
So thebquestion should be how to define a movable worksapce here
