Geometric Collision Detection

[Berb]

The problem:
In the downloadable demo map provided, there seems to be a problem. In the map there is a folder named "Game" in the map triggers. There is a trigger in that folder named "Init". In the main initialization function I create 150 "objects" which fly around with various velocities and bounce of predefined lines.

When I run the exact same demo map as the one provided everything seems to execute properly. There are no objects that get through any of the lines (which form a square) and the motion of the objects appears smooth. The system I run this on is fairly good, so you may need to decrease the value of 150 to experience this.

When I increase the number 150 to 151 something seems to happen that causes some of the detections to be ignored, as well as the motion of some of the particles (choppy rather than smooth). Some of the objects wouldn't even move from their starting position.

This made me think that I was using too many vector objects, as there are 3 in the main object struct. This is the only struct that uses the vector struct, as the others use a point struct. But at only 150 objects (each with 3 vectors) I've only got 450 vectors, which is no where near the limit.

Can anybody spot the problem?

Edit//
It seems that if I release the objects over a duration (rather than having them bounce off the wall within a very small time frame) they do not seem to go through the lines. This draws me to think that at some points I am running into thread operation limits (which would explain the detections being ignored). Once I bump up the number (before it was 150) to about 180 some of my objects stop in their tracks (which is what would happen if the thread was crashing). I really don't think I have that many actions running in a single loop...

Let's see... 180 objects with 4 lines means we're going to have to go through 180 objects 4 times. This seems incredibly inefficient, but would 760 iterations really trigger an OP limit? Does anybody know what the OP limit is?

 

[Pharaoh_]

1) I got a crash, when I tried to test it.

2) I think its the limit of the units a player can have. Try sharing their ownership among various players and test it out with higher values.

 

[Berb]

I've had far more than 180 units for a single player before...

The crash is likely due to one of the objects escaping the enclosed area and leaving the map area.

 

[PurgeandFire]

Your running into the op limit in your timer callback. If you add a debug msg at the end of the "loop" in the callback (with the object count high enough) you'll notice that it will never show up, or it will show up for a while and then suddenly stop showing up.

As for the fix, there is TriggerExecute()/ExecuteFunc() to start new threads.

Nestharus also made T32s to help avoid the op limit a bit, so you can always try using that.

 

[Berb]

This is an extremely rough draft, I figured I was hitting some sort of operation limit due to the way the objects were stuttering across (which would also explain collision detection being ignored). Right now I've got a fairly blunt script so I'm sure there's a lot of room to shorten things and speed them up.

Thanks guys. PurgeandFire111 I appreciate your time looking into that.

Just curious, does anybody actually know if there is a consistent value that determines whether the operations exceeds the OP limit? I imagine there are other factors, but for fairly simple mathematics (very few natives called) I was kind of surprised that I was hitting the OP limit so easily.

 

[D4RK_G4ND4LF]

Just curious, does anybody actually know if there is a consistent value that determines whether the operations exceeds the OP limit? I imagine there are other factors, but for fairly simple mathematics (very few natives called) I was kind of surprised that I was hitting the OP limit so easily.

you have to keep in mind that vJASS compiles to stuff with lots of array lookups so the code is longer than one would expect


I noticed that your polygon class is using division
you could instead use

inline char isLeft(float x, float y, float x1, float y1, float x2, float y2){
     return ((x2 - x1)*(y - y1) - (y2 - y1)*(x - x1)) > 0;
}

to check if the point x/y is on the left side of the line segment x1/y1 x2/y2
+ a few other conditions

so you won't risk a division by zero

 

[Berb]

The polygon class is not being used in the script. It's just there.

I think I've found another problem, though this one is a little stranger. It seems to take about 5 minutes for this to occur, but even when I'm using only 80 objects the script manages to crash Warcraft and it is not because of objects flying outside of the map area. Any ideas?

When I reduce the number from 80 to something smaller, like 40 - the crash seems to be postponed indefinitely.

I'm currently in the process of minimizing the amount of struct member references that I use (by substituting variables) so I'll let you know how this goes.

Edit//
Very strange. When I substitute multiple member references (like the first point of two that are contained in the line segment) it seems to have worse functionality than when I used direct struct references.

