Group collision detection

For a while I’ve been trying to fix & improve some code that uses some form of collision detection for a user chosen and variable group of objects, these are all the same size and aligned to a grid.
The user should be able to pick a group of cells and move them around if they do not clash with other cells.
It works ok for selections of just one cell and for certain shaped groups in many circumstances, but fails quite easily in ‘group’ mode when faced with a couple of scenarios.

Here is the main code:

/* *****************************
 ---->> SELECT/DESELECT CELLS : LMB CLICK
 ---->> MOVE SELECTED CELLS : USE ARROW KEYS
 ---->> DESELECT ALL CELLS : press 'd'
 --->> RESET CELLS TO START GRID : PRESS 'r'
 *********************************************/

import java.util.*;

final int CELL_SIZE = 44;
final int PADDING = 2; // just to keep cell stroke within buffer
final int CELL_SPACE = 4;
final int GRID_SPACE = CELL_SIZE+CELL_SPACE;
final float ORIGIN_X = 250;
final float ORIGIN_Y = 250;


int cell_count = 100;
ArrayList<Cell> cells = new ArrayList<Cell>();
Set<Cell> selected = new HashSet<Cell>();
//for group move
private Set<Float> selectedX = new HashSet<Float>(); 
private Set<Float> selectedY = new HashSet<Float>(); 
private float x_min, x_max, y_min, y_max;

boolean testGroup = true;


void setup() {
  size(1000, 1000);

  for (int i = 0; i < cell_count; i++) {
    cells.add(new Cell(this, i));
  }
}


void draw() {
  background(0);

  for (Cell cell : cells) {
    cell.display();
  }
}


public void move_cells(int direction) {
  if (selected.size() == 1 || !testGroup) {
    for (Cell cell : selected) {    
      if (checkCell(cell, direction)) {
        switch(direction) {
        case UP:
          cell.moveTo(cell.getX(), cell.getY() - GRID_SPACE);
          break;
        case DOWN:
          cell.moveTo(cell.getX(), cell.getY() + GRID_SPACE);
          break;
        case LEFT:
          cell.moveTo(cell.getX() - GRID_SPACE, cell.getY());
          break;
        case RIGHT:
          cell.moveTo(cell.getX() + GRID_SPACE, cell.getY());
          break;
        }
      }
    }
  } else {
    getGroupCorners();
    if (checkGroup(direction)) {
      for (Cell cell : selected) {
        switch(direction) {
        case UP:
          cell.moveTo(cell.getX(), cell.getY() - GRID_SPACE);
          break;
        case DOWN:
          cell.moveTo(cell.getX(), cell.getY() + GRID_SPACE);
          break;
        case LEFT:
          cell.moveTo(cell.getX() - GRID_SPACE, cell.getY());
          break;
        case RIGHT:
          cell.moveTo(cell.getX() + GRID_SPACE, cell.getY());
          break;
        }
      }
    }
  }
}


public boolean checkCell(Cell cell, int direction) {
  float tx = cell.getX();
  float ty = cell.getY();
  int id = cell.getID();
  boolean allow = false;

  switch(direction) {
  case UP:
    for (Cell other : cells) {
      if (id != other.getID() && tx == other.getX() && ty - GRID_SPACE == other.getY()) {
        allow = false;
        break;
      } else {
        allow = true;
      }
    }
    break;
  case DOWN:
    for (Cell other : cells) {
      if (id != other.getID() && tx == other.getX() && ty + GRID_SPACE == other.getY()) {
        allow = false;
        break;
      } else {
        allow = true;
      }
    }
    break;
  case LEFT:
    for (Cell other : cells) {
      if (id != other.getID() && tx - GRID_SPACE == other.getX() && ty == other.getY()) {
        allow = false;
        break;
      } else {
        allow = true;
      }
    }
    break;
  case RIGHT:
    for (Cell other : cells) {
      if (id != other.getID() && tx + GRID_SPACE == other.getX() && ty == other.getY()) {
        allow = false;
        break;
      } else {
        allow = true;
      }
    }
    break;
  }
  return allow;
}


