wc3campaigns
WC3C Homepage - www.wc3c.netUser Control Panel (Requires Log-In)Engage in discussions with other users and join contests in the WC3C forums!Read one of our many tutorials, ranging in difficulty from beginner to advanced!Show off your artistic talents in the WC3C Gallery!Download quality models, textures, spells (vJASS/JASS), systems, and scripts!Download maps that have passed through our rigorous approval process!

Go Back   Wc3C.net > Tutorials > JASS/AI scripts tutorials
User Name
Password
Register Rules Get Hosted! Chat Pastebin FAQ and Rules Members List Calendar



Reply
 
Thread Tools Search this Thread
Old 04-04-2006, 07:02 AM   #1
PipeDream
Moderator
 
PipeDream's Avatar


Code Moderator
 
Join Date: Feb 2006
Posts: 1,405

Submissions (6)

PipeDream is a glorious beacon of light (463)PipeDream is a glorious beacon of light (463)PipeDream is a glorious beacon of light (463)PipeDream is a glorious beacon of light (463)

Default 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:
Collapse 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:
Collapse 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:

Collapse 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
Collapse 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.
Collapse 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.

Collapse 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:

Collapse 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:
Collapse 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-
Collapse 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?

Last edited by PipeDream : 04-21-2006 at 07:59 PM.
PipeDream is offline   Reply With Quote
Sponsored Links - Login to hide this ad!
Old 04-19-2006, 07:58 PM   #2
BertTheJasser
xyzi - our universe
 
BertTheJasser's Avatar
 
Join Date: May 2005
Posts: 742

Submissions (2)

BertTheJasser has a spectacular aura about (111)BertTheJasser has a spectacular aura about (111)BertTheJasser has a spectacular aura about (111)BertTheJasser has a spectacular aura about (111)

Default

I myself expirienced painfully the PolarprojectionBJ thing. This blocked me out for weeks 'n weeks. Your tut is very usefull, not for me, but there are at least 100 which should first read this tut before posting threads, asking things you mentioned and explained. +Rep
__________________
Note: Bye... I had a lot of fun here!
Special thanks to Vexorian who helped me learn jass, the real jass and always helped me when problems occured, I would call him somehow my mentor. Pipedream, who made amazing Grimoire and helped me acclerating my map (currently at 99% finished, no developement atm).

Vote for Linux Ports in general of Blizzard products: http://www.PetitionOnline.com/ibpfl/
BertTheJasser is offline   Reply With Quote
Old 04-20-2006, 01:01 AM   #3
Blackroot
User
 
Join Date: Apr 2006
Posts: 260

Blackroot will become famous soon enough (40)Blackroot will become famous soon enough (40)

Spell Making Session 14 Winner

Default

Wow! I didint realize using the traditional polar projection was so leaky. I didint even realize how off reals were in small quantities. +Rep
Blackroot is offline   Reply With Quote
Old 04-20-2006, 04:38 AM   #4
Vuen
User
 
Join Date: Mar 2003
Posts: 279

Submissions (5)

Vuen will become famous soon enough (64)Vuen will become famous soon enough (64)Vuen will become famous soon enough (64)

Spell making session 4 winner

Default

Quote:
Originally Posted by Blackroot
Wow! I didint realize using the traditional polar projection was so leaky. I didint even realize how off reals were in small quantities. +Rep

Polar projection is not actually leaky. At least, that's not the problem here. At worst it only leaks two location references (not the objects themselves) per call:

Collapse JASS:
function PolarProjectionBJ takes location source, real dist, real angle returns location
    local real x = GetLocationX(source) + dist * Cos(angle * bj_DEGTORAD)
    local real y = GetLocationY(source) + dist * Sin(angle * bj_DEGTORAD)
    return Location(x, y)
endfunction

By "leaky abstraction" he meant that the function is deceptively simple; you don't realize that it takes a ton of computing power to do. People use it in loops and periodic functions without realizing it and it slows their computer to a halt.



Also, reals are not at all off in small quantities. Warcraft can hold extremely small numbers, like 4.26547 x 10^-35 with extremely high precision (less than a millionth of a percent error, regardless of how small your number is).

The problem comes with when you're trying to look at the far decimal places on big numbers. Take a number like 0.236218. A float can hold that just fine. Now watch what happens when you add a million to it and subtract it again:

