[Collisions] Simple collision detection

[craftworkgames]

Lately I've been interested in getting some simple collision detection and response working.

Note Let me just be clear right up front; I'm not talking about the same type of functionality a physics engine provides.

What I'm talking about is providing a library of classes and methods to implement the type of collision detection you might find in a platformer or other type of non-physics game. I believe if we do it right it could be very useful for a number of different style games without getting in the way too much.

There's an awesome tutorial by the creators of N that goes into quite a lot of detail about how they implemented theirs.

There's also a few great stack overflow answers on the topic:

• a physics engine is not a platformer engine
• resolving multiple collisions
• separating the intersecting objects

I very briefly started roughing out a draft of something last night. Then tonight I spent some time reading and researching how to do it properly. I've raised this issue to keep a record of the knowledge.

[HopefulToad]

That's really interesting. I've frequently run into problems with fast-moving objects, with the result that my standard method of collision detection is now multi-sampling.

[nklbdev]

Please look at this:
https://github.com/kikito/bump.lua
It's really pretty lib

[craftworkgames]

standard method of collision detection is now multi-sampling.

My assumption is that multi-sampling comes with a performance penalty but that would only be a concern if you're trying to squeeze more performance out. If your game is already running nicely there'd be no reason to do so.

Please look at this:
https://github.com/kikito/bump.lua
It's really pretty lib

That lib looks amazing. The github readme alone is incredibly detailed. Obviously it's in LUA but I'm sure it will be good reference for ideas.

Interestingly, they say that it "Handles tunnelling" by default which is basically the same as multi-sampling I think.

[nklbdev]

Hmm... multi-sampling?
It does not move all the objects at the same time as Farseer. You have to move them one by one.
(sorry, it is result of google trahslate from russian)

[craftworkgames]

@polly5315 multi-sampling is defined in the N tutorial.

--= multisampling =--
A much simpler alternative to swept tests is to multisample; instead of performing a single static test at the object's new position, perform several tests at several positions located between the object's previous and new position.

[HopefulToad]

My assumption is that multi-sampling comes with a performance penalty

Unfortunately, it does. With too many objects, the game takes a considerable hit, as I've found out. So I can't use it for everything.

[craftworkgames]

I've been working on this collision detection stuff and I've got a very basic implementation working in the sandbox. I'm not really happy with the design yet.

I also ran into this Sonic Physics Guide which looks like it could be a useful read.

Part of the problem trying to design a big feature like this is trying ti imagine how it's going to be used in the real world. I've been thinking it might be a good idea to create a little game using MonoGame.Extended to help guide the features in the library rather than trying to add them in isolation. I'll be writing a blog post about it soon.

[lithiumtoast]

I wrote something similar to this idea before. The way I did it was to have a "Broadphase" and a "Narrowphase". The Broadphase uses Spatial Partitioning to quickly resolve potential collisions with game entities' bounding volume. For my 2D implementation I used a Quadtree with axis aligned bounding boxes (AABB). The "Narrowphase" is responsible for resolving potential collisions generated from the Broadphase. For my 2D implementation I used the Separating Axis Theorem.

I have an old code base with my implementation and could integrate it into a branch with MonoGame.Extended, but it will need to be cleaned up.

Thoughts?

[craftworkgames]

I have an old code base with my implementation and could integrate it into a branch with MonoGame.Extended, but it will need to be cleaned up.

Thoughts?

Absolutely. I'm not really happy with the current implementation. It was more of an experiment than anything else.

Let's start using branches for big features like this. I've had a bad habit of checking into master, but that's gotta change if we want to do regular releases.

[lithiumtoast]

Alright cool, I'll work on this. I took a look at the Shapes namespace and it looks like I could re-use that for some parts, although I might need to edit code in that namespace for improved clarity / performance. I'll try to keep changes to existing code minimal and necessary and also post requests for the changes here in advance.

EDIT: Eh, just going to leave the Spaces namespace alone.

[craftworkgames]

EDIT: Eh, just going to leave the Spaces namespace alone.

Cool. Take your time with it, just keep me updated every so often.

[lithiumtoast]

Software Planning Document

Last Updated: Wednesday, February 5, 2016

Knowledge Resources

All material linked here was found using Google.
New to the subjects discussed here and want to learn them? I recommend you start with an article, set of slides or a book, unless you genuinely like reading papers.

Articles

(a.k.a. layman blocks of text, sometimes with visuals and questions & answers from the community)

