[SOLVED]Want to help me come up with an algorithm for a Shepherding Enemy AI?

(Helios) #1

Okay, so the basic idea behind this enemy Is keeping the player away from the edge of the screen. The function of this enemy is to harass a player that is trying to kite or bottleneck his/her enemies, and attempt to force him/her into the center of the screen where they can surround him/her. This would likely be a flying or burrowing enemy that can avoid collisions to make things easier, because I have no plans to implement any kind of serious pathfinding yet.

here’s what I’m thinking:

  1. determine the point on the edge of the screen the player is closest too. ( I have almost no idea how to go about this. I can’t even think of what criteria to use for evaluating whether a point is closer to the edge. something like summing the distances from the edges might make sense)

  2. approach that point in a roundabout way, so as not to engage the player. Perhaps a question mark approach (approach player in a straigh line, then circle around them to get to the edge)? (For this I can use the lessons learned from my spiral movement behavior) Or, I don’t know, maybe the enemy is a turret that moves on a railroad track.

  3. make lunging attacks at the player. the attack should be structured in such a way that its difficult to deal with when your attention is divided, advance quickly, attack, retreat quickly, rinse repeat. or maybe some knockback?

the biggest question I have, honestly, is how to determine what point along the edge of a border (say, the screen or a predetermined “encounter zone”[rectangle]) that the player is closest to.

any ideas or suggestions?

(Jonathan Stoler) #2

I’m not 100% sure if I’m picturing this properly but here’s what I think you should do (in regards to #1, I think you’ll just need to try a bunch of different strategies for the other questions and see what sticks).

Assuming this is a top-down style game where the player can move in “any” direction (probably limited to like 8 or something) in real-time (not turn-based or gridded) and the game is square:

  1. Find the two closest sides for the player. This is easy; just take the player’s x and y coordinates and compare them to the top, bottom, left, and, right edges of the screen; shortest distance = closest.
  2. Determine the direction the player is going in, based on their angle. This point is the point you should target. It is likely, though, that the player will not keep that angle and instead vary it as they move. So, you should pick some arbitrary distance to consider “danger zones” (maybe 5 or 10% of the edge size).
  3. Have the enemies encroach upon this zone, maybe proportionate to the distance from the true “destination point” (so more enemies will take up the space directly in front of the player than the extra 5-10% of padding).
  4. Have the enemies move as close to the center of the circle as the player’s position permits, maybe leaving some stragglers as backup.
  5. Update the “destination point” and “danger zone” every frame, so it becomes more difficult for the player to trick you.

One problem I can think of that might happen with this method is when the player is relatively close to the center; the AI might not really know what to do, since the closest edges will either be only marginally close or constantly changing.

One way to maybe get around this is to have a threshold distance before doing the method I described above, and if the player is too far from an edge, instead make the enemies form a ring or box around the player, constricting his/her movement.

Again, this is just how I would make it with the way I pictured the game. It’s likely that the reality of the situation is very different, but maybe this is a good starting point. I also haven’t tested any of this and it may work terribly; it’s literally something I just came up with and have no real reasoning to back it.

In terms of determining what point the player is approaching (different from “closest to”), I’m pretty sure this is just right-angle trigonometry?

Here’s a really bad drawing because my explanation is probably terrible: blue is the player, red are the close walls and green is the stuff you calculate.

(azrafe7) #3

Maybe it’s just overkill for a simple game, but here’s some interesting read about boids and steering behaviors you may find useful:

(Helios) #4

@JonathanStoler

First of all, your conceptualization of the game (think zelda, bastionesque) seems to be spot on. Secondly, I believe I followed you on points 1,2, and 5, but I’m still having some trouble working out what you meant on points 3 and 4… maybe more pictures? I loooove crappy MS paint visuals. they do wonders.

@azrafe7

Oh heck yeah. Bookmarked. Ill be reading through these.

(JP Mortiboys) #5

I gave this a quick go because it sounded interesting :slight_smile:

(Move with WASD/Arrows)

The attacking patterns need a bit of work, and it’s unoptimised and unpolished, but the general gist seems to be there!

(Helios) #6

that is astonishingly effective at producing the result I want. Im going to study that code!

(JP Mortiboys) #7

Let me know if there’s any bits of the code that require clarification.

(JP Mortiboys) #8

I updated the Shepherd.as code to calculate the cover spot on a curve instead of a straight line segment; I think it works better. I’ve also added lots of comments to the class.

:wolf:  Shepherd.as source

Edit: Seems I made a slight booboo here, not that it’s really visible - the Shepherd’s moveCollideX and moveCollideY function should return true, not false as they do.

(Helios) #9

ahhh and you commented those equations more. thank you

i dont suppose you could comment the if else statement section where you’re cubing coefficients of relative importance and what not? i have no idea whats goimg on there

(JP Mortiboys) #10

Funny you should mention that, there’s a little error there too, it should be:

if (dist1 < dist2) {
	coef2 = dist1 / dist2;
	coef2 *= coef2 * coef2;
	coef2 *= 0.5;
	coef1 = 1.0 - coef2;
}
else {
	coef1 = dist2 / dist1;
	coef1 *= coef1 * coef1;
	coef1 *= 0.5;
	coef2 = 1.0 - coef1;
}

We’re going to use the weights as interpolants between the two positions - when dist1 is smaller than dist2 we want the weighted target point to be closer to x1, y1, and when dist2 is smaller we want it to be closer to x2, y2. When they’re the same we want it in the middle.

Let’s take the first branch (the second is the same but opposite)

We know that dist1 is less than dist2, and both are positive; therefore the quotient dist1/dist2 is between 0 and 1. Specifically it tends towards 0 when dist1 is MUCH smaller than dist2, and tends towards 1 when they’re almost the same.

If we don’t cube it here, but divide by 2 (the step I forgot before!), we have a number going from 0 to 0.5 - which for linear interpolation means that our cover point is going to be somewhere between (x1, y1) and the midpoint of (x1, y1)-(x2, y2). Make sense?

By cubing it beforehand, we’re making the values more extreme - we’re making values closer to 1 less likely and values closer to 0 more likely - after division this means that we’re generally going to be closer to the end point than the centre.

(The quadratic bézier interpolation I’ve done works in a similar way, but uses the curve rather than the straight line. The maths are a little bit harder, but the principle is the same)

Try removing the cubing lines - you’ll see that the cover spot is less fixated on staying near the edges and is as likely to be near the middle of the curve. Change the cube to a cube root (coef1 = Math.pow(coef1, 1/3);) and you’ll see that it will be more likely to be in the middle, and less likely to be near the endpoints.

(You can use other powers too; even ones will also work because the coefs are always positive - try changing it to 1 (no change), 2 (squaring), 3 (cubing), 4 and above - and also 1/2 (square root), 1/3 (cube root), 1/4 (quartic root) and see how it changes.

You could even use different functions like exp() if you want to; just make sure that it maps from [0, 1] to [0, 1] - look up “easing functions” for other fun examples.