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. 
  randomSeed(analogRead(0));
  
  // 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 Particles 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.


A few comments about the code:

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

structs and classes are actually the same thing.
The only difference between them is that structs have public access by default and classes 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

[1] https://www.plasmaphysics.org.uk/programs/coll2d_cpp.htm

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:
collision

1 Like