# Collision Detection (Game Design)

**URL:** <https://discourse.processing.org/t/collision-detection-game-design/24142>\
**Category:** Coding Questions\
**Created:** [September 26, 2020, 8:20pm UTC](https://discourse.processing.org/t/collision-detection-game-design/24142 "2020-09-26T20:20:19Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![Aoyanco](https://avatars.discourse-cdn.com/v4/letter/a/22d042/32.png) [@Aoyanco](https://discourse.processing.org/u/Aoyanco)\
**Post date:** [September 26, 2020, 8:20pm UTC](https://discourse.processing.org/t/collision-detection-game-design/24142/1 "2020-09-26T20:20:19Z")

</div>

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

```auto
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)

```auto
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

---

<div class="post-metadata">

**Author:** ![paulgoux](https://avatars.discourse-cdn.com/v4/letter/p/b9bd4f/32.png) [@paulgoux](https://discourse.processing.org/u/paulgoux)\
**Post date:** [September 27, 2020, 12:35am UTC](https://discourse.processing.org/t/collision-detection-game-design/24142/2 "2020-09-27T00:35:45Z")

</div>

check out the following website.

> **[Collision Detection](http://www.jeffreythompson.org/collision-detection/)**
>
> An online book about collision detection using Processing.

---

<div class="post-metadata">

**Author:** ![jeremydouglass](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/jeremydouglass/32/20_2.png) [@jeremydouglass](https://discourse.processing.org/u/jeremydouglass)\
**Post date:** [September 29, 2020, 9:35pm UTC](https://discourse.processing.org/t/collision-detection-game-design/24142/3 "2020-09-29T21:35:18Z")

</div>

> [@Aoyanco](#):
>
> (Basically, I’m going to need over 500 rectangles). Is there a relatively clean way of doing this so it won’t lag?

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](http://www.jeffreythompson.org/collision-detection/rect-rect.php) collision checks per frame.

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

> **[Processing Collision Detection](https://happycoding.io/tutorials/processing/collision-detection)**
>
> Learn how to trigger an action when objects overlap in Processing!

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

- [Implementing Grid-Based Collision System](https://discourse.processing.org/t/implementing-grid-based-collision-system/3248)
- [Quadtree vs grid](https://discourse.processing.org/t/quadtree-vs-grid/13844)

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.

---

<div class="post-metadata">

**Author:** ![Chrisir](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/chrisir/32/45_2.png) [@Chrisir](https://discourse.processing.org/u/Chrisir)\
**Post date:** [September 30, 2020, 8:53am UTC](https://discourse.processing.org/t/collision-detection-game-design/24142/4 "2020-09-30T08:53:51Z")

</div>

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