• stackoverflow.com: Broad-phase collision detection methods?
• podgorskiy.com: Let’s talk about broad phase.
• metanetsoftware.com: N Tutorial B - Broad-Phase Collision
• idevgames.com: Collision Detection and Spatial Indexes
• randygual.net: Dynamic AABB Tree
• toptal.com: Video Game Physics Tutorial - Part II: Collision Detection for Solid Objects
• buildnewgames.com: Broad Phase Collision Detection Using Spatial Partitioning
• wikipedia.org: Sweep and prune (broad phase algorithm)
• allenchou.net: Game Physics: Broadphase – Dynamic AABB Tree
• developer.nvidea.com: Broad-Phase Collision Detection with CUDA

Slides (Freely Accessible)

(a.k.a. point form information with visuals, usually made for laymen attending university classes looking to become more experienced or employable)
Warning: Some links may be direct PDF files.

• Introduction to Collision Detection
• Anatomy of a Physics Engine
• Computer Graphics: Broadphase Collision Detection
• Collision Detection: Contact generation and GPU acceleration
• GPU Physics

Books

(a.k.a. those things we buy and hang up on our shelf and stare at the cover while looking up from our computer screens from time to time. also useful to impress our family, friends, and peers when they come over to visit)
You have to pay for these but still great resources nonetheless.

• Real-Time Collision Detection

Papers (Freely Accessible)

(a.k.a. ideas expressed by nerds using labyrinthine words with precise definitions to flex their intellectual prowess)
Warning: Some links may be direct PDF files. To comprehend the subject material a pre-existing knowledge of mathematics (discrete, linear algebra, calculus), operating systems, data structures & algorithms might be required.

• Broad-Phase Collision Detection Using Semi-Adjusting BSP-trees
• Broad Phase Collision Detection
• Efficient Algorithms for Two Phase Collision Detection
• An evaluation of grid based broad phase collision detection for real time interactive environments
• Hardware Accelerated Broad Phase Collision Detection for Realtime Simulations
• Parallelizing Broad Phase Collision Detection for Animation in Games: A Performance Comparison of CPU and GPU Algorithms
• Collision Detection: Broad Phase Adaptation from Multi-Core to Multi-GPU Architecture
• Analysis of Broad-Phase Spatial Partitioning Optimisations in Collision Detection
• Scalable Asynchronous Contact Mechanics with Charm++
• HGrid, Optimal broadphase contact detection
• Efficient Large-Scale Sweep and Prune Methods with AABB Insertion and Removal
• Optimization of Large-Scale, Real-Time Simulations by Spatial Hashing

Definitions

These definitions are for our purposes. They might be defined differently elsewhere.

Collision world

The game component responsible for simulating game object collisions by invoking a broad phase then a narrow phase algorithm.

Collidable object

Any game object which implements the ICollidable interface.

Collision body

A proxy (corresponding) object for a collidable object. Used by the collision simulation to store collision state information about a collidable object such as if the it has moved recently.

Render geometry (a.k.a. object model)

An explicit geometrical representation of a scene object defined by vertices. Used during rasterization of the scene.

Collision geometry

Either an explicit or implicit geometrical representation of a game object defined either by vertices or a mathematical expression, respectively. Commonly used during the narrow phase of the collision simulation.

Bounding volume

A closed volume that completely contains the collision geometry of a game object. Commonly used during the broad phase of the collision simulation.

• Oriented bounding box (OBB): A cuboid (3D), or a rectangle (2D) which contains the collision geometry of a game object even when it is rotated. When a game object is rotated, a OBB has a tighter bounding volume than a AABB for the same collision geometry. However, checking wether two OBBs intersect is more expensive than checking wether two AABBs intersect.
• Axis aligned bounding box (AABB): A cuboid (3D), or a rectangle (2D) which the contains the collision geometry but the box is aligned to the coordinate system of the scene. When a game object rotates the corresponding AABB needs to be updated. For this reason an AABB can be a larger bounding volume than OBB for the same collision geometry. However, checking wether two AABBs intersect is much cheaper than checking wether two OBBs intersect.

Broad phase (a.k.a. n-body processing)

The first pass of the collision simulation which finds pairs of bodies from the world that possibly could be colliding.

Narrow phase (a.k.a. pair processing)

The second pass of collision simulation which resolves the exact collisions, if any, for the given set of pair of bodies.

Convex hull

Smallest convex set (region) of vertices. Used for certain narrow phase algorithms.

Algorithms