When I get rid of my references to x2 and y2 which are substituting for o.position.x and o.position.y the script actually operates faster. I'm guessing the memory allocation for these takes a bigger toll on the operation thread than I thought. I may still be able to substitute variables for my multiple references to point coordinates though.

Well when I reduce the number of lines that can be collided with to 4 instead of 8 it is capable of a noticeable amount more objects. The problem is that when I increment the amount of lines used it has a significant impact on how many objects I can successfully have on the board.

Edit//
Removed size parameter on vector struct which will help bring down the OP limit... seems like it helps a little bit.

If I use individual timers for each object, I can avoid exceeding the OP limit which would solve the problem of objects ignoring collision detection. The problem with this approach is that using 200 timers for 200 objects can be fairly inefficient. I think my next step is going to be to use one timer for every 65 objects created. I want to see if splitting up the executions onto multiple timers will improve the performance.

Edit//
After splitting up the task of updating objects amongst an array of timers I seemed to find that anywhere from 80 objects to 140 objects being updated per timer used has a similar result. I am kind of disappointed that I was only getting 18 frames per second but it seemed to solve the problem of exceeding the OP limit (which caused bugs).

To be safe the OBJECTS_PER_TIMER limit has been set to 100 which ensures safety while being about as efficient as possible. With 250 objects on the board at any given time only 3 timers should be used which I don't find particularly bad. The loop at the beginning of the iterative method that updates the objects only has to run through 3 indexes to determine which scope of objects that iterative method will be scanning across.

I am still kind of puzzled as to why the frame-rate is so low. There is absolutely no memory shortage as my RAM is only at like 20% and the percentage of my CPU being used is only 10% (while the frame-rate in Warcraft is 18). I was thinking it was my GPU but there really isn't anything that graphically demanding in Warcraft III.

This is probably a question for another thread, but does anybody have any ideas on how I can improve the drop in performance when there are many lines? The same setup that runs at an FPS of 54 with only 4 walls drops down to an FPS of 15 with 8 walls. These tests are all done with 250 objects.

I suppose an updated script would be helpful, an up-to-date demo should be attached.

 

[D4RK_G4ND4LF]

if you keep on using linear movement you could calculate the time of impact in advance which can be done very fast using a sweep line algorithm

and you can check if your gpu is the bottleneck by not looking at the missiles

 

[Berb]

I don't know how to implement the sweep-line algorithm. Explanations of this algorithm on the Internet are fairly crappy, and finding one that gives help on how to implement such an algorithm (rather than just explain why it is useful) are even more scarce.

Anybody have a good tutorial... or... something?

 

[D4RK_G4ND4LF]

1. sort all lines from (for example) left to right
since wc3 maps are rather small you could use an array and clamp the coordinates to the array which would be quite fast just convert the x coordinates to something between 0 and 8190 or less
2. loop through the dots from left to right
- every time a line begins add it to a stack
- check intersections of new line with lines on the stack
- every time a line ends remove it from stack

so it is better to use lines of finite length (you will have to recompute pretty much everything after every collision if you implement ball-ball collision anyway) and maybe have a counter or something to know when it is time to calculate intersections again

and how couldn't you find anything helpful about that on the internet?
I get like 2700000 hits for "sweep line algorithm" on google

 

[Berb]

Couldn't seem to find anything about implementation... even after reading through several. I had only read through a few by the time I made the post, though I was reading about it prior to making this.

Edit//
But now I seem to have found something immediately. I must have been quite tired.

2. loop through the dots from left to right
- every time a line beginds add it to a stack
- check intersections of new line with lines on the stack
- every time a line ends remove it from stack

Well it took me a second to get a heap-sort working in Warcraft III (I believe that is O(nlogn) time) so now I've just got to finish the sweep-line algorithm to predetermine any points of intersection.

Just to make sure I've got this right (you seem to know more about it than me) I'm sorting the points (from the lines) in ascending X order. This lets me go sweep left-to-right and gather the coordinates for all the line intersections.

Once I get the coordinates of the intersections, I can then loop through the objects to determine whether or not the line formed by their linear motion runs through any of the points of intersection. If I'm right, this saves time because I can loop through the lines separately from the objects (which eliminates that n² crap) and then compare the objects only to the points of interest.

Do you feel this is an accurate understanding of how this type of thing should be implemented into JASS/vJass?

 

[PurgeandFire]

This is probably a question for another thread, but does anybody have any ideas on how I can improve the drop in performance when there are many lines? The same setup that runs at an FPS of 54 with only 4 walls drops down to an FPS of 15 with 8 walls. These tests are all done with 250 objects.

There are a few stuff that might speed it up. For example, you can switch the timer period from 0.033 to something like 0.04 or even 0.05, and that can boost the fps by quite a bit.

Also, vJASS doesn't have smart ordering or anything like that. You have to make sure your libraries have the libraries they use listed as a requirement. For example:
library Object requires Vector
library Line requires Vector

That removes a bunch of junk that was generated by jasshelper when it was trying to execute the vector functions. (a couple of triggers and evaluations)

Certain inlining may also help in these kinds of extreme cases, so you can try that. You can even try changing onDestroy to just destroy for some of them, unless you need polymorphism... Or you can change the struct allocation/switch to a linked list. However, I don't know how much performance that will all boost it by because I didn't try them.

At least, those are probably the easy ways of improving the performance. The thing about the timer period is probably the most effective, but the other stuff might help a little as well.

 

[Berb]

The problem with increasing the timer period is the motion begins to become apparent. The eye sees roughly 30 frames per second, so dividing 1 second by 30 yields 0.033333 (recurring). If I increase this even to 0.04 the choppy movement patterns become fairly noticeable.

I tried with 0.035 but I didn't really get any performance increase. I am going through many of my steps and trying to optimize the code I will take note of some of your tips. Thank you.

Also, vJASS doesn't have smart ordering or anything like that. You have to make sure your libraries have the libraries they use listed as a requirement. For example:
library Object requires Vector
library Line requires Vector

The Line library does not use the Vector library. As for the Object library, well I honestly thought that I had given it the Vector library requirement. How can I view the script after the changes made by the preprocessor?

 

[Troll-Brain]

How can I view the script after the changes made by the preprocessor?

Check the textfiles in the subfloder "logs" of your JNGP.

To get rid of auto-evaluate method you can add the tag [forcemethodevaluate] inside jasshelper.conf (the one in the JNGP folder, if i remember correctly)

TriggerEvaluate also opens a new tread but it's way faster than TriggerExecute.
The fastest way to execute code is to use ForForce (with only one player inside it ofc), it also opens a new thread.
But it's only slightly faster than TriggerEvaluate and less friendy to use.

You should try T32, and if you still reach the limit op you could try the Nestarus alternative which is supposed to be "limit op safe"

http://www.hiveworkshop.com/forums/submissions-414/snippet-timer32-safe-t32s-193396/

Also have you tried to use wc3mapoptimizer ? (short names of variables/functions are supposed to make the code faster)

 

[Berb]

Well rather than calculating interceptions on every timer period I am determining how much time will need to pass until the object collides with the line. Then instead of calculating immediate interceptions every single timer iteration I only need to determine whether a certain amount of time has passed instead of rolling through enormous amounts of loops.

 

[D4RK_G4ND4LF]

Well rather than calculating interceptions on every timer period I am determining how much time will need to pass until the object collides with the line. Then instead of calculating immediate interceptions every single timer iteration I only need to determine whether a certain amount of time has passed instead of rolling through enormous amounts of loops.

that's what I wanted to say
you can get the number of iterations until collision by dividing the distance (from position of dummy to point of interception) by speed

 

[Berb]

Yea I've already done that part. Simple unit conversions are the least of my worries with this. But thanks none the less.

The only real problem I'm running into at the moment is because of my lack of modularity. I'm trying to get a foundation laid down before I begin to recode everything but I didn't anticipate the problems I would have using arrays. Currently I have a findAllIntersects method in my line class which returns an array of points. This does not maintain interest with the actual line that was intersected with.

I think I need to modularize some of the calculations with specific object velocities in mind so I can determine line collisions easier and more effectively.

 

[Berb]

Well I figured I'd bump this back up the top because I've got some updated information. I've re-done most of the script which really helped in organizing everything and the output is actually quite good. If you've got objects moving around really quickly (colliding with walls frequently) the performance goes down but when objects move at a casual speed it doesn't seem to run into any problems.

The only problem I'm running into at the moment (which is really slowing things down) seems to be some sort of point-type leak. I've got a counter that displays how many points are currently in existence and while it starts off at a low number, which is to be expected, the more the objects collide with nearby walls the amount of points in existence goes up exponentially.

I'm pretty sure it occurs in this script:

Problem

library Object requires Vector, Line, Stack

globals
    //****  
    //* config
    //* ¯¯¯¯¯¯
    //*     # user defined constants and preferences.
    //*
    //********
    public constant integer     OBJECTS_PER_TIMER   = 32
endglobals



struct object extends objectinterface
    //****
    //* OBJECT MEMBERS
    //* ¯¯¯¯¯¯¯¯¯¯¯¯¯¯
    unit    unit                                    = null
    vector  position        
    vector  velocity
    //****
    //* IMPLEMENT PRE-MODULES
    //* ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
    implement       StackModule
    //****
    //* REAL-TIME SYNCHRONIZATION
    //* ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
    private static timer array      looptmr       
    // each timer of this array updates 'OBJECTS_PER_TIMER' to avoid
    // running into operation limits when there are many objects.
    private static constant real    tmrout          = 0.02
    private static integer          tmrcount        = 0
    //****
    //* MISC DATA
    //* ¯¯¯¯¯¯¯¯¯
    private line                    toIntersect     = 0
    private real                    toIntersectX    = 0
    private real                    toIntersectY    = 0
    private real                    ticker
    
    method computeLineContact takes nothing returns nothing
        local point array I
        local point temp
        local line L 
        local line P
        local integer i
        local integer n
        local integer m
        local boolean rite
        local boolean left
        local boolean up
        local boolean down
        
        if (velocity.isZeroVector()) then
            return
            // if the object has no velocity then there is no possibility for it to
            // come into contact with a line.
        endif
        set rite    = velocity.x > 0
        set left    = velocity.x < 0
        set up      = velocity.y > 0
        set down    = velocity.y < 0
        set L       = line.create(position.x, position.y,   /*
                */ position.x + 3000*velocity.x, position.y + 3000*velocity.y)
                
        set P       = line.arr[0]
        set m       = 0
        set n       = 0
        set i       = 0
        loop
            exitwhen (i == line.arrSize)
            if (L != line.arr[i]) then
                set temp = line.findIntersect(L, line.arr[i])
                if (temp != 0) then
                    if (rite) then
                        if (temp.x < I[m].x) then
                            set m = n
                            set P = line.arr[i]
                        endif
                    elseif (left) then
                        if (temp.x > I[m].x) then
                            set m = n
                            set P = line.arr[i]
                        endif
                    elseif (up) then
                        if (temp.y < I[m].y) then
                            set m = n
                            set P = line.arr[i]
                        endif
                    elseif (down) then
                        if (temp.y > I[m].y) then
                            set m = n
                            set P = line.arr[i]
                        endif
                    endif
                    set I[n] = temp
                    set n = n + 1
                endif
            endif
            set i = i + 1
        endloop
        
        // once this loop has finished the point "I[m]" will reference the point
        // where this object will collide with a line.
        if (n > 0) then
            set toIntersectY = I[m].y - position.y
            set toIntersectX = I[m].x - position.x
            set ticker = (SquareRoot(toIntersectY*toIntersectY +    /*
                    */ toIntersectX*toIntersectX) / velocity.length()) * tmrout
            set toIntersectX = I[m].x
            set toIntersectY = I[m].y
            set toIntersect  = P
        endif
        call BJDebugMsg(I2S(n))
        set i = 0
        loop
            exitwhen (i == n)
            call I[n].destroy()
            set i = i + 1
        endloop
        call L.destroy()
        // destroy all points and lines allocated in this process so that there are
        // no recycling problems later.
    endmethod
    
    method setVelocity takes real x, real y returns nothing
        if not (x == 0 and y == 0) then
            set velocity.x = x
            set velocity.y = y
            call computeLineContact()
        else
            set velocity.x = 0
            set velocity.y = 0
        endif
    endmethod
    
    method onDestroy takes nothing returns nothing
        call position.destroy()
        call velocity.destroy()
        call stackOut()
        if (arrSize == ((tmrcount - 1) * OBJECTS_PER_TIMER)) then
            call PauseTimer(looptmr[tmrcount])
            set tmrcount = tmrcount - 1
        endif
    endmethod
    
    static method create takes unit u returns thistype
        local thistype o = allocate()
        set o.unit      = u
        set o.position  = vector.create(GetUnitX(u), GetUnitY(u))
        set o.velocity  = vector.create(0, 0)
        if (arrSize == (tmrcount * OBJECTS_PER_TIMER)) then
            if (looptmr[tmrcount] == null) then
                set looptmr[tmrcount] = CreateTimer()
            endif
            call TimerStart(looptmr[tmrcount], tmrout, true, function thistype.loopfunc)
            set tmrcount = tmrcount + 1
        endif
        call o.stackIn()
        return o
    endmethod
    
    private static method loopfunc takes nothing returns nothing
        local integer i = arrSize - 1
        local thistype obj
        loop
            exitwhen (i < 0)
            set obj = arr[i]
            if (obj != 0) then
                if not (obj.velocity.isZeroVector()) then
                    set obj.position.x = obj.position.x + obj.velocity.x
                    set obj.position.y = obj.position.y + obj.velocity.y
                    set obj.ticker = obj.ticker - tmrout
                    if (obj.ticker <= 0.00) then
                        call obj.onLineTrip(obj.toIntersect, obj.toIntersectX, obj.toIntersectY)
                    endif
                    call SetUnitX(obj.unit, obj.position.x)
                    call SetUnitY(obj.unit, obj.position.y)
                endif
            endif
            set i = i - 1
        endloop
        call BJDebugMsg("point-count: "+I2S(point.arrSize))
    endmethod
