Colisões por Hitbox e Quadtree

[Brandt]

Hitboxes | v0.1.0 | por Masked


para RPG Maker VX Ace

Requer o script DLL Utils.

Descrição

O script implementa classes auxiliares para sistemas de detecção de colisão via hitbox, inspirado nesse post do Jorge_Maker.
Vale ressaltar que esse script não adiciona funcionalidades ao jogo por si só, apenas disponibiliza as ferramentas para que outros scripts o façam em seus próprios sistemas.

Inicialmente, o script era implementado puramente em Ruby. Conforme fui fazendo testes de performance, porém, ficou claro que o desempenho deixava a desejar, e como o intuito desse script é justamente ser eficiente, fiz o que precisava ser feito: implementei toda a lógica de colisão em C++, com paralelismo e tudo a que se tem direito, e botei numa DLL.

Esse script implementa duas classes:

• Hitbox: Classe de hitbox. É basicamente um Rect que implementa funções de interseção.
• Stage: Classe usada para colocar as hitboxes e testar colisão entre elas.

Instruções

Cole acima do script Main e abaixo do DLL Utils. Não esqueça de baixar a DLL disponível abaixo e salvar na pasta do projeto com o nome hitboxes.dll.

Exemplo de Uso

Spoiler

Segue código que faz uso de todos os recursos que o script oferece:

# Espaço para checagem de colisões
stage = Stage.new(Graphics.width, Graphics.height)

# Criamos 16 hitboxes de vários tamanhos em posições aleatórias
hitboxes = Array.new(16) do |i|
  Hitbox.new(rand(Graphics.width), rand(Graphics.height), 4 * i, 4 * i)
end

# Índice de hitboxes que colidiram, para colorir diferente
collided = {}

# Desenho na tela
screen = Sprite.new
screen.bitmap = Bitmap.new(Graphics.width, Graphics.height)

BLUE = Color.new(0, 0, 255)
RED = Color.new(255, 0, 0)

def update_hitbox(stage, hitbox)
  # Move a hitbox em direção ao centro da tela
  cx = Graphics.width / 2
  cy = Graphics.width / 2
  if cx != hitbox.rect.x
    t = Math.atan2(cy - hitbox.rect.y, cx - hitbox.rect.x)
    hitbox.move(Math.cos(t) * 2, Math.sin(t) * 2)
  end
  
  # No momento, o Stage não suporta hitboxes em movimento. Então tiramos
  # ela e colocamos de novo para atualizar a quadtree
  stage.delete(hitbox)
  stage.push(hitbox)
end

loop do
  screen.bitmap.clear
  
  for h in hitboxes
    # Desenha a hitbox na tela
    screen.bitmap.fill_rect(h.rect, collided[h.handle] ? BLUE : RED)
    
    # Atualiza o estado da hitbox
    update_hitbox(stage, h)
  end

  # Atualiza o estado das colisões
  stage.update
  
  # Sinaliza colisões
  for a, b in stage.collisions
    collided[a.handle] = true
    collided[b.handle] = true
  end
  
  Graphics.update
end

[close]

Observações

Esta é uma versão inicial do script e deve ser vista como prova de conceito.

Um problema grave da implementação atual é que a Quadtree não lida com mudança de posição das hitboxes, e deve ser reconstruída a todo frame.
Também pode ocorrer travamento do sistema por completo caso mais que 16 objetos estejam numa mesma posição no espaço. Isso acontece pela forma como a quadtree está implementada. Estou estudando uma forma de corrigir esse problema.

Ajustes voltados para a correção desses problemas serão feitos no futuro.


Download

DLL pré-compilada (Mega)

Código Fonte (Mega)

Script

Código: ruby

