Pixel Collision

ID:155935
 
Jan 30 2011, 4:13 pm (Edited on Jan 31 2011, 9:02 am)
I have pixel movement in my game --the same basic way as shadowdarke's libs, how would I go about making pixel collision? The only way I could imagine doing this is with the GetPixel() function... but the icon procs are not know for being efficient or quick.

Edit:
Looked at forum_account's stuff, and I understand what is going on, but It's too much work for only decently better results. setting a offset x for every state of my game would be ludacris.
Jan 30 2011, 5:07 pm (Edited on Jan 30 2011, 5:14 pm)
Unfortunately there's no terribly "efficient" or "quick" way to do this for multiplayer with BYOND's client-server architecture. However, if you are trying to detect collision between two objects which both implement custom collision detection you can do this a few ways.

First of all you have to determine the range for collision detection. After you obtain all atoms in that range you must interpret how they collide.

If you choose to interpret the collision areas as circles, then you must obtain the distance between both circles' centers. Then, if the distance is less than the combined length of both circles' radii then a collision has taken place.

As for interpreting collision between rectangles, this article can explain it better than I can.

You can also probably find some useful resources here.

EDIT: I also found IainPeregrine's article quite useful when I was experimenting with pixel movement in DM.
Jan 31 2011, 7:17 am
It appears Cody has pointed you in the right direction for what you should be doing. However, the way you asked your question makes me think that this was not exactly what you were looking for, but rather that you were looking for a way to do "perfect collision detection," that is, a pixel based collision detection where a collision is triggered when any one of an object's pixels overlaps any one pixel of another object.

If this is indeed what you were asking for, then the icon pixel functions are one place (probably the most generic case that would fit best in all games) to do exactly this. However, I would highly advise you to not do this. You are correct that using the pixel functions will be slow, but beyond that, the algorithm to do what you are looking for is even slower. Even in professional, commercial games that technique is not used. Instead they approximate collisions.

So, again, I direct you back to Cody's reply, as that is what he was discussing; approximating collisions. You imagine that there is a circle or a square or something around every object, and you check to see if those shapes overlap. If they do, collide.