0.236218 + 1000000 = 1000000.236218

Warcraft can't hold 13 decimal places so it rounds it, which ends up being something like 1000000.2. Subtract a million again:

1000000.2 - 1000000 = 0.2

This simple calculation should in theory give us our number back, 0.236218, but because of rounding error the answer was 0.2, which is off by 15%. This is not because the number is small, but because a million is so large that it makes 0.036218 insignificant.

The moral here is to be very careful when subtracting numbers from eachother. If they are very close together, your result will get rounded. Often, if the numbers are close enough together, the rounding will simply leave zero, which can cause divide-by-zero or can simply make nothing happen at all. Very frustrating bugs to track down without this knowledge.

Last edited by Vuen : 04-20-2006 at 04:53 AM.
Vuen is offline   Reply With Quote
Old 04-21-2006, 01:29 PM   #5
Blackroot
User
 
Join Date: Apr 2006
Posts: 260

Blackroot will become famous soon enough (40)Blackroot will become famous soon enough (40)

Spell Making Session 14 Winner

Default

Well, either way, I did not realize the amount of time you could save by avoiding blizzards math functions :P. It seems like every single math function (Atan, Atan2, Square, Pow, Cos, Sin, Tan, Cot (Might not have tan/cot)) in addition *timesaving* things like locations cause leaks, so its really best to stick with the absolute basics in jass anyways... Atleast, if you're gunning for speed.

And, reals/floats/doubles/extendeds/w/e you want to call them, they're never & never will be 100% accurate. 1/3 = .3333333333333333333333333333333 ect, but you cant hold the whole value of it, you're going to end up losing some accuracy. If you have something that can hold 8k digits, you probably wont notice it. But, blizzard decided to use... 3-4. I will never get why they did that, you end up losing a lot of precision.

Last edited by Blackroot : 04-21-2006 at 01:33 PM.
Blackroot is offline   Reply With Quote
Old 04-21-2006, 02:24 PM   #6
Thunder_Eye
Lol I got a custom title!
 
Thunder_Eye's Avatar
 
Join Date: Aug 2004
Posts: 1,236

Thunder_Eye has a spectacular aura about (92)Thunder_Eye has a spectacular aura about (92)Thunder_Eye has a spectacular aura about (92)Thunder_Eye has a spectacular aura about (92)

Default

Change these to AddSpecialEffect

Collapse JASS:
call AddSpecialEffectLoc("Abilities\\Weapons\\FarseerMissile\\FarseerMissile.mdl",tx,ty) 
__________________
Thunder_Eye is offline   Reply With Quote
Old 04-21-2006, 03:42 PM   #7
blu_da_noob
Nonchalant
 
blu_da_noob's Avatar


Respected User
 
Join Date: Mar 2006
Posts: 1,933

Submissions (2)

blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)