#==============================================================================
# Hitboxes | v0.2.0 | por Masked
#
# para RPG Maker VX Ace
#------------------------------------------------------------------------------
#  Implementa hitboxes com posição e dimensão e operações básicas como colisão
# e movimento.
#  Feito com intuito de servir de base para o desenvolvimento de outros
# scripts.
#==============================================================================
($modules ||= {})[:hitboxes] = 2.0
#==============================================================================
# ** DLLObjectWrapper
#------------------------------------------------------------------------------
#  Esta é uma classe abstrata para objetos que funcionam como wrappers de 
# ponteiros de objetos de uma DLL.
#==============================================================================
module DLLObjectWrapper
  #--------------------------------------------------------------------------
  # * Métodos estáticos
  #--------------------------------------------------------------------------
  module ClassMethods
    #------------------------------------------------------------------------
    # * Cria um objeto a partir de um ponteiro
    #   handle  : Ponteiro
    #------------------------------------------------------------------------
    def from_handle(handle)
      obj = allocate
      obj.send :initialize
      
      h = Handle.new
      h.pointer = handle
      obj.instance_variable_set(:@handle, h)
      obj
    end
    #------------------------------------------------------------------------
    # * Cria um novo objeto
    #------------------------------------------------------------------------
    def new(*args)
      obj = super()
      
      h = Handle.new
      h.pointer = obj.create_handle(*args)
      obj.instance_variable_set(:@handle, h)
      obj
    end
  end
  #--------------------------------------------------------------------------
  # * Extende a classe quando ela inclui o módulo para adicionar as funções
  #   estáticas necessárias
  #--------------------------------------------------------------------------
  def self.included(klass)
    klass.extend(ClassMethods)
  end
  #--------------------------------------------------------------------------
  # * Struct de handle
  #--------------------------------------------------------------------------
  Handle = CStruct.create do |s|
    s.attr :pointer, :long
  end
  #--------------------------------------------------------------------------
  # * Construtor
  #--------------------------------------------------------------------------
  def initialize
    @disposed = false
  end
  #--------------------------------------------------------------------------
  # * Obtém o ponteiro do objeto interno
  #--------------------------------------------------------------------------
  def handle
    @handle.pointer
  end
  #--------------------------------------------------------------------------
  # * Elimina o objeto
  #--------------------------------------------------------------------------
  def dispose
    check_disposed
    @disposed = true
  end
  #--------------------------------------------------------------------------
  # * Verifica se a hitbox foi eliminada
  #--------------------------------------------------------------------------
  def disposed?
    @disposed
  end
  #--------------------------------------------------------------------------
  # * Ponteiro C para o ponteiro do objeto
  #--------------------------------------------------------------------------
  def cptr
    check_disposed
    @handle.cptr
  end
  #--------------------------------------------------------------------------
  # * Lança erro se o objeto tiver sido eliminado
  #--------------------------------------------------------------------------
  protected
  def check_disposed
    raise 'Disposed object' if disposed?
  end
end
#==============================================================================
# ** Hitbox
#------------------------------------------------------------------------------
#  Esta classe representa uma caixa de colisão alinhada aos eixos (i.e. não 
# rotacionada)
#==============================================================================
class Hitbox
  include DLLObjectWrapper
  extend DLLImporter
  #--------------------------------------------------------------------------
  # * Struct de caixa limitante
  #--------------------------------------------------------------------------
  AABB = CStruct.create do |s|
    s.attr :x, :int
    s.attr :y, :int
    s.attr :width, :int
    s.attr :height, :int
  end
  #--------------------------------------------------------------------------
  # * Funções da DLL
  #--------------------------------------------------------------------------
  with_dll('hitboxes.dll') do
    import :CreateHitbox, :long
    import :MoveHitbox, :long
    import :HitboxIntersects, :bool
    import :GetHitboxRect, :void
    import :DestroyHitbox, :long
  end
  #--------------------------------------------------------------------------
  # * Construtor
  #   x       : Posição X da hitbox
  #   y       : Posição Y da hitbox
  #   width   : Largura da hitbox
  #   height  : Altura da hitbox
  #--------------------------------------------------------------------------
  def create_handle(x, y, width, height)
    CreateHitbox(x.to_i, y.to_i, width.to_i, height.to_i)
  end
  #--------------------------------------------------------------------------
  # * Obtém o retângulo da hitbox
  #--------------------------------------------------------------------------
  def rect
    check_disposed
    return @rect if @rect
    r = AABB.new
    GetHitboxRect(handle, r.cptr)
    @rect = Rect.new(r.x, r.y, r.width, r.height)
  end
  #--------------------------------------------------------------------------
  # * Desloca a hitbox
  #   x : Deslocamento no eixo X
  #   y : Deslocamento no eixo Y
  #--------------------------------------------------------------------------
  def move(x, y)
    check_disposed
    MoveHitbox(handle, x.to_i, y.to_i)
    @rect = nil
  end
  #--------------------------------------------------------------------------
  # * Verifica interseção com outra hitbox
  #   other : Outra hitbox
  #--------------------------------------------------------------------------
  def intersects?(other)
    check_disposed
    HitboxIntersects(handle, other.handle) != 0
  end
  #--------------------------------------------------------------------------
  # * Elimina a hitbox
  #--------------------------------------------------------------------------
  def dispose
    super
    DeleteHitbox(handle)
  end
