Collision detection for interlocking shapes

Mr Millside · October 2013

I?m looking for some advice as I?m not sure how to resolve the following problem. I have an in memory structure that holds information about shapes. Note that the shapes are drawn / displayed as coloured attributes and not as a pixel / line representation.

X
Y
Height
Width
Screen Address
Number of elements that make up the shape
List of elements that define how the shape is drawn (see below)

The list of elements defines where each part of the shape is drawn based on the previous position. For example, if I wanted to draw an ?L? shape the structure could look like this:

0 ; X position
0 ; Y Position
3 ; 3 characters high
2 ; 2 characters wide
22528 ; starting address
3 ; 3 elements to draw, note that the item placed at 22528 is not included as part of the elements list
32 ; Add 32 to the starting address (so directly below the first item drawn at 22528
32 ; Add 32 to the item drawn previously, so again directly below it.
1; Add 1 to the item drawn previously so this would be drawn to its right.

I would now have an image on the screen starting at 22528 in this shape:

H
H
HH

I have code that draws these and all works fine. I now want to test for collision so that the shapes cannot overlap. At first I decided to use collision detection based to the X,Y and Width & Height of each shape, which would work. I then realised that the shape bounding rectangles could overlap but the shapes wouldn't necessarily be touching. They could interlock, for example:

HMM
H M
HHM

I'm now thinking of using the bounding rectangles to do some basic "fast" collision detection and then looking more carefully when this is detected to see if any of the individual shape elements are actually touching. My first thought was to create a list of attribute address for the two shapes I am checking and then testing for matching addresses. For the type of game I am writing, both speed and memory size aren't too important so I guess I'm looking for a way of testing that just works and could be refactored at a later date if required. Anyone got some views on this? Could I change the way I hold the shape data to make the collision detection easier?

Dr BEEP · October 2013

You can use OR and XOR on screen.
When the same value, no collission when different collission

example

11100000
and
00011111

wil give 11111111 in both cases

where
11110000
00011111

will give 11101111 by XOR and 11111111 by OR

Arjun · October 2013

Jonathan discusses a few collision techniques this article. One of them being clipping the sprite collision box corners to more closely fit the sprite (i.e octagonal vs square collision).

David Jones · October 2013

If you're drawing using the attributes I'm guessing you're doing something Tetris like?

One very simple way you could do it is to make a shadow buffer of the attributes. So basically 1 byte per character location. Each character location on screen relates to a shadow buffer location and when you draw on the screen you set the shadow buffer locations to non-zero.

So when you start a screen draw do this :-

1. Clear the shadow buffer
2. Get a shape to draw
3. If all the shape locations in the shadow buffer are clear draw the shape
4. else do whatever you want when you don't draw a shape
5. Loop back to 2 for each shape

Does that do what you require?

It'll take 768 bytes for the shadow buffer, but the code should be very simple.

joefish · October 2013

The simplest way is probably to have a buffer the size of the attribute space and just draw each one, checking each square isn't already occupied as you go. You could start with 768 bytes all set to 0, and write into each byte the number of the block you're drawing rather than its colour attribute. Then if there is a collision, you'll know exactly which other one you've hit.

Morkin · October 2013

David Jones wrote: »

If you're drawing using the attributes I'm guessing you're doing something Tetris like?

One very simple way you could do it is to make a shadow buffer of the attributes. So basically 1 byte per character location. Each character location on screen relates to a shadow buffer location and when you draw on the screen you set the shadow buffer locations to non-zero.

So when you start a screen draw do this :-

1. Clear the shadow buffer
2. Get a shape to draw
3. If all the shape locations in the shadow buffer are clear draw the shape
4. else do whatever you want when you don't draw a shape
5. Loop back to 2 for each shape

Does that do what you require?

It'll take 768 bytes for the shadow buffer, but the code should be very simple.

joefish wrote: »

The simplest way is probably to have a buffer the size of the attribute space and just draw each one, checking each square isn't already occupied as you go. You could start with 768 bytes all set to 0, and write into each byte the number of the block you're drawing rather than its colour attribute. Then if there is a collision, you'll know exactly which other one you've hit.

...Great minds & all that - uncanny..! :razz:

David Jones · October 2013

And a small potential optimisation on that could be that you write up to 8 times before you clear the buffer by just checking and setting the next bit value in the shadow buffer.

1. clear shadow buffer
2. value = 1
3. do inner part as before, but check shadow (buffer & value) == value
4. value = value * 2
5. if value == 256 then goto 1, else goto 3

i love the z80s · October 2013

If all the offsets are nonnegative then you can compare two shapes to see if they occupy the same address by iterating through both lists at once, like so:
Imagine you have two sorted lists: {1, 2, 5, 8, 15} and {3, 4, 8, 11} you start comparing the first elements: 1 and 3, no match, then pick the lower of the two numbers and replace it with the next number in that list, so compare 2 and 3, then 5 and 3, 5 and 4, 5 and 8, 8 and 8. OK these two are the same so it's a match. If you reach the end of both lists, there's no match.

bool collision = false;
address1 = start_address_of_shape1 + shape1_offset[0]
address2 = start_address_of_shape2 + shape2_offset[0]
index1 = 1 // this is the position in the array shape1_offset
index2 = 1 // this is the position in the array shape2_offset
while (index1 < num_elements_in_shape1) and (index2 < num_elements_in_shape2)
{
      bool addr1_is_lowest;
      if (index1 == num_elements_in_shape1)
          addr1_is_lowest = false;
      else if (index2 == num_elements_in_shape2)
          addr1_is_lowest = true;
      else { addr1_is_lowest = (address1 < address2); }
      if (addr1_is_lowest) { address1 += shape1_offset[index1]; index1++; }
      else { address2 += shape2_offset[index2]; index2 ++; }
      if (address1 == address2) { collision = true; }
}

i love the z80s · October 2013

In fact you don't need to keep track of both the addresses themselves, just the difference between them.
In Z80 ASM it might look something like this (I've not checked this or even know if all the opcodes are valid and it's certainly not optimal even if it works)

; IX and IY point to the two objects, arranged as below:
; Structure { byte x, y, w, h; word address; byte numOffsets; byte offsets[]; }
    LD HL, (IX+4) ; get initial addresses of objects
    LD BC, (IY+4)
    SUB HL, BC
; D,E contain the number of remaining elements in the respective lists of offsets.
    LD D, (IX+6)
    DEC D
    LD E, (IY+6)
    DEC E
; add difference from first offset pair
    LD B, 0
    LD C, (IX+7)
    ADD HL, BC
    LD C, (IY+7)
    SUB HL, BC
    ; get the addresses of the second offsets
    ADD IX, 8 ; you don't need this if you replace (IX+0) with (IX+8) below,
    ADD IY, 8 ; same with IY, but it's easier to understand
loop:
    ; if HL is 0 we have collided.
    LD A, H
    OR L
    J Z, collision
    ; now replace the smaller of the two pairs, unless we have finished with
    ; one of the lists.
    ; check if list1 still has elements
    LD A, D
    XOR A
    JZ iy_lower
    ; check if list2 still has elements
    LD A, E
    XOR A
    JZ ix_lower
    ; no, so check if HL>0 or <0 based on the sign bit of H.
    BIT 7, H
    JNZ iy_lower
ix_lower:
    ; read the next element from list 1; add to HL.
    LD B, 0
    LD C, (IX+0)
    ADD HL, BC
    INC IX
    DEC D
    J check_done
iy_lower:
    ; read the next element from list 2; subtract from HL.
    LD B, 0
    LD C, (IY+0)
    SUB HL, BC
    INC IY
    DEC E
check_done:
    LD A, D
    J NZ, loop
    LD A, E
    J NZ loop
no_collision:
    ; if we get here, no collision occurred.
collision:
    ; if we get here, a collision occurred; work out where from IX and IY.

Mr Millside · October 2013

Thanks for some great ideas. It gives me something to think about over the next few days. I think the buffer approach may work best for what I am doing. I was hoping to have the game out for Christmas but I?m limited for time so it looks like it?ll be ready for a new year launch.

Collision detection for interlocking shapes

Comments