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

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

[attachment=20213:map.png]

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.

[attachment=20214:graph.png]

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.

[attachment=20216:query graph.png]

[attachment=20217:path.png]

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?

Dynamically changing environments are tough for algorithms like yours and navmeshes. Though Navmeshes do have some algorithms out there for recutting the mesh dynamically with decent performance, so it might be worth looking into.

But if you are really changing your environment a lot, you might have to fall back to a tilegrid.

@cormet, actually the algorithm build & rebuild graph cause the slow. dijstra are works fine here but i will try a*.

@aardvajk, i was think of that way before, as i see from here, http://www.ai-blog.net/archives/000152.html the generated graph are poor. so when the agents growns, many paths should duplicate. then agents would collide many times. then evade process occurs frequencely and slow down the game.

@ferrous: please show me those algorithms :D

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.

@pink horror: i tested with 65 nodes, and do the test 100 times per frame, i'm too lazy to draw a map 6500 nodes . and yeah right, i forgot to mention intersect condition.

How do you collide a line segment against a polygon?

first i do simple step, collide the aabb of them. if overlap, i do complex step, check collide that line segment to every single line segment of the polygon.

How do you search for which polygons to test?

i'm using quad tree to divide polygon set. the time to find which polygons to test seem cost logN time(n=number of polygon)

Alright so you have three major steps to use navmeshes.

1. navmesh generation

You can do this manually if you want, or try to autogenerate it yourself, or get a thirdparty library (Recast/Detour)

This looks like a decent article to start with: http://critterai.org/projects/nmgen_study/

2. navmesh traversal (this is basically A* with some smoothing, a lot of the same algorithms apply)

Check Knolan's links above, they do have a Navmesh entry

3. Navmesh cutting

Unfortunately I'm having trouble finding good links, I know there "Dynamically Updating a Navigation Mesh via Efficient Polygon Subdivision" by Paul Marden and Forrest Smith (AI Game Programming Wisdom 4), but that book is out of print, and uh, yeah, $599 for a used copy is insane. (I have no idea why there isn't an e-book version out there for purchase)

There is this paper: http://users.ices.utexas.edu/~acook/papers/CAVW_Dynamic_ECM.pdf, and it's accompanying video