Ball bouncing at a certain angle and efficiency computations [closed]

Question

I would like to make a pong game with a small twist (for now).

1. Every time the ball bounces off one of the paddles i want it to be under a certain angle (between a min and a max). I simply can't wrap my head around how to actually do it (i have some thoughts and such but i simply cannot implement them properly - i feel i'm overcomplicating things). Here's an image with a small explanation .

2. One other problem would be that the conditions for bouncing have to be different for every edge. For example, in the picture, on the two small horizontal edges i do not want a perfectly vertical bounce when in the middle of the edge but rather a constant angle (pi/4 maybe) in either direction depending on the collision point (before the middle of the edge, or after). All of my collisions are done with the Separating Axes Theorem (and seem to work fine).

3. I'm looking for something efficient because i want to add a lot of things later on (maybe polygons with many edges and such). So i need to keep to a minimum the amount of checking done every frame.

4. The collision algorithm begins testing whenever the bounding boxes of the paddle and the ball intersect. Is there something better to test for possible collisions every frame? (more efficient in the long run,with many more objects etc, not necessarily easy to code).

I'm going to post the code for my game:

Paddle Class

public class Paddle : Microsoft.Xna.Framework.DrawableGameComponent
{
    #region Private Members
    private SpriteBatch spriteBatch;
    private ContentManager contentManager;
    private bool keybEnabled;
    private bool isLeftPaddle;
    private Texture2D paddleSprite;
    private Vector2 paddlePosition;
    private float paddleSpeedY;
    private Vector2 paddleScale = new Vector2(1f, 1f);

    private const float DEFAULT_Y_SPEED = 150;
    private Vector2[] Normals2Edges;
    private Vector2[] Vertices = new Vector2[4];
    private List<Vector2> lst = new List<Vector2>();
    private Vector2 Edge;

    #endregion

    #region Properties

    public float Speed { get {return paddleSpeedY; }  set { paddleSpeedY = value; } }
    public Vector2[] Normal2EdgesVector { get { NormalsToEdges(this.isLeftPaddle); return Normals2Edges; } }
    public Vector2[] VertexVector { get { return Vertices; } }

    public Vector2 Scale
    {
        get { return paddleScale; }
        set { paddleScale = value; NormalsToEdges(this.isLeftPaddle); }
    }

    public float X
    {
        get { return paddlePosition.X; }
        set { paddlePosition.X = value; }
    }

    public float Y
    {
        get { return paddlePosition.Y; }
        set { paddlePosition.Y = value; }
    }

    public float Width
    {
        get { return (Scale.X == 1f ? (float)paddleSprite.Width : paddleSprite.Width * Scale.X); }
    }

    public float Height
    {
        get { return ( Scale.Y==1f ? (float)paddleSprite.Height : paddleSprite.Height*Scale.Y ); }
    }

    public Texture2D GetSprite
    {
        get { return paddleSprite; }
    }

    public Rectangle Boundary
    {
        get
        {
            return new Rectangle((int)paddlePosition.X, (int)paddlePosition.Y,
                (int)this.Width, (int)this.Height);
        }
    }

    public bool KeyboardEnabled
    {
        get { return keybEnabled;  }
    }

    #endregion

    private void NormalsToEdges(bool isLeftPaddle)
    {
        Normals2Edges = null;
        Edge = Vector2.Zero;
        lst.Clear();

        for (int i = 0; i < Vertices.Length; i++)
        {
            Edge = Vertices[i + 1 == Vertices.Length ? 0 : i + 1] - Vertices[i];
            if (Edge != Vector2.Zero)
            {
                Edge.Normalize();
                //outer normal to edge !! (origin in top-left)
                lst.Add(new Vector2(Edge.Y, -Edge.X));
            }
        }
        Normals2Edges = lst.ToArray();
    }

