PathFinder status

[NiLSPACE]

No, Minecraft doesn't do that either.

[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.

[LogicParrot]

Some questions regarding minecraft / the codebase:
-Do all 2 legged mobs have the same bounding box? e.g. skeletons, zombies, creepers, pigmen. Where are the different boundig boxes defined in the project?
-Can arbitrary data be attached to a block?

More to come

[xoft]

I don't think the optimization is needed at all. Mobs' AI will instead limit the calls to pathfinding to once a second for mobs in the player's vicinity and once every few seconds for further mobs. And even when the player moves, the AI will not have to recalculate the path at once, it can postpone until a few moments later; until then the mob can move towards the old position, with the assumption that the player will be somewhere nearby.

The bounding boxes are defined as "entity width" and "entity height" in the source code, each mob constructor should be setting these when calling the parent class constructor.

There is no support for storing arbitrary data for blocks (mostly for memory reasons), but you can of course allocate a buffer of the appropriate size and store the data locally, where needed.

[worktycho]

I agree with xoft. The optimization is really about where on the CPU/Memory tradeoff we want pathfinding to be. Since most of MCServer is memory heavy it probably worth doing the recalculation every time to avoid heavy memory usage.

[jan64]

Are You taking blocks that are right to each other into account?
(eg. you have stairs, that by itself provide pathway too small for anything, but when combined they have enough space for entity to pass)

[NiLSPACE]

I don't think Minecraft does that.

[LogicParrot]

Are You taking blocks that are right to each other into account?
(eg. you have stairs, that by itself provide pathway too small for anything, but when combined they have enough space for entity to pass)

I am not sure what you mean by that, care to explain?

---

I have been reading the "New AI for Mobs" article and I noticed that SamJBarney tried doing pathfinding once (https://forum.cuberite.org/showthread.ph...820&page=4) yet he seemed to have stumbled across performance issues.

What happened to that code? Is it still there? Is it in use? does it take bounding boxes into account? Was the performance issue discovered?

[SamJBarney]

Heh. I'm currently working on the mob rebuild right now. I don't have the code around anymore (It got lost awhile back), but I needed to rewrite the entire thing from scratch anyways to get as much performance out of it as I can. Oh, and it was A* pathfinding.

The reason for the performance drop was that I was recalculating the entire path when the target moved to another block. It worked fine when the target was within 7 blocks, but above that there was too much lag.

I was going to get around that by just storing the node at the end of each path section, and then when recalculation was needed, recalculate from the second node from the end of the path.

Another reason pathfinding was taking awhile was because of the stl containers that I was using. The dynamic allocation of memory was slowing things down. Xoft, I believe, suggested that I use static allocation of a 16x16x16 area and use a std::vector instead to increase performance.

I hadn't been taking bounding boxes into account, but I was using their height to determine if they could get to a block. I hadn't worked out stairs and half slabs yet.

Once I get the Component Rewrite done, I will be transforming the AI into a task-based AI, and I could use some help planning/implementing it, if you're interested.

[jan64]

For example, if we replaced trapdoors with cobblestone, cavespiders could still pass through that hole on the bottom.
Yes, that's mob-safe door for vanilla minecraft. Fixing that bug would be nice