Thread: Mapping Math View Single Post
 04-04-2006, 07:02 AM #1 PipeDream Moderator   Code Moderator   Join Date: Feb 2006 Posts: 1,405 Submissions (6) Mapping Math Math for Map makers I condense a little practical computer math here, for writing efficient code and avoiding bugs that are a pain in the ass to track down. This is directed at people who know a little JASS and are familiar with algebra and a little trig but are relatively new to programming-a significant fraction of the mapping community, I believe. It will be a mix of general principles and a couple of my pet peeves, hopefully sufficiently general to be useful for many. If you have suggestions for topics, please contribute! Computational Complexity - describing an algorithm's efficiency An algorithm is a set of instructions for getting something done. To rapidly analyze the efficiency of an algorithm, we estimate its performance as we adjust its input parameters. For example, if we have an array whose values we wish to sum, we would walk down the array and sum each value individually in n steps, where n is the length of the array. We say that it takes "O(n)" time to run this algorithm. That O() notation is, for all practical purposes*, just a way to say roughly. Roughly means we ignore constant factors. For example, if our algorithm sums 3 arrays, we don't say O(3n), we still say O(n). With this language in hand, let's look at an algorithm for solving a closely related problem, something I ran into recently: JASS:```function EncodeName takes string s returns integer if s == "" then return 0 else return EncodeChar(SubString(s, 0, 1)) + EncodeName(SubString(s, 1, StringLength(s))) endif endfunction``` At first glance this is a rather clever way to sum a string. Rather than using those loop commands, it uses recursion, breaking a string down into shorter and shorter pieces until it reaches the empty string, to which it assigns a value of zero. However, notice that at each iteration it runs two SubStrings, one of which creates a new string of length O(n). This requires O(n) time, because the computer must copy characters from the original to the new string. This algorithm is then executed n times, for a total cost of O(n^2). We could easily write an O(n) version like so: JASS:```function EncodeName takes string s returns integer local integer sum = 0 local integer i = StringLength(s) -1 loop exitwhen i < 0 set sum = sum + EncodeChar(SubString(s,i,i+1)) set i = i - 1 endloop return sum endfunction``` The O(n^2) version works fine in practice because names are short. Suppose it takes a microsecond to run- at thirty characters n^2 is still only 900, so it will takes less than a millisecond. But at a thousand characters, an easy length for a string to get to when it is filled with fanciful color gradients, it will take a second, in comparision to the O(n) algorithm which will take only a millisecond. Trigonometry, Vectors and Lines - or ignoring everything I said above and looking for trivial optimizations PolarProjectionBJ is a terribly useful function. You take a location, choose an angle, and then place a new point any distance away on the line that your angle and location define. Internally, it uses two magical functions, Cos() and Sin(). Cos(t) returns the x coordinate of the point on a unit circle at angle t, Sin(t) returns the y coordinate. When you combine the x and y, you get the radius unit vector. This is what makes PolarProjection and polar coordinates so useful. All lines can be easily parameterized, as all their points can be radius vectors of some circle centered about a location. Using X,Y coordinates are tricky, because you have only two sets lines that are constant in one parameter- the x axis, and the y axis, with an arbitary origin. However, using polar coordinates for lines is often a case of smashing a peanut with a sledgehammer. Suppose our spell creates evenly spaced effects on a line between caster and target location (or target unit's location). It is commonly written like this: JASS:```function CreateEffectsLoc takes location l1, location l2, integer n returns nothing local real angle = AngleBetweenPoints(l1,l2) local integer i = 1 local real dr = n/DistanceBetweenPoints(l1,l2) local location target loop exitwhen i >= n set target = PolarProjectionBJ(l1,i*dr,angle) call AddSpecialEffectLoc("Abilities\\Weapons\\FarseerMissile\\FarseerMissile.mdl",target) call RemoveLocation(target) set i = i + 1 endloop set target = null endfunction``` Let's translate this code to reals and natives to to see exactly what it does JASS:```function CreateEffectsRealPolar takes real x1, real y1, real x2, real y2, integer n returns nothing local real angle = Atan2(y2-y1,x2-x1) local integer i = 0 local real dr = (n+1)/SquareRoot((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)) local real tx local real ty loop exitwhen i >= n set tx = x1+(i+1)*dr*Cos(angle) set ty = y1+(i+1)*dr*Sin(angle) call AddSpecialEffect("Abilities\\Weapons\\FarseerMissile\\FarseerMissile.mdl",tx,ty) set i = i + 1 endloop endfunction``` We are running Atan2 and SquareRoot at start along with one Sin and one Cos per iteration, for a total of 2+2n slow math functions! This can be improved manifoldly just by caching a little data. JASS:```function CreateEffectsRealPolarCached takes real x1, real y1, real x2, real y2, integer n returns nothing local real angle = Atan2(y2-y1,x2-x1) local integer i = 0 local real dr = (n+1)/SquareRoot((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)) local real tx local real ty local real unitx = dr*Cos(angle) //No need to compute them more than once, the way PolarProjectionBJ would. local real unity = dr*Sin(angle) loop exitwhen i >= n set tx = x1+(i+1)*unitx set ty = y1+(i+1)*unity call AddSpecialEffect("Abilities\\Weapons\\FarseerMissile\\FarseerMissile.mdl",tx,ty) set i = i + 1 endloop endfunction``` This reduces it to 4 transcendental calls. However, how would you write this using locations and PolarProjectionBJ? It is not entirely clear. PolarProjectionBJ is a leaky abstraction: You don't realize something is wrong, nor is it clear how to fix it, unless you look at its internals. If you need the angle of the line for another purpose, such as to create a unit facing in a certain direction, then using this "CreateEffectsRealPolarCached" version may be most appropriate. But we can do even better if we do not need the angle. (Cos(angle),Sin(angle)) is a unit vector in the direction of location 1 -> location 2. But we have a vector in this direction, and we know its length! ((x2-x1),(y2-y1))/Length = (Cos(angle),Sin(angle)) In this case, we don't even need to know its length, because we are just dividing it up into equal portions. JASS:```function CreateEffectsRealCart takes real x1, real y1, real x2, real y2, integer n returns nothing local integer i = 0 local real tx local real ty local real unitx = (x2-x1) / (n+1) local real unity = (y2-y1) / (n+1) loop exitwhen i >= n set tx = x1+(i+1)*unitx set ty = y1+(i+1)*unity call AddSpecialEffect("Abilities\\Weapons\\FarseerMissile\\FarseerMissile.mdl",tx,ty) set i = i + 1 endloop endfunction``` This completely eliminates the transcendental functions. There is one messy thing. If we do need to know its length, and we need proper unit vectors, we have to add a constant to the squareroot: SquareRoot(dx*dx+dy*dy+0.1). Otherwise we will run into a divide by zero, which warcraft handles by killing the thread. The 0.1 will under normal circumstances have no effect due to rounding error. For example, if we want to move a unit a constant distance in the direction of the target: JASS:```function MoveUnitTowards takes unit u, real x2, real y2, real distance returns nothing local real x1 = GetUnitX(u) local real y1 = GetUnitY(u) local real dx = x2 - x1 local real dy = y2 - y1 local real scale = distance/SquareRoot(dx*dx+dy*dy+0.1) call SetUnitX(u,x1+dx*scale) call SetUnitY(u,y1+dy*scale) endfunction``` Numerical Error Computers can only store a finite amount of information about a number. JASS's real type uses a floating point format to do this. It is called floating point because it uses scientific notation- a number like 384 is written as (.5+.25)*2^(8+1) or .75*2^9. The result of this is rounding error. In general, a computer game is very insensitive to it, because humans can't perceive that many decimal places, optimally around 7 for the 32b floats used by JASS. However, it is possible to accidentally amplify this error. The principal way to do this is subtraction. Here is a plausible, if artificial example. Suppose you wish to measure the velocity or direction of a unit. You might write a timer callback like this: JASS:```//xnew,ynew,xold,yold,u are globals for brevity- use game cache in practice. //dt is the timer period function MeasureSpeed_callback takes nothing returns nothing set xnew = GetUnitX(u) set ynew = GetUnitY(u) set vx = (xnew-xold) / dt set vy = (ynew-yold) / dt set v = SquareRoot((xnew-xold)*(xnew-xold)+(ynew-yold)*(ynew-yold))/dt call BJDebugMsg("v: "+R2S(r/dt)+"vx: "+R2S(vx)+"vy: "+R2S(vy)) set udg_xold = udg_xnew set udg_yold = udg_ynew endfunction function MeasureSpeed takes nothing returns nothing set xold = GetUnitX(u) set yold = GetUnitY(u) call TimerStart(CreateTimer(),0.001,true,MeasureSpeed_callback) endfunction``` The unit in question is at a coordinate far off such as 10,000 by 10,000. It is user controlled and you wish to know if it tries to move north-south. Its movement speed is 100. In terms of an angle, the x,y velocities will be 100*cos(theta),100*sin(theta). Consider small values of theta, for which sin theta ~ theta. We expect to see a velocity of 100*theta, roughly. In the 0.001s between timer elapses, this will be a distance of .1*theta. Thus at one moment it may be at 10,000, the next 10,000.1 We write all 7 digits: 10,000.10 - 10,000.00 = .10 Our result has only two digits of precision! If the unit moves 10,000.009, or +- 5 degrees from the x axis, our routine will not notice- it will round to zero. In practice, though, this does not happen! Try making a wide skinny map- 10,000 or so. Move a footman out at one edge. Then try ordering him to the other edge. If you do not order him far enough off the x axis, he will move with 0 y velocity! When he gets close enough to the point, his behavior "snaps" and he will suddenly start to move in the proper direction.** That example tried to pack all the error in at once. You can also accumulate it in little bits and pieces. For example, if you use reals to count, you will get it wrong with out a tolerance check- JASS:```function sum takes nothing returns nothing local real sigma = 0 local real inc = 0.1 local integer i = 0 loop exitwhen sigma >= 10000 set i = i + 1 set sigma = sigma + inc if(ModuloInteger(i,1000)==999) then call TriggerSleepAction(0.) call BJDebugMsg("sigma: "+R2S(sigma)+"i: "+I2S(i)) endif endloop call BJDebugMsg("final i: "+I2S(i)) endfunction``` This code ought to print a final i of 100,000. Testing it out, I find that i, the number of times the loop really ran is 100,267! While both these examples are artificial, you can imagine a middle ground. For example, if you tried to measure the distance moved over several iterations of the MeasureSpeed loop by summing the difference at each iteration, you would rapidly accumulate severe error even if you used a larger time interval. This could be fixed by writing down the original position, so that you compute the total distance afresh when necessary. *:Technically, O(f(n)) means that asymptotically the function is bounded above by f(n) **Rounding error, or pathing map oddity?