3 replies to this topic

[polyfrag]

Does anybody know why my pathfinding is so slow?

http://corpstates.my.../CorpStates.zip

I divide the world into tiles based on the unit's radius and plot a route in this grid.

For each tile it checks, it checks for collisions with all units and buildings, which is why it's so slow, because there's so many small tiles to check.

Games like Age of Empires have to do more complex pathfinding and they aren't anywhere as laggy as mine.

Edited by polyfrag, 02 September 2012 - 01:11 AM.

[Hodgman]

Maybe you should post your A* code?

For each tile it checks, it checks for collisions with all units and buildings, which is why it's so slow, because there's so many small tiles to check.

Maybe you could check the tiles for collisions in advance (e.g. generate another array which contains true/false for passable/not-passable for each tile) before doing any path-finding, so that the two procedures are distinct.

[jefferytitan]

Agreed. For grid/graph based pathfinding you never want to do collision detection in the inner loop except perhaps for dynamic objects. You construct your graph to contain all that connectivity info so you don't need to.

[nfries88]

If your game is fairly dynamic (IE, the results of a collision test on each tile are going to change frequently), one option would be to find a means of pathfinding asynchronously.