java - 优化突破(游戏) block 命中检查

Question

我制作了《Breakout》，它运行良好，但由于要进行大量的命中检查，因此有点滞后。有谁知道如何重做命中检查以提高速度/效率？ (仅供引用，didCollide[Direction] 方法检查它是否击中该侧 - didCollideTop() 检查它是否击中 block 的顶部)

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Canvas;
import java.awt.event.KeyListener;
import java.awt.event.KeyEvent;
import static java.lang.Character.*;
import java.awt.image.BufferedImage;
import java.util.ArrayList;

public class Breakout extends Canvas implements KeyListener, Runnable, Frame
{
private Ball ball;
private Paddle paddle;
private boolean[] keys;
private BufferedImage back;
private ArrayList<Wall> walls = new ArrayList<Wall>();
private ArrayList<Square> squares = new ArrayList<Square>();
private final int SIDEBORDER = 20;
private final int BOTTOMBORDER = 60;
private final int BALL_SPEED = 20;
private final int WALL_SIZE = 20;

public Breakout()
{
    ball = new Ball((int) (Frame.WIDTH / 2.1), (int) (Frame.HEIGHT / 1.15), 20, 20, Color.green, BALL_SPEED, -BALL_SPEED);      //instantiate a Ball
    paddle = new Paddle((int) (Frame.WIDTH / 2.2), Frame.HEIGHT - 80, 100, 25, Color.blue, 20);     //instantiate a Paddle

    //makes the left walls
    for (int i = 20; i < Frame.HEIGHT - BOTTOMBORDER; i += 20)
        walls.add(new Wall(0, i, WALL_SIZE, WALL_SIZE));

    //makes the top walls
    for (int i = 0; i < Frame.WIDTH - SIDEBORDER; i += 20)
        walls.add(new Wall(i, 0, WALL_SIZE, WALL_SIZE));

    //makes the right walls
    for (int i = 20; i < Frame.HEIGHT - BOTTOMBORDER; i += 20)
        walls.add(new Wall(Frame.WIDTH - 40, i, WALL_SIZE, WALL_SIZE));

    //makes the squares (the ones you hit)
    for (int i = 80; i < Frame.HEIGHT / 2; i += 40)
        for (int j = 80; j < Frame.WIDTH / 1.1; j += 70)
            squares.add(new Square(j, i, 60, 30));

    keys = new boolean[2];

        setBackground(Color.WHITE);
    setVisible(true);

    addKeyListener(this);   
    new Thread(this).start();
}

public void update(Graphics window)
{paint(window);}

public void paint(Graphics window)
{
    Graphics2D twoDGraph = (Graphics2D) window;

    back = null;

    //take a snap shop of the current screen and save it as an image
    if (back == null)
       back = (BufferedImage)(createImage(getWidth(), getHeight()));

    //create a graphics reference to the back ground image
    //draw all changes on the background image
    Graphics graphToBack = back.createGraphics();

    ball.moveAndDraw(graphToBack);
    paddle.draw(graphToBack);

    for (int i = 0; i < walls.size(); i++) //draw walls
        walls.get(i).draw(graphToBack);

    for (int i = 0; i < squares.size(); i++) //draw squares
        squares.get(i).draw(graphToBack);

    //see if the paddle can move
    if (keys[0] == true && paddle.getX() > WALL_SIZE + 15)
        paddle.moveLeftAndDraw(window);     //move paddle left and draw it

    if (keys[1] == true && paddle.getX() + paddle.getWidth() < walls.get(walls.size() - 1).getX() - 15)
        paddle.moveRightAndDraw(window);    //move paddle right and draw it

    //see if the ball hits the top walls
    if (ball.getY() + ball.getYSpeed() <= WALL_SIZE)
        ball.setYSpeed(-ball.getYSpeed());

    //see if the ball hits the left walls
    if (ball.getX() + ball.getXSpeed() <= WALL_SIZE)
        ball.setXSpeed(-ball.getXSpeed());  

    //see if the ball hits the right walls
    if (ball.getX() + ball.getWidth() + ball.getXSpeed() >= walls.get(walls.size() - 1).getX())
        ball.setXSpeed(-ball.getXSpeed());

    //see if the ball hits the paddle
    if (ball.didCollideTop(paddle))         //top of paddle
        ball.setYSpeed(-ball.getYSpeed());

    else if (ball.didCollideLeft(paddle) || ball.didCollideRight(paddle))   //sides of paddle
        ball.setXSpeed(-ball.getXSpeed());

    //checks if the ball hits a square
    for (int i = squares.size() - 1; i >= 0; i--)
    {
        if (ball.didCollideLeft(squares.get(i)) || ball.didCollideRight(squares.get(i)))
        {
            squares.remove(i);
            ball.setXSpeed(-ball.getXSpeed());
        }

        else if (ball.didCollideTop(squares.get(i)) || ball.didCollideBottom(squares.get(i)))
        {
            squares.remove(i);
            ball.setYSpeed(-ball.getYSpeed());
        }
    }

    if (ball.getY() + ball.getHeight() > Frame.HEIGHT)  //resets ball if it goes off screen
        resetBall();

    if (squares.size() == 0)
    {
        ball.setColor(Color.white);
        graphToBack.setColor(randomColor());
        graphToBack.setFont(window.getFont().deriveFont(200f));
        graphToBack.drawString("You Win!", (int) (Frame.WIDTH / 6.5), (int) (Frame.HEIGHT / 2.5));
    }

    twoDGraph.drawImage(back, null, 0, 0);
}

/**
 * Randomly generates true or false
 * Used to randomize ball direction on reset
 * @return true or false
 */
public boolean genRandom()
{
   if ((int) (Math.random() * 2) == 0)
       return true;
   else
       return false;
}

/**
 * Generates a random color
 * @return a random color
 */
public Color randomColor()
{
    int r = (int) (1 + Math.random() * 255);
    int g = (int) (1 + Math.random() * 255);
    int b = (int) (1 + Math.random() * 255);
    return new Color(r, g, b);
}

/**
 * Resets the ball in middle
 * Resets the ball's speed
 * Chooses a random direction
 */
public void resetBall()
{
   ball.setPos((int) (Frame.WIDTH / 2.1), (int) (Frame.HEIGHT / 1.15)); //reset position
   ball.setXSpeed(BALL_SPEED);                      //reset speeds
   ball.setYSpeed(-BALL_SPEED);

   if (genRandom())                                 //random X direction
       ball.setXSpeed(-BALL_SPEED);
}


public void keyPressed(KeyEvent e)
{
  switch(toUpperCase(e.getKeyChar()))
  {
     case 'D' : keys[0] = true; break;  //left
     case 'J' : keys[1] = true; break;  //right
  }
}

public void keyReleased(KeyEvent e)
{
switch(toUpperCase(e.getKeyChar()))
{
    case 'D' : keys[0] = false; break;
    case 'J' : keys[1] = false; break;
}
}

public void run()
{
try
{
    while(true)
    {
       Thread.currentThread().sleep(8);
               repaint();
            }
    }
catch(Exception e){}
}

public void keyTyped(KeyEvent e) {}
}

Answer 1

您的 block 排列在网格中。如果将 block 存储在二维数组中(按网格行和列号索引)，则可以直接计算球的网格坐标(除以球 X/ block 宽度和球 Y/ block 高度)，然后检查是否存在该网格单元(或相邻单元格中的一个 block ，请注意，球可能位于最多 4 个单元格的边界上[假设其直径小于单元格的较小尺寸 - 但您可以轻松适应，如果事实并非如此])。这将是 O(1)；您将直接确定球可能重叠的可能 block 。

然后您只需要对最多 4 个 block (球所在的网格单元中的 block )而不是每个 block 进行实际碰撞检测 - 并且在任何时候您都不需要迭代所有 block 。

你的壁细胞也可以融入到这个网格中。