05-29-2015, 04:34 PM
My thinking is that an AI could want to query multiple paths, and even some path-related questions, before it decides what to do next. For example, if a mob sees multiple players, it might want to decide which one to hunt (multiple path queries). Or a skeleton needs to find a place that's close enough to shoot (path-related, but not pathfinding). Or when passive mobs escape, they should pick a random destination that is reachable yet furthest away from the source of the attack. These all led me to the belief that a per-mob field would be useful.
I still think it could be viable. It won't be like storing 800 KiB per mob. Even if we used a simple byte array, it would be ~110 KiB per mob (48 * 48 * 48 bytes, where each byte would represent direction to the "previous" cell; coords would be implicit by the position in the array). This should still be acceptable, as normally you'd have only a few hundreds of mobs on the server, meaning tens of MiB of this data. Passive mobs could even use much smaller sight, so again, savings.
If we used an array of {coords, direction} that were populated only for the reachable cells, it should be possible to pack the data even tighter. The assumption is that out of the 3D space, only a 2D-like subset of cells is reachable (there are no flying mobs that have true pathfinding in minecraft). This could be further enforced by limiting not only the sight, but also the path length. In such a case, a maximum of 48 * 48 * 2 records (2D plane, plus jumps), or 18 KiB per mob, would be required. The array should be sorted by the coords, so that searching it by-coords is an O(log N) operation.
I still think it could be viable. It won't be like storing 800 KiB per mob. Even if we used a simple byte array, it would be ~110 KiB per mob (48 * 48 * 48 bytes, where each byte would represent direction to the "previous" cell; coords would be implicit by the position in the array). This should still be acceptable, as normally you'd have only a few hundreds of mobs on the server, meaning tens of MiB of this data. Passive mobs could even use much smaller sight, so again, savings.
If we used an array of {coords, direction} that were populated only for the reachable cells, it should be possible to pack the data even tighter. The assumption is that out of the 3D space, only a 2D-like subset of cells is reachable (there are no flying mobs that have true pathfinding in minecraft). This could be further enforced by limiting not only the sight, but also the path length. In such a case, a maximum of 48 * 48 * 2 records (2D plane, plus jumps), or 18 KiB per mob, would be required. The array should be sorted by the coords, so that searching it by-coords is an O(log N) operation.