    public float[] ProjectPaddle(Vector2 axis)
    {
        if (Vertices.Length == 0 || axis == Vector2.Zero) return (new float[2] { 0, 0 });

        float min, max;
        min = Vector2.Dot(axis, Vertices[0]); max = min;
        for (int i = 1; i < Vertices.Length; i++)
        {
            float p = Vector2.Dot(axis, Vertices[i]);
            if (p < min) min = p; else if (p > max) max = p;
        }
        return (new float[2] { min, max });
    }

    public Paddle(Game game, bool isLeftPaddle, bool enableKeyboard = true) : base(game)
    {
        contentManager = new ContentManager(game.Services);
        keybEnabled = enableKeyboard;
        this.isLeftPaddle = isLeftPaddle;
    }

    public void setPosition(Vector2 newPos)
    {
        X = newPos.X;
        Y = newPos.Y;
    }

    public override void Initialize()
    {
        base.Initialize();
        this.Speed = DEFAULT_Y_SPEED;
        X = 0;
        Y = 0;
        NormalsToEdges(this.isLeftPaddle);
    }

    protected override void LoadContent()
    {
        spriteBatch = new SpriteBatch(GraphicsDevice);
        paddleSprite = contentManager.Load<Texture2D>(@"Content\pongBar");
    }

    public override void Update(GameTime gameTime)
    {

        //vertices array
        Vertices[0] = this.paddlePosition;
        Vertices[1] = this.paddlePosition + new Vector2(this.Width, 0);
        Vertices[2] = this.paddlePosition + new Vector2(this.Width, this.Height);
        Vertices[3] = this.paddlePosition + new Vector2(0, this.Height);

        // Move paddle, but don't allow movement off the screen
        if (KeyboardEnabled)
        {
            float moveDistance = Speed * (float)gameTime.ElapsedGameTime.TotalSeconds;
            KeyboardState newKeyState = Keyboard.GetState();
            if (newKeyState.IsKeyDown(Keys.Down) && Y + paddleSprite.Height + moveDistance <= Game.GraphicsDevice.Viewport.Height)
            {
                Y += moveDistance;
            }
            else if (newKeyState.IsKeyDown(Keys.Up) && Y - moveDistance >= 0)
            {
                Y -= moveDistance;
            }
        }
        else
        {
            if (this.Y + this.Height > this.GraphicsDevice.Viewport.Height)
            {
                this.Y = this.Game.GraphicsDevice.Viewport.Height - this.Height - 1;
            }
        }
        base.Update(gameTime);
    }

    public override void Draw(GameTime gameTime)
    {
        spriteBatch.Begin(SpriteSortMode.Texture,null);
        spriteBatch.Draw(paddleSprite, paddlePosition, null, Color.White, 0f, Vector2.Zero, Scale, SpriteEffects.None, 0);
        spriteBatch.End();

        base.Draw(gameTime);
    }
}

Ball Class

public class Ball : Microsoft.Xna.Framework.DrawableGameComponent
{
    #region Private Members
    private SpriteBatch spriteBatch;
    private ContentManager contentManager;

    private const float DEFAULT_SPEED = 50;
    private float speedIncrement = 0;
    private Vector2 ballScale = new Vector2(1f, 1f);
    private const float INCREASE_SPEED = 50;

    private Texture2D ballSprite; //initial texture
    private Vector2 ballPosition; //position
    private Vector2 centerOfBall; //center coords
    private Vector2 ballSpeed = new Vector2(DEFAULT_SPEED, DEFAULT_SPEED); //speed
    #endregion

    #region Properties

    public float DEFAULTSPEED
    {
        get { return DEFAULT_SPEED; }
    }

    public Vector2 ballCenter
    {
        get { return centerOfBall; }
    }

    public Vector2 Scale
    {
        get { return ballScale; }
        set { ballScale = value; }
    }

    public float SpeedX
    {
        get { return ballSpeed.X; }
        set { ballSpeed.X = value; }
    }

    public float SpeedY
    {
        get { return ballSpeed.Y; }
        set { ballSpeed.Y = value; }
    }

