Como encontrar células de grade 2D varridas por um círculo em movimento?

9

Estou fazendo um jogo baseado em uma grade 2D, com algumas células aceitáveis ​​e outras não. Objetos dinâmicos podem se mover continuamente, independentemente da grade, mas precisam colidir com células intransitáveis.

Eu escrevi um algoritmo para rastrear um raio contra a grade, que me fornece todas as células que cruzam o raio. No entanto, o objeto real não tem tamanho de ponto; Atualmente, estou representando-os como círculos. Mas não consigo descobrir um algoritmo eficaz para rastrear um círculo em movimento. Aqui está uma foto do que eu preciso: insira a descrição da imagem aqui

Os números mostram em que ordem o círculo colide com as células da grade. Alguém conhece o algoritmo para encontrar essas colisões? De preferência em C #.

Atualizar O círculo pode ser maior que uma única célula da grade.

deixa pra lá
fonte
mmh por que 3 colidem antes de 4?
FXIII
@FxIII Na verdade, movi o círculo na imagem e ele atingiu 3 antes de 4. Apenas um pouco, mas ainda antes.
Nevermind

Respostas:

6

Acho que seu desenho é um pouco enganador, porque você escolhe desenhar traços do ponto do círculo tangente à sua direção em movimento. Percebo que as colisões nas arestas da grade acontecem quando os pontos SUPERIOR e ESQUERDO do seu círculo tocam uma aresta.

Seja C o seu centro e r o raio, de modo que P ' = C + ( r , 0) e P " = C + (0, r).

Se D é o seu vetor de direção (o versor), você tem duas linhas:

R '= D · t + P' ,

R "= D · t + P"

Você simplesmente precisa encontrar a interseção dessas linhas com as linhas da equação:

y = ie y = i que são as arestas da sua grade!

A solução é fácil, porque você tem que considerar simplesmente o x ou o componente y de R' e R". Você vai encontrar o t valor s para cada insersection, e os pontos para thoose t s, simplesmente tipo aqueles ponto por t e você estão feitos.

Eu acredito que você pode facilmente dizer qual célula é atingida se você souber o ponto de interseção.

Isso funciona se r <1 (a largura e a altura da célula).

Funciona também para os outros casos, simplesmente fazendo alguma consideração sobre P ' e P " . Nós escolhemos TOP e ESQUERDA por causa da direção, INFERIOR e DIREITA devem ser consideradas na direção oposta, você entende o porquê.

Agora veja esta imagem: grande círculo

O círculo é maior que uma única célula e supomos que esteja seguindo a mesma direção do seu desenho. P1 é o primeiro ponto que tocará, P2 é o segundo, P3 é inútil porque está na metade inferior. O que você precisa fazer é lançar raios de P1 e P2 como vimos anteriormente e fazer o mesmo para as linhas verticais.

Em geral, você terá outros pontos de partida junto com o TOP e o ESQUERDO de onde disparar seus raios, quanto maior o seu círculo, mais raios serão lançados.

Para ser honesto, você pode evitar disparar em todos os raios fazendo alguma consideração geométrica, mas isso pode tornar as coisas mais difíceis de entender.

FxIII
fonte
Sim, eu pensei nos pontos P 'e P ", mas não conseguia descobrir o que fazer quando o círculo é maior que uma única célula. Pontos adicionais realmente fazem sentido (e eu obviamente só preciso adicionar raios entre P' e P ")
Nevermind
Podem ser feitas considerações geométricas que simplificam os cálculos, mas o uso da implementação pode levar você aos mesmos resultados por experiência.
FXIII
Está claro que você precisa testar as linhas de grade horizontal e vertical separadamente?
FXIII
Eu acho que você também deve verificar quando o círculo cobre um vértice da grade, porque o círculo colidirá com a célula adjacente na diagonal no canto, mas não será necessariamente o ponto superior / esquerdo / inferior / direito do círculo que o toca primeiro (e você detectará a colisão muito cedo.) Exemplo: quadrados 3,4,5 no diagrama de exemplo da pergunta. Eles são atingidos em ordem (3 e 4 e 5), mas seu algoritmo detectaria 4 e 5 simultaneamente.
finnw
@finnw eles tocam simultaneamente apenas se o ciclo viaja exatamente na direção da bissetriz.
FxIII
1

Se você quiser usar o algoritmo de colisão de raios, poderá escolher oito pontos em cada círculo (em incrementos de 45 graus, alinhados à sua grade quadrada) e usar a colisão de raios entre os pontos correspondentes (ou seja, do topo de um círculo para o topo do outro). A união de todas essas colisões de raios é o conjunto inteiro de células cruzadas.

Você provavelmente poderia melhorar um pouco isso - por exemplo, usando o segmento de linha do centro de um círculo para o centro do outro, mas estendido de ambos os lados pelo raio do círculo, bem como os segmentos de linha paralelos em de ambos os lados nas extremidades dos círculos.

TreDubZedd
fonte
Provavelmente, 8 raios garantirão todas as interseções, mas não serão apresentados na ordem correta. E para colisões, preciso de ordem, não apenas uma lista de células.
Nevermind
Aumente seu algoritmo de colisão de raios para reter um valor t para cada colisão. Quando você obtém a união de células, pode classificar o valor t para obter a ordem correta.
TreDubZedd
Mas como posso comparar o valor t de diferentes raios?
Nevermind
Se você sempre se origina do mesmo círculo, seus pontos de interseção estarão a distância desse círculo. Quando você chegar a uma célula que já viu, se o valor t da colisão atual for menor que o anterior, use-o ... caso contrário, descarte a interseção (mantendo o original).
TreDubZedd
11
Você pode escapar com apenas dois raios nas laterais do círculo perpendicularmente ao movimento, depois pode ver quais peças são atingidas pelos raios e pode verificar o restante para ver se os centros caem entre os dois raios. As únicas coisas que devem faltar são as coisas que colidem no círculo inicial ou final, mas são apenas dois círculos e podem ser manipuladas facilmente. Pode ser um pouco mais lento que oito raios, não tenho certeza; mas você não precisaria escalar o número com base no tamanho do círculo.
Lunin
1

Não estou dizendo que essa é uma analogia perfeita, mas você pode pensar no algoritmo de linha de Bresenham . Uma modificação desse algoritmo ou de uma de suas extensões pode ser útil, especialmente se você o associar a algumas das outras postagens e comentários. Normalmente, esse algoritmo não se preocupa com pedidos, mas acho que você seria capaz de adicioná-lo de maneira bastante trivial.

Ryan
fonte
Eu estava pensando sobre isso também, mas na minha opinião, esse não é o algoritmo certo. Bresenham escolhe apenas um pixel, ele precisa de tudo. E seria difícil adaptar Bresenham ao círculo de apenas um pixel.
Zacharmarz 22/06
O traçador de raios que eu uso é realmente meio que baseado no algoritmo de Bresenham. Tenho problemas para generalizá-lo de uma linha fina para uma "gorda", especificamente varrida em círculo.
Nevermind