collision-detection vhdl collision bounding-box

Rectangle/Box Collision in VHDL

I am working on creating Pong on an FPGA using VHDL. I have been racking my brain for days trying to figure out how to do and what is the best solution to rectangle rectangle collision and I think I have come up with the best solution although there seems to be one bug (explained below).

I took the advice from larsbutler's answer and have used this strategy to go about collision:

object.positionX += object.velocityX

check/respond collisions

object.positionY += object.velocityY

check/respond collisions

This pseudo-code explains how I check/respond to collisions:

// right edge of ball in between objects left and right edge
// OR
// left edge of ball in between objects left and right edge
if((ball.right >= object.left && ball.right <= ball.right) || (ball.left >= object.left && ball.left <= object.right))
{
    xCollision = true;
}

// top edge of ball in between objects top and bottom edge
// OR
// bottom edge of ball in between objects top and bottom edge
if((ball.top >= object.top && ball.top <= object.bottom) || (ball.bottom <= object.bottom && ball.bottom >= object.top))
{
    yCollision = true;
}

// respond to collision
if xCollision and yCollision then
{
    // This code block is respective to each x or y update in order to resolve collision
}

Keep in mind that the top left corner of the screen is (0, 0). Objects are positioned from their center. Here is a diagram:

Pong Diagram Setup

This is basic diagram of what I want the response to be: (source)

Collision response diagram

Problem:

At this moment I am just trying to work on the x collision. The problem enlies in the xPosition code to get the ball out of the paddle to avoid getting stuck. It seems that if xVelocity < 0 then does not evaluate right. Say the ball is traveling left to right(xVelocity > 0) and then we hit the paddle on the right side. The xVelocity will change signs to negative(xVelocity < 0). The problem if statement should evaluate to true and decrement the xPosition to get it out of the paddle. This does not happen though and instead jumps across the paddle and just repeats back and forth. The reason we add or subtract 40 is for testing and will actually be the amount it is inside the paddle.

