D&C_2DCollisionDetection

Número da Lista: 3
Conteúdo da Disciplina: Dividir e Conquistar

Alunos

Matrícula	Aluno
16/0049733	Felipe Borges de Souza Chaves
18/0055241	Victor Jorge da Silva Gonçalves

Sobre

O objetivo deste projeto é demonstrar a utilização de um algoritmo sofisticado para a detecção de colisão entre particulas no plano. O algoritmo adotado para este trabalho foi o Quadtree. Neste projeto, demonstramos a utilização do algoritmo através da simulação de uma mesa de bilhar com várias bolas colidindo entre si.

O principal artefato deste projeto, que é o algoritmo de detecção, pode ser visualizado neste arquivo que implementa duas funções de colisão, uma de complexidade O(n²) e a Quadtree.

Vale, entretanto, ressaltar que o projeto possui além do algoritmo de divisão e conquista, muitos outros paradigmas e estruturas contidas em sua elaboração, a saber: árvores, grafos e mapas. Com bastante afinco e dedicação, a dupla utilizou dos diversos conhecimentos da matéria e implementou manualmente cada elemento da interface gráfica, apenas com a ajuda de uma biblioteca de baixo nível para rederização de retângulos, fontes e imagens (SDL).

Screenshots

Instalação

Linguagem: C++
Biblioteca: SDL 2.0

Em caso de não portabilidade, entre em contato com a dupla!

Ubuntu ou Debian

Para efetuar a instalação das dependências, execute os comandos:

sudo apt-get install g++

sudo apt-get install make

sudo apt-get install libsdl2-dev

sudo apt-get install libsdl2-image-dev

sudo apt-get install libsdl2-ttf-dev

Windows

Infelizmente, o código deste projeto utiliza de cabeçalhos e esquemas de compilação que não são portáveis para Windows. Sendo assim, para a correta execução do código recomendamos a instalação do WSL 1, do VcXsrv e do Ubuntu 18.04 sobre o WSL1. Feita a instalação desses componentes, execute dentro do bash do Ubuntu os mesmos passos listados para Ubuntu ou Debian.

MacOS

Para instalar o SDL no MacOS, recomendamos o uso do homebew.

No terminal, execute:

brew install make

brew install sdl2

brew install sdl2_ttf

brew install sdl2_image

Uso

Para usuários Windows com WSL1 e Ubuntu, será necessário executar previamente o VcXsrv no desktop do Windows e em seguida executar no bash do Ubuntu o seguinte comando:

export DISPLAY=:0

A execução da aplicação é simples e pode ser feita executando comando abaixo a partir do diretório 2DCollisionDetection.

make && make run