Log In  

Cart #faster_collision_demo-0 | 2021-07-29 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA
2

A basic rundown of a faster Bounding Box solution.

It uses screen partitioning to select only near objects to check for collision. What is currently running is essentially a worst case scenario where all objects are searching for all other objects with no direct referencing.

The Algorithm

function buildarr()
    colarr = {}
        for y=0,18 do
            colarr[y] = {}
            for x=0,18 do
                colarr[y][x] = {}
            end
        end
end

function entcol(self,name,action)
    xx = flr(self.x/8)+2
    yy = flr(self.y/8)+2
    for xt = xx-1,xx+1 do
        for yt = yy-1,yy+1 do
            for obj in all(colarr[yt][xt]) do
                checks += 1
                if (obj.name == name and obj!= self and boxcol(self,obj)) action(self,obj)
            end
        end
    end
end
coladd = function(self)
        xx = flr(self.x/8) + 2
        yy = flr(self.y/8) + 2
        add(colarr[yy][xx],self)
    end

Essentially at the beginning of each frame an 18x18 matrix is created using buildarr(). Each object gets an extra function called coladd() that adds the object to the partitioned area. If a basic collision is called then the object calling the collisions will check in a 3x3 block of partitions around it. Each frame the array is emptied and filled again. With a little work this could be rearranged to only remove and add objects that have moved.

It's still not nearly as fast as directly targeted collisions and should be used in conjunction with other methods of collision detection to provide a truly optimized experience, but it massively improves the speed of generic collision searching when you can use no other method.

You can change the entcol function call in the mover function to "entcolgen" to directly compare the performance against the slower, non partitioned collision check. The partitioned algorithm can do around 200 object comparisons while the generic method tops out around 60.

When implementing this feature you can also add more targeted partition matrices to further reduce the number of objects checked. If you had one array for bullets, one for enemies, a player object and one for pickups or powers you could reduce the number of collision checks even further.

P#95432 2021-07-29 18:04 ( Edited 2021-07-29 18:17)


[Please log in to post a comment]

Follow Lexaloffle:        
Generated 2021-10-18 16:51:07 | 0.010s | Q:15