# Advise on Collision Detection for N Pixels?

Hey. I am new to Arduboy and I wanted to start out with a simple pixel collision simulator. I was wondering if I could get a bit of advice about the collision detection logic.

I have a Particle Class:

``````class Particle {
int x,y, dx, dy;
public:
void set_values(int,int, int, int);
int get_x();
int get_y();
int get_dx();
int get_dy();
};

#include "./Particle.h"

void Particle::set_values (int j, int k, int l, int n) {
x = j;
y = k;
dx = l;
dy = n;
}
int Particle::get_x () {
return x;
}
int Particle::get_y () {
return y;
}
int Particle::get_dx () {
return dx;
}
int Particle::get_dy () {
return dy;
}
``````

Here is the Ino:

``````/*
* Collider Demo
* At some point... the particles should bounce off one another... or perhaps explode
* Use the Arduboy buttons to add and remove particles? Not sure how to make that dynamic in c...
*/

#include <Arduboy2.h>
#include <Particle.h>
Arduboy2 arduboy;

// define framerate and how many particles.
#define FRAMERATE 60
#define HOWMANYPARTICLES 10

// Define Screen Dimensions
#define H         62
#define W         128

// Bunch of integers.
int dx, dy, cX, cY, initX, initY, initDX, initDY;

// Make an array of particles.
Particle particle[HOWMANYPARTICLES];

void setup() {

// Seed random.

// Setup serial for debugging.
Serial.begin(115200);

// Standard Arduboy stuff.
arduboy.begin();
arduboy.setFrameRate(FRAMERATE);

// The goal of this loop is to randomly place the particles.
if (arduboy.everyXFrames(6)) {
for (int j = 0; j < HOWMANYPARTICLES; j++){
// get initial particle positions.
initX = random(0,W);
initY = random(0,H);

// get random initial particle speeds.
// These forces need to be a part of the object.
initDX = random(1,5);
initDY = random(-1,-5);

// debugging.
Serial.println(initX);
Serial.println(initY);

// set the particle speeds and speeds.
particle[j].set_values(initX, initY, initDX, initDY);
}
}
}

void loop() {
if(!arduboy.nextFrame())
return;
/*
* In short, this nested loop should iterate through each particle and "animate it"
*/
for (int j = 0; j < HOWMANYPARTICLES; j++){
cX = particle[j].get_x();
cY = particle[j].get_y();
dx = particle[j].get_dx();
dy = particle[j].get_dy();
// Used the logic from the following reference for bounds checking.  If the particle reached the boundary set the dx value negative.
// Reference: https://developer.mozilla.org/en-US/docs/Games/Tutorials/2D_Breakout_game_pure_JavaScript/Bounce_off_the_walls
if ((cX + dx > W) || (cX + dx < 0)){
dx = -dx;
}
if ((cY + dy > H) || (cY + dy < 0 )) {
dy = -dy;
}
// This should check if a the current particle shares the same location as the previous particle.
// Is there is less naive way to do this?
if (cX == particle[j-1].get_x() && cY == particle[j-1].get_y()){
dx = -dx;
dy = -dy;
// Debug, print when a collusion occurs.
Serial.println("Collision!");
}
cX += dx;
cY += dy;

arduboy.drawPixel(cX,cY);
particle[j].set_values(cX, cY, dx, dy);
//arduboy.display();
}
arduboy.display();
arduboy.clear();
}
``````

The collision logic does produce output but the particles move to fast to see a vector change. Would this be a good place to do something with a sprite animation?

Thanks!

The way I do collision detection in my fill the cup game is by checking the screen buffer with arduboy.getPixel in the location the current particle wants to move. If its white then it counts as a collision but if it’s black then it’s empty space and you can feel free to move the particle there.

``````      if(canMove(p[i].x+x_vol,p[i].y)){
arduboy.drawPixel(p[i].x,p[i].y,BLACK);
p[i].x+=x_vol;
arduboy.drawPixel(p[i].x,p[i].y,WHITE);

}
bool canMove(uint8_t x, uint8_t y){
if(arduboy.getPixel(x,y)){
return false;
}
return !(x<0||y<0||y>63||x>127);//collision bounds for the particles
}
``````

