12-10-2013, 07:02 AM
If I were to write pathfinding, I'd first impose some limits - I know that there won't be paths longer than, say 64 blocks, and the max (direct) distance from start to end won't be more than 16 blocks in each direction (I'll make these named constants so that they can later be changed).
This would allow me to represent everything with flat arrays - a flat array of 64 Vector3is for the path and flat 33x33x33 arrays of ints (cost) and bytes (direction of previous block in path). Allocate these once, by using a cPathFinder class to wrap them and having one instance of such class per cWorld. Only one mob can be path-finding at a time, anyway (if we ever need more, we'll make more objects). Thus, I'd eliminate dynamic reallocation altogether from the algorithm and the algorithm itself is reduced into the simplest case of more or less floodfilling the array. Of course that needs some storage, too, include that as another flat array in cPathFinder, while imposing another limit (the current queue of open blocks must be less than N items, supposedly N ~~ 64 * 64).
This would allow me to represent everything with flat arrays - a flat array of 64 Vector3is for the path and flat 33x33x33 arrays of ints (cost) and bytes (direction of previous block in path). Allocate these once, by using a cPathFinder class to wrap them and having one instance of such class per cWorld. Only one mob can be path-finding at a time, anyway (if we ever need more, we'll make more objects). Thus, I'd eliminate dynamic reallocation altogether from the algorithm and the algorithm itself is reduced into the simplest case of more or less floodfilling the array. Of course that needs some storage, too, include that as another flat array in cPathFinder, while imposing another limit (the current queue of open blocks must be less than N items, supposedly N ~~ 64 * 64).