    public float X
    {
        get { return ballPosition.X; }
        set { ballPosition.X = value; }
    }

    public float Y
    {
        get { return ballPosition.Y; }
        set { ballPosition.Y = value; }
    }

    public Texture2D GetSprite
    {
        get { return ballSprite; } 
    }

    public float Width
    {
        get { return (Scale.X == 1f ? (float)ballSprite.Width : ballSprite.Width * Scale.X); }
    }

    public float Height
    {
        get { return (Scale.Y == 1f ? (float)ballSprite.Height : ballSprite.Height * Scale.Y); }
    }

    public float SpeedIncreaseIncrement
    {
        get { return speedIncrement; }
        set { speedIncrement = value; }
    }

    public Rectangle Boundary
    {
        get
        {
            return new Rectangle((int)ballPosition.X, (int)ballPosition.Y,
                (int)this.Width, (int)this.Height);
        }
    }
    #endregion

    public Ball(Game game) : base(game)
    {
        contentManager = new ContentManager(game.Services);
    }

    public void Reset()
    {
        ballSpeed.X = DEFAULT_SPEED;
        ballSpeed.Y = DEFAULT_SPEED;
        ballPosition.X = Game.GraphicsDevice.Viewport.Width / 2 - ballSprite.Width / 2;
        ballPosition.Y = Game.GraphicsDevice.Viewport.Height / 2 - ballSprite.Height / 2;
    }

    public void SpeedUp()
    {
        if (ballSpeed.Y < 0)
            ballSpeed.Y -= (INCREASE_SPEED + speedIncrement);
        else
            ballSpeed.Y += (INCREASE_SPEED + speedIncrement);

        if (ballSpeed.X < 0)
            ballSpeed.X -= (INCREASE_SPEED + speedIncrement);
        else
            ballSpeed.X += (INCREASE_SPEED + speedIncrement);
    }

    public float[] ProjectBall(Vector2 axis)
    {
        if (axis == Vector2.Zero) return (new float[2] { 0, 0 });

        float min, max;
        min = Vector2.Dot(axis, this.ballCenter) - this.Width/2; //center - radius
        max = min + this.Width;    //center + radius
        return (new float[2] { min, max });
    }

    public void ChangeHorzDirection()
    {
        ballSpeed.X *= -1;
    }

    public void ChangeVertDirection()
    {
        ballSpeed.Y *= -1;
    }

    public override void Initialize()
    {
        base.Initialize();
        ballPosition.X = Game.GraphicsDevice.Viewport.Width / 2 - ballSprite.Width / 2;
        ballPosition.Y = Game.GraphicsDevice.Viewport.Height / 2 - ballSprite.Height / 2;
    }

    protected override void LoadContent()
    {
        spriteBatch = new SpriteBatch(GraphicsDevice);
        ballSprite = contentManager.Load<Texture2D>(@"Content\ball");
    }

    public override void Update(GameTime gameTime)
    {
        if (this.Y < 1 || this.Y > GraphicsDevice.Viewport.Height - this.Height - 1)
            this.ChangeVertDirection();

        centerOfBall = new Vector2(ballPosition.X + this.Width / 2, ballPosition.Y + this.Height / 2);
        base.Update(gameTime);
    }

    public override void Draw(GameTime gameTime)
    {
        spriteBatch.Begin();
        spriteBatch.Draw(ballSprite, ballPosition, null, Color.White, 0f, Vector2.Zero, Scale, SpriteEffects.None, 0);
        spriteBatch.End();
        base.Draw(gameTime);
    }
}

Main game class

public class gameStart : Microsoft.Xna.Framework.Game
{
    GraphicsDeviceManager graphics;
    SpriteBatch spriteBatch;

    public gameStart()
    {
        graphics = new GraphicsDeviceManager(this);
        Content.RootDirectory = "Content";
        this.Window.Title = "Pong game";
    }

