next »

[Marchal_Mig12]

Hi everyone,

Before I start, it is important to note that I am a novice to anything related to physics. I am, however, doing my best to learn it.

I have been playing around with line-based collision physics lately and have something pretty nice so far. Collisions are working great. One of the most important part of any engine thought is the optimisation. Since I do not want the engine to loop through hundreds of lines, I though about using some kind of grid where I could store which line is in which grid. Any object that can interact with a line then can loop through the lines that cross the few cells surrounding the object in order to detect collisions.

So far I think I have done a pretty good job doing it so far :



When the world is initialised, I create a grid with cell's width and height. Every time a line is added to the world, its id is added to the cells it crosses.

That allows the collision process to be much quicker since it only checks the collision with the line being in the cells near the player.

I am looking, however for better ways to process all this. So far the steps I am using :

1- Initialise the world through a 2d array (this grid then holds a 1d array)
2- Everytime a line is added to the world, I need to add its id to every cells it crosses.
http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm <-- this alrgorithm could be used.
So far I am simply checking every pixel of the line and check in which cell it is placed... and so on. (very slow I guess)
3- The player uses 9 cells around himself and returns which lines are crossing these cells.
Of course I need to make sure the line isn't returned twice.
4- Check for collision with returned lines only. Instead of checking with every lines in the world.

Any thoughs?

[Thomas Hiatt]

Does this algorithm actually need to be more efficient? If there are not performance issues you should just continue adding more features. I don't know how slow GameMaker is but I doubt checking for circle/line collisions could ever be very expensive. You should be concerned with how much time you spend writing the code not just how long it takes the computer to run it.

[raigan]

I can see a tiny bug in the screenshot: for the \ line, there are several grid squares that it overlaps (slightly) which aren't flagged green.

