New AI for Mobs

[SamJBarney]

I do have one thing that I think will speed things up quite a bit. I'm thinking of creating a thread pool, and farming generation of paths to the thread pool. That way the world thread can be freed up from having to calculate all of the paths, and the mobs can just query the threadpool to see if their path is done yet.

[xoft]

I'm not so sure about that. Calculating a path seems too small a granularity to offload to a thread - you'll spend more time managing the queue than you'll save; not to mention penalties on a single-core machine.

[SamJBarney]

What would you suggest?

[xoft]

1, Revise the algorithm. It shouldn't be such a hog
2, Bail out quickly. If you want to navigate to a player 100 blocks away, give it up altogether. Take into account that in vanilla most mobs only track within 16 blocks away.
3, Don't call that algorithm that often. Only recalculate path when needed - once every N ticks, or if the surroundings change and the mob cannot continue along the calculated path
4, Use as few dynamic allocations as possible. Use stack-allocated values or a cache for storing lots of values of the same simple type (for example coords)

[SamJBarney]

Well, I'm already doing two.

As for one, I'm already at the most stripped down version of the algorithm I know.

I'm already doing 3, as far as I know. Currently the path only gets recalculated if something has changed on the path , or, in the case of the PathToTarget class, if the target has moved out of the block that they were in.

I'm not using any dynamic allocations.

I'm also stripping to path down to just the nodes where the mob needs to change directions, though I may just change to calculating 3 or 4 blocks along the path, have the mob walk that and then calculate more of the path. I just repeat that until they reach their destination.

[tigerw]

Something xoft always says is to use a std::vector structure to speed up stuff. I see you have a:

Code:

typedef std::deque<Vector3f> Path

in BehviourPathToPosition.h. Perhaps change it to:

Code:

typedef std::vector<Vector3f> Path

..?

[xoft]

If you're using any kind of STL container, then you're doing dynamic allocation. Lists and deques are the worst - they allocate from heap on each item added; vector only reallocates when it runs out of space and it allocates some extra items in advance, so usually it performs better. Even better is to use its reserve() function to grab enough items on the first allocation.

However, these are techniques for micro-optimization once you determine that the bottleneck really is in the containers. If you feel that the thing is too slow, use a profiler first to see what's going on.

[SamJBarney]

Ok. I'm going to move to generating partial paths first, and then come back and revamp the containers.

[xoft]

Not sure if partial paths are the way to go at all.

[SamJBarney]

Why do you say that?