3

I am working on an Android game similar to the Rush Hour/Traffic Jam/Blocked puzzle games. The board is a square containing rectangular pieces. Long pieces may only move horizontally, and tall pieces may only move vertically. The object is to free the red piece and move it out of the board. This game is only my second ever programming project in any language, so any tips or best practices would be appreciated along with your answer.

I have a class for the game pieces called Pieces that describes how they are sized and drawn to the screen, gives them drag-and-drop functionality, and detects and handles collisions.

I then have an activity class called GameView which creates my layout and creates Pieces objects to add to a RelativeLayout called Board. I have considered making Board its own class, but haven't needed to yet.

Here's what my work in progress looks like:
screen_cap1

My Question:
Most of this works perfectly fine except for my collision handling. It seems to be detecting collisions well but instead of pushing the pieces outside of each other when there is a collision, it frantically snaps back and forth between (what seems to be) where the piece is being dragged to and where it should be. It looks something like this:
screencapgif1
Another oddity: when the dragged piece collides with a piece to its left, the collision handling seems to work perfectly. Only piece above, below, and to the right cause problems.
Here's the collision code:

    @Override
public boolean onTouchEvent(MotionEvent event){

    float eventX = event.getX();
    float eventY = event.getY();

    switch (event.getAction()) {
    case MotionEvent.ACTION_DOWN:
        //check if touch is on piece
        if (eventX > x && eventX < (x+width) && eventY > y && eventY < (y+height)){
            initialX=x;
            initialY=y;
            break;
        }else{
            return false;
        }
    case MotionEvent.ACTION_MOVE:
        //determine if piece should move horizontally or vertically
        if(width>height){
            for (Pieces piece : aPieces) {
                //if object equals itself in array, skip to next object
                if(piece==this){
                    continue;
                }
                //if next to another piece, 
                //do not allow to move any further towards said piece
                if(eventX<x&&(x==piece.right+1)){
                    return false;
                }else if(eventX>x&&(x==piece.x-width-1)){
                    return false;
                }
                //move normally if no collision
                //if collision, do not allow to move through other piece
                if(collides(this,piece)==false){
                    x = (eventX-(width/2));
                }else if(collidesLeft(this,piece)){
                    x = piece.right+1;
                    break;
                }else if(collidesRight(this,piece)){
                    x = piece.x-width-1;
                    break;
                }
            }
            break;
        }else if(height>width){
            for (Pieces piece : aPieces) {
                if(piece==this){
                    continue;
                }else if(collides(this,piece)==false){
                    y = (eventY-(height/2));
                }else if(collidesUp(this,piece)){
                    y = piece.bottom+1;
                    break;
                }else if(collidesDown(this,piece)){
                    y = piece.y-height-1;
                    break;
                }
            }
        }
        invalidate();
        break;

    case MotionEvent.ACTION_UP:
        // end move
        if(this.moves()){
        GameView.counter++;
        }
        initialX=x;
        initialY=y;
        break;
        }
    // parse puzzle
    invalidate();
    return true;
    }

This takes place during onDraw:

width = sizedBitmap.getWidth();
height = sizedBitmap.getHeight();
right = x+width;
bottom = y+height;

My collision-test methods look like this with different math for each:

    private boolean collidesDown(Pieces piece1, Pieces piece2){
    float x1 = piece1.x;
    float y1 = piece1.y;
    float r1 = piece1.right;
    float b1 = piece1.bottom;
    float x2 = piece2.x;
    float y2 = piece2.y;
    float r2 = piece2.right;
    float b2 = piece2.bottom;

    if((y1<y2)&&(y1<b2)&&(b1>=y2)&&(b1<b2)&&((x1>=x2&&x1<=r2)||(r1>=x2&&x1<=r2))){
        return true;
    }else{
        return false;
    }
}

private boolean collides(Pieces piece1, Pieces piece2){
    if(collidesLeft(piece1,piece2)){
        return true;
    }else if(collidesRight(piece1,piece2)){
        return true;
    }else if(collidesUp(piece1,piece2)){
        return true;
    }else if(collidesDown(piece1,piece2)){
        return true;
    }else{
        return false;
    }
}

