AI: natural looking pathfinding for multiple zombie-like agents

P

ph101

Guest
Hiya

I'm looking for suggestions for natural looking pathfinding for multiple NPCs. Say a crowd of zombies (they aren't zombies) but that type of thing. The point is they go between different points on the grid in crowds - they aren't pursuing a player or anything.

Here's what I'm doing: I have sometimes dozens or more NPC agents calculating paths (using if mp_grid_path) between variable waypoints. They don't all calculate their paths at the same time, in fact one at a time and wait until no one else is so that there is no terrible lag. The nav grid has purely the walls added to it.

Because I want the AI agents to have a natural looking swarming type movement, and to bump off each other, they dont strictly follow the path using path_start, but use mp_potential_step (avoiding a parent object including walls and other AI agents) to walk towards a point on the path a set number of points ahead (path_get_point_x, path_get_point_y). When within a small distance of that point, they choose to move to the next point in the path (usually 5 points further along the point - can be a random amount, but the further it is, the less accurate their behaviour in term sof say going round corners).

This results in some nice natural looking crowding around behaviour, and i have to say potential step is just a great function as is the pathfinding, but I have some problems:

1. Agents coming the opposite way between waypoints are attempting to follow same path and so you get a grid lock in the middle as they all attempt to follow the trail of points at same location. Possibly I could periodically add the agent instances to the grid (this cant be dont all the time because of CPU but maybe every few seconds so they avoid a snap shot of busy locations?).

2. I want to give them more natural looking behaviour, with more variance. This would help 1). Is there a nice easy way to make them stray more from their path more or make a more varied path? I tried adding smoother paths but it is not pronounced enough to make much of a difference. All I can think of to take their next point to step towards and randomly relocate to a nearby point - but would require testing if the place is empty in the grid first so lots of CPU. Maybe would only happen sporadically?

3. Another issue is that when there are many of them bunching up to reach their next point they sometimes get pushed beyond their waypoint etc and so need to go back to reach it and trigger then next point to move towards.

Would be great to have some general thoughts on this, if you have ever done similar.

Thanks
 

DukeSoft

Member
How about you'd have a "swarm" object that does the path finding, then let the objects follow that path, adding their relative position to the main object? This way they'll stay in the same shape. KInd of like how RTS movement works in AoE and RA2
 
P

ph101

Guest
How about you'd have a "swarm" object that does the path finding, then let the objects follow that path, adding their relative position to the main object? This way they'll stay in the same shape. KInd of like how RTS movement works in AoE and RA2
Hiya - thats a nice idea, I will think about that. However, these agents, they do not all start at same point together necessarily, and I need them to appear individual and independant, however there is maybe something to that idea, thanks for your suggestion.
 

DukeSoft

Member
in that case you might want to give each agent his own seperate target. Maybe a setup like putting down "target" instances? Then you can make sure they don't overlap and you won't have a lot of those troubles. It might however be pretty CPU-intensive
 
P

ph101

Guest
in that case you might want to give each agent his own seperate target. Maybe a setup like putting down "target" instances? Then you can make sure they don't overlap and you won't have a lot of those troubles. It might however be pretty CPU-intensive
Yeah, currently each agent is calculating their own path using a grid containing only walls, then mp stepping towards every 5 point in the path in succession in a loop. This is essentaiily same as following a swarm object like you suggest, except their is no object so much as a point on a path. Ultimately they all are going towards the same target. If I understand, basically you suggest adding the path points to the grid so other paths dont plot accross them?

I'm thinking the best solution is to take a "snap shot" of agents, and add them to the grid, but only rarely so as not to hit cpu. So when each agent creates a path, they take account of other agents. if there is a "pile up", they would plot a path around that. It doesnt really help in adding human like variation to their paths but will stop pile ups.
 

DukeSoft

Member
Yeah that target instance would only help with the final position, not the steps inbetween... I must say, I'm going to have this issue too - because I want a more "human" like movement to my bots too (instead of they constantly skimming walls etc.)

I think adding the bots to the mp_grid is going to be aweful on the CPU. Maybe write some custom logic? Check if they can reach their target with the mp_path finding functions, and then make them move kind of "towards" the path, and check if the place they want to move to is available.

I'm going to add zombies in my game as well - and this combined with bots will have similar issues as you're having...
 
P

ph101

Guest
Maybe write some custom logic? Check if they can reach their target with the mp_path finding functions, and then make them move kind of "towards" the path, and check if the place they want to move to is available.
Actually that is what I am already doing in that they are using mp_potential step to move towards a series of points in the calculated path (using (path_get_point_x, y) . Think of this as like following a breadcrumb trail. When they reach a bread crumb they retrived the 5th next point in the path and mp_potential step to that instead.

Although if you mean can they reach their breadcrumb... using mp_path.. would need to add the agents to the path too. It could see how long it has taken and do another behaviour if it took too long possible.

Adding the agents to the grid is defo a huge CPU load, however I think I can get a way with doing it say only every 5 seconds. The agents will be making paths on slightly old data but I think will not really be noticeable or a huge problem (maybe) and will mean thay end up avoiding pile ups. Although I'm not sure. my agents calculate their path at the start of their jounrey and only once. Perhaps they need to check further down the line..
 
Last edited by a moderator:
Top