Jump to content
  • Advertisement
_WeirdCat_

Pathfinding??

Recommended Posts

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?

 

IMG_20190121_105511.jpg

Share this post


Link to post
Share on other sites
Advertisement
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.)

Edited by JoeJ

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!