How to make enemy AIs follow path while avoiding their fellows?

:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By tam0705

Hello everyone, so I have a 2d topdown game, and there are enemies (which are zombies) in it. My game environment is a dungeon, with rooms and corridors, generated procedurally by a Tilemap. What I want to ask is the title of this question.

My zombie AI has 4 states: Idle, Wander, Approach, and Assault. What I want to talk about is the last 2 states: Approach and Assault. Basically, the zombie will enter Approach State when they feel the player nearby (player enters their detection area), while Assault State is when they really see the player in their FOV. In both these states they will start to approach player, what different is only their speed.

So far I managed to do that by getting simple path from zombie to player, using the Tilemap’s navigation. But that hasn’t count how zombies will avoid his fellows to go to his destination.

The link below has similar question, but sadly, it’s flocking plus pathfinding. What I want is not flocking, but… well I’ll just describe it by points so it’s easier:

  • Collision avoidance. What different from regular collision avoidance is that the objects (fellows) are moving. So my zombie AI has to determine direction based on the speed of nearby fellows.
  • Intercepting. Consider my zombies as cars, and that it is. If their fellows are slower and blocking their way, I want them to intercept the other fellows, while also considering the speed from the fellows behind them, so no “car accident” happened.
  • Separation. This is the part of flocking behaviour, where I want my zombies to have a safe distance from each other.
  • Queueing. I also want them to slow down if their path is blocked, but they still can progress towards their destination. Imagine cars in a “traffic jam”.

What I want seem to be too many, I apologize for it, especially seeing I’m new in AI. But one can dream, right? :v So I beg everyone to give me a solution to what I want. Thanks in advance :slight_smile:

The link I mentioned:

:bust_in_silhouette: Reply From: MysteryGM

What I want is not flocking, but…

No what you are describing is exactly flocking.
The math for flocking doesn’t care if the objects move or not. It will still avoid them.

This is the beginner flocking AI, you should start here.

Take a look at some 2D boid examples to see how it would move if restricted to a plain.

  • Intercepting.

This is the only one Boids doesn’t cover.
Are you in for some study sessions. Intercepting involves calculating the direction the two objects as a line and then calculating the intersecting point.

However, this isn’t needed for AI to flock. Boid is all about flocking and it doesn’t have intersecting.
Because each Boid tries to reach the center point of the other Boids.

So what I want is basically flocking, but with an extra intercepting ability in it? I… don’t know that. I thought that I don’t want flocking since it includes alignment and cohesion. I don’t want my zombies to follow/move in groups, I want them to move individually, that’s why I want the interception so that faster zombies can go pass the others. Or maybe in other words, although I didn’t mention it, I want each individual zombies to reach their destination as fast as possible. (If they detected the player of course)

But I think I’ll try implementing flocking first, whether it really gives me what I originally want or not. Thank you very much for answering!

tam0705 | 2018-12-10 13:29

Flocking AI is adaptable, you can skip any step you want and only use the parts you need.

Once you start with this it opens doors you never even considered. The avoiding math uses offset vector calculations, this allows all kinds of awesome game play mechanics.
Line intersection will not only teach you to intercept, it will teach you how to slice meshes.

Honestly you will not regret learning flocking AI.
If you need help I am willing to teach the basics.

MysteryGM | 2018-12-10 16:09

Thanks! For now I instead implemented this since somehow the result is almost similar to what I want. I also tried to change the weight of each behaviors, and you’re right, things funny and unexpected started to happen XD. Now I just need to add intercepting, I suppose. Can you explain to me in a little more detail about how to use line intersections to implement it? I somehow cannot grasp what to do after we get the intersection.

tam0705 | 2018-12-11 14:18

how to use line intersections to implement it?

Remember in math class the Simultaneous Equations and how you thought you where never going to use it. Well now you get a chance to.

The trick is to break both lines into a formula. Then you will solve both lines and the one point each line shares is where it intersects.
This site teaches all concepts, from how to calculate the formula of a line and intersecting.

Also if you want a very simple explanation on a line formula: Equation of a Line from 2 Points

The cool thing about intersecting is that even if your line is short, it will still find the intersect point; where the lines would have met.

how to use line intersections to implement it?

In flocking the first thing you learn is avoidance. That is:

func Avoid(InPosition: Vector2, InDelta):
	#Offset is PointB - PointA
	var offset = InPosition - self.position
	#If in range
	if offset.length() < BoidDistance:
		#Better formula: ((offset.normalized() * ((BoidDistance*2) - offset.length())) + offset.normalized()) * InDelta
		self.position -= offset.normalized() * Speed * InDelta
		#We need a direction to look at, just keep looking at X
		offset = self.transform.x
	#Rotate in the direction we are moving
	self.rotation = offset.normalized().angle()
	#Later we will need direction so grab it while we are here
	return offset.normalized()
func _process(delta):
	for eachChild in get_node("..").get_children():
		if eachChild != self :
			var theNode = eachChild
			Direction = Avoid(theNode.transform.origin,delta)

Now when you have calculated the intersection point, keep it as a vector. Then use the Avoid formula to avoid the intersect point.

That is how AI works, it is all math simulating behavior.

MysteryGM | 2018-12-12 16:56