    protected override void Initialize()
    {
        ball = new Ball(this);
        paddleLeft = new Paddle(this,true,false);
        paddleRight = new Paddle(this,false,true);

        Components.Add(ball);
        Components.Add(paddleLeft);
        Components.Add(paddleRight);
        this.Window.AllowUserResizing = false;
        this.IsMouseVisible = true;
        this.IsFixedTimeStep = false;
        this.isColliding = false;

        base.Initialize();
    }

    #region MyPrivateStuff

    private Ball ball;
    private Paddle paddleLeft, paddleRight;
    private int[] bit = { -1, 1 };
    private Random rnd = new Random();
    private int updates = 0;

    enum nrPaddle { None, Left, Right };
    private nrPaddle PongBar = nrPaddle.None;

    private ArrayList Axes = new ArrayList();
    private Vector2 MTV; //minimum translation vector
    private bool isColliding;
    private float overlap; //smallest distance after projections
    private Vector2 overlapAxis; //axis of overlap

    #endregion

    protected override void LoadContent()
    {
        spriteBatch = new SpriteBatch(GraphicsDevice);
        paddleLeft.setPosition(new Vector2(0, this.GraphicsDevice.Viewport.Height / 2 - paddleLeft.Height / 2));
        paddleRight.setPosition(new Vector2(this.GraphicsDevice.Viewport.Width - paddleRight.Width, this.GraphicsDevice.Viewport.Height / 2 - paddleRight.Height / 2));

        paddleLeft.Scale = new Vector2(1f, 2f); //scale left paddle
    }

    private bool ShapesIntersect(Paddle paddle, Ball ball)
    {
        overlap = 1000000f; //large value
        overlapAxis = Vector2.Zero;
        MTV = Vector2.Zero;

        foreach (Vector2 ax in Axes)
        {
            float[] pad = paddle.ProjectPaddle(ax); //pad0 = min, pad1 = max
            float[] circle = ball.ProjectBall(ax);  //circle0 = min, circle1 = max
            if (pad[1] <= circle[0] || circle[1] <= pad[0]) { return false; }

            if (pad[1] - circle[0] < circle[1] - pad[0])
            {
                if (Math.Abs(overlap) > Math.Abs(-pad[1] + circle[0])) { overlap = -pad[1] + circle[0]; overlapAxis = ax; }
            }
            else 
            {
                if (Math.Abs(overlap) > Math.Abs(circle[1] - pad[0])) { overlap = circle[1] - pad[0]; overlapAxis = ax; }
            }
        }

        if (overlapAxis != Vector2.Zero) { MTV = overlapAxis * overlap; }
        return true;
    }

