Most 2D arcade video games are filled with action of moving objects. Collision in video games has been very important and one of several major aspects in arcade game development. 2D Nintendo games like Mario Bros, Mega Man and Contra are examples where collision mechanism plays important part and these games would be impossible to play without proper collision detection. Interaction between two objects attempting to occupy the same space usually needs to be considered. The process by which collision engine determines such event is called collision detection. It is crucial to understand this concept because many collision problems and glitches can arise if the collision engine developer or designer does not adequately understand this concept. Glitches like:

  • undetected collision
  • fast object bypasses thin wall
  • main character or object stuck in wall or floor
  • main character able to bypass and move to forbidden or unwanted place

can be avoided if this concept is understood.

This article is structured into six parts. Background chapter defines the importance of collision concept, Scope chapter defines the scope or boundary for this paper, Collision Detection Concept chapter describes related terminology used in this paper and also elaborates every collision concept in a brief manner. Collision Detection Phase describes two phases and algorithms available for us to choose for each phase. Geometry Calculation phase gives mathematic calculation and algorithm for detecting collision between two 2D geometrical shapes. Collision Detection Problems chapter describes various cases of collision detection and resolve problems from trivial to complex followed by the solution to each of these problems, and finally in Conclusion and Future Work we summarize list of all collision detection concept and collision problems and also briefly describes what is not covered in this paper to act as our future work.

2D Arcade Video Game

2D Arcade Video Game is a type of 2D video game where the player needs to focus on arcade action games by using player’s reflexes. This type of game usually uses very little puzzle-solving, complex thinking, or strategy skills. Player’s age range widely from childhood to old age. Some examples are: Donkey Kong, Pac-man, Space Invader, Mario Bros, Contra (fig. 1), Tron. (Herman, Horwitz, Kent, & Miller, 2002) 2D arcade video games rely heavily on collision detection and response, incorrect implementation on those concepts can cause significant effect on quality of the games.

Figure 1 Contra as example of 2D Arcade Video Games

2D Physics Engine

2D physics engine is engine for 2D arcade video games to simulate physics, it handles all collision detection and response. It also contains mechanics of game movement and additional element of physics such as force, inertia, moment, torque, etc if so desired by game developer. There are several examples of 2D physics engine such as: Matter.js (JavaScript), JBox2D (Java), Dyn4j (Java), Bullet (C++), JBullet (Java), Chipmunk2D (C). Although many physics engine existed, there are reasons why we want to develop our own physics engine:

  1. For the purpose of research and simulation, we need to understand exactly what is going on in background instead of just using abstraction from another physics engine.
  2. We can customize our physics engine to utmost detailed, high degree of customization and most relevant physics for 2D game that we want to develop while using abstraction from another physics engine is often hard to customize or fine-tune to our needs.
  3. Sometimes it is rather hard to use other physics engine correctly (bug-free implementation). Hours of careful documentation reading must be performed before we can use other physics engine correctly, in addition, some physics engines have badly written documentation.
  4. While sometimes we need both advantages of two physics engines, using combined two or more physics engines in one game implementation is always a bad idea and almost impossible to do because each physics engine has its own mechanism/system for collision detection and object storage structure and also its own event handling. Building from scratch can gain those advantages of other physics engines and perfect integration with our game engine that suits our need.
  5. Additional reasons described by Steffen Itterheim (Itterheim, 2013):
    1. Physics engine contact detection can be more expensive (slower) than it should be, we cannot optimize according game need.
    2. Physics engine often has glitches either from wrongly used or that physics engine developer’s incorrect implementation
    3. When using another physics engine we are locked by its way of moving objects (either force-based, impulse-based), physics engine often won’t support tweaking directly to acceleration, speed and position of an object. Those are already encapsulated for abstraction. For example , let us consider a very simple maneuver in game: landing.

Suppose the game rules define that player character should not bounce off of the ground when it lands. If we use another physics engine, unfortunately, with physics this bouncing behavior is pretty much guaranteed. And it is difficult to circumvent: we have to determine what actually landed, and then we have to reset the velocities. The difficulty lies not only in writing code and the tweak we need correctly, but considering the various circumstances where this ideal scenario breaks. For example: landing on a moving platform, or disregarding pickup items because we don’t actually land on them, etc.

For the next part , we will discuss more detail about collision detection concept in 2D.