bump.lua - minimal collision detection lib

[meowman9000]

A quick question about bump, what does getDictItemsInCellrect do? It seems like that is how collision is handled, but its quite confusing in how it does it.

[kikito]

what does getDictItemsInCellrect do?

In short: this function returns the items which are present in a group of cells. It's part of the collision detection, but it does not "handle" collision.

The long explanation: Bump divides space in "cells" (they look like squares in a grid, you can see them turning on the "debug info" in the demos). When an item is inserted in the world, the world notes "which cells it touches". If the item moves, this list is updated. When you want to calculate the collisions of that item, instead of comparing the item with all the items in the world, you only compare it with "the items which touch the same cells". These items are called "neighbours of the item". This makes bump go faster.

Items in bump are stored as "rectangles". If an item isn't moving, you can use its rectangle to "find neighbours". If it's moving, on each frame, its movement is also contained inside a (bigger) rectangle. You can use that to "find neighbours along its path". So in both cases you need a function which "given a rectangle, gets the items in the cells touching it".

When you want to "query those cells via a rectangle", this rectangle must be "translated into cell coordinates".In bump, that is called a "cell rect". An example: if the cells are 64x64 px and the rectangle corner is in {x=100,y=200} the cell rect will have its corner in {x=2, y=4}, since that's the cell containing that point. The width and height will be similarly adjusted taking into account cell width and height. This transformation is done elsewhere before calling this function, so we can asume it is already done. But that's the reason the function is called "InCellRect" and not just "InRect".

Finally, let's revisit the fact that an item can touch several cells at once. This means that you can not simply "go over all the cells and put the items touching those cells into an array". If you did that, you would get duplicates, and you would have to eliminate them, which is slow. What we do instead is putting them in a Dictionary. In bump, a dictionary is a table whose keys are items, and the values are usually the literal true. If you put the items in a dictionary instead of an "array-like" table, you eliminate the duplicates automatically, and very fast too. That's why the function is called "getDictItems" instead of "getItems".

I hope this explanation is enough, regards!

EDIT: This thread is for an order version of bump, to ask questions about the new one, please use the most recent thread in viewtopic.php?f=5&t=79223