Here’s relevant code from my game, I’m not sure how useful that is to you but you can see the whole thing at:

I might extract the particle physics from the game and have it as it’s own example but this is the best I can do as of now

1 Like

So do you want to:

• Check if two `Particle`s collide?
• Check if a `Particle` collides with a lit pixel?

And if they do collide, how do you want to react to that?

It does, but that’s not what you want to do because you’ll end up missing collisions.

If the aim is to test all particles against each other rather than testing the particles against screen pixels then you need to do an Nx(N-1) loop to literally test each and every particle against all other particles

Essentially something more like:

``````for(size_t index = 0; index < particleCount; ++index)
{
Particle particle = particles[index];

for(size_t otherIndex = 0; otherIndex < particleCount; ++otherIndex)
{
if(index == otherIndex)
continue;

Particle otherParticle = particles[otherIndex];

if((particle.get_x() == otherParticle.get_x()) && (particle.get_y() == otherParticle.get_y()))
{
// Handle collision
}
}
}
``````

Of course how you actually handle the collision is another matter entirely.

If you want to stick to proper physics it can get quite complicated.

An easy solution is to just invert the particle’s velocities.
It’s probably not very realisitc, but it works and it’s cheap.

`Arduboy2` already provides `width()` and `height()` functions for getting the width and height of the screen.
Alternatively there’s also `WIDTH` and `HEIGHT` (though generally macros should be avoided in favour of `constexpr` variables/functions).

Either way, the screen height is actually 64 pixels, not 62.

You’d be better off calling `arduboy.initRandomSeed()` instead of just using pin noise.

If you’re only using `cX`, `cY`, `dx` and `dy` in this loop then you’d be better off making the variables local.

Generally you should give a variable the least amount of scope that it requires.

This causes a buffer overrun bug when `j` is `0` because arrays don’t have a `-1` element and they don’t wrap around.

If you’re replacing the loop for the Nx(N-1) alternative then it won’t matter this time, but it’s something to bear in mind for the future - make sure that array indices are always between 0 and 1 less than the size of the array (inclusive).

To be honest, considering that your particles are effectively going to be ‘bags of data’, you’d probably be better off just exposing all the member variables publicly. You don’t really gain anything by having getters and setters.

``````struct Particle
{
int x;
int y;
int xVelocity;
int yVelocity;
};
``````

@Spartanfox, there’s a few potential issues with your code…

If you’re checking that `y` and `x` are less than `HEIGHT` and `WIDTH` after calling `getPixel` rather than before then you’ve potentially got a buffer overrun bug because `getPixel` will be reading outside the screen buffer.

Neither `x` nor `y` will ever be less than `0` because `uint8_t` is unsigned and hence is incapable of representing negative numbers.

In other words `canMove` should look more like:

``````bool canMove(uint8_t x, uint8_t y)
{
if((x >= Arduboy2::width()) || (y >= Arduboy2::height()))
return false;

return (arduboy.getPixel(x, y) == 0);
}
``````

(And of course, negative inputs are invalid.)

1 Like

@Spartanfox, Thanks! I haven’t had a chance to study the logic in depth but I think it would work if I were comparing pixels. But after looking at my code I think I needed to compare the particles to each other rather than the pixels they occupy. I believe I mistook a pixel and a particle to be the same thing when they are not.

@Pharap, Thanks for the in depth review and also the code review.

I did indeed want to look at each particle instead of the pixels the occupy. So I used the recommended for loop. I brought in the other recommendations as well especially the struct as that removed the need for the class.

Thanks also for the reference on 2d particle collisions. When I have a bit more time I want to see if I can work some of that physics into the sim.

I am seeing a few other issues but I should go back and read the lessons and the Arduboy2 docs because I want to see if I can figure out why they are happening, before asking.

``````/*
* Collider Demo
* At somepoint... the particles should bounce off one another... or perhaps explode
* Use the arduboy buttons to add and remove particles? Not sure how to make that dynamic in c...
*/

