4
\$\begingroup\$

I have an entity that is allowed to move in a fixed amount of directions. Let's call a the angle between two directions. r is the length of each direction vector. Now the entity wants to head from its current position (x1,y1) to a target (x2,y2) in one of the fixed directions. Instead of getting the direction that the entity should head into, I want to get a weight for all directions that is based on how close the entity gets to the target with that direction, so that I can combine those weights with other things like avoiding some direction for example.

I thought about calculating the distance from the new positions to the target and then use the closest distance (the one in which the entity heads in the direction directly to the target) to get a weighting from 1 to zero for the other directions.

Now I was wondering if there is some other way to get the weights without having to calculate the distance for each direction. Maybe there is some sort of relation between the angle from the ideal direction and the distance that could be used to calculate the weights instead? So far I've figured out that at least there is no no linear relation between the angle and the distance.

Here is an image to hopefully clear things up a bit: problem overview

\$\endgroup\$
  • \$\begingroup\$ What is your goal, a faster solution? \$\endgroup\$ – wondra Nov 16 '15 at 18:04
  • \$\begingroup\$ @wondra: a faster solution is the primary goal since it will be performed quite often (likely also for other behaviours). But I'm also just curious. \$\endgroup\$ – Cyborg Nov 16 '15 at 19:28
  • \$\begingroup\$ If you want different behavior you should specify what behavior you are after - if you don't, there is no correct answer. And for faster solution, I pretty sure there isnt better one that includes euclidean distance (there is for example squared euclidean distance or manhattan distance though). \$\endgroup\$ – wondra Nov 16 '15 at 19:50
  • 1
    \$\begingroup\$ Wouldn't this simply be accomplished by getting the actual required direction vector, and then calculating the dot product of your possible directions on that vector? \$\endgroup\$ – Peethor Nov 16 '15 at 21:07
  • \$\begingroup\$ @Peethor: would the dot product not give me the angle between the two vectors? What I'm interested in is, given an angle, the actual required direction vector and a length, what is the relation between the angle and the distance you are off from the ideal distance if you would have followed the actual required vector. I think there is atleast symmetry, as in, being 5 degrees off on the left side of the vector is the same as being 5 degrees off on the right side. \$\endgroup\$ – Cyborg Nov 21 '15 at 12:58
1
\$\begingroup\$

What you want is the dot-product between each direction vector and the vector to the target. This value will be maximised by the direction which will take you closest to the target.

If you are not familiar with the dot product:

u . v = sum(u_i * v_i)

where the sum is over the components of the vectors.

Edit: Please do ensure that the vectors are normalised (i.e. have magnitude = 1) before conducting the dot product. You can normalise a vactor by dividing by its magnitude.

\$\endgroup\$
  • \$\begingroup\$ The direction vectors must be normalized first of course - obvious to you and I but perhaps not to OP. \$\endgroup\$ – Pieter Geerkens Mar 11 '16 at 22:08
0
\$\begingroup\$

The distance between the centre of the circle (x1,y1) and the target (x2,y2) is:

D = sqrt((x1-x2)² + (y1-y2)²)

So the distance between the target and any point on the circle varies between D - r and D + r.

For a given angle a with the horizontal axis, the position of a point on the circle is:

x = x1 + r·cos(a)
y = y1 + r·sin(a)

And so the distance between (x,y) and (x2,y2) is:

d = sqrt((x1 + r·cos(a) - x2)² + (y1 + r·sin(a) - y2)²)

All these values can be combined together to compute a weight that only depends on the value of a and goes from 0 (worst choice for a) to 1 (best choice for a):

W = (D + r - d) / 2r

I hope this can be helpful.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.