public void getGroupCorners() {
  //really only needs to be cleared & reset each time cell selection changes..
  selectedX.clear();
  selectedY.clear();
  for (Cell cell : selected) {
    selectedX.add(cell.getX());
    selectedY.add(cell.getY());
  }
  //Calc and store 'corners' of selected group
  x_min = Collections.min(selectedX);
  x_max = Collections.max(selectedX);
  y_min = Collections.min(selectedY);
  y_max = Collections.max(selectedY);
  //println("X:"+x_min+":"+x_max, " Y:"+y_min+":"+y_max);
}


public boolean checkGroup(int direction) {
  boolean allow = false;

  switch(direction) {
  case UP:
    for (Cell other : cells) { 
      if (!selected.contains(other) && y_min - GRID_SPACE == other.getY() && (x_min == other.getX() || x_max == other.getX())) { 
        allow = false;
        break;
      } else { 
        allow = true;
      }
    }
    break;
  case DOWN:
    for (Cell other : cells) { 
      if (!selected.contains(other) && y_max + GRID_SPACE == other.getY() && (x_min == other.getX() || x_max == other.getX())) { 
        allow = false;
        break;
      } else { 
        allow = true;
      }
    }
    break;
  case LEFT:
    for (Cell other : cells) { 
      if (!selected.contains(other) && x_min - GRID_SPACE == other.getX() && (y_min == other.getY() || y_max == other.getY())) { 
        allow = false;
        break;
      } else { 
        allow = true;
      }
    }
    break;
  case RIGHT:
    for (Cell other : cells) { 
      if (!selected.contains(other) && x_max + GRID_SPACE == other.getX() && (y_min == other.getY() || y_max == other.getY())) { 
        allow = false;
        break;
      } else { 
        allow = true;
      }
    }
    break;
  }
  return allow;
}


void mouseReleased() { 
  for (Cell cell : cells) {
    cell.clicked();
  }
}


void keyReleased() { 
  if (key == CODED) {
    switch(keyCode) {

    case UP:
    case DOWN:
    case LEFT:
    case RIGHT:
      if (!selected.isEmpty()) {
        move_cells(keyCode);
      }
      break;
    default:
      break;
    }
  } else {
    switch(key) {

    case 't': // toggle group test 
      testGroup = !testGroup;
      println("Test Group is: "+testGroup);
      break;
      
    case 'd': //deselect all cells
      selected.clear();
      for (Cell cell : cells) {
        cell.update(); //redraw buffers
      }
      break;

    case 'r':  // reset all cells to start grid
      for (Cell cell : cells) {
        cell.reset();
      }
      break;
    }
  }
}

And here is the simple cell class:

public class Cell { 
  PGraphics buffer;
  float x, y, w, h;
  boolean invalidBuffer;
  int index;

  Cell(PApplet app, int t_index) {
    index = t_index;
    // start layout in 10x10 grid
    x = ORIGIN_X + (index/10) * GRID_SPACE ; 
    y = ORIGIN_Y + (index%10) * GRID_SPACE; 

    w = CELL_SIZE;
    h = CELL_SIZE;
    buffer = app.createGraphics(int(w+PADDING), int(h+PADDING)); 
    invalidBuffer = true;
  }


  public void display() {
    if (invalidBuffer) {
      updateBuffer();
    }
    pushMatrix();
    translate(x, y);
    image(buffer, 0, 0);
    popMatrix();
  }


  public void updateBuffer()
  {
    buffer.beginDraw();
    buffer.clear() ; 
    buffer.strokeWeight(2);
    buffer.noFill();
    if (selected.contains(this)) {
      buffer.stroke(0, 200, 0); //green when selected
    } else {
      buffer.stroke(253, 114, 63);//otherwise orange
    }
    buffer.rect(PADDING/2, PADDING/2, w-PADDING, h-PADDING, 10);  
    buffer.endDraw();
    invalidBuffer = false;
  }


