6
\$\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?

Improve this question
\$\endgroup\$
9
  • \$\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\$
    – House
    Mar 4, 2014 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\$
    – AturSams
    Mar 4, 2014 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\$
    – AturSams
    Mar 4, 2014 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, 2014 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, 2014 at 3:20

1 Answer 1

Reset to default
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!

Improve this answer
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .