Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!

1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


Member Since 29 Feb 2012
Offline Last Active Jan 29 2015 07:53 PM

Topics I've Started

Pathfinding avoid a list of polygon

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


Attached File  map.png   55.08KB   5 downloads


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.


Attached File  graph.png   87.86KB   2 downloads


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.


Attached File  query graph.png   94.74KB   5 downloads


Attached File  path.png   107.95KB   5 downloads



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?