1

I'm looking to create AI that elegantly rounds corners. To compute the path around a corner I have a set of 2d points start and end that exist exclusively as 90 degree angle pairs like in the image below.

Each point is either in the "north", "south", "east", or "west" most portion of the ellipse, and I can extrapolate the a and b values for the major and minor axes of the ellipse along these points.

The simulation is played on a grid, so the ellipse will never be rotated -- the major and minor axes will lie parallel to the x and y axes.

enter image description here

Moving the point along an ellipse by an angle is simple:

x = x + (a * math.cos(angle))  # where a is major axis
y = y + (b * math.cos(angle))  # where b is minor axis

However, I want to control the speed at which the AI traverses across the arc on the ellipse between the two points and eventually have them stop at the end position.

Ultimately, I need to compute the following:

  1. The remaining_distance between start and end along the ellipse
  2. The new location of a point after moving distance across the ellipse

Questions:

  1. Are there common tools/solutions for computing the above?
  2. Are there better or more common solutions for this problem in AI, gamedev, or other practices? I saw Bezier curves came up in my search, for example.

Thanks!

Meta:

I found similar questions asking for this problem on the stack exchange, but none really seemed to fit my use case or answered the question by offering language-specific non-python solutions.

I chose to ask here rather than the mathematics stack exchange, because I imagine there may be other solutions for the same problem more commonplace in gamedev and other programming projects.

Justian Meyer
  • 3,623
  • 9
  • 35
  • 53
  • 1
    It is very hard to find ellipse arc length, because there is no analytical formula, so traveling distance approach seems wrong. Perhaps angle aprroach (and angle velocity) is enough for your purposes. – MBo Jan 17 '20 at 08:32
  • You mention that the simulation is on a grid. Are all your ellipses the same size? In that case, the relation between distance and angle is fixed, and you can simply use a lookup table and some linear interpolation. Edit: The general case of ellipse arc length seems to be nontrivial. So I would try to exploit the fact that you are probably only dealing with a fairly limited set of different ellipses, for which you can pre-compute a lot. – DCS Jan 17 '20 at 08:34
  • @MBo Could you expand on "angle velocity" for this case? Are you suggesting going with a physics based approach? I was hoping to avoid that since there otherwise aren't other physics related elements like velocity, momentum, etc. related to the agents. – Justian Meyer Jan 17 '20 at 08:39
  • @DCS While the simulation exists on a grid and there are set paths for moving between cells, agents can effectively move freely within the cells. There may be some common paths in its current state, but this will change soon. – Justian Meyer Jan 17 '20 at 08:39
  • 1
    @Justian Meyer Note that your "angle" is not real angle between center-point and OX axis. It is just a parameter for ellipse description (sometimes referred as eccentric anomaly). It might be used as very approximate angle, but is not exact and looks unappropriate for accurate physics simulation (when small diversities might cause strange behavior) – MBo Jan 17 '20 at 08:45
  • @MBo that's helpful. Thank you – Justian Meyer Jan 17 '20 at 08:47
  • 2
    Have you look at Kepler equation? – Troopers Jan 17 '20 at 08:48
  • @Troopers I haven't. I'll need to read up on it. At least a glance, it seems relevant. – Justian Meyer Jan 17 '20 at 08:49
  • Doing this analytically every time sounds quite computationally expensive regardless of the equation you end up using, especially in a game-dev context. I'm wondering whether you could work with some pre-computed piecewise linear grid around your corners, or are the obstacles moving around? – DCS Jan 17 '20 at 08:55
  • Arc length on an ellipse: https://math.stackexchange.com/questions/433094/how-to-determine-the-arc-length-of-ellipse – High Performance Mark Jan 17 '20 at 09:36
  • @DCS The more I’m thinking on it, the more plausible it seems. Definitely a small amount of space to trade for reduced computations per frame. – Justian Meyer Jan 17 '20 at 09:44
  • @JustianMeyer This is a library you might find helpful to create elegant piecewise linear paths in complex geometric environments: https://www.cs.cmu.edu/~quake/triangle.html It was made for finite element simulations, but I have (ab-) used for other stuff as well. – DCS Jan 17 '20 at 10:14
  • [This](https://threejs.org/docs/#api/en/extras/curves/EllipseCurve) could help you but it's in javascript – Troopers Jan 17 '20 at 11:13
  • @DCs cool library! It may be a bit overkill for the simulation I’m making though as I don’t have to deal with complex geometric pathways with a grid. – Justian Meyer Jan 17 '20 at 19:45
  • Hm I wonder if there is a physics-based solution that may actually be simpler. I discounted it at first, but I see a place where I could build it that would make sense. – Justian Meyer Jan 17 '20 at 19:46
  • 1
    @JustianMeyer see [Solving Kepler's equation](https://stackoverflow.com/a/25403425/2521214) that simple `for` will convert from `M` to `E` angle ... however I got the feeling you want just control the speed from start velocity to end one (without any relation to gravity) which can be done just by modulation angular increment of your elliptic angle parameter .... but it need to be tweaked to fit into the arclength ... – Spektre Jan 18 '20 at 09:52
  • @Spektre Thanks for that! I have a *lot* of reading to do, especially if I need to tweak it for arclength. – Justian Meyer Jan 19 '20 at 04:35

0 Answers0