Jump to content

  • Log In with Google      Sign In   
  • Create Account

We need your feedback on a survey! Each completed response supports our community and gives you a chance to win a $25 Amazon gift card!


Pathfinding avoid a list of polygon


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
14 replies to this topic

#1 ngoaho91   Members   -  Reputation: 253

Like
2Likes
Like

Posted 04 March 2014 - 11:37 AM

Hello, i'm working on a 2D RTS project, no tile-based map. I have a problem on building map data structure & algorithm for that. I already think of a naive algorithm to solve that. Of course it's very slow. I'm looking for an advice from who experienced  biggrin.png

At very first, i have a list of obstacle as polygon like that

 

map.png

 

i decided to build a pathfinding graph, then i travel all pairs of node, connect them if the connection segment doesn't intersect any polygon. this process have O(n^2) time complexity.

 

graph.png

 

after that, on every path query, i try connect every node to A(startnode) and B(goal node), then do dijstra to find path. this process have O(2n) + O(nlogn) time complexity.

 

query graph.png

 

path.png

 

 

That's all, my algorithm works fine(even it's slow) if the environment is static, no insert, remove obstacle. But when the environment turn to dynamic, such as a obstacle removed, i need to rebuild pathfinding graph(O(n^2)), my fps extremely decreased, 120 to 10.

 

Is there a more professional aproach to solve my problem?


Edited by ngoaho91, 04 March 2014 - 11:44 AM.


Sponsor:

#2 TheComet   Crossbones+   -  Reputation: 1647

Like
3Likes
Like

Posted 04 March 2014 - 12:22 PM

Consider using A-star instead of dijkstra, it'll be a lot faster, and requires only a small modification to dijkstra's to make it work.

 

Secondly, don't rebuild the path every frame. Maybe space the rebuilds over 60 frames (1 second apart). You might even do it in a background thread so the main thread can continue with processing the game, and take over the newly generated graph once its ready.


YOUR_OPINION >/dev/null

#3 Aardvajk   Crossbones+   -  Reputation: 6297

Like
5Likes
Like

Posted 04 March 2014 - 12:42 PM

Something I've not yet implemented but seems all the rage these days is to define the walkable areas (rather than the obstructions) as a connected graph of convex polygons. You can then use whatever method you want to find the route across these, treating the polygons as nodes and the edges as connections of your graph. Once you have this route, you know because the polys are convex, you can plot a straight line across each one to find your initial path, then tweak to minimise.

 

http://en.wikipedia.org/wiki/Navigation_mesh


Edited by Aardvajk, 04 March 2014 - 12:42 PM.


#4 ferrous   Members   -  Reputation: 2147

Like
3Likes
Like

Posted 04 March 2014 - 01:53 PM

Dynamically changing environments are tough for algorithms like yours and navmeshes.  Though Navmeshes do have some algorithms out there for recutting the mesh dynamically with decent performance, so it might be worth looking into.

 

But if you are really changing your environment a lot, you might have to fall back to a tilegrid.



#5 ngoaho91   Members   -  Reputation: 253

Like
0Likes
Like

Posted 04 March 2014 - 09:34 PM

@cormet, actually the algorithm build & rebuild graph cause the slow. dijstra are works fine here but i will try a*.

@aardvajk, i was think of that way before, as i see from here, http://www.ai-blog.net/archives/000152.html the generated graph are poor. so when the agents growns, many paths should duplicate. then agents would collide many times. then evade process occurs frequencely and slow down the game.

@ferrous: please show me those algorithms :D



#6 Pink Horror   Members   -  Reputation: 1232

Like
3Likes
Like

Posted 04 March 2014 - 10:46 PM

That's all, my algorithm works fine(even it's slow) if the environment is static, no insert, remove obstacle. But when the environment turn to dynamic, such as a obstacle removed, i need to rebuild pathfinding graph(O(n^2)), my fps extremely decreased, 120 to 10.


For your tests, what is N? How many nodes are in your scene? There's two general approaches I would take:

1) You could reduce the number of number of connections you attempt to make within your scene by not actually checking all pairs.

2) You could reduce the cost of making each connection, by working on the collision algorithm or potentially the cost of constructing the graph itself.

Also, it is really N-squared? You're traveling all pairs. That's N-squared alone. Then, for each one, you have this condition "if the connection segment doesn't intersect any polygon". That does not sound like a constant-time condition. How do you collide a line segment against a polygon? How do you search for which polygons to test?

#7 ngoaho91   Members   -  Reputation: 253

Like
2Likes
Like

Posted 05 March 2014 - 12:02 AM

@pink horror: i tested with 65 nodes, and do the test 100 times per frame, i'm too lazy to draw a map 6500 nodes biggrin.png. and yeah right, i forgot to mention intersect condition.

 

 


How do you collide a line segment against a polygon?

first i do simple step, collide the aabb of them. if overlap, i do complex step, check collide that line segment to every single line segment of the polygon.

 

 


How do you search for which polygons to test?

i'm using quad tree to divide polygon set. the time to find which polygons to test seem cost logN time(n=number of polygon)


Edited by ngoaho91, 05 March 2014 - 12:03 AM.


#8 Ashaman73   Crossbones+   -  Reputation: 8006

Like
4Likes
Like

Posted 05 March 2014 - 06:24 AM


