Обтекание всей сетки по сетке

В настоящее время я работаю над наведением A * на сетку и пытаюсь сгладить сгенерированный путь, а также учесть степень перемещения персонажа по нему. Я использую сетку для поиска пути, однако движение персонажа является свободным перемещением, а не строгим движением тайла к тайлу.

Чтобы добиться более плавного и более эффективного пути, я делаю трассировки линий на сетке, чтобы определить, есть ли неприступные плитки между плитками, чтобы сбрить ненужные углы.

Однако, поскольку трассировка линии имеет нулевой экстент, она не учитывает экстент символа и дает плохие результаты (не возвращая непроходимые тайлы, просто пропущенные линией, вызывая нежелательные столкновения).

Так что я ищу не линейный алгоритм, который определяет плитки под ним, я ищу тот, который определяет плитки под линией экстента в масштабе плитки. Вот изображение, чтобы помочь визуализировать мою проблему!

У кого-нибудь есть идеи? Я работал с линией Брезенхэма и другими альтернативами, но я еще не понял, как решить эту конкретную проблему.

Как насчет того, чтобы нарисовать линию из каждого угла «плитки», в которую вы попадаете, в каждый угол плитки, в которую вы хотите перейти. Вы можете даже оптимизировать это до 3 строк вместо четырех. Разве это не правильно обнаружит все плитки на пути?

Что касается более плавных путей, проверьте статьи о «поведении руля», особенно те, которые сочетают его с A *, например, эти ссылки:

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

Я только что реализовал этот алгоритм для моей игры пару дней назад! (-8

Вот моя идея в виде картинки:

Обратите внимание, что алгоритм работает с прямоугольниками любого размера. это основано на факте, что один угол прямоугольника всегда сталкивается сначала с любой линией сетки. Это означает, что вы можете проследить только один луч и получить все необходимые пересечения.

Вот пошаговый алгоритм:

1. Выберите «передний» угол вашего прямоугольника. Например, на рисунке направление трассировки лежит в верхнем правом квадранте, поэтому мы выбираем верхний правый угол.
2. Проследите луч (нулевой ширины) от этого угла до пункта назначения. Вам нужно будет перебрать все пересечения вашего луча с линиями сетки.
3. Для всех пересечений луча с линиями сетки поместите прямоугольник в точку пересечения. Его сторона будет лежать точно вдоль линии сетки, касаясь нескольких ячеек сетки. Это плитки, с которыми сталкивается ваш прямоугольник на этом этапе!

Здесь есть некоторые крайние случаи, например, когда луч точно вертикальный / горизонтальный, или когда он точно попадает в угол, но это не сложно.

Эта процедура является адаптацией Bresenham, которая решает оригинальный вопрос.

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