Sign in to follow this  
Falhar

Pathfinding - non grid map

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


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


Link to 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


Link to 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


Link to 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


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

Sign in to follow this