i'm using quad tree to divide polygon set. the time to find which polygons to test seem cost logN time(n=number of polygon)

If you already have a quad tree, you already have a kind of waypoint system, much like a grid.

 

Just regard all quads in the tree, which do not intersect with a polygon and which parent is either the root or an quad which intesects a polygon. 

Place a waypoint in the center of each of those quads and at the mid of shared edges (choose the shorter edge if quads of different sizes share an edge).

Connect all waypoints on the edges with the waypoint at the center of the according quads.

 

If you change the terrain (modify polygons) you just need to regard the affected quad tree sections.


Edited by Ashaman73, 05 March 2014 - 06:25 AM.


#9 KnolanCross   Members   -  Reputation: 1371

Like
0Likes
Like

Posted 05 March 2014 - 02:03 PM

Why don't you use the good old grid + A* pathfinding?

 

It is a pretty simple approach, limit the amount of paths calculated and you should have an OK FPS rate.

 

If you need better approachs you will have to look for a better graph representation for A* than a grid.

 

I suggest reading:

http://theory.stanford.edu/~amitp/GameProgramming/ (A LOT of information on A*)

http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html (Map representation only)


Edited by KnolanCross, 05 March 2014 - 02:09 PM.

Currently working on a scene editor for ORX (http://orx-project.org), using kivy (http://kivy.org).


#10 ferrous   Members   -  Reputation: 2147

Like
2Likes
Like

Posted 05 March 2014 - 05:44 PM

Alright so you have three major steps to use navmeshes.

 

1.  navmesh generation

  You can do this manually if you want, or try to autogenerate it yourself, or get a thirdparty library (Recast/Detour)

  This looks like a decent article to start with: http://critterai.org/projects/nmgen_study/

 

2.  navmesh traversal (this is basically A* with some smoothing, a lot of the same algorithms apply)

  Check Knolan's links above, they do have a Navmesh entry

3.  Navmesh cutting

  Unfortunately I'm having trouble finding good links, I know there "Dynamically Updating a Navigation Mesh via Efficient Polygon Subdivision" by Paul Marden and Forrest Smith (AI Game Programming Wisdom 4), but that book is out of print, and uh, yeah, $599 for a used copy is insane.  (I have no idea why there isn't an e-book version out there for purchase)

There is this paper: http://users.ices.utexas.edu/~acook/papers/CAVW_Dynamic_ECM.pdf, and it's accompanying video 


Edited by ferrous, 05 March 2014 - 05:51 PM.


#11 ngoaho91   Members   -  Reputation: 253

Like
0Likes
Like

Posted 06 March 2014 - 01:24 AM

Why don't you use the good old grid + A* pathfinding?

 

It is a pretty simple approach, limit the amount of paths calculated and you should have an OK FPS rate.

 

If you need better approachs you will have to look for a better graph representation for A* than a grid.

 

I suggest reading:

http://theory.stanford.edu/~amitp/GameProgramming/ (A LOT of information on A*)

http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html (Map representation only)

 

i'm not that good to make grid movement smooth biggrin.png. i compare AOE to starcraft, i think both use grid map, but starcraft has micro skill, AOE not. smooth unit movement is important for micro.

 

 

 


Alright so you have three major steps to use navmeshes.

 

i searched and found people talking about navigation mesh, but i don't understand why there are so many nodes that doesn't belong to any obstacle. i think a shortest path never travel through them. why are they there?


Edited by ngoaho91, 06 March 2014 - 01:26 AM.


#12 TheComet   Crossbones+   -  Reputation: 1647

Like
0Likes
Like

Posted 06 March 2014 - 03:43 AM


i compare AOE to starcraft, i think both use grid map, but starcraft has micro skill, AOE not.

StarCraft 2 uses navigation meshes with A* and a funnel algorithm for pathfinding. Unless you're talking about StarCraft 1, which used a 2D grid and A*.


YOUR_OPINION >/dev/null

#13 ngoaho91   Members   -  Reputation: 253

Like
0Likes
Like

Posted 06 March 2014 - 06:33 AM

yeah, starcraft 2 is my goal, i'm talking about it's terrain and moving system. i'm already have a set of 2D assets that can form the game. but building assets can't fit in grid. i mean it's shape isn't square or rectangle or diamond, so i think of 'polygon' solution above. but it's seem unofficial and no one do it. i feel a little awkward


Edited by ngoaho91, 06 March 2014 - 06:36 AM.


#14 TheComet   Crossbones+   -  Reputation: 1647

Like
2Likes
Like

Posted 06 March 2014 - 09:32 AM

As mentioned multiple times, use navigation meshes, they're your best bet.

Is there a more professional aproach to solve my problem?

The following are two libraries. Recast Navigation generates navigation meshes and Detour is a powerful pathfinder, capable of searching for paths as well as handling the movement of agents.

https://github.com/memononen/recastnavigation

 

With that you can

  1. Automatically re-generate navigation meshes on the fly.
  2. Search paths for different sized agents.
  3. Control movement of agents using advanced flocking algorithms.

YOUR_OPINION >/dev/null

#15 ngoaho91   Members   -  Reputation: 253

Like
0Likes
Like

Posted 06 March 2014 - 08:06 PM

yeah my problem seem solved, thank you all for the support.






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS