I am trying to make a very simple game with the HTML canvas and JavaScript. I have found many tutorials and questions about detecting collisions of basic shapes on a canvas (such as rectangles and circles). But I am wondering is it possible to detect if a complex shape (a shape that is made up of many basic shapes) is colliding with another shape, or even if two complex shapes are colliding. If so, how could this be done? Thanks in advance!
Asked
Active
Viewed 1,034 times
0
-
We can't help you unless you show us your code. – Scott Marcus Jun 27 '17 at 21:45
-
@ScottMarcus Why would you need my code? – Jun 27 '17 at 21:52
-
Because there are many approaches to every problem. Seeing the code you are working with allows us to give a better answer. – Scott Marcus Jun 27 '17 at 21:52
-
@ScottMarcus I cannot currently access my code but I can give an overview of my program if you want. – Jun 27 '17 at 21:54
-
If complex shapes are made from simple shapes, and you know how to detect collisions in simple shapes, then... ... ... Also [MCV](https://stackoverflow.com/help/mcve). ;) – Brian Peacock Jun 27 '17 at 21:57
-
@BrianPeacock Yes, I could do it through many simple shapes but I would have to check each part of one complex shape against each part of another complex shape. Also, if the shapes are high quality there would be hundreds of simple shapes to make. – Jun 27 '17 at 22:02
-
@ScottMarcus you can always help anyone – B''H Bi'ezras -- Boruch Hashem Apr 29 '20 at 05:26
1 Answers
2
A general algorithm will not provide a better solution than one based specifically on the knowledge of each shape type.
Generally, for complex (i.e. compound) shapes, you would generally try as step #1 and "exit early" test. For optimization reasons, you generally try eliminate false-positives as early in the process as possible.
As simple step #1 is to test for collisions on the "bounding boxes" of each compound shape. If the bounding boxes are NOT overlapping then you can quit early and assume no collision because the compound shapes could not be colliding (see https://gamedevelopment.tutsplus.com/tutorials/collision-detection-using-the-separating-axis-theorem--gamedev-169)
If the bounding-box test cannot eliminate early, you will need to test each sub-shape in turn with algorithms most suitable to the shape (circle-circle, circle-rect etc.) leaving the most "expensive" tests to last - like polygon-polygon.
You might want to also look at this question How do I determine if two convex polygons intersect?
Thulis
- 51
- 4
-
Thank you for your answer. I will try to implement this into my program. Also, are there any other "false-positives" I could use to test for in addition to a bounding box? – Jun 27 '17 at 22:05
-
Another optimization that might be useful (depending on your application) is to divide your space into sectors or a grid. You then only need to test candidates that could possibly overlap i.e. eliminate test even before bounding-box test. For example, if you divide your game-world into a 10x10 grid then those compound shapes completely contained in grid (0, 0) need only be tested against each other, with all other eliminated. **Note** Be careful of corner-cases where shapes cross grid boundaries – Thulis Jun 27 '17 at 22:12
-
yes, those work well. Might be overkill unless you have a lot of actors/shapes active at any one time. See http://www.mikechambers.com/blog/2011/03/21/javascript-quadtree-implementation/ – Thulis Jun 27 '17 at 22:19
-
So is a QuadTree what you were referring to in your first comment? If not, what is the difference? – Jun 27 '17 at 22:21
-
I was talking about an even simpler space-division technique. It's really basic - you do not need to do bounding-box tests on every possible compound-shape against every other compound-shape. Instead, you decide which of those shapes could possibly overlap based the grid box they are in. Those shapes completely contained in different boxes could not overlap. It's Quadtree-lite. Again, configuration is all dependent on your application. – Thulis Jun 27 '17 at 22:41