Navigation in 2D space

Official forum for the Chipmunk2D Physics Library.
Post Reply
Ostsol
Posts: 12
Joined: Sat Jan 26, 2008 9:16 pm
Contact:

Navigation in 2D space

Post by Ostsol »

Navigation in a 2d space has been a difficulty for me a number of years, now, and I cannot seem to find any tutorials on the subject. Previous methods I've tried delt with playing with angles, resulting in several messes that didn't work so well. My latest attempt seems to work better, as I've taken the bit of knowledge that the dot product between two vectors is the cos of the angle between them. Using that, one can ignore angles entirely and concentrate on the vectors themselves.

Some background: the basic problem is this: given a starting point and a destination point, make an object move to the destination, accelerating until the object must decellerate to reach the destination at a velocity of zero. This, by itself, is easy. The problem is one-dimensional and it is trivial to convert the solution to apply to a two-dimensional or even a three-dimensional space.

Unforunately things get difficult when you start in a 2D space and add an initial velocity that may be on a vector entirely divergent from the vector to the destination. You have a problem whereby you not only have to accelerate to the target, but you must also negate the object's initial movement away from the target.

The easiest solution is to start off by stopping the object's movement entirely, then accelerating toward the target. This works, but not so well in a game situation. What I want is to perform both of those actions simultaneously.

My solution is to calculate two vectors: the first being the object's current velocity in the direction of the target and the second being how fast the object's path is diverging from the vector to the target. This is best illustrated by the following diagram:

Image

The blue line is the vector (not normalized) toward the destination. The red line is the current velocity vector. The green line partially along the blue line is the componant of velocity in the direction of the target and the green line at a right angle to that is the component of velocity divergent from the target.

Logically, it follows that to move toward the target one must reduce the length of that divergent vector to zero. This is easy: normalize that vector, negate it, and apply a force along it. Similarily, the issue of accelerating toward the target is returned to a one-dimensional problem. Both of these operations can effectively be performed simultaneously, simply by adding the forces resulting from each.

How does once come up with the vectors? As I said: use a dot-product. The dot-product of the normalized velocity and direction-to-target vectors is the cos of the angle between them. What we want are vectors that are at right-angles to each other, so this turns into a right-angled triangle. Some basic trigonometry and some basic Pythagorous and we have both the magnitude of the forward velocity and the divergent velocity. The forward velocity vector is derived by normalizing the vector to the target and multiplying by the forward velocity magnitude.

Unfortunately, finding the vector for the divergent velocity is not so simple. Finding the right angle to a vector is accomplished by negating either the x or y components, depending on the situation. The vector must be on the same side as the initial velocity vector. I. . . ended up with a massive "if" structure:

Code: Select all

    if vny > 0:
        if dny > 0:
            if vnx < dnx:
                err = (-dny, dnx)
            elif vnx > dnx:
                err = (dny, -dnx)
        else:
            if abs (vny) < abs (dny):
                if vnx < dnx:
                    err = (dny, -dnx)
                elif vnx > dnx:
                    err = (-dny, dnx)
            else:
                if vnx < dnx:
                    err = (-dny, dnx)
                elif vnx > dnx:
                    err = (dny, -dnx)
    else:
        if dny > 0:
            if abs (vny) < abs (dny):
                if vnx < dnx:
                    err = (-dny, dnx)
                elif vnx > dnx:
                    err = (dny, -dnx)
            else:
                if vnx < dnx:
                    err = (dny, -dnx)
                elif vnx > dnx:
                    err = (-dny, dnx)
        else:
            if vnx < dnx:
                err = (dny, -dnx)
            elif vnx > dnx:
                err = (-dny, dnx)
"err" is the vector we want, while "vnx" and "vny" are the components of the normalized velocity vector, and "dnx" and "dny" are the components of the normalized vector to the destination. I'd really like to reduce this massive structure, if possible. Can anyone help, here?

I hope the rest of this post helped other who are also interested in this problem. :)

(After this I need to account for rotation, making it so that the object must turn in order to accelerate in a particular direction -- accounting for angluar velocity, of course. . .)
User avatar
slembcke
Site Admin
Posts: 4166
Joined: Tue Aug 14, 2007 7:13 pm
Contact:

Re: Navigation in 2D space

Post by slembcke »

I've actually done something similar before for an autopilot for a prototype I made.

What I did was to blend the two thrust values together. I'd add the maximum thrust in the direction to negate the relative velocity to the maximum thrust in the direction to accelerate/decelerate the ship. (I'd also blend in other thrust values for orienting the ship so the biggest thruster would point in the direction of the greatest need) Once all these thruster values were added up, I'd scale them all back so that no thruster would be running at more than 100% power.

I played with the blending values a bit, but it always seemed to work fine when the weights were all the same for different priorities with the potential exception of orientation which was better with a smaller weight. It worked well in cases when you were close to the target, but had a large difference in velocity as well as when you were far away with a small relative velocity. This was because the smaller factor was usually eliminated quickly, thus dropping it's effective blending value to 0 and giving priority to other factors. This was very cool to watch, especially when you assigned a group of other ships to fly in formation with yourself.
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
Ostsol
Posts: 12
Joined: Sat Jan 26, 2008 9:16 pm
Contact:

Re: Navigation in 2D space

Post by Ostsol »

Yeah, formations one of the things I eventually want to simulate with this.

By the way, it seems that angles in Chipmunk are oriented in a rather different way from what I'm used to. I expected pi/2 to point directly to the right, but instead it points left. The rotation vector for that angle is (0,1), but I expect that to be straight up. I don't think that it's my Python bindings doing this (I'm not using PyMunk; I made my own using Pyrex/Cython). What's with this?
User avatar
slembcke
Site Admin
Posts: 4166
Joined: Tue Aug 14, 2007 7:13 pm
Contact:

Re: Navigation in 2D space

Post by slembcke »

I think you have your coordinates switched or something. (0, 1) is correct and points up on the y axis. I use the "classical" definition of radians or whatever you want to call it. 0 radians starts on the x axis and goes around counterclockwise.

http://en.wikipedia.org/wiki/Radian
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
Ostsol
Posts: 12
Joined: Sat Jan 26, 2008 9:16 pm
Contact:

Re: Navigation in 2D space

Post by Ostsol »

Ah, I had not known about that definition. I've always taken for granted declarations in various tutorials for other systems that 0 degrees is always up. I'll have to adjust some of the shapes I create to take this into account, too. Thanks!
Post Reply

Who is online

Users browsing this forum: No registered users and 14 guests