I don't know C++ but here is an algorithm which I would try if want to solve this. The examples will be in JS but I will try too make code much easy to read as possible
What you should know about JS canvas and circle:
The point (0, 0) is the left upper corner of canvas
The positive direction of Ox is right
The positive direction of Oy is down
The coordinates of circle is the center of circle
Let's forget about many circles and think that we have only one circle in rectangle. We want circle to bounce from walls. We always know the center of circle and movement direction
The red dot is touch point. Circle can touch line only in one point
The green dot is center of circle
The arrow in left is the previous movement direction
The arrow in right is the next movement direction
We want to calculate the next direction. To calculate it we need to know that circle touches wall. But how to detect it if we know only position of the center of circle?
For example we can track the 4 additional point on circle (topmost, bottommost, rightmost and leftmost points) and check if some of this point touches the wall. But it is not beautiful method for me and we know that in future we need to work with two (or more) circles which can touch each other not only in given 4 points. Adding more points is too complicated to calculating
Here is more efficient method: Instead of tracking the circle touching with wall we can track the touching center of circle and the touch with smaller rectangle. The smaller rectangle has offsets equal to radius of circle. When we touch the wall we can just reverse the direction of movement of circle depending on the wall that was touched. For example, if we touch the top or bottom wall, we only need to change the direction along Oy.
Let's code it:
const canvas = document.querySelector('#myCanvas');
const ctx = canvas.getContext('2d');
class Dot {
x;
y;
constructor(x, y) {
this.x = x;
this.y = y;
}
}
class Vector {
x;
y;
constructor(x, y) {
this.x = x;
this.y = y;
}
}
class Circle {
center;
radius;
speed;
direction;
path2D;
constructor(center, radius, speed, direction, color) {
this.center = center;
this.radius = radius;
this.speed = speed;
this.direction = direction;
this.color = color;
}
draw() {
this.path2D = new Path2D();
this.path2D.arc(this.center.x, this.center.y, this.radius, 0, 2 * Math.PI);
ctx.fillStyle = this.color;
ctx.fill(this.path2D);
}
checkCollisionWithVerticalWalls() {
const nextPositionX = this.center.x + this.direction.x;
if (
// CHECK IF CIRCLE TOUCHES RIGHT WALL OF SMALLER RECTANGLE
nextPositionX > canvas.width - this.radius ||
// CHECK IF CIRCLE TOUCHES LEFT WALL OF SMALLER RECTANGLE
nextPositionX < this.radius
) {
// REVERSE THE MOVEMENT DIRECTION BY Ox
this.direction.x = -this.direction.x;
}
}
checkCollisionWithHorizontalWalls() {
const nextPositionY = this.center.y + this.direction.y;
if (
// CHECK IF CIRCLE TOUCHES TOP WALL OF SMALLER RECTANGLE
nextPositionY > canvas.height - this.radius ||
// CHECK IF CIRCLE TOUCHES BOTTOM WALL OF SMALLER RECTANGLE
nextPositionY < this.radius
) {
// REVERSE THE MOVEMENT DIRECTION BY Oy
this.direction.y = -this.direction.y;
}
}
move() {
this.checkCollisionWithVerticalWalls();
this.checkCollisionWithHorizontalWalls();
this.center.x += this.direction.x * this.speed;
this.center.y += this.direction.y * this.speed;
}
}
const circle = new Circle(
new Dot(canvas.width / 2, canvas.height / 2),
16,
2,
new Vector(1, -1),
'white'
);
function updateFrame() {
// CLEAR CANVAS
ctx.clearRect(0, 0, canvas.width, canvas.height);
// DRAW CIRCLE
circle.draw();
// MOVE CIRCLE
circle.move();
}
// DO NOT PAY ATTENTION TO THIS BELOW
// IT IS JUST CONFIGURING GAME LOOP
const targetFPS = 60;
const timeInterval = Math.floor(1000 / 60 * (60 / targetFPS));
let previousFrameTime = performance.now();
(function gameLoop(currentFrameTime = performance.now()) {
requestAnimationFrame((timeStamp) => gameLoop(timeStamp));
if (currentFrameTime - previousFrameTime < timeInterval) return;
previousFrameTime = currentFrameTime;
updateFrame();
})()
canvas {
background: black;
}
<canvas id="myCanvas" width="480" height="320"></canvas>
This method works perfectly while the walls along the Ox or Oy. But what if the wall will be at a 45 degree angle? In this situation we can't just reverse the movement by Ox or Oy. In previous we understand how does touch detection principle work. Now let's talk about why if the walls along the Ox or Oy we can just reverse the movement
Some math theory:
The angle of incidence is equal to the angle of reflection
If we know the coordinates of incidence vector and the coordinates of surface normal then the coordinates of reflection vector can be calculated in this way
b = a - 2 * (a, n) * n / (|n| ^ 2)
b - reflection vector
a - incidence vector
n - surface normal
(a, n) - scalar product of incidence vector and surface normal
|n| - length of surface normal
If we know the coordinates both of vectors (a = (a_1, a_2), n = (n_1, n_2)) then the scalar product we can be calculated in this way (a, n) = a_1 * n_1 + a_2 * n_2
In 2D the surface is a line so the normal is perpendicular to the direction vector of the line. To check if two vectors are perpendicular we can just calculate their scalar product and sure that it is 0
If we don't know the coordinates of vector x but know the coordinates of its start point (C = (c_1, c_2)) and end point (D = (d_1, d_2)) then the coordinates of vector can be calculated in this way x = (d_1 - c_1, d_2 - c_2)
If we know the coordinates of vector then the length of vector can be calculated in this way |n| = (n, n) ^ (1 / 2) = sqrt((n, n)). But we need to calculate the square of length, so we will not need to calculate the square root of scalar product
The direction vector of Ox is (0, 1) so the normal (perpendicular vector) is (1, 0) because scalar product is 0 * 1 + 1 * 0 = 0. Let's we have a movement direction vector a = (a_1, a_2) and our circle touches the one of horizontal wall. Let's calculate the vector b:
b = a - 2 * (a, n) * n / (|n| ^ 2) =
= (a_1, a_2) - 2 * ((a_1, a_2), (n_1, n_2)) * (n_1, n_2) / (sqrt(((n_1, n_2), (n_1, n_2))) ^ 2) =
we know the coordinates of vector n it is (0, 1)
= (a_1, a_2) - 2 * ((a_1, a_2), (0, 1)) * (0, 1) / ((0, 1), (0, 1)) =
= (a_1, a_2) - 2 * (a_1 * 0 + a_2 * 1) * (0, 1) / (0 * 0 + 1 * 1) =
= (a_1, a_2) - 2 * a_2 * (0, 1) / 1 =
= (a_1, a_2) - (0, 2 * a_2) =
= (a_1 - 0, a_2 - 2 * a_2) =
= (a_1, -a_2)
Let's recap:
The vector a = (a_1, a_2)
The vector b = (a_1, -a_2)
With the same calculations we can prove that if our circle touches the one of horizontal wall then the vector b will be (-a_1, a_2)
Let's code it:
const canvas = document.querySelector('#myCanvas');
const ctx = canvas.getContext('2d');
class Dot {
x;
y;
constructor(x, y) {
this.x = x;
this.y = y;
}
}
class Vector {
x;
y;
constructor(x, y) {
this.x = x;
this.y = y;
}
}
class MyMath {
static scaleVector(vector, scale) {
return new Vector(vector.x * scale, vector.y * scale);
}
static sumOfVectors(vector1, vector2) {
return new Vector(vector1.x + vector2.x, vector1.y + vector2.y);
}
static diffOfVectors(vector1, vector2) {
return MyMath.sumOfVectors(vector1, MyMath.scaleVector(vector2, -1));
}
static scalarProduct(vector1, vector2) {
return vector1.x * vector2.x + vector1.y * vector2.y;
}
static reflectionVector(normal, incidenceVector) {
const scalarProduct = MyMath.scalarProduct(normal, incidenceVector);
const dividendVector = MyMath.scaleVector(normal, 2 * scalarProduct);
const divisor = MyMath.scalarProduct(normal, normal);
const subtrahendVector = MyMath.scaleVector(dividendVector, 1 / divisor);
return MyMath.diffOfVectors(incidenceVector, subtrahendVector);
}
}
class Circle {
center;
radius;
speed;
directionVector;
path2D;
constructor(center, radius, speed, directionVector, color) {
this.center = center;
this.radius = radius;
this.speed = speed;
this.directionVector = directionVector;
this.color = color;
}
draw() {
this.path2D = new Path2D();
this.path2D.arc(this.center.x, this.center.y, this.radius, 0, 2 * Math.PI);
ctx.fillStyle = this.color;
ctx.fill(this.path2D);
}
checkCollisionWithVerticalWalls() {
const nextPositionX = this.center.x + this.directionVector.x;
if (
// CHECK IF CIRCLE TOUCHES RIGHT WALL OF SMALLER RECTANGLE
nextPositionX > canvas.width - this.radius ||
// CHECK IF CIRCLE TOUCHES LEFT WALL OF SMALLER RECTANGLE
nextPositionX < this.radius
) {
// REVERSE THE MOVEMENT DIRECTION BY Ox
this.directionVector = MyMath.reflectionVector(new Vector(1, 0), this.directionVector);
}
}
checkCollisionWithHorizontalWalls() {
const nextPositionY = this.center.y + this.directionVector.y;
if (
// CHECK IF CIRCLE TOUCHES TOP WALL OF SMALLER RECTANGLE
nextPositionY > canvas.height - this.radius ||
// CHECK IF CIRCLE TOUCHES BOTTOM WALL OF SMALLER RECTANGLE
nextPositionY < this.radius
) {
// REVERSE THE MOVEMENT DIRECTION BY Oy
this.directionVector = MyMath.reflectionVector(new Vector(0, 1), this.directionVector);
}
}
move() {
this.checkCollisionWithVerticalWalls();
this.checkCollisionWithHorizontalWalls();
this.center.x += this.directionVector.x * this.speed;
this.center.y += this.directionVector.y * this.speed;
}
}
const circle = new Circle(
new Dot(canvas.width / 2, canvas.height / 2),
16,
2,
new Vector(1, -1),
'white'
);
function updateFrame() {
// CLEAR CANVAS
ctx.clearRect(0, 0, canvas.width, canvas.height);
// DRAW CIRCLE
circle.draw();
// MOVE CIRCLE
circle.move();
}
// DO NOT PAY ATTENTION TO THIS BELOW
// IT IS JUST CONFIGURING GAME LOOP
const targetFPS = 60;
const timeInterval = Math.floor(1000 / 60 * (60 / targetFPS));
let previousFrameTime = performance.now();
(function gameLoop(currentFrameTime = performance.now()) {
requestAnimationFrame((timeStamp) => gameLoop(timeStamp));
if (currentFrameTime - previousFrameTime < timeInterval) return;
previousFrameTime = currentFrameTime;
updateFrame();
})();
canvas {
background: black;
}
<canvas id="myCanvas" width="480" height="320"></canvas>
Now we have almost everything we need to solve the main problem. The problems are that we don't have any wall between circles when they touch each other, we don't know the normal of this wall and we must know when two circles are touching each other
Some math theory:
Two circles are touching each other if the distance between their centers are equal (or less) to sum of their radii
Two circles can touch each other only in one point
1.1. To find this point we must know the coordinates of centers of circles and their radii
1.2. Calculate the ratio of two radii
If we draw a radius from center of any circle to this point then the radius will be perpendicular to the wall
We know the coordinates of each circle, we also know their radii and because of the radius is perpendicular we can use it as normal to wall. Notice that if we already have normal to wall we don't need in wall itself
Some math theory:
Let's we have two points A(a_1, a_2) and B(b_1, b_2) and we must find the point M (m_1, m_2) between these two points which divide segment in given ratio R = AM / BM where the AM - is length of AM segment and the BM - is length of BM segment. In general terms, the formula looks like this:
If the ratio is equal to BM / AM then the formula looks like this:
We have same problem but in our situation the centers of circles are the edge points of segment and the ratio is equal to r_1 / r_2. We also have condition that all circles have same radii so the ratio will be equal to 1. Then formula for us will look like this:
Now we know everything to solve the main problem
Let's code it:
const canvas = document.querySelector('#myCanvas');
const ctx = canvas.getContext('2d');
class Dot {
x;
y;
constructor(x, y) {
this.x = x;
this.y = y;
}
}
class Vector {
x;
y;
constructor(x, y) {
this.x = x;
this.y = y;
}
}
class MyMath {
static distance (dot1, dot2) {
return Math.sqrt((dot1.x - dot2.x) ** 2 + (dot1.y - dot2.y) ** 2);
}
static vectorFromTwoDots(dot1, dot2) {
return new Vector(dot2.x - dot1.x, dot2.y - dot1.y);
}
static scaleVector(vector, scale) {
return new Vector(vector.x * scale, vector.y * scale);
}
static sumOfVectors(vector1, vector2) {
return new Vector(vector1.x + vector2.x, vector1.y + vector2.y);
}
static diffOfVectors(vector1, vector2) {
return MyMath.sumOfVectors(vector1, MyMath.scaleVector(vector2, -1));
}
static scalarProduct(vector1, vector2) {
return vector1.x * vector2.x + vector1.y * vector2.y;
}
static reflectionVector(normal, incidenceVector) {
const scalarProduct = MyMath.scalarProduct(normal, incidenceVector);
const dividendVector = MyMath.scaleVector(normal, 2 * scalarProduct);
const divisor = MyMath.scalarProduct(normal, normal);
const subtrahendVector = MyMath.scaleVector(dividendVector, 1 / divisor);
return MyMath.diffOfVectors(incidenceVector, subtrahendVector);
}
}
class Circle {
center;
radius;
speed;
directionVector;
path2D;
constructor(center, radius, speed, directionVector, color) {
this.center = center;
this.radius = radius;
this.speed = speed;
this.directionVector = directionVector;
this.color = color;
}
draw() {
this.path2D = new Path2D();
this.path2D.arc(this.center.x, this.center.y, this.radius, 0, 2 * Math.PI);
ctx.fillStyle = this.color;
ctx.fill(this.path2D);
}
checkCollisionWithVerticalWalls() {
const nextPositionX = this.center.x + this.directionVector.x;
if (
// CHECK IF CIRCLE TOUCHES RIGHT WALL OF SMALLER RECTANGLE
nextPositionX > canvas.width - this.radius ||
// CHECK IF CIRCLE TOUCHES LEFT WALL OF SMALLER RECTANGLE
nextPositionX < this.radius
) {
// REVERSE THE MOVEMENT DIRECTION BY Ox
this.directionVector = MyMath.reflectionVector(new Vector(1, 0), this.directionVector);
}
}
checkCollisionWithHorizontalWalls() {
const nextPositionY = this.center.y + this.directionVector.y;
if (
// CHECK IF CIRCLE TOUCHES TOP WALL OF SMALLER RECTANGLE
nextPositionY > canvas.height - this.radius ||
// CHECK IF CIRCLE TOUCHES BOTTOM WALL OF SMALLER RECTANGLE
nextPositionY < this.radius
) {
// REVERSE THE MOVEMENT DIRECTION BY Oy
this.directionVector = MyMath.reflectionVector(new Vector(0, 1), this.directionVector);
}
}
checkCollisionWithCircle(circle) {
const distanceBetweenCenters = MyMath.distance(this.center, circle.center);
const sumOfRadii = this.radius + circle.radius;
if (distanceBetweenCenters > sumOfRadii) return;
const touchPoint = new Dot(
(this.center.x + circle.center.x) / 2,
(this.center.y + circle.center.y) / 2,
);
const normal = MyMath.vectorFromTwoDots(touchPoint, this.center);
this.directionVector = MyMath.reflectionVector(normal, this.directionVector);
circle.directionVector = MyMath.reflectionVector(normal, circle.directionVector);
}
move() {
this.checkCollisionWithVerticalWalls();
this.checkCollisionWithHorizontalWalls();
this.center.x += this.directionVector.x * this.speed;
this.center.y += this.directionVector.y * this.speed;
}
}
const radius = 16;
const speed = 2;
const circles = [
new Circle(
new Dot(canvas.width / 2 - 30, canvas.height / 2 - 30),
radius,
speed,
new Vector(-1, -1),
'red'
),
new Circle(
new Dot(canvas.width / 2 - 30, canvas.height / 2 + 30),
radius,
speed,
new Vector(-1, 1),
'green'
),
new Circle(
new Dot(canvas.width / 2 + 30, canvas.height / 2 - 30),
radius,
speed,
new Vector(1, -1),
'blue'
),
new Circle(
new Dot(canvas.width / 2 + 30, canvas.height / 2 + 30),
radius,
speed,
new Vector(1, 1),
'yellow'
)
];
function updateFrame() {
// CLEAR CANVAS
ctx.clearRect(0, 0, canvas.width, canvas.height);
// DRAW CIRCLE
for (let i = 0; i < circles.length; ++i) {
circles[i].draw();
}
// MOVE CIRCLE
for (let i = 0; i < circles.length; ++i) {
circles[i].move();
}
// CHECK COLLISION WITH OTHER CIRCLES
for (let i = 0; i < circles.length; ++i) {
for (let j = i + 1; j < circles.length; ++j) {
circles[i].checkCollisionWithCircle(circles[j]);
}
}
}
// DO NOT PAY ATTENTION TO THIS BELOW
// IT IS JUST CONFIGURING GAME LOOP
const targetFPS = 60;
const timeInterval = Math.floor(1000 / 60 * (60 / targetFPS));
let previousFrameTime = performance.now();
(function gameLoop(currentFrameTime = performance.now()) {
requestAnimationFrame((timeStamp) => gameLoop(timeStamp));
if (currentFrameTime - previousFrameTime < timeInterval) return;
previousFrameTime = currentFrameTime;
updateFrame();
})();
canvas {
background: black;
}
<canvas id="myCanvas" width="480" height="320"></canvas>
P.S.
Perhaps there are more optimal methods / algorithms for solving this problem, but I would do this
P.P.S.
Feel free to ask any questions about code or algorithm
