Rectangle Intersection Z80 machine code implementation - any tips?

Page 1/2
| 2

By DamnedAngel

Master (143)

DamnedAngel's picture

08-04-2019, 01:43

Hi folks,

I am facing the following problem:

I have a set of rectangles in memory (defined with X, Y, Width, Height - all bytes) and I need to, for each of them, calculate the intersection rectangles (also X, Y, Width, Height) between them and a reference rectangle (again, X, Y, Width, Height) - in Z80 machine code, as fast as possible.

First things first: is there, by any chance, some free, optimized lib which does that or which could be adapted to do that?

Supposing such lib is not available, I imagine to use a basic algorithm like:

Loop through Rectangles
  ; test overlap
  if (Rn.X + Rn.Width) < RefRect.X, break loop
  if (RefRect.X + RefRect.Width) < Rn.X, break loop
  if (Rn.Y + Rn.Height) < RefRect.Y, break loop
  if (RefRect.Y + RefRect.Height) < Rn.Y, break loop

  ; overlap confirmed. Calculate intersection
  if (Rn.X > RefRect.X)
    IntRect.X = Rn.X
    IntRect.Width = Min (Rn.Width, RefRect.Width - (Rn.X - RefRect.X))
  else
    IntRect.X = RefRect.X
    IntRect.Width = Min (RefRect.Width, Rn.Width - (RefRect.X - Rn.X))

  if (Rn.Y > RefRect.Y)
    IntRect.Y = Rn.Y
    IntRect.Height = Min (Rn.Height, RefRect.Height - (Rn.Y - RefRect.Y))
  else
    IntRect.Y = RefRect.Y
    IntRect.Height = Min (RefRect.Height, Rn.Height - (RefRect.Y - Rn.Y))

  < Use IntRect >

Note: I don't need to store IntRect. If in the end it is all set in registers, all the better.

Question 1: The algorithm is clearly a basic, straight-forward one. I see that maybe treating all horizontal calculations first and all vertical ones afterwards could improve code size and cycles. I wonder, however, if it can be heavily optimized in some way. Do you guys have any idea?

Question 2: It looks to me that implementing an optimized Z80 code for the algorithm above may be somewhat tricky, given the alternances of live data in registers (as opposed to data stored in memory). Do you foresee any pitfalls I'd want to avoid or any path I'd want to pursue in the implementation? Do you have any insights on approaches you'd suggest me to explore?

Thanks in advance!

Login or register to post comments

By Juan Luis

Resident (46)

Juan Luis's picture

09-04-2019, 13:45

