PathFinder status

[LogicParrot]

Edit: Fixed serious typos. Please re-read.
Edit 2: Clarified the example.
Analysis - O(K*Number Of Players)

Most path-finding techniques are dependent upon the number of mobs, the speed is about O(something*number_of_pathfinding_agents).

However, in some cases this can be greatly optimized. For example, if 1000 mobs are targeting a single player, we can make the needed calculation once! This is illustrated in the following image (ignore the red square)
http://www.gamedeveloperskills.com/wp-co...-stepN.jpg

One needs to calculate such a map for each player, then any mob can use that map to reach the player without further calculations. of course, the map has to be recalculated whenever the player moves, but with the old fashioned way, the map has to be recalculated for *each mob* whenever the player moves.

However, this sort of optimization has some requirements. In Minecraft's case, all mobs that are using the same map must have the same bounding boxes (A path calculated for a chicken can't possibly be the same path of an iron golem).

Which leads to my question/proposal: How about grouping mobs into groups of roughly the same sizes, and giving each group an equal approximated bounding box? For example: Zombies, Skeletons, and most "android" mobs, can all have an equal approximated size of 0.8m, allowing them all to use the same map. Of course, the old fashioned calculation must be done for mobs which are way off the approximation, such as spiders.

Note that this approximation is only for the path-finding, not for the rest of the game.

This would lead to a drastic performance increase.

Example case: 5 zombies, 2 skeletons, 3 spider,

Old method: 5+2+3=10 path calculations
Proposed method: 1 calculation per each mob group targeting the same player. A mob group is a collection of all mobs with the same bounding box (The 5 zombies and the 2 skeletons are one group, the 3 spiders are a second group).

So we have 2 groups.
Worst case: each single mob is targeting a single player (10 players), 10 path calculations

Best case: The 2 groups are targeting the same player: 2 calculations.

Note: If all similar mobs have identical bounding boxes, the approximation part is irrelevant. (Do they?)

---

No, Minecraft doesn't do that either.

Phew! Thank you.