Mob status
#43
(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.
Reply
Thanks given by:


Messages In This Thread
Mob status - by LogicParrot - 05-01-2015, 04:54 PM
RE: AI Reborn - by tonibm19 - 05-01-2015, 07:30 PM
Breeding todo'ed - by LogicParrot - 05-01-2015, 07:32 PM
RE: AI Reborn - by Seadragon91 - 05-01-2015, 08:28 PM
RE: AI Reborn - by worktycho - 05-01-2015, 09:16 PM
Merged - by LogicParrot - 05-01-2015, 10:34 PM
RE: Mob status - by Jammet - 05-07-2015, 02:27 AM
RE: Mob status - by LogicParrot - 05-08-2015, 10:58 PM
RE: Mob status - by NiLSPACE - 05-07-2015, 05:52 AM
RE: Mob status - by Jammet - 05-08-2015, 11:03 PM
RE: Mob status - by sphinxc0re - 05-09-2015, 01:32 AM
RE: Mob status - by LogicParrot - 05-25-2015, 03:08 AM
RE: Mob status - by Jammet - 05-25-2015, 06:42 PM
RE: Mob status - by Jammet - 05-27-2015, 03:44 AM
RE: Mob status - by LogicParrot - 05-27-2015, 05:33 PM
RE: Mob status - by Jammet - 05-27-2015, 08:11 PM
Reproduce? - by LogicParrot - 05-27-2015, 11:47 PM
RE: Mob status - by Jammet - 05-27-2015, 11:50 PM
RE: Mob status - by LogicParrot - 05-27-2015, 11:55 PM
RE: Mob status - by Jammet - 05-27-2015, 11:57 PM
RE: Mob status - by LogicParrot - 05-28-2015, 12:42 AM
RE: Mob status - by Jammet - 05-28-2015, 01:37 AM
RE: Mob status - by LogicParrot - 05-28-2015, 04:58 PM
RE: Mob status - by Jammet - 05-28-2015, 05:25 PM
RE: Mob status - by LogicParrot - 05-28-2015, 05:53 PM
RE: Mob status - by bearbin - 05-28-2015, 05:59 PM
RE: Mob status - by LogicParrot - 05-28-2015, 06:00 PM
Skeleton diagnosis - by LogicParrot - 05-28-2015, 10:51 PM
RE: Mob status - by xoft - 05-29-2015, 12:58 AM
RE: Mob status - by worktycho - 05-29-2015, 01:37 AM
RE: Mob status - by LogicParrot - 05-29-2015, 02:03 AM
RE: Mob status - by worktycho - 05-29-2015, 02:26 AM
RE: Mob status - by LogicParrot - 05-29-2015, 02:28 AM
RE: Mob status - by LogicParrot - 05-29-2015, 02:47 AM
RE: Mob status - by worktycho - 05-29-2015, 03:00 AM
RE: Mob status - by jan64 - 05-29-2015, 04:53 AM
RE: Mob status - by LogicParrot - 05-29-2015, 05:21 AM
RE: Mob status - by Jammet - 05-29-2015, 05:35 AM
RE: Mob status - by LogicParrot - 05-29-2015, 05:43 AM
RE: Mob status - by xoft - 05-29-2015, 06:18 AM
RE: Mob status - by LogicParrot - 05-29-2015, 07:26 AM
RE: Mob status - by xoft - 05-29-2015, 04:34 PM
Dijkstra considerations - by LogicParrot - 05-29-2015, 06:37 PM
RE: Mob status - by LogicParrot - 05-29-2015, 06:49 PM
RE: Mob status - by xoft - 05-29-2015, 07:42 PM
RE: Mob status - by LogicParrot - 05-29-2015, 07:51 PM
RE: Mob status - by Jammet - 05-29-2015, 07:52 PM
RE: Mob status - by LogicParrot - 05-29-2015, 08:03 PM
RE: Mob status - by ReonBalisty - 05-30-2015, 05:27 AM
RE: Mob status - by LogicParrot - 05-30-2015, 08:17 AM
RE: Mob status - by LogicParrot - 05-30-2015, 08:44 PM
RE: Mob status - by Jammet - 05-30-2015, 08:58 PM
RE: Mob status - by warmist - 06-16-2015, 03:13 AM
Breeding implemented - by LogicParrot - 11-30-2015, 05:05 PM
RE: Mob status - by Jammet - 12-07-2015, 10:36 PM
RE: Mob status - by LogicParrot - 01-12-2016, 07:11 PM
RE: Mob status - by LogicParrot - 01-12-2016, 10:49 PM
Spawn distance - by LogicParrot - 01-13-2016, 12:55 AM
RE: Mob status - by Jammet - 01-13-2016, 01:49 AM
RE: Mob status - by xoft - 01-13-2016, 03:02 AM
Ball of Mud - by LogicParrot - 01-15-2016, 11:44 PM
RE: Mob status - by xoft - 01-16-2016, 12:13 AM
RE: Mob status - by LogicParrot - 01-16-2016, 03:37 AM
RE: Mob status - by xoft - 01-16-2016, 06:59 AM
RE: Mob status - by LogicParrot - 01-17-2016, 12:14 AM
Smart dogs and spiders - by LogicParrot - 01-23-2016, 05:31 AM
RE: Mob status - by Jammet - 01-23-2016, 11:02 AM
RE: Mob status - by warmist - 03-04-2016, 07:24 PM
RE: Mob status - by LogicParrot - 03-28-2016, 10:29 PM
RE: Mob status - by Jammet - 03-28-2016, 10:30 PM
RE: Mob status - by LogicParrot - 03-28-2016, 10:31 PM
RE: Mob status - by LogicParrot - 04-15-2016, 04:25 AM
RE: Mob status - by hangyas - 09-11-2016, 07:25 AM
RE: Mob status - by LogicParrot - 09-11-2016, 05:56 PM
RE: Mob status - by LogicParrot - 08-05-2017, 10:00 PM



Users browsing this thread: 2 Guest(s)