# 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.
– House
Mar 4, 2014 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? Mar 4, 2014 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 Mar 4, 2014 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. Mar 4, 2014 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. Mar 5, 2014 at 3:20