3

Let's assume we have two objects, A and B. What we know about them is their center points' coords (x, y which are floats) and a map (a string of one-zeros - objects' heights are always equal to its width), that tell us which areas of an object can collide with other objects.

I already have all the side tools, e.g. to check whether a given point is lying inside an object, and in which area (and whether it's marked as solid, or not).

Two objects collision - auxiliary drawing

Since I want to implement it in the HTML5 game that I'm working on, I need this algorithm to be working really fast. The first thing I've done, I'm obviously excluding all the objects, that are basically out of reach. But when two objects do interfere - I'm stuck. Of course I could just loop through all the map pieces of both objects, but that would be way too slow, since in practice, my object's actual maps are usually 15x15 (400 fields) or even 25x25. Combining only two objects like this would take ~400 000 loop iterations.

EDIT: As mentioned before, I already implemented bounding boxes, and since my objects are not simple shapes, the standard solutions do not seem to apply here. enter image description here

Do you have any ideas, how should I solve this problem?

Lis
  • 555
  • 4
  • 26
  • 1
    Well you don't need to check every field of the object since you are only interested in the border ones: entire first row, entire last row, first field from the left & right in the middle. – Mike Doe Nov 29 '18 at 22:54
  • Possible duplicate of [Javascript: Collision detection](https://stackoverflow.com/questions/2440377/javascript-collision-detection) – Mike Doe Nov 29 '18 at 22:57
  • 1
    I have to disagree - game world simulation is sometimes not fast enough to catch the exact moment, when two objects meet their borders (or border rows, in this case). And it could not work with strange shapes, like C-shaped. But, just from looking at the 2nd illustration i made, I came up with idea to only focus on the areas, that interfere - that could save a lot of time – Lis Nov 29 '18 at 23:02
  • If your shapes are just 15 x 15 shapes, then you could save them as 15 integers, each holding a shape's line bitwise. When both sprites overlay try to AND the integer values depending where the object frames intersect (y-axis) and also you might have to bit shift before (x-axis) ANDING the corresponding values. – Maksim Nov 30 '18 at 00:43
  • 1
    To remain performant, a good first step is to first check the bounding boxes of the objects to see if they collide, as you show in your second picture. The calculation for this should be fast, even for many objects. Then only do the more expensive collision calculation if the boxes. Also, as you can see from the second picture, you don't really need to check all the pixels of each item, you only need to check the pixels that belong to the intersection of the bounding boxes. – Durstann Jul 29 '20 at 03:40

0 Answers0