As a second question, should my x,y,right,bottom,width,height variables be ints instead of floats like they are now? Also, any suggestions on how to implement things better would be greatly appreciated, even if not relevant to the question! Thanks in advance for the help and for sitting through such a long question!

Update:
I have gotten it working almost perfectly with the following code (this doesn't include the code for vertical pieces):

@Override
public boolean onTouchEvent(MotionEvent event){

    float eventX = event.getX();
    float eventY = event.getY();

    switch (event.getAction()) {
    case MotionEvent.ACTION_DOWN:
        //check if touch is on piece
        if (eventX > x && eventX < (x+width) && eventY > y && eventY < (y+height)){
            initialX=x;
            initialY=y;
            break;
        }else{
            return false;
        }
    case MotionEvent.ACTION_MOVE:
        //determine if piece should move horizontally or vertically
        if(width>height){
            for (Pieces piece : aPieces) {
                //if object equals itself in array, skip to next object
                if(piece==this){
                    continue;
                }
                //check if there the possibility for a horizontal collision
                if(this.isAllignedHorizontallyWith(piece)){
                    //check for and handle collisions while moving left
                    if(this.isRightOf(piece)){
                        if(eventX>piece.right+(width/2)){
                            x = (int)(eventX-(width/2)); //move normally
                        }else{
                            x = piece.right+1;
                        }
                    }
                    //check for and handle collisions while moving right
                    if(this.isLeftOf(piece)){
                        if(eventX<piece.x-(width/2)){
                            x = (int)(eventX-(width/2));
                        }else{
                            x = piece.x-width-1;
                        }
                    }
                    break;
                }else{
                    x = (int)(eventX-(width/2));
                }

The only problem with this code is that it only detects collisions between the moving piece and one other (with preference to one on the left). If there is a piece to collide with on the left and another on the right, it will only detect collisions with the one on the left. I think this is because once it finds a possible collision, it handles it without finishing looping through the array holding all the pieces. How do I get it to check for multiple possible collisions at the same time?

1
  • I have answered the question from your update below.
    – Timo
    Mar 16, 2011 at 11:52

5 Answers 5

1

My best guess is that the dragged piece is dragged into the other piece, then moved back so it is no longer colliding, then dragged into the other piece again. At least that is what I would expect if collision response happens after drawing.

On a side note, the following code makes me wonder a bit:

            //if next to another piece, 
            //do not allow to move any further towards said piece
            if(eventX<x&&(x==piece.right+1)){
                return false;
            }else if(eventX>x&&(x==piece.x-width-1)){
                return false;
            }

Checking for equality (==) on floats is generally a very bad idea, see zillions of "floating point precision" topics. Alternative a) use ints instead of floats. b) use ranged comparisions (>=, etc.). Don't use (a) though, there are many drawbacks with tiny (time) steps and such.

Try using the same approach as with the touch detection instead:

    //check if touch is on piece
    if (eventX > x && eventX < (x+width) && eventY > y && eventY < (y+height))
1
  • Thank you for your help, I have updated my question with new code at the bottom. And I did end up using ints instead of floats. Let me know what you think.
    – Amplify91
    Mar 16, 2011 at 0:10
1

You should be able to do this more simply :)

Note that I made some assumptions on how you store the direction of movement, which you may have to adjust to your likings.

Also note that I treat piece1 as the moving piece we are concerned with, and piece2 simply as an object it collides with. So piece1 is repositioned, piece2 is not.

// Horizontal:
if( piece1.isMovingLeft )
    piece1.x += Math.max( 0, piece2.right - piece1.x );
else if( piece1.isMovingRight )
    piece1.x -= Math.max( 0, piece1.right - piece2.x );

// Vertical:
if( piece1.isMovingUp )
    piece1.y -= Math.max( 0, piece2.bottom - piece1.y );
else if( piece1.isMovingDown )
    piece1.y += Math.max( 0, piece1.bottom - piece2.y )

What I do here is as follows:

  • If the piece is moving in a certain direction, we move it back (a little bit) in the opposite direction to compensate for (possible) collision. We need to move it back by exactly the amount of overlapping pixels.
  • The amount of overlap, when moving left, for instance, is the right side of the second object minus the left side of the first object. (Negative means no overlap.)
  • The Math.max( 0, overlap ) ensures that said negative values become 0, i.e. no collision leads to no compensation.
  • The compensation is then applied in the direction opposite of movement, effectively taking piece1 out of piece2. (You can then choose to invert its movement direction or respond in any further way.)

You can apply this simple routine to every possible combination of two pieces, and they will no longer penetrate.

I hope this helps you out!

1
  • Thank you for your answer! I wish I could accept more than one because this was very helpful. Check out what I have posted in the update near the bottom.
    – Amplify91
    Mar 16, 2011 at 0:08
0

In reply to your second question:

The only problem with this code is that it only detects collisions between the moving piece and one other (with preference to one on the left). If there is a piece to collide with on the left and another on the right, it will only detect collisions with the one on the left.

There is a break statement within your loop - specifically, in the left collision check. ;)

4
  • The break statement actually occurs at the end of if(this.isAllignedHorizontallyWith(piece)) and it needs to be there. I was thinking of having a different for loop check for a different piece to the right if it had already found one to the left and vice versa. Thoughts?
    – Amplify91
    Mar 16, 2011 at 19:37
  • You're right indeed, it's not inside the left collision check. However, it is causing your problem! You see, when there are two other horizontally aligned pieces (one to your left, the other to your right), your piece detects being horizontally aligned with the first (the one to its left, as you stated in your question). This causes you to reach the break statement, i.e. stopping the loop and preventing the other collision check from ever happening. Does removing the break statement solve your problem?
    – Timo
    Mar 21, 2011 at 14:12
  • I did try removing it, but then it gave me other problems. The solution I have come to now seems to be working perfectly (knock on wood). I changed isLeftOf() to return true if it is left of a piece AND that piece is the closest piece horizontally alligned and to the right (or if it is the only piece). If not, it continues checking for possible collision.
    – Amplify91
    Mar 21, 2011 at 18:14
  • 1
    I ended up just posting the code that is working now in another answer. Feel free to check it out.
    – Amplify91
    Mar 21, 2011 at 18:33
0

I made a few changes and, so far, it has been working perfectly. Here is my new code:

case MotionEvent.ACTION_MOVE:
        //determine if piece should move horizontally or vertically
        if(width>height){
            for (Pieces piece : aPieces) {
                //if object equals itself in array, skip to next object
                if(piece==this){
                    continue;
                }
                //check if there the possibility for a horizontal collision
                if(this.isAllignedHorizontallyWith(piece)){
                    //check for and handle collisions while moving left
                    if(this.isRightOf(piece)){
                        if(eventX>piece.right+(width/2)){
                            x = (int)(eventX-(width/2)); //move normally
                            continue;
                        }else{
                            x = piece.right+1;
                        }
                    }else if(this.isLeftOf(piece)){ //check for and handle collisions while moving right
                        if(eventX<piece.x-(width/2)){
                            x = (int)(eventX-(width/2));
                            continue;
                        }else{
                            x = piece.x-width-1;
                        }
                    }else{
                        continue;
                    }
                    break;
                }else{
                    x = (int)(eventX-(width/2));
                }
            }
        }
        if(height>width){
            for (Pieces piece : aPieces) {
                //if object equals itself in array, skip to next object
                if(piece==this){
                    continue;
                }
                //check if there the possibility for a vertical collision
                if(this.isAllignedVerticallyWith(piece)){
                    //check for and handle collisions while moving up
                    if(this.isBelow(piece)){
                        if(eventY>piece.bottom+(height/2)){
                            y = (int)(eventY-(height/2)); //move normally
                            continue;
                        }else{
                            y = piece.bottom+1;
                        }
                    }else if(this.isAbove(piece)){ //check for and handle collisions while moving down
                        if(eventY<piece.y-(height/2)){
                            y = (int)(eventY-(height/2));
                            continue;
                        }else{
                            y = piece.y-height-1;
                        }
                    }else{
                        continue;
                    }
                    break;
                }else{
                    y = (int)(eventY-(height/2));
                }
            }
        }
        invalidate();
        break;

And these are the methods I use:

private boolean isLeftOf(Pieces piece) {
    int r1 = this.right;
    int x2 = piece.initialX;
    boolean bool = false;
    if (r1<=x2){
        for(Pieces piece2: aPieces){
            if (piece2==piece || piece2==this){
                continue;
            }
            if (this.isAllignedHorizontallyWith(piece2) && r1<=piece2.initialX){
                if (piece.x>piece2.x){
                    bool = false;
                    break;
                }else{
                    bool = true;
                    continue;
                }
            }else{
                bool = true;
            }
        }
    }else{
        bool = false;
    }
    return bool;
}

private boolean isRightOf(Pieces piece) {
    //True means that "this" is right of "piece" and "piece" is farther right than other possible pieces
    int x1 = this.initialX;
    int r2 = piece.right;
    boolean bool = false;

    if (x1>=r2){
        for(Pieces piece2: aPieces){
            if (piece2==piece || piece2==this){
                continue;
            }
            if (this.isAllignedHorizontallyWith(piece2) && x1>=piece2.right){
                if (piece.x<piece2.x){
                    bool = false;
                    break;
                }else{
                    bool = true;
                    continue;
                }
            }else{
                bool = true;
            }
        }
    }else{
        bool = false;
    }
    return bool;
}

private boolean isBelow(Pieces piece){
    int y1 = this.initialY;
    int b2 = piece.bottom;
    boolean bool = false;
    if (y1>=b2){
        for(Pieces piece2: aPieces){
            if (piece2==piece || piece2==this){
                continue;
            }
            if (this.isAllignedVerticallyWith(piece2) && y1>=piece2.bottom){
                if (piece.y<piece2.y){
                    bool = false;
                    break;
                }else{
                    bool = true;
                    continue;
                }
            }else{
                bool = true;
            }
        }
    }else{
        bool = false;
    }
    return bool;
}

private boolean isAbove(Pieces piece){
    int y2 = piece.initialY;
    int b1 = this.bottom;
    boolean bool = false;
    if (b1<=y2){
        for(Pieces piece2: aPieces){
            if (piece2==piece || piece2==this){
                continue;
            }
            if (this.isAllignedVerticallyWith(piece2) && b1<=piece2.y){
                if (piece.y>piece2.y){
                    bool = false;
                    break;
                }else{
                    bool = true;
                    continue;
                }
            }else{
                bool = true;
            }
        }
    }else{
        bool = false;
    }
    return bool;
}

private boolean isAllignedHorizontallyWith(Pieces piece) {

    int y1 = this.y;
    int b1 = this.bottom;
    int y2 = piece.y;
    int b2 = piece.bottom;

    if((y1>=y2&&y1<=b2)||(b1>=y2&&b1<=b2)){
        return true;
    }else{
        return false;   
    }
}

private boolean isAllignedVerticallyWith(Pieces piece) {

    int x1 = this.x;
    int r1 = this.right;
    int x2 = piece.x;
    int r2 = piece.right;

    if((x1>=x2&&x1<=r2)||(r1>=x2&&r1<=r2)){
        return true;
    }else{
        return false;   
    }
}

This could be commented better and probably done much simpler, but I am leaving it here for reference.

0

Nothing just get the your imageviews Left,right,top,bottom, and intersect with current x and y and find this solution more about this go to this link its also help i hop you got a right answer on this link

/technical/game-programming/collision-detection-algorithm-r754">http://www.gamedev.net/page/resources//technical/game-programming/collision-detection-algorithm-r754

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.