# Pathfinding avoid a list of polygon

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 :D

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

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.

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.

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?

• Place nodes a small distance out from the normal of each vertex. Path find along the nodes, ensuring each connection doesn't overlap a polygon. Only test for overlap when attempting to use the node. – MichaelHouse Mar 4 '14 at 18:35
• You could either use the flow field pathfinding approach (if the obstacles are sparse enough) or create a regular nav mesh and then use that in conjunction with possibly with flow field to make motion between nodes more organic (and less rigid). What is your desired approach? – wolfdawn Mar 4 '14 at 18:40
• If you want to explore advance dynamic techniques similar but more efficient than what you described you can begin here: users.ices.utexas.edu/~acook/papers/CAVW_Dynamic_ECM.pdf – wolfdawn Mar 4 '14 at 18:45
• Does your pathfinding need to update when the terrain moves? If so, it will require a lot of computation to recalculate each body's path every frame. You could make it so whenever something hits a wall it regenerates the node graph and makes a new path. – Yos233 Mar 4 '14 at 19:05
• terrain doesn't move Yos233 :D my obstacles are sparse enough but i have no idea to implement the flow field aproach, is it necessary to rebuild if i remove an obstacle? Byte56, i dont understand you clearly but seem every query, you tried to check if the path overlap polygons or not. this query took O(n^2) too, not a good idea. – ngoaho91 Mar 5 '14 at 3:20