Detecting enemies in elipse

Hi guys

I have a problem, or more like dilemma, about detecting units in elipse range. Here is what i mean:

<img src="https://dl.dropboxusercontent.com/u/19082408/123.JPG" border="0" />

So, as i see it, there are 2 approaches about this:

• First approach is to make a collision surface, detecting foes on collision. That have many advantages, but one main downside - the 8 pointed collision polygon is not enough to make a decent looking detection. When trying to add more points (16 would be enough as i see it)it sais all collision polygons over 8 points are very havy.

So there is my question: How exactly expensive is to have polygons with more then 8 point? (is having 16 point polygon twice as heavy as to have 8 point poly, or there is another cunning reason we shouldnt make more then 8 points?)

If there is such reasons i can make it works by setting the sprite with 2 frames, both to have slightly different 8 pointed collision polys. So i figure if i play the animation fast it will detect foes for both the yellow and the blue collision polys.

<img src="https://dl.dropboxusercontent.com/u/19082408/456.JPG" border="0" />

• Second approach is to make it by detecting distances. But the problem is, because of the camera angle, i want it to be an ellipse, not a circle. Im not sure if that is possible to make with the -Get Distance To-. The only way to achieve this, as i see it, is to have a hidden layer with all the foes and rally points, and keep it scaled so it becomes like top view (not even sure its possible).

Anyways, if anyone have any thoughts or advices for me, and most of all answer of my 8 pointed collision poly question, pls dont hesitate to write.

Thanks for baring with me and my problems ;)

Pakost

The basic formula you will need is (x-h)^2/a^2 + (y-k)^2/b^2 <= 1

x and y are going to be one set of coordinates say for the bad guy

h and k are the other set of coordinates say for the good guy

a is the radius that the ellipse extends horizonally

b is the radius that the ellipse extends vertically

If the equation is less than 1, than one set of coordiantes is within the ellipse that is centered on the other set of coordinates.

So lets say that a bad guy is located at x and y coordinates of (50, 100) and has an ellipses sized detection. The ellipse extends 20 pixels above and 20 pixels below the enemy so the b value is 20 and it also extends 50 pixels to the left and 50 pixels to the right so the a value is 50. (Remember that the screen takes place in the 4th quadrant of the cartesian plane so the y axis increases as you move down.) The Hero is located at h and k coordiantes of (90, 95).

Is the Hero within the ellipse?

The equation will be populated like this: (50 - 90)^2/50^2 + (100 - 95)^2/20^2 <= 1. If you do the math, you see that it comes out to .7025 which is indeed less than 1. So he is within the enemy's ellipse. It doesn't matter whether you subtract the hero's coordinate minus the enemies coordinate because the value is being squared anyways. Just be consistant. (x - y)^2 will yield the same value as (y - x)^2 so don't get hung up about which coordinate is which. you are just finding the DIFFERENCE between them and squaring that value.

Thanks a lot for the answer —

Math is not my brightest side but i think i got the idea... I'll try it out tonight when i got home.

The problem i see with this is that i should every second make this calculations about every unit on the field. Since i plan to have many units i dont know if that is the right approach. Maybe i should simply detect distnaces between the 2 units, and only if the distance is smaller then the largest radius of the ellipse, only then to make that calculations and see if the other unit is within the ellipse radius? What u think about it?

Anyways if anyone can answer my question about the collision polys with more then 8 point i will greatly appreciate it, i was often wondering about it:

Pakost

It would definitely not be efficient to every second check whether every unit in the field is within the ellipse of an enemy unit. A good game will narrow down to just the bare minimum what it needs to be doing every second. For example, a three dimensional game will have algorithms to determine whether objects are occluded from your viewpoint by a wall or some other barrier. If you can't see that hidden object, there's no point in the game wasting time and drawing it. So you would need to develop a way to only test the more costly ellipse collision if there is a definite possibility that the enemy is indeed overlapping the ellipse. An enemy that is on the other side of the screen can't possibly be within the ellipse. One way could be to enclose the ellipse in a basic rectangle. If a unit is overlapping that rectangle, then you will do the ellipse collision test once to determine if the unit is touching the ellipse.

— at that point couldn't you just replace the ellipse calculations with the invisible rectangle and do an is overlapping test? Or even an on collision with rectangle (or ellipse) attack... OR do something like when distance is less than Width of the ellipse, do a check to see if they are overlapping the ellipse. That way they are using the largest known plain of the ellipse (the X axis of the ellipse), and when they have crossed that boundary, then we test to see if they are overlapping it as if they are above or below you they may not be due to the ellipse having less depth above and below.

BluePhaze

If I am understanding you correctly, you are saying that when the unit overlaps the rectangle that encompasses the enemy and the enemy's ellipse, you could "just replace the ellipse calculations with the invisible rectangle and do an is overlapping test". That defeats the purpose of the ellipse test because simply testing the rectangle collision would result in a collision range that is based on a rectangle and not on an ellipse!

You could check to see if the unit is within the largest radius of the ellipse to then start testing whether the unit is in fact touching the actual ellipse. However, there is a trade off. Imagine that you have an ellipse which is 1000 pixels wide and 10 pixels tall. Then your distance method of detection would detect that a unit is "touching" at a distance of 500 pixels above the bad guy even though the unit still has another 495 pixels to go before colliding with the ellipse. The closer that the ellipse is to a perfect circle, the more accurate the first line of detection will be. And the problem with the rectangle is that the corners will always give false positives. So it's a trade off and I can't catagorically say which method is better.

Aside from all these calculations, I think using an octagonal detection shape will be sufficient, especially if you strategically place the detection shape. The pictures you have show the octagonal shapes fully inside the ellipse. But if you place the octagonal shape on top of the ellipse so it weaves in and out, I think that offers a pretty accurate recreation of the ellipse and the end user would probably not even know the difference.

<img src="http://imageshack.us/a/img11/3272/19280691.png" border="0" />

Thank you both guys for showing that interest in the topic

The calculations — showed will help me great deal about some other stuff i need to implement so learning that trick is quite useful for me.

Anyways, after a long evening in testing i think i got what would be the most comfortable for me to use. Since I am no programmer and my math is intermediate, and my trade is more like art orientated than coding, i prefer the visual than the logical approach.

The 8 point collision poly is not quite accurate by me since i will have graphic appearance of the ellipse, so i divided an invisible object in 2 frames, each frame containing opposite semi ellipse collisions, so in fact i get a 14 pointed collision of the ellipse.

<img src="https://dl.dropboxusercontent.com/u/19082408/789.JPG" border="0" />

Blue line is the 1st frame collision

Yellow is the 2nd frame collision

I haven't yet tested it but i feel confident it should work as expected.

I remember you asked a similar question a few months back. You can use the same solution I proposed to you back then. A custom distance function, that scale the delta Y according to the ratio width / height of your ellipse.

Here's an example.

Yeah Magistross I remember that well since it works fine for my woodcutter to find the nearest tree. In that case I needed it now and then when the last cutting tree gets exhausted.

In this case tho, I need an event ran every tick. I imagine making calculations about every unit in the field every second gets too much.

Can't be worse than checking for collision for every unit every tick though ! <img src="smileys/smiley17.gif" border="0" align="middle" />

In fact, if you use only a "sum of deltas" approach instead of checking for the exact distance, I think it would be much LESS expensive than collision checking. Wouldn't hurt to try ! <img src="smileys/smiley2.gif" border="0" align="middle" />

I see

I'm new to all that scripting/coding stuff so excuse my ignorance :)

So you are saying Magistross that using collisions for detection also runs check every tick for all units? Not good.

I'll try your approach and will run some stress tests.

Thanks