Tile-luasnya menelusuri pada grid

Saat ini saya sedang mengerjakan pathfinding A * pada grid dan saya ingin memuluskan path yang dihasilkan, sambil juga mempertimbangkan sejauh mana karakter bergerak di sepanjang itu. Saya menggunakan kotak untuk pathfinding, namun pergerakan karakter bebas roaming, bukan pergerakan ubin ke ubin yang ketat.

Untuk mencapai jalur yang lebih mulus dan lebih efisien, saya melakukan penelusuran garis pada kisi untuk menentukan apakah ada ubin yang tidak dapat dikunci di antara ubin untuk memotong sudut yang tidak perlu.

Namun, karena jejak garis adalah batas nol, itu tidak mempertimbangkan sejauh mana karakter dan memberikan hasil yang buruk (tidak mengembalikan ubin yang tidak dapat dikunci hanya terlewatkan oleh garis, menyebabkan tabrakan yang tidak diinginkan).

Jadi yang saya cari bukan algoritma garis yang menentukan ubin di bawahnya, saya mencari yang menentukan ubin di bawah garis luas ubin. Ini adalah gambar untuk membantu memvisualisasikan masalah saya!

Adakah yang punya ide? Saya telah bekerja dengan garis Bresenham dan alternatif lain tetapi saya belum menemukan cara untuk mengatasi masalah khusus ini.

Bagaimana jika Anda menggambar garis dari setiap sudut 'ubin' Anda berada di setiap sudut ubin yang ingin Anda tuju. Anda bahkan dapat mengoptimalkan ini ke 3 baris, bukan empat. Tidakkah ini mendeteksi semua ubin di jalur dengan benar?

Adapun jalur yang lebih mulus, periksa artikel tentang 'perilaku kemudi' terutama yang menggabungkannya dengan A * misalnya tautan ini:

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

Saya baru saja mengimplementasikan algoritma ini untuk permainan saya beberapa hari yang lalu! (-8

Inilah ide saya dalam bentuk gambar:

Perhatikan bahwa algoritma ini bekerja dengan persegi panjang dengan ukuran berapa pun. ini didasarkan pada kenyataan bahwa salah satu sudut persegi panjang selalu bertabrakan terlebih dahulu dengan garis kisi apa pun. Ini berarti bahwa Anda hanya dapat melacak satu sinar, dan mendapatkan semua persimpangan yang Anda butuhkan.

Berikut algoritma langkah-demi-langkah:

1. Pilih sudut "maju" dari persegi panjang Anda. Misalnya, pada gambar, arah penelusuran terletak di kuadran kanan atas, jadi kami memilih sudut kanan atas.
2. Lacak sinar (lebar nol) dari sudut ini ke tujuan Anda. Anda perlu mengulangi semua persimpangan sinar Anda dengan garis kotak.
3. Untuk semua persimpangan sinar dengan garis kisi, letakkan persegi panjang Anda di titik persimpangan. Sisi sisinya akan terletak tepat di sepanjang garis kisi, menyentuh sejumlah sel kisi. Ini adalah ubin yang bertabrakan dengan persegi panjang Anda pada saat ini!

Ada beberapa kasus tepi di sini, seperti ketika sinar persis vertikal / horizontal, atau ketika menyentuh sudut persis, tetapi mereka tidak sulit.

Prosedur ini merupakan adaptasi dari bresenham, yang memecahkan pertanyaan orisinal.

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;
      }
    }
  }
}