Jump to content

  • Log In with Google      Sign In   
  • Create Account


ngoaho91

Member Since 29 Feb 2012
Offline Last Active Jul 26 2014 07:50 AM
-----

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   4 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   4 downloads

 

Attached File  path.png   107.95KB   4 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?


PARTNERS