AFAIK (which isn't much) you shouldn't literally use Bresenham; instead you should use a similar process, which is given in this paper: http://www.cse.chalmers.se/edu/course/TDA361/grid.pdf

(or you might already be doing this, but you're using a single ray per line; since the lines are thick, maybe you need to use two rays to approximate the footprint of the line?)

(or, simplest: just look through a wider neighbourhood when querying the grid; maybe less efficient, but you'll get correct results for a probably small constant time cost)

[Marchal_Mig12]

Well this algorithm might not need to be more efficient but I am however looking for people insights in order to optimise the physics as much as possible.

thanks for the algorithm raigan, I'll have a look. There is a bug indeed. The thickness of the line is not taken into account yet.

[voidSkipper]

Does this algorithm actually need to be more efficient? If there are not performance issues you should just continue adding more features. I don't know how slow GameMaker is but I doubt checking for circle/line collisions could ever be very expensive. You should be concerned with how much time you spend writing the code not just how long it takes the computer to run it.

This post is so perfectly in line with your avatar and user message. 

[DrDerekDoctors]

I'd be tempted to store your lines in a BSP tree rather than a series of buckets, where the line is placed in the highest level node which completely contains it. That way if you decide to add moving lines, then instead of having to pull them out of n number of buckets whenever you update their position, you only have to remove them from a single node.

I used to use a bucket list like yourself for my object-to-object collision but now I use a BSP tree and its a lot more robust.

[raigan]

I would absolutely recommend a grid over any other approach (eg BSP, quadtree, etc).. for 2d especially. Grids are fast, and more than anything SIMPLE -- very few lines of code (Real-time Collision Detection has an excellent chapter on grids).

@DrDerekDoctors: inserting/removing from buckets is likely to be much simpler+faster than rebuilding a BSP tree (which AFAIK you'd have to do if something moves; I might not be understanding how your BSP works though!)

[DrDerekDoctors]

You don't have to rebuild the BSP tree at all. Each node in the tree just contains a linked-list. Moving a line from one node to another means just popping it out of the node it's in (which is obviously trivial) and then popping it into the top node of the BSP tree and letting it recurse down to the new node (a maximum of maybe 6-8 levels, thanks to the sizes of the nodes being half of the parent each time meaning you get a lot of granularity without much effort) and add itself to that list.

That's opposed to having to loop through ALL the buckets in the grid it's in, remove itself from those buckets and then add itself to ALL the buckets it is now in.

[Marchal_Mig12]

I cannot really see how that BSP tree really works. I am not sure to understand it but it looks promising.

I could also store, in every line, in which bucket it is placed and then removing it from those instead of looping through all buckets.

[DrDerekDoctors]

I would hope you were doing that latter point, anyway, as otherwise increasing your world size would slow down the game, which is less than ideal.

Obviously if do you have a list like that per line (or rather, per line which can move) which grows and shrinks in size you'll be encouraging a bit more memory fragmentation as it does so, although personally I wouldn't worry about that too much.

If you like, I can send over my BSP tree code. It works based on rects rather than lines, but it's a trivial change to adapt it.

If you aren't having slow-down yet, I would simply not worry about it. As long as your code is nice and abstracted, changing over to a different collision optimisation solution should be painless down the line.

[raigan]

@DrDerekDoctors: it sounds like we might be talking about different things; is there any chance your BSP is eg a kd-tree or a quadtree? Otherwise I'm not sure how you're handling the case where the line overlaps one of the hyperplanes (and thus has to be inserted into multiple nodes).

I still assert that -- IMO -- for 2d, a grid should be the first solution you try: very simple and easy, and quite often good enough.

[RandyGaul]

I cannot really see how that BSP tree really works. I am not sure to understand it but it looks promising.

I could also store, in every line, in which bucket it is placed and then removing it from those instead of looping through all buckets.

That's because using a tree for something a grid does perfectly is a bit silly. A tree would be necessary for a very large and rather unbounded world with lots of empty space. This is pretty much never the case for a 2D game.

A grid is simple, fast, and solves your problem in an appropriate manner. Of course, as raigan said, you can't just use raw bresenham -- you'll need to modify the algorithm slightly to find all cells a line overlaps.

This modified bresenham can also be used for extremely fast 2D raycasting through your grid, so if you do write code for the broadphase you can re-use the code for raycasting.

Edit: Oh and I'm just being nit-picky but... This topic isn't about physics at all, just collision detection. Collision detection and physical simulation are closely related but still different.

[DrDerekDoctors]

@DrDerekDoctors: it sounds like we might be talking about different things; is there any chance your BSP is eg a kd-tree or a quadtree? Otherwise I'm not sure how you're handling the case where the line overlaps one of the hyperplanes (and thus has to be inserted into multiple nodes).

I still assert that -- IMO -- for 2d, a grid should be the first solution you try: very simple and easy, and quite often good enough.

I'm wondering myself what it actually is now...

Each line only lives in a single node, that being the lowest-level node which can completely contain it. If it's bigger than the world or outside the world for the time being, it just sits in the top-level node (and therefor collides with everything, although in practice this would be largely optimised with a simple rect-overlap, and truthfully, in practice not much lives in the top level node).

It's not a quad-tree for sure as I only ever divide each node into two, alternating between vertical and horizontal division with each generation.

As I say, my only issue with a grid was maintaining the contents of each cell. If you have a line which intersects with dozens of cells then that's quite a lot things to pull it out of and push it into each frame if it's moving around.

The method I use definitely has drawbacks, but I like it.

[Marchal_Mig12]

There could also be a solution where we could predict where the line is moving and into which (and when) new cells should it be stored.

We could then easily move a line around and store it in different cells?

[DrDerekDoctors]

Yeah, you could calculate are the new cells and which are the old cells and only address those, sure, although I'm not sure it wouldn't end up taking a similar amount of time. Don't worry about it. Computers are fast.

[HellaciousPuppy]

3- The player uses 9 cells around himself and returns which lines are crossing these cells.
Of course I need to make sure the line isn't returned twice.

Sorry to add to an old thread, but I thought I would just respond to this part. I have implemented an uniform grid system for my latest game, very similar to what is being discussed here. To make sure I process lines only once, despite them being in multiple cells, I use an unordered_set: http://www.cplusplus.com/reference/unordered_set/unordered_set/
If you are not using C++, it may be a bit of work to create your own implementation, but it would be worth it.

[raigan]

3- The player uses 9 cells around himself and returns which lines are crossing these cells.
Of course I need to make sure the line isn't returned twice.

Sorry to add to an old thread, but I thought I would just respond to this part. I have implemented an uniform grid system for my latest game, very similar to what is being discussed here. To make sure I process lines only once, despite them being in multiple cells, I use an unordered_set: http://www.cplusplus.com/reference/unordered_set/unordered_set/
If you are not using C++, it may be a bit of work to create your own implementation, but it would be worth it.

One easy solution to avoid duplicate processing is to give each object a "timestamp" flag; when you test for collision you increment a global counter, and check the timestamp of each object you test against: if it's not equal to the current global value, set it to the global value and perform the test, otherwise skip it (already tested).

I'm not sure how this stacks up vs unordered set, but it's pretty easy to implement in case anyone isn't in C++.