That's actually close to what it does, but it does it by removing the unit from the unit group to prevent redundant checking. It's still O(n2) anyway.
Maybe it's not as fast as I think it is because I'm not even sure what the data structure for unit groups is.
Congratz on your tutorial being Featured! BTW, your chat channel at your signature is really helpful! There were like 4 ppl willing to help me with my triggers!
That's actually close to what it does, but it does it by removing the unit from the unit group to prevent redundant checking. It's still O(n2) anyway. Maybe it's not as fast as I think it is because I'm not even sure what the data structure for unit groups is.
It might be true that both options are O(n²), but when programming something with a high runtime you always have to save wherever you can (if it doesn't hurt the program).
Option 1 = n²
Option 2 = n*(n+1)/2
Option 2 allows about 40% more units (sqrt(2) on big numbers).
Example:
100 objects with option 1 = 10.000
140 objects with option 2 = 140*141/2 = 9870
Now use a simple grid, nothing serious, use 9 squares and I think you will probably save more than 50% of your checks.
Example:
1 2 3
4 5 6
7 8 9
Checks to be done:
1 - 1, 1 - 2, 1 - 4, 1 - 5 = 4 checks
2 - 2, 2 - 3, 2 - 5, 2 - 6 = 4 checks
3 - 3, 3 - 6 = 2 checks
4 - 4, 4 - 5, 4 - 7, 4 - 8 = 4 checks
5 - 5, 5 - 6, 5 - 8, 5 - 9 = 4 checks
6 - 6, 6 - = 2 checks
7 - 7, 7 - 8 = 2 checks
8 - 8, 8 - 9 = 2 checks
9 - 9 = 1 check
25 checks
That might seem a lot so lets see how much it is if we group all objects perfectly (will probably never happen, but the worst case is still the same as before):
10 units in every square, so we got 90
every check is 9*10/2 = 45
45 * 25 = 1.125
90 objects without a grid = 90*91/2 = 4095
180 opbjects with perfect grid placement = 5250
Now let's think about a larger grid, like 16 fields: 9*4 + 6*2 +1*1 checks = 49 checks * 1/16² = 49/256 wich is a bit less than 1/5.
.
New question: How do we define the grid size?
Well, the grid can be built on every iteration, sorting everything into a grid every time you need it has a lower runtime than updating the grid by checking borders. (A quadtree would need a lot higher performance because you have to check 4 borders on every iteration or 2 per depth level to find the new position.)
Sorting everything in on every iteration allows us to use a dynamic squaresize wich has to at least be slightly higher than the biggest radius of your objects.
Example, your mapsize is 256 and your biggest object has a radius of 1.5 (diameter of 3). Your gridsize is 2. 128*128 squares, 127*127*4 + 127*2*2 + 1 checks = 65.025 checks
Sounds ridiculous? Sure, the checks will kill your computer, even though you will probably only check for 100 collision if you randomly spread 1000 objects. Oh, and don't forget to empty the grid after each run...
But we can fix that. Add an integer for every grid position and a global one. Increase your global integer every time you run a collision check (for the whole field). Whenever you add an object to the grid position you check if the integer on that field equals your global int, if it doesn't clear the object list for that field and update the integer (then add the object).
Now we get to the second problem, we have to know wich squares are used and wich aren't. We just need another global integer and an integer array wich has to be equal (or greater) than the object count. The integer will be our counter, before we start the whole check we have to set it to -1 (every time). When we add an object to a square in the grid and the integer on that position is updated we have to increase our counter and set our array[counter] to the gridposition.
.
The last thing we have to do is run 4 checks for every gridposition saved in that array:
square with itself (in case there is only 1 object 0 collision checks are needed)
square with the square to its right (0 objects = 0 collision checks)
square with the one below (0 objects = 0 collision checks)
.
1000 objects: worst case (fields to check): 4000 and probably less than 100 collision checks
1000 objects without grid (n*(n+1)/2) = 500.500 collision checks...
.
No evil funcs needed (square root, sin, cos etc. are slow).
Btw. it's still O(n²). Oh, and I'd suggest a grid size between 4 and 8, a slight bit more collision checks and less squares to check.
Thanks for reading (if you did so :D).
edit:
Small note, if you want to add unmovable objects, add a second list to each square in the grid wich contains them. Now you have to check all 9 fields around (including the field where your object is) for unmovable objects and the normal 4 fields for movable objects. This makes unmovable objects your biggest friends because you can add thousands of em and won't even feel it.
Thanks for the post. But as I said I did make it to not do any redundant checks, so it's already doing n*n/2 checks.
And about the "evil functions" that gives me an idea, maybe instead of taking the square root for the distance I should just square the other side of the inequality. Not sure how much faster that would be.
Thanks for the post. But as I said I did make it to not do any redundant checks, so it's already doing n*n/2 checks.
I wasn't saying you did a bad job, I just wanted to show that the speed of O(n²) != O(n²). O(n²) shows how fast the time needed increases with additional objects, not how fast your algorithm is. A slow O(n) can be worse than a fast O(n²) algorithm for n = 1.000.000.
And about the "evil functions" that gives me an idea, maybe instead of taking the square root for the distance I should just square the other side of the inequality. Not sure how much faster that would be.
That's the normal method, a square root is one of the worst functions you can find.
For some reason I can't get my self to like sweep and prune. But you are free to chose, I just wanted to show you a method better than forcing a collision check between every object pair.
I've already done a lot of 3D stuff, it began with this wc3 map:
edit: oh, you might want some information if you want to test that map^^
movement: arrows + j
creating blocks: k (have to be selected via chat, "-model 1-6"), presets: just write "1", "2" or "3" into the chat
camera, hiding objects in your field of view: "-camz x", "-camx x", "-camc x" (greyout value), "-camf x" (transparency)
camera: "-camax x", "-camaz x", "-follow x" (smoothness of the camera movement)
bugs: sometimes you have to move away from new objects or you fall through (moving away one times solves this)
objects placed too low look like they are above ground even though they arent (you can move through the model)
good job at this :) i really like it but you should learn vJass ^_^
and plzzzzzz use this tool for you code: http://www.hiveworkshop.com/forums/tools-560/script-language-aligner-v2-0-a-186353/
because i can't figure out how you are doing this things :S
do you may have it/somethis similar in another language? a real one like c+ + / java / c# ....
Well, it's been one of my first maps (well, not a finished map, let's say project), I did that before entering the first wc3 forum. A few month after finishing this I learned vJass.
I just wanted to show that I'm not new to this topic and know what I'm talking about. This map is made pretty bad, but its damn old, so it shows that I'm a senior 3D developer (*coughs*).
I've got a working version in galaxy script, at least it would work with floats >.< I am tracking real collision between n-edged or round objects with a flat top and bottom but the error is so big that I sometimes get stuck. The prod function I created (real collisions while prodding till no objects are stuck) made everything lag, so I kicked it out again.
The version uploaded is somewhere from during the development (wich already stopped) but it's one of the playable versions <.<
Our conversation is off topic and I'd prefer pms for further conversation (instead of writing here).
Thanks for the tutorial. I am going through it now. One thing though, your example of a vector from points (2, 7) to (-4, 3), should be the vector (-6, -4) not (4,-6).
Hey not sure if this has been caught or not, but you don't destroy the triggers once they have been applied to a ball. Once you throw a bunch of balls, the map starts lagging like hell. It is just because there is a periodic loop going on each ball, and when there are 70 or more balls, it is just too many balls, you know? I mean 2 is enough.
Yeah I'm aware, no reason it should stop checking collision on the balls if they still exist. I didn't give them an expiration timer so that I could test how many I have to throw until it starts to lag. Then, when I finally get around to optimizing the map, I'll see how much it improves.
Ok ive spent some serious time modifying this engine.
Couple things to note. About the ball throwing function.
Z-velocity
doesnt take into account the force being applied to the unit
doesnt take into account the mass of the object.
odd ratio being used to calculate needed Z-velocity for the ball to reach target point based on Z-Velocity = Distance / (Force * 100) or Z-Velocity = Distance / 31 as you will see in the test map.
Velocities
do not suffer from friction in air
No where to apply external pressures such as wind
Gravity
G = .04
does not appear to take objects mass into account
gravity is applied to the objects Z-velocity as a constant.
z = z - .004 every loop this is the only reduction the the z velocity I would think this needs to be a bit more involved for a truer system.
Im trying to set this up so i can input a height and force as a variable to throw the ball accurately but the current way of handling the Z-axis kinda prevents me from doing so easily.
Z-velocity really needs to take into account the force being applied to the unit..... and then adjust the X-Y velocities according to the Z-velocity...... and I pretty much am brand new to vector math but maybe I can figure it out over the next couple of weeks...
Yeah, the purpose of this tutorial is to keep it as simple as possible and provide you with the tools you need to modify it for your own purpose. It should be trivial to make another ApplyForce function that also affects the Z, and adding air resistance would just involve using the "else" part of the friction conditional. The formula I got for deciding the initial Z-velocity was a matter of guess and check for the constant; I'm sure there's a more generic way of doing it though. You could multiply it by the mass, which is 1.0 so perhaps if you did that it would become more modular (I say multiply because if the mass was greater, it'd be moving slower, so it'd need more air time to reach destination, haven't tested it though).
Adding wind would be as simple as repeatedly applying a small force in the direction of the wind to all objects. In fact that's how you'd do a constant force of any kind, by repeatedly calling ApplyForce every game loop. See Homing Missile. Although yeah, objects with larger surface areas would tend to receive more force from wind, so maybe just multiply by the unit's radius.
Gravity doesn't care about mass in this simplified case. I'm assuming the mass of the ground is significantly greater than each object and distance is insignificant, and the ground is flat. This isn't meant to simulate planet-star systems. It gives you a parabolic trajectory for throwing footballs.
yeah the only problem I have with this. Is that it is a perfect arc. The formula its using basically just increases and decreases the Z value unit the ball hits the right spot. Which in some cases the ball goes damn near straight up in the air or more or less doesnt look like a thrown football. Theres the other case of a kicked football acts much differently. Arc wise anyways. Ive been working on modifying it myself to try and input a "thrown angle" and have it use that for the base of the acr. Only problem is that you basically need to increase the X and Y velocities from what they currently are to do it this way.. I havent worked out the math yet.
Rollback Post to RevisionRollBack
Skype
KageNinpo = SN
My Libraries
DialogLeaderboard & TeamSort
My Projects
SPACEWAR Tribute
Infinite TD
I managed to set up a fairly full-featured physics engine shortly after SC2's release which included the full suite of sphere-level physics with the exception of 3-degree rotation and spin. There was marble-level physics with ballistics (air drag), accurate parabolic aiming, sphere-sphere collision, terrain normal and terrain cliff detection, homing and linear acceleration, restitution, and all sorts of other shit.
The irony was that having objects in motion didn't actually lag; it was the involved initial setup that really killed the network performance, and not because of the physics... The fucking sound effects being spammed via triggers lagged the game the most (NETWORK LAG FROM SOUNDS WHAT). Unbelievable. In single player, though, everything ran smooth as butter on any dual core CPU up to about a hundred colliding projectiles (performance drop if they are all in the same/adjacent sectors) and a couple hundred non-colliding projectiles. Lower the number slightly if the projectiles are affected by gravity and slide around on the ground.
It was the network lag that killed the project I was using the physics engine for. Hell, I even had most of the UI finished. The physics engine has some bugs but is useable. I used parts of it for SCU but the biggest features (sphere collision) were taken out.
PS. Yes my system is rather advanced and no it was not written in straight Galaxy, this was done in GUI. Galaxy would be approximately 10-20% faster on runtime. I don't even try to touch data tables; they are very slow. If you want to use the system, contact me. I won't charge any money for it because it has some bugs and is basically undocumented, but it is very complete.
A grid or quadtree should definitely be possible. At least, it did work just fine back in Wc3 (its basically just calculation, after all).
That's actually close to what it does, but it does it by removing the unit from the unit group to prevent redundant checking. It's still O(n2) anyway. Maybe it's not as fast as I think it is because I'm not even sure what the data structure for unit groups is.
Congratz on your tutorial being Featured! BTW, your chat channel at your signature is really helpful! There were like 4 ppl willing to help me with my triggers!
It might be true that both options are O(n²), but when programming something with a high runtime you always have to save wherever you can (if it doesn't hurt the program). Option 1 = n² Option 2 = n*(n+1)/2 Option 2 allows about 40% more units (sqrt(2) on big numbers).
Example: 100 objects with option 1 = 10.000 140 objects with option 2 = 140*141/2 = 9870
Now use a simple grid, nothing serious, use 9 squares and I think you will probably save more than 50% of your checks. Example: 1 2 3
4 5 6
7 8 9
Checks to be done:
1 - 1, 1 - 2, 1 - 4, 1 - 5 = 4 checks
2 - 2, 2 - 3, 2 - 5, 2 - 6 = 4 checks
3 - 3, 3 - 6 = 2 checks
4 - 4, 4 - 5, 4 - 7, 4 - 8 = 4 checks
5 - 5, 5 - 6, 5 - 8, 5 - 9 = 4 checks
6 - 6, 6 - = 2 checks
7 - 7, 7 - 8 = 2 checks
8 - 8, 8 - 9 = 2 checks
9 - 9 = 1 check
25 checks
That might seem a lot so lets see how much it is if we group all objects perfectly (will probably never happen, but the worst case is still the same as before): 10 units in every square, so we got 90 every check is 9*10/2 = 45
45 * 25 = 1.125
90 objects without a grid = 90*91/2 = 4095
180 opbjects with perfect grid placement = 5250
Now let's think about a larger grid, like 16 fields: 9*4 + 6*2 +1*1 checks = 49 checks * 1/16² = 49/256 wich is a bit less than 1/5.
.
New question: How do we define the grid size?
Well, the grid can be built on every iteration, sorting everything into a grid every time you need it has a lower runtime than updating the grid by checking borders. (A quadtree would need a lot higher performance because you have to check 4 borders on every iteration or 2 per depth level to find the new position.)
Sorting everything in on every iteration allows us to use a dynamic squaresize wich has to at least be slightly higher than the biggest radius of your objects.
Example, your mapsize is 256 and your biggest object has a radius of 1.5 (diameter of 3). Your gridsize is 2. 128*128 squares, 127*127*4 + 127*2*2 + 1 checks = 65.025 checks
Sounds ridiculous? Sure, the checks will kill your computer, even though you will probably only check for 100 collision if you randomly spread 1000 objects. Oh, and don't forget to empty the grid after each run...
But we can fix that. Add an integer for every grid position and a global one. Increase your global integer every time you run a collision check (for the whole field). Whenever you add an object to the grid position you check if the integer on that field equals your global int, if it doesn't clear the object list for that field and update the integer (then add the object).
Now we get to the second problem, we have to know wich squares are used and wich aren't. We just need another global integer and an integer array wich has to be equal (or greater) than the object count. The integer will be our counter, before we start the whole check we have to set it to -1 (every time). When we add an object to a square in the grid and the integer on that position is updated we have to increase our counter and set our array[counter] to the gridposition.
.
The last thing we have to do is run 4 checks for every gridposition saved in that array:
square with itself (in case there is only 1 object 0 collision checks are needed)
square with the square to its right (0 objects = 0 collision checks)
square with the one below (0 objects = 0 collision checks)
.
1000 objects: worst case (fields to check): 4000 and probably less than 100 collision checks
1000 objects without grid (n*(n+1)/2) = 500.500 collision checks...
.
No evil funcs needed (square root, sin, cos etc. are slow).
Btw. it's still O(n²). Oh, and I'd suggest a grid size between 4 and 8, a slight bit more collision checks and less squares to check.
Thanks for reading (if you did so :D).
edit: Small note, if you want to add unmovable objects, add a second list to each square in the grid wich contains them. Now you have to check all 9 fields around (including the field where your object is) for unmovable objects and the normal 4 fields for movable objects. This makes unmovable objects your biggest friends because you can add thousands of em and won't even feel it.
@Arkless: Go
Thanks for the post. But as I said I did make it to not do any redundant checks, so it's already doing n*n/2 checks.
And about the "evil functions" that gives me an idea, maybe instead of taking the square root for the distance I should just square the other side of the inequality. Not sure how much faster that would be.
And yes I'm aware of that method of collision but I might be more comfortable with the sweep and prune technique (http://en.wikipedia.org/wiki/Sweep_and_prune).
@Arkless: Go
I wasn't saying you did a bad job, I just wanted to show that the speed of O(n²) != O(n²). O(n²) shows how fast the time needed increases with additional objects, not how fast your algorithm is. A slow O(n) can be worse than a fast O(n²) algorithm for n = 1.000.000.
That's the normal method, a square root is one of the worst functions you can find.
For some reason I can't get my self to like sweep and prune. But you are free to chose, I just wanted to show you a method better than forcing a collision check between every object pair.
I've already done a lot of 3D stuff, it began with this wc3 map:
edit: oh, you might want some information if you want to test that map^^
movement: arrows + j
creating blocks: k (have to be selected via chat, "-model 1-6"), presets: just write "1", "2" or "3" into the chat
camera, hiding objects in your field of view: "-camz x", "-camx x", "-camc x" (greyout value), "-camf x" (transparency)
camera: "-camax x", "-camaz x", "-follow x" (smoothness of the camera movement)
bugs: sometimes you have to move away from new objects or you fall through (moving away one times solves this) objects placed too low look like they are above ground even though they arent (you can move through the model)
@Arkless: Go
good job at this :) i really like it but you should learn vJass ^_^
and plzzzzzz use this tool for you code: http://www.hiveworkshop.com/forums/tools-560/script-language-aligner-v2-0-a-186353/
because i can't figure out how you are doing this things :S
do you may have it/somethis similar in another language? a real one like c+ + / java / c# ....
@HellGateSc2: Go
Well, it's been one of my first maps (well, not a finished map, let's say project), I did that before entering the first wc3 forum. A few month after finishing this I learned vJass.
I just wanted to show that I'm not new to this topic and know what I'm talking about. This map is made pretty bad, but its damn old, so it shows that I'm a senior 3D developer (*coughs*).
I've got a working version in galaxy script, at least it would work with floats >.< I am tracking real collision between n-edged or round objects with a flat top and bottom but the error is so big that I sometimes get stuck. The prod function I created (real collisions while prodding till no objects are stuck) made everything lag, so I kicked it out again.
The version uploaded is somewhere from during the development (wich already stopped) but it's one of the playable versions <.<
Our conversation is off topic and I'd prefer pms for further conversation (instead of writing here).
@LosTacos: Go
Thanks for the tutorial. I am going through it now. One thing though, your example of a vector from points (2, 7) to (-4, 3), should be the vector (-6, -4) not (4,-6).
Thanks, fixed.
not bad but a constant looping engine checking to move everything lags like hell.
BTW I was interested in working on a serious Foot Ball map as well. If your interested in collaborating message me.
Hey not sure if this has been caught or not, but you don't destroy the triggers once they have been applied to a ball. Once you throw a bunch of balls, the map starts lagging like hell. It is just because there is a periodic loop going on each ball, and when there are 70 or more balls, it is just too many balls, you know? I mean 2 is enough.
Great to be back and part of the community again!
Yeah I'm aware, no reason it should stop checking collision on the balls if they still exist. I didn't give them an expiration timer so that I could test how many I have to throw until it starts to lag. Then, when I finally get around to optimizing the map, I'll see how much it improves.
@SouLCarveRR: Go
Originally I was just making it for a friend who's kind of new. I don't think I know enough of the details of football to pull it off.
@LosTacos: Go
Well thanx a lot for this tutorial..
Ive managed get this to really fit in nicely with my own foot ball map.
After a lot of time recoding certain aspects of it. It is really quite impressive.
Ok ive spent some serious time modifying this engine.
Couple things to note. About the ball throwing function.
Im trying to set this up so i can input a height and force as a variable to throw the ball accurately but the current way of handling the Z-axis kinda prevents me from doing so easily.
Z-velocity really needs to take into account the force being applied to the unit..... and then adjust the X-Y velocities according to the Z-velocity...... and I pretty much am brand new to vector math but maybe I can figure it out over the next couple of weeks...
Yeah, the purpose of this tutorial is to keep it as simple as possible and provide you with the tools you need to modify it for your own purpose. It should be trivial to make another ApplyForce function that also affects the Z, and adding air resistance would just involve using the "else" part of the friction conditional. The formula I got for deciding the initial Z-velocity was a matter of guess and check for the constant; I'm sure there's a more generic way of doing it though. You could multiply it by the mass, which is 1.0 so perhaps if you did that it would become more modular (I say multiply because if the mass was greater, it'd be moving slower, so it'd need more air time to reach destination, haven't tested it though).
Adding wind would be as simple as repeatedly applying a small force in the direction of the wind to all objects. In fact that's how you'd do a constant force of any kind, by repeatedly calling ApplyForce every game loop. See Homing Missile. Although yeah, objects with larger surface areas would tend to receive more force from wind, so maybe just multiply by the unit's radius.
Gravity doesn't care about mass in this simplified case. I'm assuming the mass of the ground is significantly greater than each object and distance is insignificant, and the ground is flat. This isn't meant to simulate planet-star systems. It gives you a parabolic trajectory for throwing footballs.
@LosTacos: Go
yeah the only problem I have with this. Is that it is a perfect arc. The formula its using basically just increases and decreases the Z value unit the ball hits the right spot. Which in some cases the ball goes damn near straight up in the air or more or less doesnt look like a thrown football. Theres the other case of a kicked football acts much differently. Arc wise anyways. Ive been working on modifying it myself to try and input a "thrown angle" and have it use that for the base of the acr. Only problem is that you basically need to increase the X and Y velocities from what they currently are to do it this way.. I havent worked out the math yet.
I managed to set up a fairly full-featured physics engine shortly after SC2's release which included the full suite of sphere-level physics with the exception of 3-degree rotation and spin. There was marble-level physics with ballistics (air drag), accurate parabolic aiming, sphere-sphere collision, terrain normal and terrain cliff detection, homing and linear acceleration, restitution, and all sorts of other shit.
The irony was that having objects in motion didn't actually lag; it was the involved initial setup that really killed the network performance, and not because of the physics... The fucking sound effects being spammed via triggers lagged the game the most (NETWORK LAG FROM SOUNDS WHAT). Unbelievable. In single player, though, everything ran smooth as butter on any dual core CPU up to about a hundred colliding projectiles (performance drop if they are all in the same/adjacent sectors) and a couple hundred non-colliding projectiles. Lower the number slightly if the projectiles are affected by gravity and slide around on the ground.
It was the network lag that killed the project I was using the physics engine for. Hell, I even had most of the UI finished. The physics engine has some bugs but is useable. I used parts of it for SCU but the biggest features (sphere collision) were taken out.
PS. Yes my system is rather advanced and no it was not written in straight Galaxy, this was done in GUI. Galaxy would be approximately 10-20% faster on runtime. I don't even try to touch data tables; they are very slow. If you want to use the system, contact me. I won't charge any money for it because it has some bugs and is basically undocumented, but it is very complete.
@LosTacos: Go
SPACEWAR
How would I make this system detect cliffs or doodads and bounce off of them? I read the whole thing... or did i miss something?
You even mention elasticity and a Custom Value that detects cliff height, but then you never go over how and when to use them. =(