    protected override void Update(GameTime gameTime)
    {
        updates += 1;
        float ftime =  5 * (float)gameTime.ElapsedGameTime.TotalSeconds;

        if (updates == 1)
        {
            isColliding = false;
            int Xrnd = bit[Convert.ToInt32(rnd.Next(0, 2))];
            int Yrnd = bit[Convert.ToInt32(rnd.Next(0, 2))];
            ball.SpeedX = Xrnd * ball.SpeedX;
            ball.SpeedY = Yrnd * ball.SpeedY;
            ball.X += ftime * ball.SpeedX;
            ball.Y += ftime * ball.SpeedY;
        }
        else
        {
            updates = 100;
            ball.X += ftime * ball.SpeedX;
            ball.Y += ftime * ball.SpeedY;
        }

        //autorun :)
        paddleLeft.Y = ball.Y;

        //collision detection
        PongBar = nrPaddle.None;
        if (ball.Boundary.Intersects(paddleLeft.Boundary))
        {
            PongBar = nrPaddle.Left;
            if (!isColliding)
            {
                Axes.Clear();
                Axes.AddRange(paddleLeft.Normal2EdgesVector);
                //axis from nearest vertex to ball's center
                Axes.Add(FORMULAS.NormAxisFromCircle2ClosestVertex(paddleLeft.VertexVector, ball.ballCenter));
            }
        }
        else if (ball.Boundary.Intersects(paddleRight.Boundary))
        {
            PongBar = nrPaddle.Right;
            if (!isColliding)
            {
                Axes.Clear();
                Axes.AddRange(paddleRight.Normal2EdgesVector);
                //axis from nearest vertex to ball's center
                Axes.Add(FORMULAS.NormAxisFromCircle2ClosestVertex(paddleRight.VertexVector, ball.ballCenter));
            }
        }

        if (PongBar != nrPaddle.None && !isColliding)
            switch (PongBar)
            {
                case nrPaddle.Left:
                    if (ShapesIntersect(paddleLeft, ball))
                    {
                        isColliding = true;
                        if (MTV != Vector2.Zero) ball.X += MTV.X; ball.Y += MTV.Y;
                        ball.ChangeHorzDirection();
                    }
                    break;
                case nrPaddle.Right:
                    if (ShapesIntersect(paddleRight, ball))
                    {
                        isColliding = true;
                        if (MTV != Vector2.Zero) ball.X += MTV.X; ball.Y += MTV.Y;
                        ball.ChangeHorzDirection();
                    }
                    break;
                default:
                    break;
            }

        if (!ShapesIntersect(paddleRight, ball) && !ShapesIntersect(paddleLeft, ball)) isColliding = false;

        ball.X += ftime * ball.SpeedX;
        ball.Y += ftime * ball.SpeedY;

        //check ball movement
        if (ball.X > paddleRight.X + paddleRight.Width + 2) 
        { 
            //IncreaseScore(Left);
            ball.Reset();
            updates = 0;
            return;
        }
        else if (ball.X < paddleLeft.X - 2)
        {
            //IncreaseScore(Right);
            ball.Reset();
            updates = 0;
            return;
        }

        base.Update(gameTime);
    }

    protected override void Draw(GameTime gameTime)
    {
        GraphicsDevice.Clear(Color.Aquamarine);
        spriteBatch.Begin(SpriteSortMode.BackToFront, BlendState.AlphaBlend);
        spriteBatch.End();
        base.Draw(gameTime);
    }
}

And one method i've used:

public static Vector2 NormAxisFromCircle2ClosestVertex(Vector2[] vertices, Vector2 circle)
    {
        Vector2 temp = Vector2.Zero;
        if (vertices.Length > 0)
        {
            float dist = (circle.X - vertices[0].X) * (circle.X - vertices[0].X) + (circle.Y - vertices[0].Y) * (circle.Y - vertices[0].Y);
            for (int i = 1; i < vertices.Length;i++)
            {
                if (dist > (circle.X - vertices[i].X) * (circle.X - vertices[i].X) + (circle.Y - vertices[i].Y) * (circle.Y - vertices[i].Y))
                {
                    temp = vertices[i]; //memorize the closest vertex
                    dist = (circle.X - vertices[i].X) * (circle.X - vertices[i].X) + (circle.Y - vertices[i].Y) * (circle.Y - vertices[i].Y);
                }
            }
            temp = circle - temp;
            temp.Normalize();
        }
        return temp;
    }

Thanks in advance for any tips on the 4 issues.

EDIT1:

Something isn't working properly. The collision axis doesn't come out right and the interpolation also seems to have no effect. I've changed the code a bit:

private bool ShapesIntersect(Paddle paddle, Ball ball)
    {
        overlap = 1000000f; //large value
        overlapAxis = Vector2.Zero;
        MTV = Vector2.Zero;

        foreach (Vector2 ax in Axes)
        {
            float[] pad = paddle.ProjectPaddle(ax); //pad0 = min, pad1 = max
            float[] circle = ball.ProjectBall(ax);  //circle0 = min, circle1 = max
            if (pad[1] < circle[0] || circle[1] < pad[0]) { return false; }

            if (Math.Abs(pad[1] - circle[0]) < Math.Abs(circle[1] - pad[0]))
            {
                if (Math.Abs(overlap) > Math.Abs(-pad[1] + circle[0])) { overlap = -pad[1] + circle[0]; overlapAxis = ax * (-1); } //to get the proper axis
            }
            else 
            {
                if (Math.Abs(overlap) > Math.Abs(circle[1] - pad[0])) { overlap = circle[1] - pad[0]; overlapAxis = ax; }
            }
        }

        if (overlapAxis != Vector2.Zero) { MTV = overlapAxis * Math.Abs(overlap); }
        return true;
    }

