Jump to content
• Advertisement

# Pathfinding - non grid map

This topic is 3937 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

## Recommended Posts

I need help in programing of pathfinding for my game. I have map that consists of basic geometric shapes(circles, rectangles, triangles). And i have lot (2000) of starting positions. I need to find shortest way from these positions to ONE target. Perfect precision is not necessary, but it has to run in real-time. Any suggestions? Algorithms? Thanks for help.

#### Share this post

##### Share on other sites
Advertisement
The easiest way would be to overlay a grid on top of your non-grid map. Or, you can use some other algorithm to sprinkle pathing nodes along the edges and among the inside of walkable areas, then use something like A*.

#### Share this post

##### Share on other sites
Yes, the grid that many people use is completely arbitrary. You can use any graph you like, basically.

2 potential approaches to get you started which should be simple to implement are:

a) Place A* nodes in the middle of each of these polygons. This is essentially what you have with a grid, where each polygon happens to be a square. Or...
b) Place A* nodes in the middle of each edge shared by 2 polygons - this looks more realistic when turning corners but can cause problems the corner-cutting comes too close to an edge.

#### Share this post

##### Share on other sites
You can cheat performance by using a couple of tricks:

Use a separate pathfinding thread and/or a few seaches every frame.

Play a "getting ready to move animation" as soon as a path is requested, and calculate the path while this is played.

Begin moving stuff slowly towards the target as soon as a path is requested.

Sort units(?) by distance to target, and solve the path-requests closest-first.
If this is applied to a group, the result would be that it looks as if the units are following a chain of command (like vehicles in a convoy).

Solve path requests for units that are displayed first, then move to solve the others. Gives the illusion that the pathfinding is instantanious.

Use several layers - finely detail or coarse.

The biggest slowdown I'm having is finding the actual nodes that the starting and ending position links to. I've done this with over 200 simultanious units (each on requesting paths as soon as it found one) without any noticable delay.
With this many units moving no one would even bother that some started later than other.

#### Share this post

##### Share on other sites
Well, i think i need to more specify my problem .. with my bad english :(
The usage of square grid is out of option because map can be very complex and distance between objects can be very small.
I have basic concept of graph-based approach for this, but as Rasmadrak stated, the problem is to find where the particles(not units) are connected to this graph.

#### Share this post

##### Share on other sites

• Advertisement
• Advertisement

• ### Popular Contributors

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5
• Advertisement

• 14
• 30
• 13
• 11
• 11
• ### Forum Statistics

• Total Topics
631781
• Total Posts
3002319
×

## Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!