Skip to content

Instantly share code, notes, and snippets.

@mrspeaker
Created March 5, 2012 13:56
Show Gist options
  • Star 5 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mrspeaker/1978410 to your computer and use it in GitHub Desktop.
Save mrspeaker/1978410 to your computer and use it in GitHub Desktop.
Why does Notch check X and Y separately in the collision detection routine?
/*
After watching a few of Notch's (and Mojan's) "write a game in a weekend" livecasts and
pulling apart some of the code (http://www.mrspeaker.net/2011/12/30/colorising-sprites-1/)
I've noticed that the collision detection routines are broken into two methods - usually
called "move" and "move2".
The move method gets the amount the entity will move on the X axis and calls
move2 with move2(x, 0). Then the same thing is done with the Y: move2(0,y).
Why would this be necessary? I've broken the code down into pseudo code to see if I
could figure out why... but I'm stuck.
===== AND THE ANSWER (thank you /r/gamedev/) ======
* So you can slide along walls.
–tcoxon
* In addition to this, it allows correct collision detection in diagonal movement.
If you're at (0,0) and the adjacent squares (1,0) and (0,1) are blocked, then you
should not be able to move straight to (1,1). If you do collision detection for both
x and y at the same time in this case, it will incorrectly allow the movement.
–Slime0
http://www.reddit.com/r/gamedev/comments/qijw6/collision_detection_why_does_notch_do_separate_x/
==============================================
For reference, here is how move is called in the entity subclasses. For example, in
the player class, the xa and ya is determined user input:
int xa = 0;
int ya = 0;
if (input.up.down) ya--;
if (input.down.down) ya++;
if (input.left.down) xa--;
if (input.right.down) xa++;
Then the "move" method of the base class is called:
move(xa, ya);
*/
// This is pseudo code of the actual code below...
Entity {
...
public int x, y;
public int xr = 6; // "radius" of the entity
public int yr = 6;
public boolean move(int xa, int ya) {
if xa isnt 0 then check for x collisions with move2(xa, 0)
if ya isnt 0 then check for y collisions with move2(0, ya)
if both of those checks didnt block
find the tile you're on now and ".steppedOn" it
return if it was free to move or not;
}
protected boolean move2(int xa, int ya) {
get the tile index range that you are currently overlapping (eg x tile 4 to 5, y tile 5 to 6)
get the tile index range that you will be overlapping if you apply the xa and ya
for each tile index you will be overlapping
if you were already overlapping last time, continue to next tile
get the tile at the index and ".bumpInto" it
if you cant ".mayPass" the tile
return false //the tile blocks you
List<Entity> wasInside = level.getEntities in the tiles you are currently overlapping
List<Entity> isInside = level.getEntities in the tiles you will be overlapping
for each isInside do entity.touchedBy(this)
isInside.get rid of all the one also in wasInside
for each still in isInside
if entity.blocks(this)
return false; // the entity blocks you
// Add to the actual x and y
x += xa;
y += ya;
return true; // No one blocks
}
}
// This is lifted from Minicraft
public int x, y;
public int xr = 6;
public int yr = 6;
public boolean move(int xa, int ya) {
if (xa != 0 || ya != 0) {
boolean stopped = true;
if (xa != 0 && move2(xa, 0)) stopped = false;
if (ya != 0 && move2(0, ya)) stopped = false;
if (!stopped) {
int xt = x >> 4;
int yt = y >> 4;
level.getTile(xt, yt).steppedOn(level, xt, yt, this);
}
return !stopped;
}
return true;
}
protected boolean move2(int xa, int ya) {
if (xa != 0 && ya != 0) throw new IllegalArgumentException("Move2 can only move along one axis at a time!");
int xto0 = ((x) - xr) >> 4;
int yto0 = ((y) - yr) >> 4;
int xto1 = ((x) + xr) >> 4;
int yto1 = ((y) + yr) >> 4;
int xt0 = ((x + xa) - xr) >> 4;
int yt0 = ((y + ya) - yr) >> 4;
int xt1 = ((x + xa) + xr) >> 4;
int yt1 = ((y + ya) + yr) >> 4;
boolean blocked = false;
for (int yt = yt0; yt <= yt1; yt++)
for (int xt = xt0; xt <= xt1; xt++) {
if (xt >= xto0 && xt <= xto1 && yt >= yto0 && yt <= yto1) continue;
level.getTile(xt, yt).bumpedInto(level, xt, yt, this);
if (!level.getTile(xt, yt).mayPass(level, xt, yt, this)) {
blocked = true;
return false;
}
}
if (blocked) return false;
List<Entity> wasInside = level.getEntities(x - xr, y - yr, x + xr, y + yr);
List<Entity> isInside = level.getEntities(x + xa - xr, y + ya - yr, x + xa + xr, y + ya + yr);
for (int i = 0; i < isInside.size(); i++) {
Entity e = isInside.get(i);
if (e == this) continue;
e.touchedBy(this);
}
isInside.removeAll(wasInside);
for (int i = 0; i < isInside.size(); i++) {
Entity e = isInside.get(i);
if (e == this) continue;
if (e.blocks(this)) {
return false;
}
}
x += xa;
y += ya;
return true;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment