Collision handling problem (fixed)

ID:141684
 
Dec 12 2008, 6:51 pm
Fixed, I took the algorithm a little too literally, those returns should have been continues.


Anyone know what's wrong with this proc? I took the algorithm itself directly from the website I found it from, and although it was in C++, I'm pretty sure I got the algorithm correct.

    iscolliding(xp,yp)
        if(!density) return

        var
            top1 = pixy+yp+height
            bottom1 = pixy+yp
            left1 = pixx+xp
            right1 = pixx+xp+width

        for(var/atom/A in range(1,src))
            if(!A.density || A==src) continue

            var
                top2 = A.pixy+A.height
                bottom2 = A.pixy
                left2 = A.pixx
                right2 = A.pixx + A.width

            if(bottom1 > top2)    continue
            if(top1    < bottom2) continue
            if(right1  < left2)   continue
            if(left1   > right2)  continue

            return A
Dec 13 2008, 1:11 am
You will run into problems with that setup as it is, because of the range(). You first should order the atoms to be checked by absolute distance from your midpoint to theirs (or if you have some really outrageously differing object sizes, from nearest edge to nearest edge). Otherwise, you run the risk of bumping something that shouldn't be bumped, because the range() proc orders things different than the order you're likely to encounter them.

In other words, you might bump a chair on the other side of the table without first bumping the table. I highly recommend Theodis' QuickSort library for this task. If you need some tips on getting it working, let me know.
Dec 13 2008, 8:43 am
In response to Xooxer
So I should order the list based on what's closest to it?
Dec 13 2008, 11:02 am
In response to Jeff8500
Yes.
Dec 13 2008, 1:17 pm
In response to Xooxer
Thanks, what formula would I have to use for sorting? Right now I have this:

((C.mob.midx-A.midx)**2 + (C.mob.midy-A.midy)**2) - ((C.mob.midx-B.midx)**2 + (C.mob.midy-B.midy)**2)


Where C is the client. I can't seem to figure out what's wrong, but the player is pulled down through objects by gravity the second the mob created.
Dec 13 2008, 3:54 pm (Edited on Dec 13 2008, 4:05 pm)
In response to Jeff8500
This is the proc I use to get the absolute distance between two points.

        get_abs_dist2(X1, Y1, X2, Y2)
            if(!X1 || !Y1 || !X2 || !Y2) return FALSE // if missing args, retrun
            return (X2-X1)*(X2-X1) + (Y2-Y1)*(Y2-Y1)


[edit]
Oh, and this is what I pass to the sorting proc:

proc
    dist_check(atom/A, atom/B, atom/C)
        var/Adx = Choreographer.get_abs_dist(C.midx, C.midy, A.midx, A.midy)
        var/Bdx = Choreographer.get_abs_dist(C.midx, C.midy, B.midx, B.midy)
        return (Adx - Bdx)


So, my call to QuickSort looks like:

                if(density) // if we're dense, check for collisions:

                    // get all the atoms in range of us
                    var/list/range = range(1, src) - src
                    // and sort them by absolute distance
                    // from us, from nearest to furthest away
                    QuickSort(range, /proc/dist_check, src)

                    // then check each atom for collision
                    for(var/atom/A in range)


[edit2]
And now that I look at it, I think I altered QuickSort() to pass some args to the dist check proc. Just in case, here's my version of it.

/*

QuickSort library by Theodis
http://www.byond.com/developer/Theodis/QuickSort

Updates:
Version 2
Tweaked the logic for the cutoff point to check before partitioning
rather than after.  Might have been the source of bugs with lists
smaller than 2.  Plus it looks cleaner.

Usage

QuickSort(L[], cmp, start = 1, end = L.len)

L - The list to be sorted
cmp - The comparision function to be used to compare elements in the list
start - The start of the region in the list to be sorted
end - The end of the region in the list to be sorted

The comparision function should take two parameters.  The parameters
are the two items being compared.  This function should return a negative
number if the first item is less than the second, 0 if the items have
an equal weight for the sorting, and positive if the first item is
larger than the second.


*/

var/const/QS_CUTOFF = 10

