Detecting collision algorithm

In the previous post, I talked about how I learned to build a basic game.

Take a look at the game here, play it, and come back.

One challenge I had while developing it, was how can I detect the collision between the square and the balls (I didn't give them cute names yet?!).

I held a paper and drew an imaginary frame that captures the square with a group of balls in different positions:

1- A square surrounded by 7 balls

I wanted to understand how I can know if any of these balls are touching the edges of the square.

Clearly, if the ball touches the square, then the distance between the centerline of the circle and the centerline of the square should equal (diameter+side)/2.

So, let's have a variable named touching that holds that distance. The problem was: which centerline should I consider: the horizontal or the vertical?
Consider this frame:

2- Vertical and horizontal centerlines

Each one gives different distances, and only one is a correct indication to a no collision, but using our human intuition is a start to understand how the natural algorithm works.

They are not touching, which means that the distance between the two centerlines should be greater than touching, which means that the natural algorithm picks the horizontal centerlines (the vertical centerlines says there's a collision!). By noticing multiple circles, I noticed a pattern: if the circle intersects with the vertical extension of the square, then we pick the vertical distance (between the horizontal centerlines), and if the circle intersects with the horizontal extension, we pick the horizontal distance:

3- The circle intersects with the vertical extension

Another example, ball number 4: it intersects with the horizontal extension of the square, then we consider the horizontal distance which is equal to touching.

Ok, the tough part is demystified, now we know how the algorithm will work, but how we know with which extension the circle intersects?

It's easy actually: we calculate the distance between the most right x and the most left x (of both the circle and the square), and the same for the y-axis, the one with greater value is the axis with the extension that intersects with the circle (if it's greater than diameter+side then the circle is outside the two square extensions, like circle #7). The code looks like:

right = Math.max(square.x+square.side, circle.x+circle.rad);

left = Math.min(square.x, circle.x-circle.rad);

bottom = Math.max(square.y+square.side, circle.y+circle.rad);

top = Math.min(square.y, circle.y-circle.rad);

if (right - left > down - top) {

//compare with horizontal distance

}

else {

//compare with vertical distance

}

/*These equations assume that the reference point of the square is at its top left corner, and the reference point of the circle is at its center*/

And that ends the collision algorithm. Maybe there's a known algorithm for this, maybe it's simpler, I didn't search, I got excited with the problem and started solving it my self.

Building a game - the curiosity part

I’m really excited to be back to writing, been a tough time during corona, but learned a few things that I want to share.

One of the most interesting fields of programming is game development, I don’t have that much experience (actually I don’t have game development experience at all) to give that bold statement but I think creativity is at its peak when there is an imaginary story, and when you build “a whole new world” with code.

I was viewing my Twitter feed randomly as usual, until I found a tweet by Filip Hráček, that has a link to a game he’s developed, I played it and loved it so much, loved its simplicity and the reality, and its application of physics laws.

As an online surfer, I loved it, and as a programmer, I wished I can create things that have so much life in its movements on screen. But the problem is that I didn’t know where should I start! Thankfully, someone in the replies in that tweet mentioned a playlist that seemed to cover this topic, I started watching it right away, day after day. A week after, I was a big fan of Shiffman’s work already and his channel, he is a very talented teacher, funny and professional in his material, take a second to think how lucky we are to have all these combinations together available on the internet for free, what a time we are living, no really, with all bad things happening in the world, people like Shiffman give it a reason for hope. I watched almost all the videos on the playlist.

That sort of finding is invaluable, which you find hidden somewhere by mere accident (I mean the reply in Filip’s tweet), a lot of things I’ve learned that way, no prior planning, just pure desire of knowing something and learning it IMMEDIATELY. The material discussed in the playlist is exactly what I needed to build a game like Filip’s. I was still loving his game (as an online surfer) and playing it from time to time along with watching Shiffman’s videos, it gave me the needed fuel to continue learning.

After a period of time, I made some work with p5js- the JavaScript library used in Shiffman’s videos to apply physics of particles, it’s sometimes confusing to see what the channel is exactly teaching: is it tutorials on p5js library? or it’s physics and math tutorials applied with the help of p5js library?- actually, it’s both, and p5js is a really very good library to use for that purpose. At the end of the playlist, I had already made some work (as I mentioned when I was following Shiffman’s tutorials); one of them was about a square that can be pushed up under an upward force until it's left to the gravitational force down until its rest on the “floor”, with a nice natural bouncing effect (Euler's effect).

and another one was about balls moving around the screen in random directions and get redirected when they hit the edges of the canvas. I combined both ideas and made a game, named it Mates (play it to know why I chose that name 😁):
https://mshwf.github.io/mates

I’m excited I'm finally making a game that I myself can play and even enjoy it, though, it’s not the same level of complexity as Filip’s, but I’m satisfied with the result, I understood the math and physics concepts that one need to make that sort of games, and I can improve easily now (my curiosity is fine).

In the next post, I will discuss the collision algorithm I developed, which I think is interesting to talk about. Hope you enjoy it.