Hi Guys, I need some help!
I'm working on a game at the momment, with a 3d grid like world (think minecraft).
My world is made up of chunks (16 * 16 * 64) and I'm attempting to create an efficent pathfinding algorithm.
An example of this is:
What I have then, is generally large open spaces. I'm thinking, A* wise, that these areas can be converted into large rectangles as nodes for which simple pathfinding (cut diagonal etc) can be done.
First: Is there an algorithm/area of research about say turning a 2d array of walkability into a minimum number of rectangle "regions" that could define the given space?
Because the world is dynamic, it needs to be fairly quick.
The idea is to initially prebake this into the map, and as new blocks/items are removed destroyed then this is quick and dirtly fixed by splitting a region. And every so often a second thread loops through and swaps these out for more efficen region definitions.
I hope that makes sense, if not, soem other advice on efficent 3d pathfinding would be helpful!
I generally expect there to be around 40/100 units pathfinding in the world at any give momment, but this needs to scale to 600. Current bog standard A* is pathetic (spending upwards of 30ms a frame pathfinding with only 40 units) but this is of course to be expected.
Edited by anttoo, 21 November 2013 - 09:32 AM.