5
\$\begingroup\$

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

map

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

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

path

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?

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – MichaelHouse Mar 4 '14 at 18:35
  • \$\begingroup\$ 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? \$\endgroup\$ – wolfdawn Mar 4 '14 at 18:40
  • \$\begingroup\$ 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 \$\endgroup\$ – wolfdawn Mar 4 '14 at 18:45
  • \$\begingroup\$ 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. \$\endgroup\$ – Yos233 Mar 4 '14 at 19:05
  • \$\begingroup\$ 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. \$\endgroup\$ – ngoaho91 Mar 5 '14 at 3:20
1
\$\begingroup\$

i found a solution, it's recastnavigation and detour by memononen.

the main idea are divide the map into many square, called tile. if the polygon doesn't fit the tile, it splitted. then each tile, we can considered it as a map. when a new obstacle placed, only the tile it belong must rebuild.

it's sound simple, but with some cache tricks, performance improved significantly.

thanks for the support!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.