SerraAvenger
Cuz I can
When you are changing v_x/v_y you'll have to do the calculations again, ofc.
And you need knowledge of vector algebra, because collision detection of two moving circles is not that easy to make. I'll try to write a function for you that calculates where and when two missiles of radius r collide with each other.When you are changing v_x/v_y you'll have to do the calculations again, ofc.
See better version two posts below!
1) How can parallels intersect?phew, unnecessary work I'd say. You can just approximate it very good by using cubes, or, even better, just intersecting the parallels. That way you get a time gate in which the things are APPROXIMATELY colliding.
library CollisionDetection
public struct collision
real x1
real y1
real x2
real y2
real time
static method create takes real x1, real y1, real x2, real y2, real time returns collision
local collision c = collision.allocate()
set c.x1 = x1
set c.y1 = y1
set c.x2 = x2
set c.y2 = y2
set c.time = time
return c
endmethod
endstruct
private function Distance takes real x1, real x2, real y1, real y2 returns real
return SquareRoot((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))
endfunction
private function CollisionGetMoveVector takes real x1, real y1, real movex1, real movey1, real x2, real y2, real r1, real r2 returns vector
local vector movevec = vector.create(movex1, movey1, 0)
local vector N = vector.create(movex1, movey1, 0)
local vector C
local real D
local real dist = Distance(x1, x2, y1, y2)
local real sumRadii = r1 + r2
local real lengthC
local real F
local real T
local real distance
local real mag = movevec.getLength()
set dist = dist - sumRadii
//early escape:
//if length of movevector is less than distance between centers of circles minus their radii,
//theres no way they can hit
if mag < dist then
return 0
endif
call N.setLength(1.00)
set C = vector.create(x2-x1, y2-y1, 0)
set D = vector.dotProduct(N, C)
// Another early escape: Make sure that 1 is moving
// towards 2! If the dot product between the movevec and
// 2.center - 1.center is less that or equal to 0,
// 1 isn't isn't moving towards 2
if D <= 0 then
return 0
endif
set lengthC = C.getLength()
set F = (lengthC * lengthC) - (D * D)
// Escape test: if the closest that 1 will get to 2
// is more than the sum of their radii, there's no
// way they are going collide
if F >= sumRadii*sumRadii then
return 0
endif
// We now have F and sumRadii, two sides of a right triangle.
// Use these to find the third side, sqrt(T)
set T = sumRadii*sumRadii - F
// If there is no such right triangle with sides length of
// sumRadii and sqrt(f), T will probably be less than 0.
// Better to check now than perform a square root of a
// negative number.
if T < 0 then
return 0
endif
// Therefore the distance the circle has to travel along
// movevec is D - sqrt(T)
set distance = D - SquareRoot(T)
// Finally, make sure that the distance 1 has to move
// to touch 2 is not greater than the magnitude of the
// movement vector.
if mag < distance then
return 0
endif
// Set the length of the movevec so that the circles will just touch
call movevec.setLength(distance)
call N.destroy()
call C.destroy()
return movevec
endfunction
private function GetCollisionTime takes real x1, real y1, real movex1, real movey1, real x2, real y2, real movex2, real movey2, real r1, real r2 returns real
//returns a percentage (1 being 100%) that indicates at which point of the movement vector the circles collide.
//multiply it with the length of the original movement vector and you got the new shortened movement vector
//returns -1 if the circles do not collide.
local vector C = CollisionGetMoveVector(x1, y1, movex1-movex2, movey1-movey2, x2, y2, r1, r2)
local real percentage = -1.
if C != 0 then
set percentage = (C.getLength())/(SquareRoot((movex1-movex2)*(movex1-movex2) + (movey1-movey2)*(movey1-movey2)))
endif
call C.destroy()
return percentage
endfunction
public function GetCollisionStruct takes location missile1start, location missile1end, real missile1radius, real missile1speed, location missile2start, location missile2end, real missile2radius, real missile2speed returns collision
//returns a struct with all useful information for the collision
local collision data = 0
local real x1 = GetLocationX(missile1start)
local real y1 = GetLocationY(missile1start)
local real x2 = GetLocationX(missile2start)
local real y2 = GetLocationY(missile2start)
local real dx1 = GetLocationX(missile1end)-x1
local real dy1 = GetLocationY(missile1end)-y1
local real dx2 = GetLocationX(missile2end)-x2
local real dy2 = GetLocationY(missile2end)-y2
local real time1 = SquareRoot(dx1*dx1 + dy1*dy1) / missile1speed
local real time2 = SquareRoot(dx2*dx2 + dy2*dy2) / missile2speed
local real collisiontime
//temporarily scale both missile move vectors to the same move speed
if time1 < time2 then
set dx1 = dx1 * time2/time1
set dy1 = dy1 * time2/time1
else
set dx2 = dx2 * time1/time2
set dy2 = dy2 * time1/time2
endif
set collisiontime = GetCollisionTime(x1, y1, dx1, dy1, x2, y2, dx2, dy2, missile1radius, missile2radius)
if collisiontime >= 0 then
if time1 < time2 then
if collisiontime <= time1/time2 then
set x1 = x1+dx1*collisiontime
set y1 = y1+dy1*collisiontime
set x2 = x2+dx2*collisiontime
set y2 = y2+dy2*collisiontime
set data = collision.create(x1, y1, x2, y2, time2*collisiontime)
endif
else
if collisiontime <= time2/time1 then
set x1 = x1+dx1*collisiontime
set y1 = y1+dy1*collisiontime
set x2 = x2+dx2*collisiontime
set y2 = y2+dy2*collisiontime
set data = collision.create(x1, y1, x2, y2, time1*collisiontime)
endif
endif
endif
return data
endfunction
endlibrary
to 1)1)
Seems like you misunderstood me.
I meant not intersecting parallels of course. It is quite hard to intersect parallels in wc3.
What I meant was drawing parallels to the actual movement graphs, then intersecting parallels from graph a with those of graph b. I can't be bothered to think about which parallels need to be intersected to get the time frame right now, though.
2)
Squares collide more easily than circles.
EDIT: OF COURSE the side of the cube needs to be the diameter of the sphere...
2) ... even with squares, the thing I mentioned about low angles causing problems when using the time zone approach is still there. The shape of the collision geometry has no influence on that.[/QUOTE]to 1)
I thought about that too, but it's not going to work, unfortunately, as a mere intersection of lines does not neccesarily require that they really collide with each other.
You can determine the intersection point of those parallels, yes, but then you'd require the "time zone" approach again:
determine wether both missiles are at intersection point almost at the same time, and if they do, they collided. However ...
Yes, you are missing something. The collision detection algorythm on the last page has to be run only (n-1) times upon missile creation (for n being your number of currently existing missiles) instead of (n-1) times per tick.Hmm... Seems to me that using a region would still probably win in terms of efficiency. Or am I wrong?
It doesn't seem as though Zwiebelchen's method on the previous page would allow for 75+ projectile's with collision enabled. Or am I missing something?
Hmm... That kinda sucks for homing projectiles and spells that modify the projectiles direction.No more periodic checks or events required. You know right from the moment of creation, where and when other missiles are going to collide with your created missile (as long as the missile movement is linear).
You are right in saying that. It would definately be the best way of doing it. However, non-locust projectiles are crap and butt-ugly.Surely the most efficient is a unit enters range event with no-locust projectiles?. Did I miss something? No periodic actions except for moving the projectile...
O(8191) ~ O(1) >> O(n)?Firstly, in computer science, O(n-1) == O(n) (there's no such thing as a constant, only the highest order is observed).
You missed that unit enters range only checks every 0.1 second or so, according to "Troll-Brain research", and is not very responsive.Surely the most efficient is a unit enters range event with no-locust projectiles?. Did I miss something?
Yes, yes.. well..O(8191) ~ O(1)
Yes, however, the target position can be as far away as you want. However, logic should tell you that there is no real infinite missile movement and that it makes no sense to have real infinite movement, as the map borders limit your movement anyways.After reading over it again it does seem quite self explanatory. However, am I right in saying that the method you posted requires the linear projectiles to have a fixed target position (at which they will cease moving/be destroyed)?
Not really. As I said, the missile destination point can be as far away as you want. If required, you can simulate infinite movement by just placing the destination point on the map border.If so, that may become a problem as it effects what the users is able to do with the system.
Just extrapolate the target point by missilespeed*duration and you got your new 'real' missile destination.Currently, you can target an XYZ coordinate, but have the projectile travel for 10 seconds, even if it passed the targeted coordinates after the first half a second.
Not really, as each calculation has to be done only once per missile (for homing missiles x times with x being the amount of line segments).No, the complexity would be a straight O(n^2). Just less periodic.
Only once per projectile, so, if you do not spawn all at the same time, the processing amount spreads over the game, - and only if you have no early-escape checks in your system, you really need to check all.Secondly, you would still need to check each projectile against each other projectile.
If what Azlier and Weed said is true, then this is nothing else than a periodic enumeration.Surely the most efficient is a unit enters range event with no-locust projectiles?. Did I miss something? No periodic actions except for moving the projectile...