This is the sixth in the canvas series of notes to study and review. For the full notes, see Canvas Core Technologies.
In the last Canvas Core technology – How to achieve complex animation notes, we discussed in detail the time factor, physical factor and so on need to be considered in the production of complex animation, and also reviewed how to use the easing function to distort the time axis to achieve nonlinear motion, such as common slow in, slow out, slow in and slow out, etc. In games or animations, moving objects may collide with each other in the process of change. In this chapter, we will learn how to conduct collision detection in detail.
Boundary value detection
The simplest detection method is boundary value detection, which is to judge the conditions of some attributes of a moving object. If this condition is reached, it means that a collision has occurred. For example, in the example in the last article, the ball is falling freely. When detecting whether the ball collides with the ground, we detect whether the falling height of the ball FH reaches dh, the height between the ball and the ground. If FH > DH, it indicates that the ball has collided with the ground.
let distance = ball.currentSpeed * t;
if (ball.offset + distance > ball.verticalHeight) {
// Hit the ground, there was a collision
// ...
} else {
// It has not hit the ground yet
ball.offset += distance;
}
Copy the codeHere is my complete online example of a ball in free fall
This detection method is very simple and accurate. When developing similar businesses, we can simplify it into boundary value detection. But when we are developing more complex games, boundary value detection is often not implemented well, and it is often used in conjunction with other detection methods to be more realistic.
External graph detection
In Canvas game, we can abstract irregular objects, such as moving little people, into a rectangle, so that the rectangle can exactly wrap the object. In collision detection, we can use this rectangle to replace the actual object. This method, in fact, is to simplify the complexity through abstraction. For animations or games where the accuracy is not so high, we can directly use this kind of external graphics to detect. In the abstract graph, we should according to the specific object, for example, the small man can be abstracted into a rectangle, the sun will be abstracted into a circle, the specific object is abstracted with its similar shape, so that the detection will be more accurate.
After the graph abstraction, we only need to detect the graph in the detection. For the collision of two figures, we only need to judge whether there is an intersection part between them. If there is an intersection part, then it can be considered that there is a collision, otherwise there is no collision. Next, we will study the collision detection of rectangle and rectangle, circle and circle, and rectangle and circle respectively.
Rectangle colliding with rectangle,
Here is a list of all the situations where two rectangles collide. The specific code in Canvas is as follows:
/* Determine if two rectangles collide */
private didRectCollide(sprite: RectSprite, otherSprite: RectSprite) {
let horizontal = sprite.left + sprite.width > otherSprite.left && sprite.left < otherSprite.left + otherSprite.width;
let vertical = sprite.top < otherSprite.top + otherSprite.height && sprite.top + sprite.height > otherSprite.top;
return horizontal && vertical;
}
Copy the codeIn fact, it is to determine whether the two rectangles overlap in the horizontal and vertical directions.
Circles collide with circles,
To determine whether two circles collide is to determine whether the distance between the centers of two circles is less than the sum of their radii. If the distance is less than the sum of their radii, a collision occurs, otherwise there is no collision. Basically, it calculates the distance between two centers, which can be obtained according to the distance formula between two points in the coordinate system,
The specific code in Canvas is as follows:
/* Determine if two circles collide */
private didCircleCollide(sprite: CircleSprite, otherSprite: CircleSprite) {
return distance(sprite.x, sprite.y, otherSprite.x, otherSprite.y) < sprite.radius + otherSprite.radius;
}
Copy the codeRectangles and circles collide,
In this case, it is determined whether the distance between the circle and the nearest point on the rectangle is less than the radius of the circle. If it is less than the radius of the circle, the collision occurs; otherwise, no collision occurs. First, we need to find the coordinates of the nearest point of the circle to the rectangle. In this way, we need to consider five situations: the center of the circle is to the left of the rectangle, the center is above the rectangle, the center is to the right of the rectangle, the center is under the rectangle, and the center is inside the rectangle. If the center is inside the rectangle, it must collide. The other four cases are calculated based on each case to find the point closest to the center of the rectangle. Here’s an example of one of the cases. The other cases work similarly, like the center of the rectangle on the left,
In this case, the x-coordinate of the nearest point is equal to the x-coordinate of the top left corner of the rectangle, is equal to the y-coordinate of the center of the circle, and that gives us,
/* Check if rectangle and circle collide */
private didRectWidthCircleCollide(rectSprite: RectSprite, circleSprite: CircleSprite) {
let closePoint = { x: undefined.y: undefined };
if (circleSprite.x < rectSprite.left) {
closePoint.x = rectSprite.left;
} else if (circleSprite.x < rectSprite.left + rectSprite.width) {
closePoint.x = circleSprite.x;
} else {
closePoint.x = rectSprite.left + rectSprite.width;
}
if (circleSprite.y < rectSprite.top) {
closePoint.y = rectSprite.top;
} else if (circleSprite.y < rectSprite.top + rectSprite.height) {
closePoint.y = circleSprite.y;
} else {
closePoint.y = rectSprite.top + rectSprite.height;
}
return distance(circleSprite.x, circleSprite.y, closePoint.x, closePoint.y) < circleSprite.radius;
}
Copy the codeHere is my online example of add-on graphics collision detection.
Ray projection detection
Ray projection method: draw a line coincident with the velocity vector of the object, and then start from another object to be detected, draw a second line, according to the intersection of the two lines to determine whether there is a collision.
Light projection will commonly combined with boundary value testing for strictly accurate judgment, this method requires that we in the animation updates, constantly to calculate the intersection of two velocity vector coordinates, according to the intersection point coordinate determine whether meet the collision conditions, intersection point meet the conditions, we need to use boundary value detection method to detect moving object boundary value conditions, A collision is judged to have occurred only when both are satisfied. This kind of detection, accuracy is generally relatively high, especially suitable for moving fast objects. Taking the example of ball dropping into a bucket, the detection code is as follows:
/* Whether a collision occurred */
public didCollide(ball: CircleSprite, bucket: ImageSprite) {
let k1 = ball.verticalVelocity / ball.horizontalVelocity;
let b1 = ball.y - k1 * ball.x;
let inertSectionY = bucket.mockTop; // Compute the Y coordinate of the intersection
let insertSectionX = (inertSectionY - b1) / k1; // Compute the X coordinate of the intersection
return (
insertSectionX > bucket.mockLeft &&
insertSectionX < bucket.mockLeft + bucket.mockWidth &&
ball.x > bucket.mockLeft &&
ball.x < bucket.mockLeft + bucket.mockWidth &&
ball.y > bucket.mockTop &&
ball.y < bucket.mockTop + bucket.mockHeight
);
}
}
Copy the codeHere is my online example of raycast detection.
Separation shaft detection
When judging the collision detection of convex polygons, we can use the split axis method. Before learning separation axis detection, we need to be familiar with some basic knowledge of vectors.
Vector basics:
- In a planar two dimensional coordinate system, we can use vectors to represent the position of a point. Vector representation is the point from the origin (0,0) to the target point (x, y).
- You subtract two vectors, you get another new vector.
- You take the dot product of two vectors, you get the value of the projection.
- The unit vector, which is a vector of length one, is really just a direction.
- One vector is perpendicular to another vector, we call it the practice vector.
As you can see in the picture,
Separation axis detection idea,
- Firstly, all the projection axes of the detected polygon are obtained. Generally, it is only necessary to calculate the projection axes of the corresponding sides of the polygon
- Calculate the projection of the detected polygon on each projection axis
- Determine whether their projections overlap. If the projections on any projection axis do not overlap, then they do not collide; otherwise, they collide
/* Determine whether a collision occurred */
public didCollide(sprite: Sprite, otherSprite: Sprite) {
let axes1 = sprite.type === 'circle' ? (sprite as Circle).getAxes(otherSprite as Polygon) : (sprite as Polygon).getAxes();
let axes2 = otherSprite.type === 'circle' ? (otherSprite as Circle).getAxes(sprite as Polygon) : (otherSprite as Polygon).getAxes();
// Get all the projection axes
// Step 2: Get the projection of the polygon on each projection axis
// Step 3: Check whether there is a projection axis on which the polygon's projections do not intersect. If there is a projection axis on which the polygon's projections do not intersect, return false directly. If there is a projection axis on which the polygon's projections do intersect, it indicates that the polygon's projections collide.
let axes = [...axes1, ...axes2];
for (let axis of axes) {
let projections1 = sprite.getProjection(axis);
let projections2 = otherSprite.getProjection(axis);
if(! projections1.overlaps(projections2)) {return false; }}return true; }}Copy the codeNow we follow these three steps to achieve the separation shaft detection method step by step.
Get projection axis
In a polygon, we build an edge vector with an edge, and the normal vector of an edge vector is the projection axis of this edge. For the projection axis, we just need its direction, so we format it as a unit vector.
// Get the projection axis of the convex polygon
public getAxes() {
let points = this.points;
let axes = [];
for (let i = 0, j = points.length - 1; i < j; i++) {
let v1 = new Vector(points[i].x, points[i].y);
let v2 = new Vector(points[i + 1].x, points[i + 1].y);
axes.push(
v1
.subtract(v2)
.perpendicular()
.normalize(),
);
}
let firstPoint = points[0];
let lastPoint = points[points.length - 1];
let v1 = new Vector(lastPoint.x, lastPoint.y);
let v2 = new Vector(firstPoint.x, firstPoint.y);
axes.push(
v1
.subtract(v2)
.perpendicular()
.normalize(),
);
return axes;
}
Copy the codeAfter obtaining the projection axis of the graph to be detected, we need to calculate the projection of the graph on each projection axis
public getProjection(v: Vector) {
let min = Number.MAX_SAFE_INTEGER;
let max = Number.MIN_SAFE_INTEGER;
for (let point of this.points) {
let p = new Vector(point.x, point.y);
let dotProduct = p.dotProduct(v);
min = Math.min(min, dotProduct);
max = Math.max(max, dotProduct);
}
return new Projection(min, max);
}
Copy the codeAnd finally determine whether the projections overlap
/* Whether the projection overlaps */
overlaps(p: Projection) {
return this.max > p.min && p.max > this.min;
}
Copy the codeAmong them, if it is a circle and a convex polygon, the calculation of the projection axis corresponding to the circle is special. The circle has only one projection axis, which is the vector between the center of the circle and the nearest vertex of the polygon.
// Get the projection axis of the circle
public getAxes(polygon: Polygon) {
// For a circle, to get its projection axis is to connect the center of the circle to its nearest vertex from the polygon
let { x, y } = this;
let nearestPoint = null;
let nearestDistance = Number.MAX_SAFE_INTEGER;
for (let [index, point] of polygon.points.entries()) {
let d = distance(x, y, point.x, point.y);
if(d < nearestDistance) { nearestDistance = d; nearestPoint = point; }}let v1 = new Vector(x, y);
let v2 = new Vector(nearestPoint.x, nearestPoint.y);
return [v1.subtract(v2).normalize()];
}
Copy the codeHere is an online example of my separation axis detection.
summary
This note records the collision detection methods in 2D graphics in detail. The relatively simple methods are external graphics method and boundary value detection method, which are not so precise. The more complex and accurate methods are ray projection method and separation axis method. We chose different methods according to different scenarios and accuracy requirements. In addition, in addition to the above methods, there are also pixel detection and other methods to achieve collision detection. Pixel detection is detected in the unit of pixel. If there are opaque pixels overlapping on the same coordinate, it means that a collision has occurred. For detailed implementation, you can view Pixel Accurate Collision Detection with Javascript and Canvas.
For these detection methods, it is strongly recommended to master the separation axis method, because it is the most widely used, for any convex polygon, it can be more accurate detection. Due to the separation of shaft test computation is compared commonly big, so before the test, we never would have happened to filter out the first collision of graphics, a general method is the spatial separation method, filtering or not visible graphic visual interval, etc., and then to the small part of possible collision graphics to calculate detection, this can improve detection rate.
reference
- “Wait, I touch! — Common 2D collision detection [Part of the picture quotes from this article, this article is better, I suggest readers have a look]
- HTML5 Canvas Core Technology: Graphics, Animation and Game Development