Cuberite Forum

(05-29-2015, 06:18 AM)xoft Wrote: [ -> ]Yeah, I didn't crunch the numbers when I wrote that, I was just brainstorming out loud

What exactly is the issue that is worrying you?

---

Skeleton status updated. It now works fine.

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.

(05-29-2015, 04:34 PM)xoft Wrote: [ -> ]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.

• Changing from A* to Dijkstra is an immediate performance hit. A* is when you know where you're going, Dijkstra is exactly the field around the mobs which covers all paths that you're describing.
  
• Skeletons are doing pretty well with the current system. They PathFind just like zombies, and they stop moving when they detect a line of sight.
  
• Passive mobs are doing pretty well with the current system. They pick an entirely random spot, then, If the PathFinder finds a path, they go there. If it doesn't find a path, it always returns a path to a nearby spot, so they go there instead, which doesn't matter because they're simply escaping and they don't care where they go.
  
• Isn't picking the nearest player (euclidian-nearest) and locking on them for a while good enough? I think that's what Vanilla does. Intelligently calculating paths to all players, then deciding which is best sounds overkill. With that said, it could be done in a much more efficient manner without going Dijkstra all the way. See my "finding stuff" paragraph.
  

Finding stuff
Sometimes, mobs want to go to a specific spot. In that case, A* is best. But sometimes, mobs don't care where to go, they only care about what to find. E.g. A woodcutter looking for wood, villagers looking for wheat, Zombies looking for shade. It would be nice if they could tell the Pathfinder "Find me the nearest shade" or "Find me the furthest wheat".

For that kind of querying, Dijkstra works best. It would be possible and it's relatively easy to have both systems (Implementing Dijkstra is pretty much short-circuiting some of A*). You use A* for going to a specific X. You use Dijkstra for finding the nth nearest x. From an interface perspective, there'd be a new function, cPath::FindNthNearest(Blocktype or functor, n);

Going back to zombies picking which players to attack: I still think that plain old euclidean distance is good enough. But if you want more flexibility, a zombie could use FindNthNearest(...) To pick a target, but it would then LOCK on that target for a while and use plain old A* to chase it. The reason for this is that FindNthNearest is more costly and should be used in a conservative manner. This hybrid solution is very efficient.

To sum it up: FindNthNearest to lock, Plain old pathfinding to attack, then unlocking target after a few seconds and repeating, hence using FindNthNearest as little as possible.

Just a remark: FindNthNearest was just an example. It could be a more flexible function which allows for e.g. finding the player with the lowest health, etc.

Alright, that sounds reasonable. Let's keep the current system, then. I still don't like the partial updates, though. I think pathfinding should be fast enough to perform it all at once, and it shouldn't get called too often.

(05-29-2015, 07:42 PM)xoft Wrote: [ -> ]Alright, that sounds reasonable. Let's keep the current system, then. I still don't like the partial updates, though. I think pathfinding should be fast enough to perform it all at once, and it shouldn't get called too often.

I observed that in most cases, it IS finishing the calculation the first few ticks. Perhaps I should simply get rid of the partial stepping. That shouldn't be a problem and it would simplify Monster.cpp.

Just did a monster test on my server with the most recent build.

Current notes:

Mobs spawn in clusters. Overall, there are too many mobs in one spot, but not spread out enough.
They spawn right in front of you. A spider will spawn right besides the other spider you are fighting with a sword.
Spiders don't jump you. They sit next to you and you take damage.
Every arrow that hits you makes the sound of you getting experience. Maybe you even get experience.
Every arrow you shoot and that hits a monster gives you the experience sound, too, even if the monster is still alive.
Skeletons seem to shoot / aim a bit too slow. Usually if I assault one frontally on a mojang server, I'd get an arrow to the knee one time before I get close enough.
Endermen I'll completely ignore for now because they also spawn in clusters and don't behave anything like Endermen.
Creepers have a tiny explosion trigger radios. They will stand idle next to you and go SSssSSSssSs for hours if you don't hug them close.
Spiders don't seem to really climb or jump.
Monster density seemed to be too high in well lit areas.
Zombies don't move their arms to attack you.
I've never seen a Zombie that looked different in some way. Don't seem to carry items or wear bits of armor, ever, so far.

All these are purely random notes; monster mobs are not as important to me personally as tame animals just yet, but I thought this might help.
Safwat was testing along with me, he might have other or more conclusions.

(05-29-2015, 07:52 PM)Jammet Wrote: [ -> ]Just did a monster test on my server with the most recent build...

Thanks, I'll add the problems not already reported to the to-do.

Had a several guardians come up on land and try to act like squids do. They catch fire and just run around, I do not think they take health damage from the fire as they walk on land. It was creepy.

(05-30-2015, 05:27 AM)ReonBalisty Wrote: [ -> ]Had a several guardians come up on land and try to act like squids do. They catch fire and just run around, I do not think they take health damage from the fire as they walk on land. It was creepy.

I should incapacitate guardians and squids until they're properly programmed.