Editing Collision detection (section)

== Usage ==

=== Collision detection in computer simulation ===
{{unreferenced section|date=January 2024}}
Physical simulators differ in the way they react on a collision. Some use the softness of the material to calculate a force, which will resolve the collision in the following time steps like it is in reality. This is very CPU intensive for low softness materials. Some simulators estimate the time of collision by [[linear interpolation]], [[Rollback (data management)|roll back]] the simulation, and calculate the collision by the more abstract methods of [[conservation laws]].

Some iterate the linear interpolation ([[Newton's method]]) to calculate the time of collision with a much higher precision than the rest of the simulation. Collision detection utilizes time coherence to allow even finer time steps without much increasing CPU demand, such as in [[air traffic control]].

After an inelastic collision, special states of sliding and resting can occur and, for example, the [[Open Dynamics Engine]] uses constraints to simulate them. Constraints avoid inertia and thus instability. Implementation of rest by means of a [[scene graph]] avoids drift.

In other words, physical simulators usually function one of two ways: where the collision is detected ''[[Empirical evidence|a posteriori]]'' (after the collision occurs) or ''[[A priori and a posteriori|a priori]]'' (before the collision occurs). In addition to the ''a posteriori'' and ''a priori'' distinction, almost all modern collision detection algorithms are broken into a hierarchy of algorithms. Often the terms "discrete" and "continuous" are used rather than ''a posteriori'' and ''a priori''.

==== ''A posteriori'' (discrete) versus ''a priori'' (continuous) ====
{{Unreferenced section|date=August 2022}}
In the ''a posteriori'' case, the physical simulation is advanced by a small step, then checked to see if any objects are intersecting or visibly considered intersecting. At each simulation step, a list of all intersecting bodies is created, and the positions and trajectories of these objects are "fixed" to account for the collision. This method is called ''a posteriori'' because it typically misses the actual instant of collision, and only catches the collision after it has actually happened.

In the ''a priori'' methods, there is a collision detection algorithm which will be able to predict very precisely the trajectories of the physical bodies. The instants of collision are calculated with high precision, and the physical bodies never actually interpenetrate. This is called ''a priori'' because the collision detection algorithm calculates the instants of collision before it updates the configuration of the physical bodies.

The main benefits of the ''a posteriori'' methods are as follows. In this case, the collision detection algorithm need not be aware of the myriad of physical variables; a simple list of physical bodies is fed to the algorithm, and the program returns a list of intersecting bodies. The collision detection algorithm doesn't need to understand friction, elastic collisions, or worse, nonelastic collisions and deformable bodies. In addition, the ''a posteriori'' algorithms are in effect one dimension simpler than the ''a priori'' algorithms. An ''a priori'' algorithm must deal with the time variable, which is absent from the ''a posteriori'' problem.

On the other hand, ''a posteriori'' algorithms cause problems in the "fixing" step, where intersections (which aren't physically correct) need to be corrected. Moreover, if the discrete step is too large, the collision could go undetected, resulting in an object which passes through another if it is sufficiently fast or small.

The benefits of the ''a priori'' algorithms are increased fidelity and stability.  It is difficult (but not completely impossible) to separate the physical simulation from the collision detection algorithm. However, in all but the simplest cases, the problem of determining ahead of time when two bodies will collide (given some initial data) has no closed form solution—a numerical [[Root-finding algorithm|root finder]] is usually involved.

Some objects are in ''resting contact'', that is, in collision, but neither bouncing off, nor interpenetrating, such as a vase resting on a table. In all cases, resting contact requires special treatment: If two objects collide (''a posteriori'') or slide (''a priori'') and  their relative motion is below a threshold, friction becomes [[stiction]] and both objects are arranged in the same branch of the [[scene graph]].

=== Video games ===
Video games have to split their very limited computing time between several tasks. Despite this resource limit, and the use of relatively primitive collision detection algorithms, programmers have been able to create believable, if inexact, systems for use in games.{{Citation needed|date=August 2014}}

For a long time, video games had a very limited number of objects to treat, and so checking all pairs was not a problem. In two-dimensional games, in some cases, the hardware was able to efficiently detect and report overlapping pixels between [[sprite (computer graphics)|sprite]]s on the screen.<ref>{{Cite web|url=http://amigadev.elowar.com/read/ADCD_2.1/Hardware_Manual_guide/node0004.html#line95|title=Components of the Amiga: The MC68000 and the Amiga Custom Chips|at=Chapter 1|type=Reference manual|archive-url=https://web.archive.org/web/20180717093216/http://amigadev.elowar.com/read/ADCD_2.1/Hardware_Manual_guide/node0004.html#line95|archive-date=2018-07-17|url-status=live|access-date=2018-07-17|quote=Additionally, you can use system hardware to detect collisions between objects and have your program react to such collisions.|edition=2.1}}</ref> In other cases, simply tiling the screen and binding each ''sprite'' into the tiles it overlaps provides sufficient pruning, and for pairwise checks, bounding rectangles or circles called [[hitbox]]es are used and deemed sufficiently accurate.

Three-dimensional games have used spatial partitioning methods for <math>n</math>-body pruning, and for a long time used one or a few spheres per actual 3D object for pairwise checks. Exact checks are very rare, except in games attempting to [[Simulation game|simulate]] reality closely. Even then, exact checks are not necessarily used in all cases.

Because games do not need to mimic actual physics, stability is not as much of an issue. Almost all games use ''a posteriori'' collision detection, and collisions are often resolved using very simple rules. For instance, if a character becomes embedded in a wall, they might be simply moved back to their last known good location. Some games will calculate the distance the character can move before getting embedded into a wall, and only allow them to move that far.

In many cases for video games, approximating the characters by a point is sufficient for the purpose of collision detection with the environment. In this case, [[binary space partitioning]] trees provide a viable, efficient and simple algorithm for checking if a point is embedded in the scenery or not. Such a data structure can also be used to handle "resting position" situation gracefully when a character is running along the ground. Collisions between characters, and collisions with projectiles and hazards, are treated separately.

A robust simulator is one that will react to any input in a reasonable way. For instance, if we imagine a high speed [[Racing game|racecar video game]], from one simulation step to the next, it is conceivable that the cars would advance a substantial distance along the race track. If there is a shallow obstacle on the track (such as a brick wall), it is not entirely unlikely that the car will completely leap over it, and this is very undesirable. In other instances, the "fixing" that posteriori algorithms require isn't implemented correctly, resulting in [[software bug|bug]]s that can trap characters in walls or allow them to pass through them and fall into an endless void where there may or may not be a deadly [[bottomless pit (video gaming)|bottomless pit]], sometimes referred to as "black hell", "blue hell", or "green hell", depending on the predominant color. These are the hallmarks of a failing collision detection and physical simulation system. ''[[Big Rigs: Over the Road Racing]]'' is an infamous example of a game with a failing or possibly missing collision detection system.

==== Hitbox ====<!-- Deleted image removed: [[File:GearheadsCollisionBoxSize.png|thumb|A [[Debug menu|debug]] dialogue box in ''[[Gearheads (video game)|Gearheads]]'' controlling an object's hitbox {{Deletable file-caption|Tuesday, 9 July 2024|F7}}]] -->
<!-- Deleted image removed: [[File:GearheadsCollisionBox.png|thumb|The hitbox of a ''[[Gearheads (video game)|Gearheads]]'' toy, controlled by the above screen {{Deletable file-caption|Tuesday, 9 July 2024|F7}}]] -->

A '''hitbox''' is an invisible shape commonly used in [[video game]]s for real-time collision detection; it is a type of bounding box. It is often a rectangle (in 2D games) or [[cuboid]] (in 3D) that is attached to and follows a point on a visible object (such as a model or a sprite). Circular or spheroidial shapes are also common, though they are still most often called "boxes". It is common for animated objects to have hitboxes attached to each moving part to ensure accuracy during motion.<ref>{{cite web|title=Hitbox|work=Valve Developer Community|url=http://developer.valvesoftware.com/wiki/Hitbox|publisher=[[Valve Corporation|Valve]]|access-date=18 September 2011}}</ref>{{Unreliable source?|date=March 2018|Wikis are not suitable sources.}}

Hitboxes are used to detect "one-way" collisions such as a character being hit by a punch or a bullet. They are unsuitable for the detection of collisions with feedback (e.g. bumping into a wall) due to the difficulty experienced by both humans and [[Artificial intelligence (video games)|AI]] in managing a hitbox's ever-changing locations; these sorts of collisions are typically handled with much simpler [[axis-aligned bounding box]]es instead. Players may use the term "hitbox" to refer to these types of interactions regardless.

A '''hurtbox''' is a hitbox used to detect incoming sources of damage. In this context, the term ''hitbox'' is typically reserved for those which deal damage. For example, an attack may only land if the hitbox around an attacker's punch connects with one of the opponent's hurtboxes on their body, while opposing hitboxes colliding may result in the players trading or cancelling blows, and opposing hurtboxes do not interact with each other. The term is not standardized across the industry; some games reverse their definitions of ''hitbox'' and ''hurtbox'', while others only use "hitbox" for both sides.