#include <Arduboy2.h>
Arduboy2 arduboy;
BeepPin1 beep;

// define framerate and how many particles.
#define FRAMERATE 60
#define HOWMANYPARTICLES 10

struct Particle
{
int x;
int y;
int xVelocity;
int yVelocity;
};

// Make an array of particles.
Particle particles[HOWMANYPARTICLES];

void setup() {

int initX, initY, initDX, initDY;

// Seed random.
arduboy.initRandomSeed();

// Setup serial for debugging.
Serial.begin(115200);

// Standard Arduboy stuff.
arduboy.begin();
beep.begin();
arduboy.setFrameRate(FRAMERATE);

// The goal of this ugly loop is to randomly place the particles.
if (arduboy.everyXFrames(6)) {
for (int j = 0; j < HOWMANYPARTICLES; j++){
// get initial particle positions.
initX = random(0,arduboy.width());
initY = random(0,arduboy.height());

// get random initial particle speeds.
// These forces need to be a part of the object.
initDX = random(1,5);
initDY = random(-1,-5);

// debugging.
Serial.println(initX);
Serial.println(initY);

// set the particle speeds and speeds.
particles[j].x = initX;
particles[j].y = initY;
particles[j].xVelocity = initDX;
particles[j].yVelocity = initDY;
}
}
}

void loop() {
int dx, dy, cX, cY, collisionCount;
beep.timer();
if(!arduboy.nextFrame())
return;

for(size_t index = 0; index < HOWMANYPARTICLES; ++index)
{
Particle particle = particles[index];

cX = particles[index].x;
cY = particles[index].y;
dx = particles[index].xVelocity;
dy = particles[index].yVelocity;
// Used the logic from the following reference for bounds checking.  If the particle reached the boundary set the dx value negative.
// Reference: https://developer.mozilla.org/en-US/docs/Games/Tutorials/2D_Breakout_game_pure_JavaScript/Bounce_off_the_walls
if ((cX + dx > arduboy.width()) || (cX + dx < 0)){
dx = -dx;
}
if ((cY + dy > arduboy.height()) || (cY + dy < 0 )) {
dy = -dy;
}

for(size_t otherIndex = 0; otherIndex < HOWMANYPARTICLES; ++otherIndex)
{
if(index == otherIndex)
continue;

Particle otherParticle = particles[otherIndex];

if((particle.x == otherParticle.x) && (particle.y == otherParticle.y))
{
// Handle collision
dx = -dx;
dy = -dy;
collisionCount++;
beep.tone(beep.freq(1000), 100);
Serial.println("Collision!");
}
}
cX += dx;
cY += dy;

particles[index].x = cX;
particles[index].y = cY;
particles[index].xVelocity = dx;
particles[index].yVelocity = dy;
arduboy.drawPixel(particles[index].x,particles[index].y);

}

arduboy.print(collisionCount);
arduboy.display();
arduboy.clear();
}
``````
1 Like

`struct`s and `class`es are actually the same thing.
The only difference between them is that `struct`s have `public` access by default and `class`es have `private` access by default.

When you’re dealing with a type that’s only a container for data and/or doesn’t need any extra validation then it’s usually not worth having getters and setters, they typically just add noise.

Just to check, are you aware that you don’t have to declare your variables at the top of the function?
(It’s generally considered good practice to declare them as local as possible.)

Also be aware that if you don’t initialise a variable it ends up with a junk value.
E.g. `collisionCount` won’t be reliable becuase you aren’t setting it to `0` at any point before trying to increment it.

Which issues specifically?
Does this fix any of them?

``````/*
* Collider Demo
* At somepoint... the particles should bounce off one another... or perhaps explode
* Use the arduboy buttons to add and remove particles? Not sure how to make that dynamic in c...
*/

#include <Arduboy2.h>
Arduboy2 arduboy;
BeepPin1 beep;

// define framerate and how many particles.
#define FRAMERATE 60
#define HOWMANYPARTICLES 10