  public void clicked() { 
    if (mouseX >x && mouseX< x+w && mouseY>y && mouseY<y+h) {
      if (!selected.contains(this)) {
        selected.add(this);
      } else {
        selected.remove(this);
      }
    }
    invalidBuffer = true;
  }

  public void moveTo(float tx, float ty) {
    x = tx;
    y = ty;
  }

  public float getX() {
    return this.x;
  }

  public float getY() {
    return this.y;
  }

  public int getID() {
    return this.index;
  }

  public void reset() { // realign to start grid
    moveTo(ORIGIN_X + (index/10)*GRID_SPACE, ORIGIN_Y + (index%10)*GRID_SPACE);
  }

  public void update() {
    invalidBuffer = true;
  }
  //end class
}

To show how it can fail:

  • Set the cells up as shown below and then press the down arrow, the group will move down when it shouldn’t, from the code it is obvious that it fails because only the corners of the group are being checked for possible collision.
  • Now Reset the grid, by pressing ‘r’, then press ‘t’ this will instead search every cell of the group for a clash rather than just group corners. (‘t’ toggles group search mode on/off)
  • Move the group over the ‘spike’ and try to move down.
  • We don’t get collisions, BUT the group falls apart, due to the code checking it’s selected neighbour, if we try an ignore other selected cells then they will start to overlap each other within the group.

Has anyone got any suggestions on how to make this work without losing the group integrity ?
Or for that matter how to make the existing code, which I feel is a bit messy any more efficient ?

Cheers,
mala

1 Like

I’m having a hard time telling exactly what you’re trying to do, but I think an object-oriented approach might be really helpful here: making a Cell class that can be selected, moved, etc.

1 Like

I’m trying to move around a group of selected cells without them overlapping / colliding with other cells.

Ah… I thought that’s what I was doing ? Perhaps the Cell Class would have been clearer if I had left it in the main block of code ?

Figured it out… the solution of course is to check every selected cell for a clash with all unselected cells, provided there is no clash found THEN move all the selected cells.Don’t try and move cells one at a time …doh!
No need for finding size of group etc, etc.

Code here for anyone who may find it useful:

/* *****************************
 ---->> SELECT/DESELECT CELLS : LMB CLICK
 ---->> MOVE SELECTED CELLS : USE ARROW KEYS
 ---->> DESELECT ALL CELLS : press 'd'
 --->> RESET CELLS TO START GRID : PRESS 'r'
 *********************************************/

import java.util.*;

final int CELL_SIZE = 44;
final int PADDING = 2; // just to keep cell stroke within buffer
final int CELL_SPACE = 4;
final int GRID_SPACE = CELL_SIZE+CELL_SPACE;
final float ORIGIN_X = 250;
final float ORIGIN_Y = 250;


int cell_count = 100;
ArrayList<Cell> cells = new ArrayList<Cell>();
Set<Cell> selected = new HashSet<Cell>();



void setup() {
  size(1000, 1000);

  for (int i = 0; i < cell_count; i++) {
    cells.add(new Cell(this, i));
  }
}


void draw() {
  background(0);

  for (Cell cell : cells) {
    cell.display();
  }
}


public void move_cells(int direction) {
  boolean move = true;

  //first check for ALL selected cells is there may be a clash in direction of move
  for (Cell cell : selected) {    
    move = checkCell(cell, direction);
    if (!move) { // If any cell has a clash then exit loop
      break;
    }
  }

  if (move) { // If no clashes then go ahaed and move all selected cells
    for (Cell cell : selected) {  
      switch(direction) {
      case UP:
        cell.moveTo(cell.getX(), cell.getY() - GRID_SPACE);
        break;
      case DOWN:
        cell.moveTo(cell.getX(), cell.getY() + GRID_SPACE);
        break;
      case LEFT:
        cell.moveTo(cell.getX() - GRID_SPACE, cell.getY());
        break;
      case RIGHT:
        cell.moveTo(cell.getX() + GRID_SPACE, cell.getY());
        break;
      }
    }
  }
}


