Rastreio de extensão em todo o bloco em uma grade

Atualmente, estou trabalhando em A * pathfinding em uma grade e estou procurando suavizar o caminho gerado, considerando também a extensão do personagem se movendo ao longo dele. Estou usando uma grade para encontrar o caminho, no entanto, o movimento do personagem é de roaming gratuito, não o movimento estrito de ladrilhos para ladrilhos.

Para obter um caminho mais suave e eficiente, estou traçando linhas em uma grade para determinar se há peças imersas entre peças para raspar cantos desnecessários.

No entanto, como um rastreamento de linha é de extensão zero, ele não considera a extensão do caractere e produz resultados ruins (não retornando blocos não-passíveis de passagem perdidos pela linha, causando colisões indesejadas).

Então, o que estou procurando é, em vez de um algoritmo de linha que determina os blocos embaixo dele, estou procurando um que determine os blocos sob uma linha de extensão de bloco inteiro. Aqui está uma imagem para ajudar a visualizar o meu problema!

Alguém tem alguma idéia? Eu tenho trabalhado com a linha de Bresenham e outras alternativas, mas ainda não descobri como resolver esse problema específico.

Que tal se você desenhar uma linha de todos os cantos do 'bloco' em que está localizado em todos os cantos do bloco que deseja ir. Você provavelmente pode até otimizar isso para 3 linhas em vez de quatro. Isso não detectaria corretamente todos os blocos no caminho?

Quanto a caminhos mais suaves, consulte artigos sobre o 'comportamento da direção', especialmente aqueles que o combinam com A *, por exemplo, nos seguintes links:

• http://rocketmandevelopment.com/2010/11/10/a-star-and-pathfollowing-steering-behavior/
• http://www.red3d.com/cwr/steer/

Acabei de implementar esse algoritmo para um jogo meu alguns dias atrás! (-8

Aqui está a minha ideia em forma de imagem:

Observe que o algoritmo trabalha com retângulos de qualquer tamanho. baseia-se no fato de que um canto do retângulo sempre colide primeiro com qualquer linha de grade. Isso significa que você só pode rastrear um raio e obter todas as interseções necessárias.

Aqui está o algoritmo passo a passo:

1. Escolha o canto "para a frente" do seu retângulo. Por exemplo, na figura a direção do traçado está no quadrante superior direito, então escolhemos o canto superior direito.
2. Rastreie o raio (largura zero) deste canto até o seu destino. Você precisaria percorrer todas as interseções do seu raio com linhas de grade.
3. Para todas as interseções do raio com linhas de grade, coloque seu retângulo no ponto de interseção. Seu lado estaria exatamente ao longo de uma linha de grade, tocando várias células da grade. Estes são os blocos que seu retângulo colide com neste momento!

Existem alguns casos extremos aqui, como quando o raio é exatamente vertical / horizontal ou quando atinge um canto exatamente, mas não é difícil.

Este procedimento é uma adaptação de bresenham, que resolve a questão original.

final int cols = 64;
final int rows = 64;
color tiles = new color[cols*rows];

void squaretrace(int x1, int y1, int x2, int y2, color c) {
  if (x1==x2 && y1==y2) {
    tiles[x1+y1*cols] += c;
  } else {
    // make sure y1 is less or equal to y2
    if (y2 < y1) {
      int t = x1;
      x1 = x2;
      x2 = t;
      t = y1;
      y1 = y2;
      y2 = t;
    }
    // along y-axis
    if (x1==x2) {
      for(int y = y1; y <= y2; y++){
        tiles[x1 + y * cols] += c;
      }
    }
    // along x-axis
    else if (y1==y2) {
      int xLo, xHi;
      if(x1 < x2){
        xLo = x1;
        xHi = x2;
      }
      else{
        xLo = x2;
        xHi = x1;
      }
      for(int x = xLo; x <= xHi; x++){
        tiles[x + y1 * cols] += c;
      }
    }
    // northeast
    else if (x1 < x2) { 
      // NW and SE corner
      int dx = x2 - x1;
      int dy = y2 - y1;
      int m = 8;
      int k = (1<<m) * dx / dy;

      int minx = x1 << m;
      int maxx = (x1+1) << m;

      for (int y = y1; y <= y2; y++) {
        int xLo = minx >> m;
        if (y!=y1) minx += k;
        if (y<y2) maxx += k;
        int xHi = (maxx-1) >> m;
        for (int x = xLo; x <= xHi; x++) {
          tiles[x+y*cols] += c;
        }
        tiles[xLo+y*cols] += c;
        tiles[xHi+y*cols] += c;
      }
    }
    // northwest
    else {
      // NW and SE corner
      int dx = x2 - x1;
      int dy = y2 - y1;
      int m = 8;
      int k = (1<<m) * dx / dy;

      int minx = x1 << m;
      int maxx = (x1+1) << m;

      for (int y = y1; y <= y2; y++) {

        if (y<y2) minx += k;
        int xLo = minx >> m;
        int xHi = (maxx-1) >> m;
        if (y!=y1) maxx += k;

        for (int x = xLo; x <= xHi; x++) {
          tiles[x+y*cols] += c;
        }
        tiles[xLo+y*cols] += c;
        tiles[xHi+y*cols] += c;
      }
    }
  }
}