And part of the Update method:

if (ShapesIntersect(paddleRight, ball))
                    {
                        isColliding = true;
                        if (MTV != Vector2.Zero) { ball.X += MTV.X; ball.Y += MTV.Y; }
                        //test
                        if (overlapAxis.X == 0) //collision with horizontal edge
                        {
                        }
                        else if (overlapAxis.Y == 0) //collision with vertical edge
                        {
                            float factor = Math.Abs(ball.ballCenter.Y - paddleRight.Y) / paddleRight.Height;
                            if (factor > 1) factor = 1f; 

                            if (overlapAxis.X < 0) //left edge?
                                ball.Speed = ball.DEFAULTSPEED * Vector2.Normalize(Vector2.Reflect(ball.Speed, (Vector2.Lerp(new Vector2(-1, -3), new Vector2(-1, 3), factor))));
                            else //right edge?
                                ball.Speed = ball.DEFAULTSPEED * Vector2.Normalize(Vector2.Reflect(ball.Speed, (Vector2.Lerp(new Vector2(1, -3), new Vector2(1, 3), factor))));
                        }
                        else //vertex collision???
                        {
                            ball.Speed = -ball.Speed;
                        }
                    }

What seems to happen is that "overlapAxis" doesn't always return the right one. So instead of (-1,0) i get the (1,0) (this happened even before i multiplied with -1 there). Sometimes there isn't even a collision registered even though the ball passes through the paddle... The interpolation also seems to have no effect as the angles barely change (or the overlapAxis is almost never (-1,0) or (1,0) but something like (0.9783473, 0.02743843)... ). What am i missing here? :(

Answer 1

1. My suggestion to accomplish this would be to adjust the collision normal accordingly. You could have one normal at the top corner pointing, say 45 deg, up/right and one normal in the bottom corner pointing down/right. For any collision between these you can interpolate between these two normals (using Vector2.Lerp) to get an angle that will then point stright to the right in the exact middle of the edge. In case you want a region with perfect horizontal bounce you can use two normals on the borders of this region pointing in the horizontal direction.

2. You can handle this by using different normals for different edges.

3 and 4. You are on the right track. In the future you can implement a sweep and prune algorithm to determine for which entities to make the broad phase collision detect. For your purpose there is no need for it right now as you only need to check the ball against all other entities which is a O(n) operation. If you have many moving entities which may hit each other you might need it as check all these against each other will be a O(m^2) operation (m number of moving entities that can hit each other)

EDIT: Note that when interpolating two unitvectors you are not guaranteed to get a unit vector back, it will probably be a little shorter. So make sure to normalize after interpolation.

EDIT 2: If you are interpolating along the vertical side then you want your amount to be zero when at the top and one at the bottom. This should depend on the y-value of the contact point.

float amount = (contact.Point.Y - top.Y) / (bottom.Y - top.Y);

Assuming that y is positive in the downwards direction (bottom.Y > top.Y). This will give a value for amount that is in the range of [0..1]

EDIT 3: To find correct contact points you will have two cases to handle. For ball-edge contact follow the reverse axis of collision (which is the edge normal) from the center of ball to the edge of the ball. That will be your contact point. You might have some overlapping due to movement from last frame and this can be handled by a special interpenetration handling method before handleing the collision. Remember to check if you actually have a closing velocity along the axis before handling collision or you might experience some very strange behaviour.

To find contact point for ball-vertex contact do the same thing but the axis in this case is the vecetor from the vertex to the ball center.