[Quicksilver #2] - 2nd Place[Quicksilver#1] 1st place

Send a message via MSN to blu_da_noob
Default

Quote:
Originally Posted by Blackroot
If you have something that can hold 8k digits, you probably wont notice it. But, blizzard decided to use... 3-4. I will never get why they did that, you end up losing a lot of precision.

They don't use 3-4 decimal place precision. That would be retarded. You're probably just thinking that because R2S 'rounds' it to 3 decimals.
blu_da_noob is offline   Reply With Quote
Old 04-21-2006, 08:01 PM   #8
PipeDream
Moderator
 
PipeDream's Avatar


Code Moderator
 
Join Date: Feb 2006
Posts: 1,405

Submissions (6)

PipeDream is a glorious beacon of light (463)PipeDream is a glorious beacon of light (463)PipeDream is a glorious beacon of light (463)PipeDream is a glorious beacon of light (463)

Default

Oops! Thanks, Thunder.

Blackroot, using locations can be just as fast. See http://www.wc3jass.com/viewtopic.php?t=2542
PipeDream is offline   Reply With Quote
Old 04-22-2006, 12:40 AM   #9
mmx2000
User
 
Join Date: Dec 2003
Posts: 123

mmx2000 has little to show at this moment (7)

Default

Just a tip for your pythagorean theorems: As an alternative to doing (x2-x1)*(x2-x1) in case you have huge variable names or whatever, I believe you can use Pow(x2-x1, 2.0) to square it.
mmx2000 is offline   Reply With Quote
Old 04-22-2006, 01:47 AM   #10
Vuen
User
 
Join Date: Mar 2003
Posts: 279

Submissions (5)

Vuen will become famous soon enough (64)Vuen will become famous soon enough (64)Vuen will become famous soon enough (64)

Spell making session 4 winner

Default

Quote:
Originally Posted by Blackroot
Well, either way, I did not realize the amount of time you could save by avoiding blizzards math functions :P. It seems like every single math function (Atan, Atan2, Square, Pow, Cos, Sin, Tan, Cot (Might not have tan/cot)) in addition *timesaving* things like locations cause leaks, so its really best to stick with the absolute basics in jass anyways... Atleast, if you're gunning for speed.



They don't leak. They're just a mathematical operation. It's not Blizzard's fault that trigonometric functions are slow; it's just a fact of life.

100 years ago, before we had all this fancy electronics, if you wanted to calculate the sine/cosine of a number directly with any decent amount of precision it could take an hour of work. You could take the Taylor expansion and start doing some rather large long-division, or you could take a known sine value and repeatedly doing halfangle/doubleangle computations, or a variety of other ways that take a ridiculous amount of computation...



This is why hundreds, even thousands of years ago, people would spend years writing and publishing "sine tables", which would be an enormous book containing nothing but the sine of every number with, say, 5 decimal places. If you wanted the sine of a number, say 0.26349 you had to break out the book, find page 26, scroll across to the 34th row and 9th column, and that was your answer.

This is not Blizzard's fault. Taking a sine is a big deal. People really take their calculator for granted.
Vuen is offline   Reply With Quote
Old 04-22-2006, 09:23 AM   #11
blu_da_noob
Nonchalant
 
blu_da_noob's Avatar


Respected User
 
Join Date: Mar 2006
Posts: 1,933

Submissions (2)

blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)blu_da_noob is just really nice (398)

[Quicksilver #2] - 2nd Place[Quicksilver#1] 1st place

Send a message via MSN to blu_da_noob
Default

Quote:
Originally Posted by mmx2000
Just a tip for your pythagorean theorems: As an alternative to doing (x2-x1)*(x2-x1) in case you have huge variable names or whatever, I believe you can use Pow(x2-x1, 2.0) to square it.

That's doing exactly the same thing, and might even be slower depending on how exactly the native Pow function works. The only advantage it would have with large variable names is number of characters?

Another useful thing to avoid having to SquareRoot in cases is when you are checking the distance between points against a certain number (using mathematical comparison, 2 > 1 etc).

Instead of:
Collapse JASS:
if SquareRoot(x*x+y*y) > dist then
Use:
Collapse JASS:
if x*x+y*y > dist*dist then
blu_da_noob is offline   Reply With Quote
Old 04-22-2006, 09:52 AM   #12
PipeDream
Moderator
 
PipeDream's Avatar


Code Moderator
 
Join Date: Feb 2006
Posts: 1,405

Submissions (6)

PipeDream is a glorious beacon of light (463)PipeDream is a glorious beacon of light (463)PipeDream is a glorious beacon of light (463)PipeDream is a glorious beacon of light (463)

Default

Vuen, if blizzard really wanted fast trig, they could do tables. Especially easy because we only have single precision. Anyway, Cos/Sin are fast enough as is- they execute in less than 2us on my 1.6GHzish machine. I think most of that time is the interpreter..
As a side note I think the way the C++ stdlib does it is by transforming first to 0 to pi/2, doing a couple 3rd 5th or 7th angle formulas and then two or three taylor terms suffices. Since it's an alternating series you can maybe do the trick of taking only half of the next term to get another order of precision, but maybe it converges too fast for that.

Blu: good suggestion, thanks
As for Pow, the thing that scares me even more than efficiency is that JASS automatically typecasts between reals and integers.
PipeDream is offline   Reply With Quote
Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off


All times are GMT. The time now is 11:12 AM.


Affiliates
The Hubb The JASS Vault Clan WEnW Campaign Creations Clan CBS GamesModding Flixreel Videos

Powered by vBulletin (Copyright ©2000 - 2019, Jelsoft Enterprises Ltd).
Hosted by www.OICcam.com
IT Support and Services provided by Executive IT Services