struct Particle
{
int x;
int y;
int xVelocity;
int yVelocity;
};

// Make an array of particles.
Particle particles[HOWMANYPARTICLES];

void setup() {
// Seed random.
arduboy.initRandomSeed();

// Setup serial for debugging.
Serial.begin(115200);

// Standard Arduboy stuff.
arduboy.begin();
beep.begin();
arduboy.setFrameRate(FRAMERATE);

// The goal of this ugly loop is to randomly place the particles.
for (int j = 0; j < HOWMANYPARTICLES; j++){
// get initial particle positions.
int initX = random(0,arduboy.width());
int initY = random(0,arduboy.height());

// get random initial particle speeds.
// These forces need to be a part of the object.
int initDX = random(1,5);
int initDY = random(-1,-5);

// debugging.
Serial.println(initX);
Serial.println(initY);

// set the particle speeds and speeds.
particles[j].x = initX;
particles[j].y = initY;
particles[j].xVelocity = initDX;
particles[j].yVelocity = initDY;
}
}

void loop() {
beep.timer();

if(!arduboy.nextFrame())
return;

int collisionCount = 0;

for(size_t index = 0; index < HOWMANYPARTICLES; ++index)
{
// Make a copy of the particle
Particle particle = particles[index];

// Bounce off the vertical walls
if ((particle.x + particle.xVelocity > arduboy.width()) || (particle.x + particle.xVelocity < 0)) {
particle.xVelocity = -particle.xVelocity;
}

// Bounce off the horizontal walls
if ((particle.y + particle.yVelocity > arduboy.height()) || (particle.y + particle.yVelocity < 0 )) {
particle.yVelocity = -particle.yVelocity;
}

for(size_t otherIndex = 0; otherIndex < HOWMANYPARTICLES; ++otherIndex)
{
// Don't compare a particle against itself
if(index == otherIndex)
continue;

// Copy the other particle
Particle otherParticle = particles[otherIndex];

// If the particles are colliding
if((particle.x == otherParticle.x) && (particle.y == otherParticle.y))
{
// Handle the collision
particle.xVelocity = -particle.xVelocity;
particle.yVelocity = -particle.yVelocity;

// Count the collision
++collisionCount;

beep.tone(beep.freq(1000), 100);

Serial.println(F("Collision!"));
}
}

// Update the particle's position
particle.x += particle.xVelocity;
particle.y += particle.yVelocity;

// Copy the particle back into the array
particles[index] = particle;

// Draw the particle
arduboy.drawPixel(particle.x, particle.y);
}

arduboy.print(collisionCount);
arduboy.display();
arduboy.clear();
}
``````

One last tip: if the particles can’t go off screen then you might want to drop down to `int8_t` for `x`, `y`, `xVelocity` and `yVelocity` - that will allow you to have twice as many particles as you would with `int` because `int8_t` is half the size.

1 Like

I believe beep.timer() needs to go below the next frame too, otherwise the timing will be way off and the beep.tone below wont last for 100 frames. Not sure if that’s one of the issues you’re experiencing but thought it’d mention it none the less.

3 Likes

Yep the updated code is a lot cleaner and reminds me that I still have a lot to learn and relearn about low level resource management and efficient use of variables (less redundancy etc).

I did make the collision counter global and set it in the setup() function because inside of the loop() it would reset to 0. But I did see the random value issue previously when it was not initialized. It is just debugging variable as I would like to see how many collisions have occurred without a serial monitor.

I do not fully understand the implementation of the physics reference [1] but I have been messing with it. I was able to get the first method to work, the one for remote collisions. Once I figure out how to ensure collision of two particles I will test both implementations.

Thanks again. This has been pretty fun

If you want any tips, advice or information feel free to ask.

Nor do I really, I just grabbed something that looked like it knew what it was talking about.
The main point was to illustrate that resolving collisions ‘properly’ is quite difficult and rather maths-intensive.

(There’s also the issue of whether to consider particles to be circles or polygons - each would probably result in a different collisions resolution algorithm.)

I think I chose that page purely because of the diagram with the three circles:

1 Like