面试题：Ruby游戏开发中的碰撞检测优化

优化思路

减少不必要计算：
- 帧间连贯性：利用前一帧的碰撞检测结果。如果玩家角色和平台的位置在两帧之间变化不大，可以假设碰撞状态没有改变，避免重复检测。
- 粗粒度到细粒度检测：先进行粗略的碰撞检测，例如基于边界框（Bounding Box）检测。只有在边界框检测到可能碰撞时，再进行精确的碰撞检测，如基于像素的检测。
空间分区算法：
- 四叉树（Quadtree）：将游戏场景划分为四个象限，每个象限再递归划分。将平台和玩家角色根据其位置分配到相应的节点。在碰撞检测时，只需检测同一节点或相邻节点内的对象，减少需要检测的对象数量。
- 网格（Grid）：将场景划分为网格，每个对象根据其位置归属到相应网格单元。碰撞检测时，仅检测同一网格单元或相邻网格单元内的对象。

关键代码片段

基于边界框的粗粒度检测：

class GameObject
  attr_accessor :x, :y, :width, :height

  def initialize(x, y, width, height)
    @x = x
    @y = y
    @width = width
    @height = height
  end

  def collides_with?(other)
    (self.x < other.x + other.width) &&
    (self.x + self.width > other.x) &&
    (self.y < other.y + other.height) &&
    (self.y + self.height > other.y)
  end
end

# 使用示例
player = GameObject.new(100, 100, 50, 50)
platform = GameObject.new(120, 120, 80, 20)
puts player.collides_with?(platform)

四叉树实现示例：

class Quadtree
  attr_accessor :bounds, :capacity, :objects, :nodes

  def initialize(bounds, capacity = 4)
    @bounds = bounds
    @capacity = capacity
    @objects = []
    @nodes = []
  end

  def insert(object)
    if @nodes.empty?
      @objects << object
      if @objects.length > @capacity
        split
        @objects.each do |obj|
          @nodes.each do |node|
            node.insert(obj) if node.bounds.include?(obj)
          end
        end
        @objects = []
      end
    else
      @nodes.each do |node|
        node.insert(object) if node.bounds.include?(object)
      end
    end
  end

  def retrieve(object)
    result = []
    if @nodes.empty?
      result += @objects.select { |obj| obj.collides_with?(object) }
    else
      @nodes.each do |node|
        if node.bounds.intersects?(object.bounds)
          result += node.retrieve(object)
        end
      end
    end
    result
  end

  private

  def split
    x = @bounds.x
    y = @bounds.y
    w = @bounds.width / 2
    h = @bounds.height / 2
    @nodes << Quadtree.new(Rectangle.new(x, y, w, h), @capacity)
    @nodes << Quadtree.new(Rectangle.new(x + w, y, w, h), @capacity)
    @nodes << Quadtree.new(Rectangle.new(x, y + h, w, h), @capacity)
    @nodes << Quadtree.new(Rectangle.new(x + w, y + h, w, h), @capacity)
  end
end

class Rectangle
  attr_accessor :x, :y, :width, :height

  def initialize(x, y, width, height)
    @x = x
    @y = y
    @width = width
    @height = height
  end

  def include?(object)
    object.x >= @x && object.x + object.width <= @x + @width &&
    object.y >= @y && object.y + object.height <= @y + @height
  end

  def intersects?(other)
    (self.x < other.x + other.width) &&
    (self.x + self.width > other.x) &&
    (self.y < other.y + other.height) &&
    (self.y + self.height > other.y)
  end
end

性能提升量化指标估算方法

时间复杂度分析：
- 优化前：假设场景中有n个平台和1个玩家角色，每次碰撞检测都需要遍历所有平台与玩家角色进行检测，时间复杂度为O(n)。
- 优化后：
  - 基于帧间连贯性：如果帧间位置变化不大，大部分时间可以直接复用前一帧结果，时间复杂度可能降为O(1)。
  - 基于四叉树：假设四叉树深度为d，每个节点平均对象数为m。在理想情况下，每次碰撞检测只需遍历部分节点内的对象，时间复杂度降为O(m * d)，d通常远小于n，m也远小于n，因此性能大幅提升。
实际性能测试：
- 基准测试：使用Ruby的Benchmark库，在优化前后分别运行碰撞检测代码多次，记录每次运行的时间，计算平均时间。例如：

require 'benchmark'

# 优化前的碰撞检测代码块
before_code = Proc.new do
  # 未优化的碰撞检测逻辑
end

# 优化后的碰撞检测代码块
after_code = Proc.new do
  # 优化后的碰撞检测逻辑
end

puts "Before optimization: #{Benchmark.realtime(&before_code)} seconds"
puts "After optimization: #{Benchmark.realtime(&after_code)} seconds"

通过对比优化前后的平均运行时间，可以直观地看到性能提升的量化指标。

星途面试题库

面试题：Ruby游戏开发中的碰撞检测优化

知识考点

面试题答案

优化思路

关键代码片段

性能提升量化指标估算方法