proc
    _QSPartition(L[], l, r, cmp, source)
        var
            s
            m
            pivot
        ASSERT(l != r)
        s = l
        m = (l+r)>>1

        if(call(cmp)(L[l],L[m], source) > 0)
            L.Swap(l,m)
        if(call(cmp)(L[l],L[r], source) > 0)
            L.Swap(l,r)
        if(call(cmp)(L[m],L[r], source) > 0)
            L.Swap(m,r)

        L.Swap(m,r-1)
        pivot = r-1
        r--;
        while(1)
            do
                l++
            while(call(cmp)(L[l],L[pivot], source) < 0)
            do
                r--
            while(call(cmp)(L[r],L[pivot], source) > 0)
            if(l < r)
                L.Swap(l,r)
            else
                break;
        L.Swap(l,pivot)
        return l - s

    QuickSort(L[], cmp, source, start = 1, end = L.len)
        if(start < end)
            if(end - start + 1 < QS_CUTOFF)
                InsertSort(L,cmp, source,start,end)
            else
                var/i = _QSPartition(L, start, end, cmp, source);
                QuickSort(L, cmp, source, start, start + i);
                QuickSort(L, cmp, source, start + i + 1, end);

    InsertSort(L[], cmp, source, start = 1, end = L.len)
        for(var/i = start; i <= end; i++)
            var/val = L[i]
            var/j = i - 1
            while(j > 0 && call(cmp)(L[j],val, source) > 0)
                L[j+1] = L[j]
                j--
            L[j+1] = val
Dec 13 2008, 4:03 pm
In response to Xooxer
Don't compare using absolute distance - compare using absolute distance squared. You can remove the sqrt() call and get the same ordering.
Dec 13 2008, 4:04 pm
In response to Jp
Good catch.
Dec 13 2008, 4:09 pm
In response to Xooxer
So the multiplication and subtraction operators are still more efficient than the exponent operator? Other than that, I think I got it, thanks!
Dec 13 2008, 5:03 pm
In response to Jeff8500
Oh, I don't know if they are. I just did it that way.
Dec 13 2008, 5:04 pm
In response to Xooxer
Ok, I fixed it. I was using the QuickSort() proc wrong (I assumed it returned a value, rather than just purely rearranging the list). I have a few more questions, though.

  • What would be the best way to make my atoms move faster? I was thinking increase how many pixels they move each movement, then upon movement, check if they are colliding at any of the points, and locate them to the correct spot
  • EDIT: Right after writing this, I realized it was because of how I was handling movement
Dec 13 2008, 5:11 pm
In response to Jeff8500
You can increase the pixel step size to a point, but then you'll run into problems again, like over-shooting an obstacle and never bumping it, because the two checks happened when you were clear of the object. This can be solved by some more involved collision detection techniques that do numerous checks per atom to make sure it can pass through the step it wants to take. Unless your atoms are moving really fast, covering more pixels in a step than your thinnest obstacle, you probably won't encounter this.

You'll find some issues with corners of some obstacles if your atoms are of a certain size. There are some tricks to get round this without altering your system too much. One way is to allow the mob to pass through the corner diagonally, to give corners a sort of rounded effect. Another method is to try and line up your moving atoms to the grid, by nudging them a pixel towards the center of the grid each time they step. That way, you stick to a clean route that you know won't snag. If your monsters also align to the grid, you'll never miss them by a mere pixel. That's how Zelda does it, anyways.
Dec 13 2008, 7:43 pm
In response to Jeff8500
Yes, much faster. Although recalculating the subtracted value like Xooxer does might be slower than storing it:

var/a = b-c
return a*a


But that's not quite so clear-cut - it involves extra stack space, for example. Not sure if such considerations apply to the BYOND VM, but you never know.

Anyway, in general:

Bit operations (&, |, ^, ~, <<, >>) are really fast.
Addition and subtraction are fast
Multiplication is a slower
Exponentiation and division are really slow, and should be avoided in inner loops.

That said, this is a level of micro-optimisation that's generally not relevant to BYOND. It only comes into play once you start making isometric systems or pixel-movement systems, really, because nothing else requires that many computations.