05-29-2015, 12:58 AM
The more this is discussed, the more I start believing that we've gone the wrong path with pathfinding.
It might have been better to have each mob have an "AStarField" that has a cube of predefined size (mob sight) around the mob with calculated A* cells, and then be able to construct paths out of this field, with questions like "Get path to point B", "Get path to the point nearest to point B", "Get the point nearest to point B that is reachable" etc. It would be much easier to write the mob AI with these methods.
Also, updating the field would be necessary only when the mob moves out of its current block coords, which is very cheap for slow mobs, zero cost for mobs that are currently stationary and still cheap enough even for fast mobs. I don't have any mob speed data, but I'd guess the speed to be less than 4 blocks per second, which would make the maximum recalculation rate some 6 times per second (moving along a diagonal). Given that the field's size is rather small, it should be possible to just update the field in a single step, rather than dividing the work across multiple ticks.
My assumption is that the mob sight is rather limited, some 24 blocks, which means the field would be sized 48 * 48 * 48 blocks, with normal worlds being more on the 2D side of things, so something like N * 48 * 48 ~~ N * 2000 cells to be expanded per recalculation.
We could also have a lazy recalculation - when the first pathfinding request comes, put the field in a "to-update" list, out of which only constant amount of work is done in each tick; the pathfinder would simply return a "NotNow" response. The AI would retry the task on next tick, and only after the field is recalculated, it will receive a positive response and could act accordingly. This could make the server quite robust against entity CPU overload.
It might have been better to have each mob have an "AStarField" that has a cube of predefined size (mob sight) around the mob with calculated A* cells, and then be able to construct paths out of this field, with questions like "Get path to point B", "Get path to the point nearest to point B", "Get the point nearest to point B that is reachable" etc. It would be much easier to write the mob AI with these methods.
Also, updating the field would be necessary only when the mob moves out of its current block coords, which is very cheap for slow mobs, zero cost for mobs that are currently stationary and still cheap enough even for fast mobs. I don't have any mob speed data, but I'd guess the speed to be less than 4 blocks per second, which would make the maximum recalculation rate some 6 times per second (moving along a diagonal). Given that the field's size is rather small, it should be possible to just update the field in a single step, rather than dividing the work across multiple ticks.
My assumption is that the mob sight is rather limited, some 24 blocks, which means the field would be sized 48 * 48 * 48 blocks, with normal worlds being more on the 2D side of things, so something like N * 48 * 48 ~~ N * 2000 cells to be expanded per recalculation.
We could also have a lazy recalculation - when the first pathfinding request comes, put the field in a "to-update" list, out of which only constant amount of work is done in each tick; the pathfinder would simply return a "NotNow" response. The AI would retry the task on next tick, and only after the field is recalculated, it will receive a positive response and could act accordingly. This could make the server quite robust against entity CPU overload.