endstruct

endlibrary

God I'm really starting to grow tired of these dumb JASS limitations. I've solved the above problem but now I've run into a problem such that whenever an object collides with a wall (based on the ticker value) it should ignore its movement (velocity will not be added to position) and then a new velocity is given based on the reflection of the old velocity upon the normal vector of the wall. This should ensure that objects do not escape the walls. But they do. I'm thinking there's some rounding error that's causing this to screw up like this.

Objects end up hitting walls and when the ticker is recalculated it seems that they are colliding with the same wall over and over, which only makes sense if the object is moving through the wall or constantly being told to move into the wall. Neither of these should logically be the case. If the velocity of the object is reflected then it is not being told to move into the wall again. Since I ignore updating the unit's position if it is due to collide with a wall then it should disallow the objects from moving through the wall. Apparently this logic means nothing to JASS.

 

[Berb]

Okay. Only had a couple of days off in the last little while but I've been back and diligently working on this. I must have typed the second draft up when I was pretty tired because I found a few typos but I also came across something quite strange.

When I use the boolean operators <= and >= they didn't seem to catch when two numbers were equal. For example, when the wall's Y-coordinate (it is horizontal) is 1000 and the point-of-intersection Y-coordinate is 1000 it seemed to return false that 1000 <= 1000, or 1000 >= 1000.

By explicitly determining whether or not the two Y-coordinates were equal to each other I was able to solve the problem, but it seems weird that I have to do this. I'm quite certain that once I define a line I do not modify its members beyond that of instantiation, which would somewhat explain why the equal-comparison of two identical real values would not return true.

Anybody have any ideas? This seems quite scary as I use these operators a lot.

While I'm still a little ways of having a satisfactory version of this the performance compared to my prior demo version is drastically improved. Instead of experiencing quite a bit of lag with only 4 walls and 250 objects, I can run 500 objects against 8 walls dropping to about 47 FPS. This is still quite good, in my opinion.

