A Basic Introduction to Collision Detection Without Algorithms

I think, before we start looking at an example, we need to discuss what collision detection even is. Collision detection is a set of algorithms that is used to introduce physics into our game world. Specifically the physics of collision. Depending on the game that you choose to make this could look like the player character landing on a platform in a platformer, it could be a weapon hit with an enemy, or running into a boundary in a dungeon crawler.

Apr. 8, 2024 1023 words problem-solving ·

Understanding our 2D game world

To get started with this post, we’re going to jump back into the game that I’m currently building with the in-person class that I’ve been teaching at a local library. This is the submarine game, where there is a battle ship dropping depth charges on submarines lurking below. The game we’re patterning our game off of is sink sub, if you want to check it out via Youtube.

Lets think about the game entities that exist within our game. We have a battleship, a slice each of submarines, depth charges, and torpedoes. Every one of these entities (or structs) share the same set of properties:

Location
Dimension

We can look at it like this:

package main

import "github.com/hajimehoshi/ebiten/v2"

// Our core positioning data stored for a game entity, called Entity
type Entity struct {
	X float64
	Y float64
	Width float64
	Height float64
}

func (e *Entity) Collides(alt *Entity) bool {
	if(/*actual collision check*/) {
		return true
	}
	return false
}

// We can embed our entity like this in a different type
// This is stored as a top level component, meaning that it's components and methods can be accessed by
// the wrapping struct.
type Ship struct {
	*Entity
}

func (s *Ship) Update() error {
	// Handle movement and firing logic
	return nil
}

type Submarine struct {
	*Entity
}

func (s *Submarine) Update() error {
	// Handle AI movement and firing logic
	return nil
}

type DepthCharge struct {
	*Entity
}

func (dc *DepthCharge) Update() error {
	// Handle AI movement logic
	return nil
}

type Torpedo struct {
	*Entity
}

func (t *Torpedo) Update() error {
	// Handle AI movement logic
	return nil
}

Before we can get started talking about collision detection, lets look at an image to remind ourselves how the 2D graphics work in ebitengine (and likely many other game engines). The top left is our 0, 0 origin. As x increases we go to the right, as y increases we go to the bottom.

Collision detection overview

We’ll need to keep this concept in mind as we go over the high-level perspective of collision detection.

Our algorithm free algorithm

Great, we’ve set the groundwork to start thinking about collision detection.

But what do I mean by algorithm free algorithm? An algorithm is just a set of steps to take to accomplish something, in our case steps in code. To keep this discussion a bit more high level, I just want to discuss the general algorithm of running through collision detection, rather than specific algorithms for actually determining collisions (those will come later).

First, we need to identify the in game entities that will need to have collisions detected between.

Ship and torpedoes
Submarines and depth charges
Torpedoes and depth charges

Now that we know what needs to have collision detection, we can think about what this might look like within our game.

Update the ship
Update the submarines
Update the depth charges
Update the torpedoes
Check for collisions between the ship and all torpedoes
Check for collisions between all submarines and all depth charges
Check for collisions between all torpedoes and all depth charges

Here are some illustrations of what our collision detection is checking for in our submarine game. The first image with green shows two game entities without a collision. The second image with red entities show a collision.

Let’s now look at some game code that outlines this algorithm.

// This code continues from the code above.
type Game struct {
	ship *Ship
	subs []*Submarine
	torpedoes []*Torpedo
	depthCharges []*DepthCharge
}

func (g *Game) Update() error {

	// Handle entities individual update methods
	g.ship.Update()
	for _, sub := range g.subs {
		sub.Update()
	}
	for _, torpedo := range g.torpedoes {
		torpedo.Update()
	}
	for _, dc := range g.depthCharges {
		dc.Update()
	}

	// Check collisions on our ship from the torpedoes
	for _, torpedo := range g.torpedoes {
		if g.ship.Collides(torpedo) {
			// We have a collision, update game i.e. ship health, ship animation, torpedo explosion animation
		}
	}

	// Check collisions on our subs from each depth charge
	for _, sub := range g.subs {
		for _, dc := range g.depthCharges {
			if sub.Collides(dc) {
				// We have a collision with a sub and depth charge, update game states i.e. sub health, sub animation, depth charge explosion animation
			}
		}
	}

	// Check collisions on a depth charge and a torpedo
	for _, dc := range g.depthCharges {
		for _, torpedo := range g.torpedoes {
			if dc.Collides(torpedo) {
				// We have a collision with a depth charge and a torpedo, update game states i.e. show explosions
			}
		}
	}

	return nil
}

func (g *Game) Draw(screen *ebiten.Image) {
	// Handle drawing all of our screen components
}

func (g *Game) Layout(w, h int) (int, int) {
	return w, h
}

Collisions are the core of games

As you’ve gone through this post, I hope you have a high level understanding of what we need to accomplish in our games. Collisions really are the core of our games. They are what bring about a sense of reality into our game.

But, if you’ve noticed, we haven’t really talked about the core algorithm for determining if we’ve had a collision. Those are more complex algorithms as well, and they vary in complexity depending on the game environment and accuracy required. I wanted to skip over them today, to just give a sense of understanding to the overall thought process and logic of solving our collision detection problem.