Many of my implementations seem to fall into this pitfall xVelocity not evaluating right. The code works if you switch the plus and minus in the if else but that does not make any logical sense in my mind. Why must it be the opposite of what I have below? (keep in mind that the xVelocity is multiplied by -1 before this.

-- respond to collision
if xCollision = '1' and yCollision = '1' then

    -- Change direction
    xVelocity <= xVelocity * (-1);
    -- Add glancing y velocity of paddle
    yVelocity <= yVelocity + (collisionObjects(i)(5)/4);

    -- If bouncing in the left direction
    if xVelocity < 0 then
        -- move outwards as much as we are inside the paddle
        -- Should be negating from xPosition as we are bouncing left and want to resolve that way
        xPosition <= xPosition - 40;
    else
        xPosition <= xPosition + 40;
    end if;
end if;

Full code: (VHDL)

-- Ball collision is using discrete collision! 
-- not sweep collision which helps with small fast objects passing through each other


library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use ieee.std_logic_unsigned.all;

--note this line.The package is compiled to this directory by default.
--so don't forget to include this directory. 
library work;
--this line also is must.This includes the particular package into your program.
use work.my_package.all;

entity Ball is
    generic(
        numCollisionObjects: integer := 2;
        ballRadius : integer := 10;
        rgbColor : std_logic_vector(7 downto 0) := "111" & "111" & "11"
    );
    port(
        reset: in std_logic;
        clk: in std_logic;
        hCounter: in std_logic_vector(9 downto 0);
        vCounter: in std_logic_vector(9 downto 0);
        colObject: out type_collisionObject;
        collisionObjects: in type_collisionObjectArray(0 to numCollisionObjects-1);

        pixelOn: out std_logic;
        rgbPixel: out std_logic_vector(7 downto 0) := rgbColor
    );
end Ball;

architecture Behavioral of Ball is
    signal xPosition : integer := 0;
    signal yPosition : integer := 0;

    signal xVelocity : integer := 0;
    signal yVelocity : integer := 0;

    signal pixelBuffer : std_logic;
    signal RGBBuffer : std_logic_vector(7 downto 0) := rgbColor;

    signal colObjectBuffer: type_collisionObject;
begin
    pixelOn <= pixelBuffer;
    rgbPixel <= RGBBuffer;

    colObjectBuffer <= (xPosition, yPosition, ballRadius * 2, ballRadius * 2, xVelocity, yVelocity);
    colObject <= colObjectBuffer;

    animation: process(clk)
        variable update_clk_count: natural := 0;
        variable update_clk_prescaler: natural := 10000000; -- 833333; -- Slow because of debuging... 50 Mhz / clk_prescaler = desired speed
        --variable i: natural := 1;
        variable xCollision: std_logic := '0';
        variable yCollision: std_logic := '0';

        variable colObject_lastState: type_collisionObject;
    begin

        if rising_edge(clk) then
            -- While reset is high then we reset the positions
            if reset = '1' then

                xPosition <= SCREEN_RESX/2;
                yPosition <= SCREEN_RESY/2;

                xVelocity <= 3;
                yVelocity <= 0;

            else
                if update_clk_count >= update_clk_prescaler then

                    colObject_lastState := colObjectBuffer;

                    -- if we are hitting the left wall
                    if (xPosition - ballRadius + xVelocity) <= 0 then
                        RGBBuffer <= rgbColor;

                        if xVelocity < 0 then
                            xVelocity <= xVelocity * (-1);
                        end if;
                    end if;

                    -- if we are hitting the right wall
                    if (xPosition + ballRadius + xVelocity) >= 640 then
                        RGBBuffer <= rgbColor;

                        if xVelocity > 0 then
                            xVelocity <= xVelocity * (-1);
                        end if;
                    end if;

                    -- if we are hitting the top wall
                    if (yPosition - ballRadius + yVelocity) <= 0 then
                        RGBBuffer <= rgbColor;

                        if yVelocity < 0 then
                            yVelocity <= yVelocity * (-1);
                        end if;
                    end if;

                    -- if we are hitting the bottom wall
                    if (yPosition + ballRadius + yVelocity) >= 480 then
                        RGBBuffer <= rgbColor;

                        if yVelocity > 0 then
                            yVelocity <= yVelocity * (-1);
                        end if;
                    end if;

                    -- Update x position
                    xPosition <= xPosition + xVelocity;

                    -- Check for collision after x updates
                    if not(xVelocity = 0) then
                        for i in collisionObjects'range loop
                            xCollision := '0';
                            yCollision := '0';

                            -- right edge of ball in between objects left and right edge
                            -- OR
                            -- left edge of ball in between objects left and right edge
                            if (xPosition + ballRadius >= collisionObjects(i)(0) - (collisionObjects(i)(2)/2) and xPosition + ballRadius <= collisionObjects(i)(0) + (collisionObjects(i)(2)/2)) 
                                    OR (xPosition - ballRadius >= collisionObjects(i)(0) - (collisionObjects(i)(2)/2) and xPosition - ballRadius <= collisionObjects(i)(0) + (collisionObjects(i)(2)/2)) then
                                xCollision := '1';
                            end if;

                            -- top edge of ball in between objects top and bottom edge
                            -- OR
                            -- bottom edge of ball in between objects top and bottom edge
                            if (yPosition - ballRadius >= collisionObjects(i)(1) - (collisionObjects(i)(3)/2) and yPosition - ballRadius <= collisionObjects(i)(1) + (collisionObjects(i)(3)/2)) 
                                    OR (yPosition + ballRadius >= collisionObjects(i)(1) - (collisionObjects(i)(3)/2) and yPosition + ballRadius <= collisionObjects(i)(1) + (collisionObjects(i)(3)/2)) then
                                yCollision := '1';
                            end if;

                            -- respond to collision
                            if xCollision = '1' and yCollision = '1' then

                                -- Change direction
                                xVelocity <= xVelocity * (-1);
                                -- Add glancing y velocity of paddle
                                yVelocity <= yVelocity + (collisionObjects(i)(5)/4);

                                -- If bouncing in the left direction
                                if xVelocity < 0 then
                                    -- move outwards as much as we are inside the paddle
                                    -- Should be negating from xPosition as we are bouncing left and want to resolve that way
                                    xPosition <= xPosition - 40;
                                else
                                    xPosition <= xPosition + 40;
                                end if;
                            end if;

                        end loop;
                    end if;


                    -- Update y position
                    yPosition <= yPosition + yVelocity;

                    -- Check for collision after y updates
                    if not(yVelocity = 0) then
                        for i in collisionObjects'range loop
                            xCollision := '0';
                            yCollision := '0';

                            -- right edge of ball in between objects left and right edge
                            -- OR
                            -- left edge of ball in between objects left and right edge
                            if (xPosition + ballRadius >= collisionObjects(i)(0) - (collisionObjects(i)(2)/2) and xPosition + ballRadius <= collisionObjects(i)(0) + (collisionObjects(i)(2)/2)) 
                                    OR (xPosition - ballRadius >= collisionObjects(i)(0) - (collisionObjects(i)(2)/2) and xPosition - ballRadius <= collisionObjects(i)(0) + (collisionObjects(i)(2)/2)) then
                                xCollision := '1';
                            end if;

                            -- top edge of ball in between objects top and bottom edge
                            -- OR
                            -- bottom edge of ball in between objects top and bottom edge
                            if (yPosition - ballRadius >= collisionObjects(i)(1) - (collisionObjects(i)(3)/2) and yPosition - ballRadius <= collisionObjects(i)(1) + (collisionObjects(i)(3)/2)) 
                                    OR (yPosition + ballRadius >= collisionObjects(i)(1) - (collisionObjects(i)(3)/2) and yPosition + ballRadius <= collisionObjects(i)(1) + (collisionObjects(i)(3)/2)) then
                                yCollision := '1';
                            end if;

                            -- respond to collision
                            if xCollision = '1' and yCollision = '1' then

                                yVelocity <= yVelocity * (-1);

                                -- If ball is moving in same direction the paddle is
                                if (yVelocity < 0 and collisionObjects(i)(5) < 0) 
                                        OR (yVelocity > 0 and collisionObjects(i)(5) > 0) then
                                    yVelocity <= yVelocity + (collisionObjects(i)(5)/2);
                                end if;
                            end if;

                        end loop;
                    end if;

                    update_clk_count := 0;
                end if;
            end if;

            update_clk_count := update_clk_count + 1;
        end if;
    end process;



    drawing: process(hCounter, vCounter)
    begin
        -- If within pixel bounds of bar
        if hCounter >= (xPosition - ballRadius) and hCounter <= (xPosition + ballRadius) and vCounter >= (yPosition - ballRadius) and vCounter <= (yPosition + ballRadius) then
            pixelBuffer <= '1';
        else
            pixelBuffer <= '0';
        end if;
    end process;

end Behavioral;

And the relevant information from my_package.vhd:

constant SCREEN_RESX: integer := 640;
constant SCREEN_RESY: integer := 480;

-- 0: position X
-- 1: position Y
-- 2: size X 
-- 3: size Y
-- 4: velocityX
-- 5: velocityY
type type_collisionObject is array (0 to 5) of integer; 
type type_collisionObjectArray is array(natural range <>) of type_collisionObject;

Update

My collision detection is not bullet proof nor working to my satisfaction but I did seem to find my bug. I had no clue but in VHDL a signal does not update its value until the end of a process and will update to the last statement. Meaning if you turn it negative and then add onto it, you will only get the addition.

I wish this was stressed more in guides and tutorials because this cost me loads of time.

Solution

I have not inspected every line of your code in detail but it looks as if you have introduced many opportunities for bugs in your translation from pseudocode to VHDL. Even if the transcoding is completely correct, it is much harder to trace to/from the pseudocode than it needs to be...

Assuming you trust the pseudocode (and I can see some problems with it :-)

Why not translate

if((ball.right >= object.left && ball.right <= ball.right) || (ball.left >= object.left && ball.left <= object.right))
{
    xCollision = true;
}

into VHDL (correcting the obvious) as

if (ball.right >= object.left and ball.right <= object.right) 
   or (ball.left >= object.left and ball.left <= object.right) then
   xCollision := true;
end if;

or simply

xCollision := (ball.right >= object.left and ball.right <= object.right) 
   or (ball.left >= object.left and ball.left <= object.right);

and create the datatypes for ball, object (records) and xCollision (boolean) appropriately?

Go the next step and wrap that as a function or procedure:

   function XCollision (ball, object : rect) return boolean is
   begin 
      return (ball.right >= object.left and ball.right <= ball.right) 
       or (ball.left >= object.left and ball.left <= object.right);
   end XCollision;

callable as

   x_collision := false;
   for i in objects'range loop
      x_collision := x_collision or XCollision (ball, objects(i));
   end loop;

VHDL is a high level language offering a powerful type model - probably better than the language your pseudocode is written in. Use it that way. (You have already made a good start using packages).

You will have a much easier time of writing, analysing and debugging your VHDL. For an alternative to using records, create an enumeration and use it to index an array of values.

type Sides is (left, right, top, bottom); 
type obj_type is array (sides) of integer;
variable ball, object : obj_type;

in which case XCollision can now be

   function XCollision (ball, object : rect) return boolean is
   begin 
      return (ball(right) >= object(left) and ...);
   end XCollision;

There is nothing fundamentally non-synthesisable in the above.

Though I have seen a 2010 build of Synplicity object to certain functions - it lags considerably behind XST in some respects - strangely enough it was happy with the equivalent procedure with an OUT parameter for the return value.

Those who say that programming for FPGA (designing hardware) is different from software coding are absolutely correct - within limits - but approximately NEVER when they recommend crippling your ability to create clean, understandable code that says what it does and does what it says.

Where hardware design DOES differ is in things like:

is the hardware feasible? a FOR loop with known bounds IS feasible (given a sufficiently large FPGA) - a WHILE loop with unknown bounds generates an unknown amount of hardware ... not feasible! Pointers (VHDL access types) and "malloc" are obviously out...
is the hardware small and fast enough? Given enough objects, the "for" loop above will overflow the FPGA or generate such a long chain of logic that it won't meet your speed target. Then you have to translate it into a pipelined design (large and fast) or a state machine (small and fast, but takes many cycles) to meet your goals.
using appropriate datatypes. If I need a 17-bit number, I simply create one, and save a lot of gates over the best available size (32-bit) available to a C programmer. (There are software languages that allow this, obviously, but their users are still not the majority)
and no doubt others, but these IMO are the most important.
Re the comments; the parallel processing aspects and the use of signals for reliable inter-process communication are the biggest difference : while the points above are valid within a single process; signals and multiple processes are a HUGE difference from most other programming paradigms.