library Sphere requires Object
struct sphere extends object
    method onLineTrip takes line L, real x, real y returns nothing
        local vector N = vector.create(L.normalVector.x, L.normalVector.y)
        local real k
        local real l = velocity.length()
        
        call DestroyEffect(AddSpecialEffect("Abilities\\Weapons\\DemolisherFireMissile\\DemolisherFireMissile.mdl", x, y))
        call BJDebugMsg("Object ("+I2S(this)+") has tripped on Line ("+I2S(L)+") with a velocity "+R2S(l))
        
        call N.normalize()
        set k = vector.dot(velocity, N)
        set velocity.x = velocity.x - (N.x*2*k)
        set velocity.y = velocity.y - (N.y*2*k)
        call velocity.setLength(l)
        call BJDebugMsg("   <Object reflection yields length of "+R2S(velocity.length()))
        
        // formula for vector reflection:
        //  R = V - 2 × (V • N)
        call setVelocity(velocity.x, velocity.y)
        
        call N.destroy()
    endmethod
endstruct
endlibrary

This is the method that is executed when an object "trips" on a line. When this is executed, the object's position is not updated based on its velocity (so that the object does not pass through the line). The problem here is that the velocity vector seems to continuously grow in length.

Here is the code for the vector library:

2D Vector Library

library Vector

struct vector
    real x
    real y
    
    // Modifies the length/direction of a vector to 'l'.
    method setLength takes real l returns nothing
        set x = l * Cos(rotation())
        set y = l * Sin(rotation())
    endmethod
    method normalize takes nothing returns nothing
        call setLength(1)
    endmethod
    method setRotation takes real r returns nothing
        local real l = length()
        set x = l * Cos(r)
        set y = l * Sin(r)
    endmethod
    
    // Returns true if the length of the vector is 0.
    method isZeroVector takes nothing returns boolean
        return (x == 0 and y == 0)
    endmethod
    
    // Returns the magnitude/direction of a vector.
    method length takes nothing returns real
        return SquareRoot(x*x + y*y)
    endmethod
    method rotation takes nothing returns real 
        return Atan2(y, x)  // Direction is returned in radians.
    endmethod
    
    // Returns the magnitude squared of the vector. Provides
    // more efficiency when using it in comparisons.
    method lengthSq takes nothing returns real
        return x*x + y*y
    endmethod
    
    // Scales a vector by a factor of 'f'.
    method scale takes real f returns nothing
        set x = x * f
        set y = y * f
    endmethod
    
    // Adds/subtracts vector 'v' from a vector.
    method add takes thistype v returns nothing
        set x = x + v.x
        set y = y + v.y
    endmethod
    method sub takes thistype v returns nothing
        set x = x - v.x
        set y = y - v.y
    endmethod
    
    // Returns the dot product of vectors 'A' and 'B'.
    static method dot takes thistype A, thistype B returns real
        return A.x * B.x + A.y * B.y
    endmethod
    
    // Returns a vector that is perpendicular to this vector.
    method normal takes nothing returns thistype
        local thistype u = allocate()
        set u.x = -y
        set u.y = x
        return u
    endmethod
    
    // Returns a projection of vector 'A' onto vector 'B'. Result
    // refers to a new vector reference and must be recycled manually.
    static method projection takes thistype A, thistype B returns thistype
        local thistype C = allocate()
        local real k = dot(B, A) / B.lengthSq()
        set C.x = B.x * k
        set C.y = B.y * k
        return C
    endmethod
    
    // Creates a vector given two real values.
    static method create takes real x, real y returns thistype
        local thistype v = allocate()
        set v.x = x
        set v.y = y
        return v
    endmethod
endstruct


endlibrary

I'm going to try to re-work some of my methods so that I do not have to use extremely low numbers to calculate velocities; I may simply be running into precision problems.

Edit//
Doesn't seem to be that. Even when I use larger numbers for the vectors (by only doing multiplication in the timer loop-method) it still seems as though the length of the vector mysteriously grows as it trips over lines.

None of the objects trip twice over the same line (the debug messages show that different lines are always being tripped over). With that in mind, there isn't any extra code execution which may be inadvertently increasing the velocity of the object.

I'll upload another demo, just in case anybody needs to actually see/test the code.