0

I get the positions of 5 enemies in the game in vectors. Depending on the distance I choose, the number of enemies can vary from 0 to 5. I need to know their vectors each time to check whether it is possible to draw a straight line through a certain number of heroes (vectors).

After that, my hero will have to use his ability called wall. It consists of 2 start and end vectors. Thus, check whether my hero can put a wall on the enemies in the line to catch them

Let's say there are 3 enemy heroes whose positions I can get. I need to find out if I can pass through them directly, in order to use the ability on them.

1

Here's what using the ability looks like in the game

2

Here is getting the vector of one of the heroes 3

The ability itself can be twisted at a certain point. But anyway, it is necessary that the wall would touch several heroes 4

Wherever I move the mouse, I can put it in the desired position. But unfortunately it takes a lot of time, so I would like to automate 5

The coordinates of the wall itself, or rather its two edges, I can also get, but only after the ability has been used 6

Aloex
  • 3
  • 4

4 Answers4

0

Any line in the plane can be described by an equation a*x + b*y + c = 0 with (a, b) ≠ (0, 0). Note that if you have an equation of this form, then multiplying each coefficient a, b, c with the same number yields an equation describing the same line. That's the reason (a, b, c) is called a homogeneous coordinate vector for that line.

How do you find a, b, c? One simple approach would be treating this as three linear equations in three unknowns. You plug in the x and y coordinates for all your three points, and get tree equations for a thorough c. However, there is a catch. Since the right hand side of each equation is zero, a = b = c = 0 is always a solution. In those cases where there is only one solution, that will be it. So in order for there to be a line, you need more than one solution. The mathematical tool to determine whether a set of equations had more than one solution is the determinant. It is zero if the system has no single unique solution.

Long story short: three points are collinear (on a line) if

    ⎛x1 y1 1⎞
det ⎜x2 y2 1⎟ = 0
    ⎝x3 y3 1⎠

The homogeneous coordinate vector describing the line world correspond to the kernel of that matrix.

Of course, if your input coordinates are floating point numbers, exact zero is unlikely. Presumably that wall does allow for some error in some way, and you'd need to tell us about that in order to get an answer that models this aspect correctly. In the mean time, know that the absolute value of the determinant above is proportional to the area of the triangle created by these three points. So if your were to pick a constant threshold value, the farther your enemies are apart along the direction of the wall, the less they could deviate from the straight line without violating that threshold.

MvG
  • 57,380
  • 22
  • 148
  • 276
  • 1
    The answer is mathematically correct. But practically it does not answer the question. OP wants to work with approximate lines, it is pretty clear from the pictures in the question. In other words, `det` will never be equal to zero exactly. – Egor Skriptunoff Jun 06 '21 at 20:26
  • @Egor, you probably have a point there. I don't know the game, and in theory it might be based on a coarse square grid. But if not, the question probably should be specific about what kind of deviation from an exact line is permitted. I'd imagine e.g. a circle around each opponent which must be intersected by the line. That makes this a different question with a different answer. Using the determinant with some error threshold might work as a first approximation of that, but it wouldn't be exact either. – MvG Jun 06 '21 at 20:50
0

If one prefers geometry to linear algebra... Then One can compute the dot product of (unit-vector1. Unit-Vector2). That is equal to the SIN of the angle between them.

So if unit vector is the shooter position to target1, unit vector2 is the shooter to target2, etc... then when DOTPRODUCT(Vector1,vector2) = 1 and DOTPRODUCT(Vector1,vector3) = 1, then the three points are in syzygy.

And repeat from shooter to as many targets as you have to determine whether some or all of the points are in syzygy.

Holmz
  • 714
  • 7
  • 14
0

From your statement that there is a start and an endpoint I take that you select two enemys and want to trap anything in between.

So you're actually not looking for a straight line that can be drawn through your enemy positions but if they are withn a rectangle. It would be very unlikely and for more points nearly impossible that they are all collinear anyway.

So it becomes quite trivial. You draw a line through start and end enemy. Then you check the remaining enemies distance to that line vs the width of your AoE. Maye you want to also handle some body width in that calculation.

https://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line

Piglet
  • 27,501
  • 3
  • 20
  • 43
0

You can describe all points belonging to line (x0, y0) + (dx, dy)t = (x1, y1). Chose any two points and t as 1 and you will get (dx, dy) for line connecting two dots. Now you will need to find distance between this line and (x2, y2). it is distance between (x2, y2) and (xd, yd), where on one hand (xd, yd) = (x0, y0) + t1(dx, dy) and on other hand (xd, yd) = (x2, y2) + t2*(-dy, dx). Solving this two equations you will find t1, t2, (xd, yd) and distance between (x2, y2) and (xd, yd), which is distance between (x2, y2) and line, connecting (x0, y0) and (x1, y1).

Knowing this, you select dots with min_x and max_x and calculate ditance between line, connecting said dots and rest of the dots. If distance is lesser then some threshold of your choice, then you can assume that you can have line passing through all dots.

Andrew Kashpur
  • 736
  • 5
  • 13