end
#==============================================================================
# ** Stage
#------------------------------------------------------------------------------
#  Esta classe representa um plano, onde hitboxes são adicionadas para que suas
# colisões sejam detectadas.
#==============================================================================
class Stage
  include DLLObjectWrapper
  extend DLLImporter
  #--------------------------------------------------------------------------
  # * Funções da DLL
  #--------------------------------------------------------------------------
  with_dll('hitboxes.dll') do
    import :CreateStage, :long
    
    import :StageAddHitbox, :void
    import :StageRemoveHitbox, :void
    
    import :StageCheckCollisions, :long
    
    import :BeginIterateStageCollisions, :long
    import :IterateStageCollisions, :bool
    import :EndIterateStageCollisions, :void
    
    import :DestroyStage, :void
  end
  #--------------------------------------------------------------------------
  # * Construtor
  #   width   : Largura do plano
  #   height  : Altura do plano
  #--------------------------------------------------------------------------
  def create_handle(width, height)
    CreateStage(width.to_i, height.to_i)
  end
  #--------------------------------------------------------------------------
  # * Adiciona uma hitbox ao plano
  #   hitbox  : Hitbox a ser adicionada
  #--------------------------------------------------------------------------
  def push(hitbox)
    check_disposed
    StageAddHitbox(handle, hitbox.handle)
  end
  alias << push
  #--------------------------------------------------------------------------
  # * Remove uma hitbox do plano
  #   hitbox  : Hitbox a ser removida
  #--------------------------------------------------------------------------
  def delete(hitbox)
    check_disposed
    StageRemoveHitbox(handle, hitbox.handle)
  end
  #--------------------------------------------------------------------------
  # * Atualiza o estado das colisões
  #--------------------------------------------------------------------------
  def update
    check_disposed
    StageCheckCollisions(handle)
  end
  #--------------------------------------------------------------------------
  # * Colisões detectadas
  #--------------------------------------------------------------------------
  def collisions
    check_disposed
    Enumerator.new do |enum|
      a = Hitbox.from_handle(0)
      b = Hitbox.from_handle(0)
      it = BeginIterateStageCollisions(handle)
      while IterateStageCollisions(handle, it, a.cptr, b.cptr) != 0
        enum.yield a, b
      end
      EndIterateStageCollisions(it)
    end
  end
  #--------------------------------------------------------------------------
  # * Elimina o objeto
  #--------------------------------------------------------------------------
  def dispose
    super
    DestroyStage(handle)
  end
end

Licensa: Creative Commons Attribution-ShareAlike 4.0 International

[Jorge_Maker]

Não tinha hora melhor pra tu fazer e disponibilizar esse script, Masked.
Vou começar estudar os conceitos do script para tentar aplicar em algum sistema. Mas acho que eu ainda vou bater um pouco de cabeça com essa de Quadtree. xD
Muito obrigado. o/

[Raizen]

Minhas palavras a do Jorge_Maker hahah,
essa não é a minha área de expertise na parte de code xD, então é uma bela hora para disponibilizar e eu dar aquela estudada básica!

[Brandt]

@Raizen

Não é minha área de expertise também na real
Peguei a quadtree olhando a referência da wikipedia pra você ter ideia kkkk

Disponibilizei o código em C++ do que eu fiz, acho que dá uma boa fonte de estudos hein.


@Jorge_Maker

Hehe, você que me deu a ideia xd

Não recomendo muito pegar o script pra implementar nada ainda, provavelmente vão acontecer mudanças bem drásticas na API, e tem vários bugs e melhorias pra serem feitas. Mas assim que tiver uma versão mais sólida apoio totalmente kk


Aliás...



Versão 0.2.0 - Changelog

Não deu, o Ruby estava limitando demais a performance do sistema. Transferi toda a lógica para C++ e coloquei numa DLL, disponível pra download no tópico.

Com isso, temos algumas mudanças significativas:

- Remoção da classe RotatedHitbox. Não que não vá ter, é só que não tive tempo pra implementar ela em C++, e tenho que planejar direitinho como vou colocar ela lá pra não ter mais problemas.

- Bug monstro na quadtree. E não é feature: quando tem mais que 16 objetos juntos no espaço na mesma quadtree, ela entra em recursão infinita. Isso acontece porque cada quatree aguenta no máximo 16 objetos (dá pra mexer nisso, mas afeta a performance e não resolve o problema) antes de se subdividir, mas se os 16 objetos estão na mesma posição a quadtree fica se dividindo indefinidamente, sem nunca conseguir dividir os objetos em árvores diferentes. Isso pode ser resolvido com um valor de profundidade máxima para a árvore ou subdividindo as hitboxes na hora de armazenar elas, mas vou estudar melhor qual a melhor solução.

- Performance absurda. Fora os problemas, tem esse ponto, que acho que faz o resto valer a pena: dá pra rodar colisões entre 2600 hitboxes a 60 fps!! Iterando por todas as colisões, porém, existe um overhead do ruby e das chamadas da API, e assim o limite cai pra umas 600 hitboxes, que ainda é 3x mais que o teste anterior.

- Paralelismo. A detecção de colisões usa multithreading para paralelizar o trabalho de detectar as interseções das hitboxes, se possível. O algoritmo determina a quantidade de cores disponíveis na máquina e faz uso do máximo deles para dividir a carga entre eles. Como o meu processador tem 4 cores, dá pra estimar (bem por cima) que em um computador 16 core o script potencialmente suporta por volta de 10000 hitboxes a 60 fps sem contar a iteração, o que é bem incrível kk.

A DLL está disponível para download no tópico junto do código fonte.

\o