java - 2D 平台游戏中的碰撞错误

Question

我目前正在开发一款类似马里奥的 2D 平台游戏。我遇到了一个碰撞问题，我已经尝试解决了一段时间了，但似乎没有任何效果:/

基本上，我有一个 CenterLayer，它存储在哪个位置的 Tile 类型。然后我有一些 Sprite 和一个播放器，它们应该与这些图 block 发生碰撞。

因为这些图 block 可以是三角形(或任何其他类型的凸多边形)，所以我决定通过 SAT(分离轴定理)来处理碰撞。这效果很好，但是当与地板发生碰撞时，其中许多瓷砖彼此相邻并且 Sprite 向左移动，它会选择错误的边缘并将 Sprite 移动到右侧，但预期的结果是将其向上移动。这会导致 Sprite 卡住。

这是我当前使用的代码:

package level;

import java.awt.Polygon;

import tiles.Tile;
import sprites.*;

public class Collider { 
/** Collide Sprite (or Player) with CenterLayer **/ 
public static void collide(Sprite s, CenterLayer c){
    CollisionPolygon ps = s.getPolygon();

    //Get blocks to collide with
    int startXTile = (int) (s.getX() / CenterLayer.TILE_WIDTH) - 1;
    int endXTile = (int) Math.ceil((s.getX() + s.getWidth()) / CenterLayer.TILE_WIDTH) + 1;
    int startYTile = (int) (s.getY() / CenterLayer.TILE_HEIGHT) - 1;
    int endYTile = (int) Math.ceil((s.getY() + s.getHeight()) / CenterLayer.TILE_HEIGHT) +1;

    //limit to level boundaries
    if(startXTile < 0) startXTile = 0;
    if(endXTile > c.LEVEL_WIDTH) endXTile = c.LEVEL_WIDTH;
    if(startYTile < 0) startYTile = 0;
    if(endYTile > c.LEVEL_HEIGHT) endYTile = c.LEVEL_HEIGHT; 

    int sizeX = endXTile - startXTile;
    int sizeY = endYTile - startYTile;

    //loop through tiles and collide
    for(int xc = 0; xc < sizeX; xc++)
    for(int yc = 0; yc < sizeY; yc++){
        int xblock = xc + startXTile;
        int yblock = yc + startYTile;

        Tile t = c.getTile(xblock, yblock);
        if(t!=null){ //if tile == null --> tile is air
            CollisionPolygon pt = t.getPolygon(xblock, yblock);

            double[] projection = PolygonCollision(ps, pt);             

            //if collision has happened
            if(projection[0] != 0 || projection[1] != 0){
                //collide
                s.moveBy(projection[0], projection[1]);

                //update sprites polygon to new position                    
                ps = s.getPolygon();
            }
        }
    }
}

public static double dotProduct(double x, double y, double dx, double dy) {
    return x * dx + y * dy;
}

// Calculate the projection of a polygon on an axis (ax, ay)
// and returns it as a [min, max] interval
public static double[] ProjectPolygon(double ax, double ay, Polygon p) {
    double dotProduct = dotProduct(ax, ay, p.xpoints[0], p.ypoints[0]);
    double min = dotProduct;
    double max = dotProduct;
    for (int i = 0; i < p.npoints; i++) {
            dotProduct = dotProduct(p.xpoints[i], p.ypoints[i], ax, ay);
            if (dotProduct < min) {
                    min = dotProduct;
            } else if (dotProduct > max) {
                    max = dotProduct;
            }
    }
    return new double[] { min, max };
}

// Calculate the distance between [minA, maxA](p1[0], p1[1]) and [minB, maxB](p2[0], p2[1])
// The distance will be negative if the intervals overlap
public static double IntervalDistance(double[] p1, double[] p2) {
    if (p1[0] < p2[0]) {
        return p2[0] - p1[1];
    } else {
        return p1[0] - p2[1];
    }
}

public static double[] PolygonCollision(CollisionPolygon p1, CollisionPolygon p2){
    boolean intersection = true;

    int edgeCount1 = p1.npoints;
    int edgeCount2 = p2.npoints;

    double projectionX = 0;
    double projectionY = 0;
    double projectionDist = Double.POSITIVE_INFINITY;

    //loop through all the edges
    for(int edgeIndex = 0; edgeIndex < edgeCount1 + edgeCount2; edgeIndex++){
        //find edges

        double[] axis;

        if(edgeIndex < edgeCount1){
            axis = p1.getAxis(edgeIndex);
        } else {
            axis = p2.getAxis(edgeIndex - edgeCount1);
        }

        double axisX = axis[0];
        double axisY = axis[1];

        //System.out.println("edge: " +axisX + ", "+ axisY);

        //find the projection of both polygons on current axis
        final double[] proj1 = ProjectPolygon(axisX, axisY, p1);
        final double[] proj2 = ProjectPolygon(axisX, axisY, p2);

        //Check if polygons are intersecting, if not end loop
        double id = IntervalDistance(proj1, proj2); 
        if(id > 0){
            intersection = false;
            break;
        }

        //Check if projection would be shorter than previous one
        id = Math.abs(id);
        if(id < projectionDist){
            projectionDist = id;
            projectionX = axisX;
            projectionY = axisY;


            //check if hit from "false" side
            double d1x = p1.getCenterX();
            double d1y = p1.getCenterY();
            double d2x = p2.getCenterX();
            double d2y = p2.getCenterY();

            double midx = d1x - d2x;
            double midy = d1y - d2y;

            double dot = dotProduct(midx, midy, projectionX, projectionY);

            if(dot < 0){
                projectionX = -projectionX;
                projectionY = -projectionY;
            }
        }

    }

    double[] result = new double[]{0, 0};

    if(intersection){
        //System.out.println("colliison: " + projectionX +"; "+ projectionY + ", " + projectionDist);
        result[0] = projectionX * projectionDist;
        result[1] = projectionY * projectionDist;   
    }

    return result;
}
}

有什么想法吗？

汤姆

Answer 1

我也遇到了这个错误，当多边形上有平行边时就会发生这种情况。解决此问题的简单方法是将多边形中心之间的差异投影到找到的轴上。如果结果为负，您只需将轴乘以 -1 即可。

  Vector aMidPoint = new Vector();
  Vector bMidPoint = new Vector();
  for ( Vector v : aVerts) {
     aMidPoint = aMidPoint.add(v);
  }
  for ( Vector v : bVerts) {
     bMidPoint = bMidPoint.add(v);
  }
  aMidPoint = aMidPoint.scalarDivision(aVerts.size());
  bMidPoint = bMidPoint.scalarDivision(bVerts.size());

  Vector ba = aMidPoint.subtract(bMidPoint);

  if (ba.dotProduct(minOverlapVector) < 0) {
     minOverlapVector = minOverlapVector.scalarMultiplication(-1);
  }