Technically, there are three ways to do this. The first one I learned was based on trig. You have to determine the angle of movement, use a polar coordinate system with the origin at the current position of the entity to represent the movement, and then convert back to Cartesian coordinates. This is the worst solution. Computers don't do trig well. The trig functions, which are used for the conversions, require a lot of processing power. It also turns out that it requires more memory than non-trig solutions. It is almost always best to avoid using trig whenever possible, so we will not be discussing this solution any further.
Triangle Scaling
The second solution is geometric triangle scaling. Really, what we are working with here is a vector. The vector is represented as the line from the current position to the desired position. Most vectors can be represented as triangles, and geometric scaling of triangles is easy.
In this case, the unit is starting at (0, 0), and the destination is (10, 6). To find the movement vector, we subtract the starting point from the ending point: (10, 6) - (0, 0) = (10 - 0, 6 - 0) = (10, 6). The triangle representation has a base of 10, and a height of 6. Scaling this is easy. Just multiply the height and width of the triangle by some scalar value. In this case, we want to scale it down, so that value will be between 0 and 1, depending on the speed of the movement we want. Now, this is where we are going to come up against the limitation of this method, but it may not be initially obvious.
Before we can determine the scaling value, we have to decide how fast we want the entity to move. We could scale by time passed, but this is more complicated, so we are going to assume that the time value is static (the game is bound to a set frame rate). So we will say that in one time increment (one game frame), the unit can travel 3 grid units in either dimension. We want to keep the unit on that line, so we have to make sure both dimensions are scaled by the same value. The x movement is bigger, so that will be the limiting dimension. So, we divide the speed (3) by 10 to get the scaling value, which will be 0.3. Now we multiply both sides of the triangle by that value, which gives us 3 on the x axis and 1.8 on the y axis (position should be stored as a float in most cases). Now we add this to our current position, giving us the new position of (3, 1.8). This is where we start at the next game loop, and we have to do all of the math over again.
This is the function, written in Python, for this algorithm:
def move(src, dest, speed):
'''Move entity using geometric triangle scaling
src - Tuple with x and y coordinates of current location
dest - Tuple with coordinates for destination
speed - Maximum distance moved on either axis
'''
# Find the triangle
diff = (dest[0] - src[0], dest[1] - src[1])
# If we can get to the dest at this speed, do it
if diff[0] < speed and diff[1] < speed:
return dest
# Figure out the scaling value
scalar = 0
if diff[0] > diff[1]:
scalar = float(speed) / diff[0]
else:
scalar = float(speed) / diff[1]
return (src[0] + (diff[0] * scalar),
src[1] + (diff[1] * scalar))
This algorithm will work fairly well, but it has the effect of sort of warping the map around the current unit (this is not a visible warping; rather it is a sort of temporal warping; ignore this if you still don't get it). The problem is that unit move faster at angles than they do parallel to the x or y axes.
Linear Algebra
When doing this kind of thing in game programming, the best solution is linear algebra. Linear algebra can do pretty much everything trig can do, without the need for a polar coordinate system. This means that you can do most things without the need for trig functions. The only exception is rotation using an angle, because angles are already polar and must be converted.
The linear algebra solution to this particular problem requires a bit more math, but it also eliminates temporal warping. In other words, distances are the same regardless of the angle of motion. The movement range graph would be represented as a circle instead of a square. For real-time games, this is what you want. Interestingly, this method is very similar to triangle scaling, with a few important differences.
In any case using a Cartesian coordinate system, vectors can be represented as triangles. For this though, it is probably easier to treat vectors as vectors. Before we start, there is some important vector math we will need to know.
The first vector math we need to know should already be familiar. We are going to represent vectors in the following format: <x, y>. This will help avoid confusion with coordinates: (x, y). (Technically coordinates are position vectors, but we need to differentiate between position vectors and vectors representing desired movement.) We will need to know the length of our movement vector. The length of a vector is found using the Pythagorean Theorem, as if the vector elements were the sides of a triangle. For a vector <x, y>, sqrt(x^2 + y^2) = length. This length will always come out positive. In linear algebra, this is called the "norm" of the vector, and for a vector v it is represented as |v|.
The second important vector math is the unit vector. The unit vector for any vector points in the same direction as that vector, but it is exactly 1 unit in length. Unit vectors represent directions (or angles). This is important, because we will want to move our entity a set distance in a specific direction, without worrying about the distance from the source to the destination. The unit vector is found by dividing the initial vector by its norm, represented as v/|v| = u.
This should be enough vector math to create the algorithm we need. We start by finding the difference between the source and destination vectors: m = d - s (bold symbols are 2 element vectors). Given s = (1, 1) and d = (2, 3), m = (2, 3) - (1, 1) = (2 - 1, 3 - 1) = <1, 2>. So, the total movement the entity needs to get to the destination is <1, 2>. We don't actually care about this though, because we are only taking one step in this path. We need to know where that step lands.
Now that we have m, we can use it to figure out the direction of our movement. This is the unit vector: u = m/|m|. Using the m we just calculated, that is u = <1, 2> / sqrt(1^2 + 2^2) = <1, 2> / sqrt(5) = <1, 2> / 2.24 = <1/2.24, 2/2.24> = <0.447, 0.894>. If you take the norm of u, it should be exactly 1 (slightly less, because I rounded).
We could add the unit vector to s (the source) to move the entity exactly 1 unit closer to d (the destination). This is rarely what is needed though. In this case, let's say the entity has a speed of 2 units per game loop. This means we need to move the unit by the value of u twice. We can find the vector for this by multiplying u by the speed. The new vector will be 2u = <0.447 * 2, 0.894 * 2> = <0.894, 1.789>. We want to add this to s to find the new position: p = s + 2u = (1, 1) + <0.894, 1.789> = (1 + 0.894, 1 + 1.789) = (1.894, 2.789). So, that is our new position, and it is exactly 2 unit closer to d than the original position, on the line between s and d.
This may still be confusing. If it is, that is fine for now. This math has tons of applications in game development, from drawing lines to gradating colors to movement. It is definitely worth learning, but if all you need to do right now is move entities from one point to another in steps of a specific distance, you can work on that later. Right now, I am going to give you the function, in Python, for finding the next step along a straight line.
def move(src, dest, speed):
'''Move toward destination by a set number of units
src - The current position of the entity
dest - The final destination
speed - The number of units to move
'''
# First we need the difference between dest and src
# Note that this corresponds with m above
diff_v = (dest[0] - src[0], dest[1] - src[1])
# We need the norm to find the unit vector
# Note that you need to import math for this to work
norm = math.sqrt(diff_v[0]**2 + diff_v[1]**2)
# Let's make sure we do not overshoot
# Since norm is the length of diff_v, if it
# is less that the speed, we have arrived at
# the destination.
if (norm <= speed):
return dest
# Now we can extract the direction from diff
unit_v = (diff_v[0] / norm, diff_v[1] / norm)
# Now we will calculate the actual movement we need
move_v = (unit_v[0] * speed, unit_v[1] * speed)
# Now we just need to add the movement to the
# current position and return the result
return (src[0] + move_v[0], src[1] + move_v[1])
Given a source, destination, and speed (movement distance), this function will return the next step. Note that you can take some shortcuts with this that will save memory and processing power. For example, you can combine the unit_v and move_v steps into a single step to save memory. Doing that will allow you to precalculate speed / norm, which will reduce the number of divisions in the function by half. The following code could replace the unit_v and move_v parts:
scalar = speed / norm
move_v = (diff_v[0] * scalar, diff_v[1] * scalar)
The scalar variable only holds one float, instead of a tuple of two floats, and we trade the two divisions for just one. This may seem minor, but this function will get called for every moving entity every game loop, so the small difference will add up quickly.
In most cases, this linear algebra solution will be the best way to manage real-time movement.
I hereby release the code presented in this article into the Public Domain. In jurisdictions that do not allow this, all parties may use this code under a license allowing copying, modification, distribution, commercial use, and non-commercial use freely, with or without attribution.
No comments:
Post a Comment