Collision Detection (Game Design)

Processing Coding Questions
1

Hi! I’m trying to make a platformer style game. I already have most of the physics done, but I’m now trying to do the collision detection and I’m stumped. I can think of ways to do it, but in my game, the levels will be randomly generated with Cellular Automata (Basically, I’m going to need over 500 rectangles). Is there a relatively clean way of doing this so it won’t lag?

Physics Code

boolean onGround, isColliding;
boolean switch1;
boolean wasd=true;
boolean isLeft, isRight, isUp, isDown;
float x=0;
float y=0;
int unit;
float yVel=0;
float xVel=0;

void setup() {
  fullScreen();
  unit=width/50;
  x=width/2;
  y=height/2;
}
void draw() {
  y=y-yVel/3.0;
  x=x+xVel/3.0;
  if(y>height-15)y=height-15;
  if(y==height-15)yVel=-yVel*.30;
  if(isLeft && isRight)xVel=xVel*0.8;
  if(!(isRight && isLeft)){
   if (isLeft && abs(xVel)<3){
     if(xVel<-0.1)xVel=xVel*1.1;
     if(xVel>0.1)xVel=xVel-0.5;
    if(xVel<0.1 && xVel>-0.1)xVel=0.2;
   }  
   if (isRight && abs(xVel)<3){
    if(xVel>0.1)xVel=xVel*1.1;
    if(xVel<-0.1)xVel=xVel+0.5;
    if(xVel<0.1 && xVel>-0.1)xVel=0.2;
   }
  }
  if(isUp && onGround==true)yVel=10;
  if (!isRight && !isLeft)xVel=xVel*0.8;
  
  //Gravity
  if(yVel>0.1)yVel=yVel*0.95-0.06;
  if(yVel<0.1)yVel=-abs(yVel*1.05-0.06);
  
  if (isUp)yVel=10; 
  
  
  fill(255,12);
  rect(0,0,width,height);
  fill(0);
  rectMode(CENTER);
  rect(x,y+6,3,3);
  if(!isDown)rect(x,y,3,9);
  rectMode(CORNER);
  
  
  
  //Buttons
  fill(255,127);
  rect(20, 20, 50, 30);
  fill(0,127);
  textSize(unit/2);
  text("close", 45, 35);
  
  
  
  
  //Key Indacator
  
  //W or Up
  fill(128,127);
  if(isUp)fill(255,127);
  rect(unit*3/2.0,height-7.0/4*unit,unit*3.0/4,unit/2.0);
  
  //A or Left
  fill(128,127);
  if(isLeft)fill(255,127);
  rect(unit/2.0,height-unit,unit*3.0/4,unit/2.0);
  
  //S or Down
  fill(128,127);
  if(isDown)fill(255,127);
  rect(unit*3/2.0,height-unit,unit*3.0/4,unit/2.0);
  
  //D or Right
  fill(128,127);
  if(isRight)fill(255,127);  
  rect(unit*5/2.0,height-unit,unit*3.0/4,unit/2.0);
  
  //WASD and arrow keys switcher
  textSize(unit/3);
  textAlign(CENTER, CENTER);
  fill(0);
  if(!switch1)text("WASD Mode",unit*1.875,height-8.875/4*unit);
  if(switch1)text("Arrow Keys Mode",unit*1.875,height-8.875/4*unit);
  fill(128,127);
  rect(unit/2.0,height-10.0/4*unit,unit*2.75,unit/2.0);
  
  
}
 
void mousePressed() {
  if (mouseX >= unit*0.5 && mouseX < unit*3.25 && mouseY >= height-2.5*unit && mouseY < height-2*unit) {
      if(switch1==true)switch1=false;
      else if(switch1==false)switch1=true;
  }
  if (mouseX >= 20 && mouseX < 70 && mouseY >= 20 && mouseY < 50) {
      exit();
  }
  
}