Using bounding squares is a lot faster than using bounding circles. For squares (or rectangles) you only check a few values against each other to see which is higher or lower, and possibly do a few additions. For bounding circles, you have to perform multiplications (some people do square roots, but you don't really need them and they are even slower yet). Normally multiplications are considered fast enough that you don't care in normal programs if you have to multiply, but if you have a ton of objects that you need to check collisions against you want it to be as fast as possible.

If you do not have a ton of objects to check for collisions against, circles are reasonable, though not necessarily better - depends on the shape of the objects you have.

As long as your objects do not have very weird shapes, I highly suggest you just use bounding rectangles.
rect
    var
        x;y; width;height

    New(width,height)
        src.width = width
        src.height = height

    // returns 1 on collision with r, 0 otherwise
    proc/checkCollision(rect/r)
        return !(x>r.x2() || x2()<r.x || y2()<r.y || y>r.y2())
    proc/x2() return x+width
    proc/y2() return y+height


// example use
atom/var/rect/bounds

mob/littleGuy
    New()
        bounds = new(10,10) // 10x10 pixel bounds
mob/tallGuy
    New()
        bounds = new(5,20) // 5x20 pixel bounds

// whatever you use for pixel movement
mob/your_pixel_movement_function(x_pixel_location, y_pixel_location)
    // your normal movement stuff here
    // then...
    bounds.x = x_pixel_location
    bounds.y = y_pixel_location

    for(var/mob/M in list_of_stuff_to_check_collisions_against)
        if(rect.checkCollision(M.rect))
            src << "You ran into [M]"
            M << "[src] ran into you"
Jan 31 2011, 7:53 am
In response to Loduwijk
Aproximating pixel colision it`s the best choice for byond (specially).I use a pixel movement , as well , + ai`s (a little tricky)+ shadows - i can use around 200+ mobs...Probably up to 300 ai`s + players(not sure)...So first think what kind of game you do , and , for how many players!
Jan 31 2011, 9:10 am
In response to Loduwijk
Loduwijk yours is exactly what I was looking for, but I have a few werid shapes, Diamonds aren't covered well by rectangles, especially in games with 8 dir icon_states. What I was thinking about doing was having there exact bounds calculated at runtime for all obj's, and putting them in a master list, so that it calls them relatively quickly with a long start-up time. And of course I'll only call it for only atoms that are dense and have an icon_state. Do you think this would work?
Jan 31 2011, 12:31 pm
In response to Tubutasx1
Tubutasx1 wrote:
Diamonds aren't covered well by rectangles

No, but there are special cases for everything. You can do collision detection against rectangles, circles, triangles, convex polygons with any arbitrary number of sides, and even other shapes.

What I was thinking about doing was having there exact bounds calculated at runtime for all obj's, and putting them in a master list, so that it calls them relatively quickly with a long start-up time. ... Do you think this would work?

If I understand you correctly, sure. Any such optimizations are going to make it work better.

As long as you do not allow new icons during runtime, you could, at startup, go through every icon that exists and calculate a compact bounding shape around it, or you could make an outline around it and do exact pixel-collisions against the outline - still slow but a lot faster than checking the full sprite.

You could even try to find a way to make a many-sided polygon which is an exact convex polygon around the image except for the concave parts of the image, and it would likely be both somewhat fast and accurate.

There are a lot of ways you can do it, and all of them have pros and cons. I took a class on game programming before, and we spent weeks talking about collision detection and lots of different ideas and algorithms for it.

Still, I think the best use of your time is to use rectangles. They are not as accurate, but it might not even be noticeable.
Jan 31 2011, 1:26 pm
Hobnob wrote a great article on vectors, part of which includes using them for collision detection.

However, if you're determined on getting pixel-perfect collision detection, I would try the following:
- Either at compile-time or when the game loads create a list that contains a value indicating whether each pixel is 'dense' for each object that requires pixel collisions. Since this is only done once, you could use GetPixel().
- Give every dense object a bounding box. When two objects are close, first check to see if their bounding boxes collide. If they do, then find the overlapping area (which will be a rectangle). Then, loop through the pixel information for one of the colliding objects, but only the pixels that are in the overlapping region.
- If one pixel in the first object is dense, then check to see if the pixel in the same position on the other object is dense. If it is, then there is a collision.

I have no clue, though, how well this would perform.
Jan 31 2011, 2:34 pm
In response to Nickr5
I don't want to put in the time only to find that the loadup takes 1 hour.

Also is multiplication that much slower than addition? Circles are more efficient for what I'm doing.

circle
    var
        x
        y
        radius
    New(x,y,radius)
        src.x=x
        src.y=y
        src.radius=radius
    proc
        checkCollision(circle/c)
            return (c.radius+radius)**2>=(c.x-x)**2+(c.y-y)**2
Jan 31 2011, 2:40 pm
In response to Tubutasx1
There wouldn't be a significant load time if you included the lists needed at compile-time.

As for your question, don't optimize prematurely. If circles fit your game better, use them until you find out that they are definitely too slow (which I doubt will be the case).
Jan 31 2011, 4:36 pm
As other people have mentioned, you're better off using simple shapes to approximate the shapes of the objects. For most uses you can get away with a surprisingly large lack of precision. Unless the shape really matters (ex: if accurate physics were important to you) then there isn't much benefit to be had.
Feb 1 2011, 5:34 am
In response to Tubutasx1
Tubutasx1 wrote:
I don't want to put in the time only to find that the loadup takes 1 hour.

Agreed, though, if the icons will be the same between executions of the game, you can do it once at compile time, as Nick suggests, instead of every game startup.

Also is multiplication that much slower than addition? Circles are more efficient for what I'm doing.

They are slower, but what you have there are exponents, not multiples. You could just do x*x instead of x**2 and it would be faster as well.

However, as I noted in my original reply, all these little optimizations are only important if you are going to have tons of objects being checked every game tick.

I once made an asteroids game where the asteroids used circle bounds. I could get hundreds of asteroids on the screen, at which point almost all of them were colliding with another one (at which point they bounced off each other) many times every second, so I was probably getting thousands of collisions every second. But it was fine; that was not enough to slow down the game on my computer.

It all depends on your situation. If you are going to check 10,000 circular collisions every game tick, then you need to spend most of your time optimizing to make it work efficiently enough. If you don't have that crazy huge number of collisions going on all the time, then don't worry so much about optimization.

Heck, if you have only 2 objects in the game, such as in a 1vs1 fighter, you can even go the super slow route of checking every individual pixel for a perfect collision system and even use an inefficient algorithm for it. You have to scale your implementation and your optimization to your game. You're probably fine with what you have there.
Feb 1 2011, 9:58 am
In response to Loduwijk
Loduwijk wrote:
Agreed, though, if the icons will be the same between executions of the game, you can do it once at compile time, as Nick suggests, instead of every game startup.

I ended up using combination of basic shapes. Lets see how that works out for me.

They are slower, but what you have there are exponents, not multiples. You could just do x*x instead of x**2 and it would be faster as well.

I can't see how x**2 should be any slower than x*x. If it is slower it has to be so marginal, that it should never make a difference.

Thanks for the help though.
Feb 1 2011, 2:00 pm
In response to Tubutasx1
Tubutasx1 wrote:
I can't see how x**2 should be any slower than x*x. If it is slower it has to be so marginal, that it should never make a difference.

It depends on the situation, just like it does in the choice between "should I go with squares/addition, or can I spare the processing power for circles/multiplication"

Normally you don't care what you're doing. You can do square roots and trig functions and whatever else you want all day long; for most apps, even games, it usually doesn't matter. The only time it does matter is when you're doing it a million times per second, which goes back to the discussion we've already had a few times in this thread already; how many times it has to do this every second.

If you have a piece of code that happens literally a million times every second, then you want to get every last ounce of speed out of it that you can. This means that you go so far as to risk making the code almost unmaintainable for that one little part as long as it gets a tiny bit more speed out of it.

If something takes 1 microsecond longer and you do that a million times every second, then that means you have a second wasted every second. That is, you just made your application twice as slow by having an operation that wasted 1 microsecond. You will almost certainly not have this situation, but it's not an infeasible situation to have, and it's just an extreme example.

Again, it depends on your use.
Feb 2 2011, 3:49 am
In response to Tubutasx1
Because general-purpose exponentiation isn't built into ALUs on processors (because it's hard/impossible to build a circuit that'll do it /and/ be fast /and/ not take up much room), so exponentiation is implemented as a series of multiplications. And the code for doing it will be general-case - that is, it'll do this:

proc/exp(b, p)
    . = 1
    for(var/i = 0, i < p, i++) . *= b


And, of course, the implementation DM uses probably handles fractional and negative powers as well, so there's more complexity there.

Exponentiation is a nontrivial function. Don't use it in code that's speed-critical, if you can avoid it.
Feb 2 2011, 2:21 pm
In response to Jp
Yeah that makes sense thanks.
Feb 3 2011, 1:21 pm
In response to Loduwijk
Do you think it would benefit greatly if you were to use circle and rectangle-based collisions for a large part of your collisions, but at the same time, use some precise-pixel collisions?