The broad phase and narrow phase have many different algorithms, each with their own assumptions of the properties of the game scene and it's objects. Assumed properties for game objects may include the geometrical representation (explicit or implicit), if and how they move, if they are allowed to intersect, and whether they are rigid or flexible. Furthermore, some games may require less or more sophistication from the collision simulation compared to other games. Thus, it's up to the game creator to choose which algorithms, or create a new algorithm, that is most appropriate for use in his or her game. However, using an inappropriate algorithm could have negative consequences on the overall performance of the game.

The following is a list of broad phase and narrow phase algorithms along with their complexity in computational space and time.

2D Broad Phase Algorithms

All broad phase algorithms will need to iterate over the collision bodes at least once.

1. Brute Force
   • Time: O(n^2)
   • Space: O(1)
   • Description: Linearly identifies possibly colliding bodies by checking every pair of bodies to see if their axis aligned bounding boxes (AABBs) intersect. This algorithm is good for games with small amount of collidable objects (< 100).

2D Narrow Phase Algorithms

To be analyzed

[craftworkgames]

Real-Time Collision Detection

I've got that book on my shelf 😄

[craftworkgames]

@lithiumtoast Okay I've created a branch called collision-detection for this feature. The goal is to replace the code in the Collisions folder with something better. Let me know how you go this weekend.

[lithiumtoast]

@craftworkgames I'm working on bounding volumes and I'm not sure if they are better off residing in the Shapes namespace or a BoundingVolumes namespace under the Collisions namespace. See #115

[craftworkgames]

Either Shapes or Collisions is fine with me for the moment. We can always refactor it before release if it doesn't quite fit. I wouldn't create a BoundingVolumes namespace, that'll just be confusing I think.

Great work so far. Would you like me to regularly merge the PR's into my branch? I probably won't have a lot of time to help but I'd be happy to take a closer look and give you feedback as it progresses.

[lithiumtoast]

I'm hesitant to clutter the the Collisions namespace right now with different bounding volumes as there are a few different types of bounding volumes I will be creating over time. I'm thinking it's probably best if they went in the Shapes namespace, cause they are shapes after all and could possibly be used by someone outside the context of collisions (for whatever reason).

[craftworkgames]

I agree. Glad to see you thinking about this stuff.

[lithiumtoast]

@craftworkgames I see there is a GetBoundingRectangle() for IShapeF. I'm thinking of adding a GetBoundingVolume<TBoundingVolume>() where TBoundingVolume : IBoundingVolume to IShapeF. IBoundingVolume will then be AxisAlignedBoundingBox2D or later implemented bounding volumes. This way I could use IShapeF as the collision geometry interface for collision world bodies. What do you think?

[craftworkgames]

On the surface it sounds reasonable. You're welcome to do it and I'll code review.

Btw.. where are you doing this work? I don't see a fork of the repo on your profile.

[lithiumtoast]

@craftworkgames https://github.com/LithiumToast/MonoGame.Extended

I'm going to delete all my commits on my fork and make meaningful commits for each piece of code and then do a pull request when I have something functional and fairly stable.

[craftworkgames]

I'm going to delete all my commits on my fork and make meaningful commits for each piece of code and then do a pull request when I have something functional and fairly stable.

I wouldn't panic about it too much. I don't really care if the commits are meaningful or chaotic. There's really no benefit to wasting your time fixing this stuff up. At the end of the day it's final code that matters and even then it's never going to be perfect.

[lithiumtoast]

@craftworkgames Progress will be posted at #205

[lithiumtoast]

I'm working on the Separating Axis Thorem in #254. I can find the minimum penetration axis and minimum penetration given two convex polygons no problem. The trouble I was having is generating the contact manifold... For the longest time I was trying to find definitions and examples of contact manifolds for SAT in 2D to test that the code is correct, specifically when two convex polygons intersect significantly. I finally found what I was looking for: "Contact Manifolds" by Catto Erin, Blizzard Entertainment, GDC 2007. (Catto Erin created Box2D.) Here is the link to all Catto Erin's posted slides.

[craftworkgames]

Nice work. So what does that mean for the PR?

[lithiumtoast]

That PR will have the separating axis theorem (SAT) algorithm for narrow phase and brute force algorithm for broad phase. Together they offer collision detection which can replace the old code. From there I can do separate PRs to add uniform grid, quad tree, and sweep prune broad phase algorithms. The idea is that people can easily choose which algorithm they would like to use for their game just by passing an instance of IBroadphase2D and INarrowphase2D when constructing the CollisionSimulation2D. From there on out it is less about about collision detection and more about collision response.

[lithiumtoast]

Time flies. I'm extremely busy with other things for the near future. I'm still interested in finishing this hopefully by the end of 2018.

[lithiumtoast]

With @janfokke we have a prototype in the works for this ticket recently. More news soon.