//Test if a position is already occupied by a non selected cell
public boolean checkCell(Cell cell, int direction) {
  float tx = cell.getX();
  float ty = cell.getY();
  boolean allow = false;

  switch(direction) {
  case UP:
    for (Cell other : cells) {
      if (!selected.contains(other) && tx == other.getX() && ty - GRID_SPACE == other.getY()) {
        allow = false;
        break;
      } else {
        allow = true;
      }
    }
    break;
  case DOWN:
    for (Cell other : cells) {
      if (!selected.contains(other) && tx == other.getX() && ty + GRID_SPACE == other.getY()) {
        allow = false;
        break;
      } else {
        allow = true;
      }
    }
    break;
  case LEFT:
    for (Cell other : cells) {
      if (!selected.contains(other) && tx - GRID_SPACE == other.getX() && ty == other.getY()) {
        allow = false;
        break;
      } else {
        allow = true;
      }
    }
    break;
  case RIGHT:
    for (Cell other : cells) {
      if (!selected.contains(other) && tx + GRID_SPACE == other.getX() && ty == other.getY()) {
        allow = false;
        break;
      } else {
        allow = true;
      }
    }
    break;
  }
  return allow;
}


//--->> User interaction with mouse or keys <<---
void mouseReleased() { 
  for (Cell cell : cells) {
    cell.clicked();
  }
}


void keyReleased() { 
  if (key == CODED) {
    switch(keyCode) {

    case UP:
    case DOWN:
    case LEFT:
    case RIGHT:
      if (!selected.isEmpty()) {
        move_cells(keyCode);
      }
      break;
    default:
      break;
    }
  } else {
    switch(key) {

    case 'd': //deselect all cells
      selected.clear();
      for (Cell cell : cells) {
        cell.update(); //redraw buffers
      }
      break;

    case 'r':  // reset all cells to start grid
      for (Cell cell : cells) {
        cell.reset();
      }
      break;
    }
  }
}


//--->> SIMPLE CELL CLASS



public class Cell { 
  PGraphics buffer;
  float x, y, w, h;
  boolean invalidBuffer;
  int index;

  Cell(PApplet app, int t_index) {
    index = t_index;
    // start layout in 10x10 grid
    x = ORIGIN_X + (index/10) * GRID_SPACE ; 
    y = ORIGIN_Y + (index%10) * GRID_SPACE; 

    w = CELL_SIZE;
    h = CELL_SIZE;
    buffer = app.createGraphics(int(w+PADDING), int(h+PADDING)); 
    invalidBuffer = true;
  }


  public void display() {
    if (invalidBuffer) {
      updateBuffer();
    }
    pushMatrix();
    translate(x, y);
    image(buffer, 0, 0);
    popMatrix();
  }


  public void updateBuffer()
  {
    buffer.beginDraw();
    buffer.clear() ; 
    buffer.strokeWeight(2);
    buffer.noFill();
    if (selected.contains(this)) {
      buffer.stroke(0, 200, 0); //green when selected
    } else {
      buffer.stroke(253, 114, 63);//otherwise orange
    }
    buffer.rect(PADDING/2, PADDING/2, w-PADDING, h-PADDING, 10);  
    buffer.endDraw();
    invalidBuffer = false;
  }


  public void clicked() { 
    if (mouseX >x && mouseX< x+w && mouseY>y && mouseY<y+h) {
      if (!selected.contains(this)) {
        selected.add(this);
      } else {
        selected.remove(this);
      }
    }
    invalidBuffer = true;
  }

  public void moveTo(float tx, float ty) {
    x = tx;
    y = ty;
  }

  public float getX() {
    return this.x;
  }

  public float getY() {
    return this.y;
  }

  public int getID() {
    return this.index;
  }

  public void reset() { // realign to start grid
    moveTo(ORIGIN_X + (index/10)*GRID_SPACE, ORIGIN_Y + (index%10)*GRID_SPACE);
  }

  public void update() {
    invalidBuffer = true;
  }
  //end class
}
3 Likes