void keyPressed() {
  if(!switch1)setMove(key, true);
  if(switch1)setMove(keyCode, true);
}
 
void keyReleased() {
  if(!switch1)setMove(key, false);
  if(switch1)setMove(keyCode, false);
}
boolean setMove(int k, boolean b) {
  switch (k) {
  case 'w':
    return isUp = b;
  case UP:
    return isUp = b;
  case 's':
    return isDown = b;
  case DOWN:
    return isDown = b;
  case 'a':
    return isLeft = b;
  case LEFT:
    return isLeft = b;
  case 'd':
    return isRight = b;
  case RIGHT:
    return isRight = b;
  default:
    return b;
  }
}

Cellular Automata Code (Just a rough draft)

int cols;
int rows;
int bias=42;
int[][] grid;
int[][] finalGrid;

void setup(){
  size(800,600);
  cols = width/10;
  rows = height/10;
  
  // Declare 2D array
  grid = new int[cols][rows];
  finalGrid = new int[cols][rows];
  
  // Initialize 2D array values
  for (int i = 0; i < cols; i++) {
    for (int j = 0; j < rows; j++) {
      grid[i][j] = int(random(100));
      if(grid[i][j]<bias)grid[i][j]=0;
      if(grid[i][j]>=bias)grid[i][j]=1;
    }
  }
}

int numberOfNeighbors(int gridX, int gridY){
  int c=0;
  for (int i = gridX-1; i < gridX+2; i++) {
    for (int j = gridY-1; j < gridY+2; j++) {
      if(j!=-1 && i!=-1 && i!=cols && j!=rows){
        if(grid[i][j]==0){
          if(!(i==gridX && j==gridY)){
            c=c+1;
          }
        }
      }else{
       c=c+1;
        
      }
    }
  }
  return(c);
}

void draw(){
 smooth();
 for (int i = 0; i < cols; i++) {
    for (int j = 0; j < rows; j++) {
      
      stroke(grid[i][j]*256);
      textSize(4);
      rectMode(CENTER);
      fill(grid[i][j]*256);
      rect(10*i,10*j,10,10);
      fill(0.5+(-(grid[i][j]-0.5))*256);
      rectMode(CORNER);      
    }
  } 
  
}



void smooth(){
  fill(255);
  rect(0,0,width,height);
  for (int i = 0; i < cols; i++) {
    for (int j = 0; j < rows; j++) {
      
      if(numberOfNeighbors(i,j)<4)finalGrid[i][j]=1;
      if(numberOfNeighbors(i,j)>5)finalGrid[i][j]=0;
      stroke(finalGrid[i][j]*256);
      textSize(5);
      rectMode(CENTER);
      fill(finalGrid[i][j]*256);
      rect(10*i,10*j,10,10);
      fill(0.5+(-(finalGrid[i][j]-0.5))*256);
      rectMode(CORNER);      
    }
  }
  for (int i = 0; i < cols; i++) {
    for (int j = 0; j < rows; j++) {
      grid[i][j]=finalGrid[i][j];
    }
  }
}

P.S. Sorry there arn’t any comments, but the code doesn’t really matter, It’s just so you can get an idea of what I’m trying to achieve

1 Like
2

check out the following website.

3 Likes
3

How to optimize depends on the details. Are they all moving every frame? Are any limited to specific regions, such that they could never interact with each other?

In the worst case, if you have 500 rectangles bouncing at super-speed around a space, then you would need to do about 500*499 = 249,000 rectRect collision checks per frame.

You may be interested in @Kevin 's page – particularly the last two sections on many objects and “grid-based” detection.

A common advanced approach is cell-space partitioning and specifically quad trees. Here are two past discussions that get into the details:

In particular, @quark’s QuadTreeDemo is great to play around with to understand what some of the tradeoffs are in trying to decide how to partition space based on the number and size of your objects.

1 Like
4

When the platforms are fixed and not moving you check only the player against the platforms

When it’s a side scroller check only the visible platforms

1 Like