Separation with Pathfinding

Currently, in my game, the AI zombies follow a set of points using the pathfinding service. They are able to walk through one another. The issue is, the zombies will either walk in a straight line one behind another or bunch up into one close group.

I want to add some sort of “separation” feature to the zombies, but I don’t want to do anything too intensive because the pathfinding itself is already doing that on the server. I also don’t want the separation to push a zombie completely off its path.

Any ideas how I would go about making a separation mechanic while having the zombie still follow its general path??

If you don’t want them to clump up on the same spot, you can simply alter the position you use for FindPathAsync. So for example. Instead of doing

target.Position

Do this instead

target.Position + Vector3.new(math.random(-4,4),0,math.random(-4,4))

This will add some randomization to their finishing point. Of course you can always alter these numbers and use different methods.

3 Likes

You could also write a law that, if another zombie is too close; stop (or slow) the zombie behind.

So none come to a stop you could apply this rule to zombies that see other zombies within its FOV.

2 Likes

A few months ago I made an AI system that would try not to hit each other(I made it for cars, but I think it is possible to make it for normal NPCs too.) Here are the ways I can think of:

  1. Now, if it is just a few, raycasting could help you but if it is not, I can feel the lag from here if you use raycasting.
  2. If only a script is leading a group of zombies(Which I highly suggest, like one script leading 20 zombies at once, that would reduce lag. Check this topic to see what I am talking about.) you can write a formation script which will make zombies to move to the closest formation position by calculating CFrames from a leader zombie. However, formation needs to be broken in narrowed areas. Shouldn’t be hard to break formations for those cases.
  3. Also you can check the area of the zombies. Let’s say, if zombies’ are moving with a loop that has 0.5 seconds(Which would move zombie 8 studs each loop if zombie has 16 speed) you can check that are and see if there are any zombie around close-by. Zombies close-by can think of going as a horde in those situations. CFrame calculation here again, hordes should try to be same type of zombie(Since speed can change depending on type, I think?) and try going shoulder to shoulder. That would give a nice look.
  4. Another way of doing what you want is to increase the ways that zombies can come. Eventually, they will pick different ways. This would decrease unnecessary calculations for formations. But this time when they are about to attack to a player, you should code them like to surround the player. For example, make only six zombies get near to a player at once and keep others right behind but not attacking. CFrame calculation again, but much lesser than 2 and 3.

Best option there is to use 3 and 4 together but not forgetting the link that is provided in second way. Good luck on your project!

2 Likes

As far as I know the most commonly used solution to this problem is something called flocking behaviour. It’s designed to mimic the way birds (and other organisms) tend to clump up and move in large groups. This seems like a good place to start https://gamedevelopment.tutsplus.com/tutorials/3-simple-rules-of-flocking-behaviors-alignment-cohesion-and-separation--gamedev-3444.

I would recommend designating a “lead” zombie which uses pathfinding and use flocking behaviour on the zombies nearby to follow that zombie in a natural looking way.

6 Likes

You can also implement FlowField or A* or etc pathfinding. You can generate navigation meshes or create your own nodes / navmeshes but then you can randomize connection weights per zombie in order to make them take different paths. This might make them a bit smarter but also less random unless there are more nodes. You can also implement the above flocking behavior to reduce computation times. The pathfinding itself is also more lightweight because there are a defined set of nodes and it runs very quickly, also without being async

It’d be really fun to work on the pathfinding system Roblox uses. Last I knew they used the open source Recast navigation mesh generator and Detour pathfinding library. Detour does have crowd navigation capabilities baked in, it is just a matter of hooking it up to the Roblox engine. I applied for an internship to work on the pathfinding service, but I was required elsewhere. Maybe someone else can throw in a couple hours for us?

(Edit: Oh yeah, and I also need this for my tower rts game as well. I was going to roll my own navigation since I have a fairly simple map which I could make a very fast custom pathfinder for.)

Yeah but Ive been trying this for several months

But a lot of the times the flocking can push the zombies off their path

How do i make them not clump up while following their path?

Collision groups would be the best way to do this, also refer to my earlier reply for info about end point variation.

If NPCs don’t clump up then they spread out and can fall off the path. To prevent them from getting off of a desired path, each must calculate their own path. The calculation of a path is what assures it is save to travel, and any deviation for flocking behavior will break the pathfinder’s assurance unless the pathfinder included allowances for flocking (Roblox’s engine currently doesn’t support this). Unfortunately though, Roblox’s pathfinding also only assures it is clear when the path was calculated, not factoring in additional units planning to traverse the same path later, or parts sliding, flying, or perhaps falling onto or around the path. =( Because the pathfinder is very rudimentary, you cannot communicate any game logic for the pathfinder to factor in to the path. It can’t decide to avoid enemies, find paths for vehicles, use custom material/elevation weights, use doors or teleporters, find the shortest path between multiple goals, much less with constraints on the order those goal must be in (think: I need to grab the key before I can get through the door), using custom turning radiuses, or even group movement. It can’t decide that waiting at the elevator is faster than taking the stairs, and doesn’t care for escalators. Don’t even try asking it to help your space ship find its way through an asteroid field, It’ll tell you to stay where you are.

ANYWAYS, I really went off on a tangent there. To summarize it, the only way to truly solve your problem would be to create a pathfinder that can factor in room for units who are planning to be at a specific location at a specific time. To do that requires a lot of groundwork to get it near the level of Roblox’s current pathfinder, and a decent amount afterward to add your desired feature. I’d say the engine somewhat limits your options here, so I’d go with @magnalite’s suggestion and just define a CFrame from a point on a path looking to the next point on the path, and offset the unit’s locations in the local space of this CFrame. If some NPCs don’t make it, that is the best Roblox has right now unless you are willing to spend some time helping to push the frontier.

(PS, if you are a Roblox developer who has worked on the pathfinding service, I’m sorry. I just feel a lot more resources could be put into AI development on the Roblox platform.)

2 Likes

Yes, I did that a while ago.

Right now it’s my last resort if I cant do any other effective form of separation.

How would you check if its a narrow area?

I would suggest you to do it manually, having nodes for narrow areas. When leader zombie passes through narrow nodes, it should break the formation until it passes, but not the group. It’s best to keep search-and-group script usage at a minimum.

1 Like