Damned Angel, MSX VDP can detect sprite collisions (I'm not sure about V9990). Are you trying to detect collisions between sprites or between sprites and scene objects?

By DamnedAngel

Master (143)

DamnedAngel's picture

09-04-2019, 14:09

Hi Juan Luis,

Thanks a lot for your interest!

Actually, none of the cited. I am using Screen 8 without sprites. Yes, I know I am making it the hard way, but I am trying to take full avantage of the 256 color mode, and I am planning to have multicolored objects going behind and partially behind the scenery - so sprites are not really good for me. It is not an action game, but I am still going to have some objects moving around. That is why I am building my own depth/transparency/intersection engine, and I need it to be as fast as possible to replace VPD sprites (in the least limited way possible).

I eventually may use HW sprites in very specific contexts, due to their color limitation and due to be hard to hide/partially hide them behind scenery, but that is not the immediate issue now.

[]s

By Juan Luis

Resident (46)

Juan Luis's picture

09-04-2019, 17:28

There are several methods for collision detection depending on if they are moving objects or objects with fixed location on the scene:

- For moving scene you can use rectangle bounding boxes and circles. Rectangle bounding boxes can be represented as (x, y, width, height) or (xLeft, xRight, yTop, yBottom). The first one requires only 2 additions when you are moving the bounding box, but during collision test you'll have to perform 2 additions more. The second one requires 4 additions during moving, but only requires comparison during collision test. It's your choice.

During the game, the main character don't use to collide with the most of the objects in the scene. You can use a cascade filter. A cascade filter is to check necessary conditions first (lighter conditions to compute), and if the condition is met then check more accurate condition (rectangle intersection condition in this case). A light to compute condition is to check an square bounding box. The size of the side of this square bounding box is the size of the longer side of the rectangle bounding box, and compare the distance between the centers of the squares (you can store the center as part of the info of the character). If the distance is less than the sum of the half square sides check rectangle instersection. You can cache collision distances between your main character and the objects into an array. You can cache the sum of the half squares to save compute time, and compare with cached values.

Other light condition is using circles instead of bounding boxes. You can check distance between two circles (x1,y1,r1) and (x2,y2,r2) computing (x1-y1)^2+(x2-y2)^2 < (r1+r2)^2. Z80 don't have multiplication instructions but you can cache square values into an array to avoid multiply.

Example: uint16_t squares[256] = { 0, 1, 4, 9, 16, .., 65025 }.

On the other hand you can have precached collision distance between your main character and the rest of the objects:
uint16_t collision_distance = { (radius_player_circle + radius_object1)^2, (radius_player_circle + radius_objectn)^2 }

You can use with large sceneries with many static objects a binary spatial abstract data types like Quadtree. Take a look on Wikipedia and search for Quadtree. You can implement with Z80 a quadtree of a few levels. Quadtree divides scenary into zones recursively. If your character is in a zone, you only have to check collision with the objects in the same zone. Find out the zone of your character and later check collisions with the objects in the zone.

Other alternative is the collision map. The collision map is binary 2D precached matrix where is stored the coordinates where the main character collides with scenery objects. Unfortunately this technique takes a large memory space. For instance, Graeme Cowie uses this tecnique with Rygar version of Amiga (still work in progress).

https://www.youtube.com/watch?v=7p-qjlr4SMg

By Grauw

Ascended (8395)

Grauw's picture

09-04-2019, 17:57

If you store collision boxes as (center, extents) you can check for overlap with abs(a.center - b.center) < (a.extents + b.extents) for both x and y. If you cache an array of all possible collision pairs, you can also precalculate the sum of the extents to save an addition at run time.

By theNestruo

Expert (108)

theNestruo's picture

09-04-2019, 19:05

I think most games use the approach described by Grauw: it is simple, small, relatively fast, and does the job.

Some ASM examples by nanochess, myself, and Konami.

By Grauw

Ascended (8395)

Grauw's picture

09-04-2019, 19:55

Juan Luis wrote:

For instance, Graeme Cowie uses this tecnique with Rygar version of Amiga (still work in progress).

https://www.youtube.com/watch?v=7p-qjlr4SMg

Just in case anyone was wondering like me if there was a work in progress thread accompanying those videos of Graeme’s, it’s here. I always like reading those.

By DamnedAngel

Master (143)

DamnedAngel's picture

09-04-2019, 20:30

HI Juan, Grauw and theNestruo,

Thanks for the insights. I particularly found the cascade filter technique interesting for my specific case. The (center, extents) calculation is also notable, but it is not straight forward since all my structure uses (X, Y, H, W). I will give some thought whether the real time conversion is applicable (or whether I refactor all my data structure, although I deem that improbable).

I will also check where I can use cached data. That seems promising too.

theNestruo,
Thanks a lot for the code examples. Those will help a lot.

I will make some experiments and if I get stuck somewhere I will let you know. Thanks a lot in advance!

By Grauw

Ascended (8395)

Grauw's picture

09-04-2019, 23:23

Good luck and have fun Smile.

By Juan Luis

Resident (46)

Juan Luis's picture

10-04-2019, 07:51

Grauw wrote:

If you store collision boxes as (center, extents) you can check for overlap with abs(a.center - b.center) < (a.extents + b.extents) for both x and y. If you cache an array of all possible collision pairs, you can also precalculate the sum of the extents to save an addition at run time.

It's equivalent to a squared bounding box with precomputed distances. It's true. It's one of the most common used techniques.

By Juan Luis

Resident (46)

Juan Luis's picture

10-04-2019, 07:54

Good luck and show your results if it's possible.

Page 1/2
| 2