Fliesenweite Ausdehnung auf einem Raster

Ich arbeite derzeit an der A * -Pfadfindung in einem Raster und möchte den generierten Pfad glätten, wobei ich auch das Ausmaß des Zeichens berücksichtige, das sich darauf bewegt. Ich verwende ein Raster für die Wegfindung, aber die Bewegung von Charakteren ist freies Roaming, keine strikte Bewegung von Kachel zu Kachel.

Um einen glatteren und effizienteren Pfad zu erzielen, führe ich Linienspuren in einem Raster durch, um festzustellen, ob sich zwischen den Kacheln nicht begehbare Kacheln befinden, um unnötige Ecken zu entfernen.

Da eine Linienverfolgung jedoch keine Ausdehnung aufweist, wird die Ausdehnung des Zeichens nicht berücksichtigt und es werden schlechte Ergebnisse erzielt (es werden keine nicht begehbaren Kacheln zurückgegeben, die nur von der Linie übersehen wurden, was zu unerwünschten Kollisionen führt).

Ich suche also nicht nach einem Linienalgorithmus, der die Kacheln darunter bestimmt, sondern nach einem, der die Kacheln unter einer kachelweiten Ausdehnungslinie bestimmt. Hier ist ein Bild, um mein Problem zu visualisieren!

Hat jemand irgendwelche Ideen? Ich habe mit Bresenhams Linie und anderen Alternativen gearbeitet, aber ich habe noch nicht herausgefunden, wie ich dieses spezielle Problem lösen kann.

Wie wäre es, wenn Sie von jeder Ecke der Kachel, auf der Sie sich befinden, eine Linie zu jeder Ecke der Kachel ziehen, zu der Sie gehen möchten. Sie können dies wahrscheinlich sogar auf 3 statt auf vier Zeilen optimieren. Würde dies nicht alle Kacheln auf dem Pfad korrekt erkennen?

Informationen zu glatteren Pfaden finden Sie in Artikeln zum Thema "Lenkverhalten", insbesondere in Artikeln, die es mit A * kombinieren, z. B. die folgenden Links:

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

Ich habe diesen Algorithmus gerade vor ein paar Tagen für ein Spiel von mir implementiert! (-8

Hier ist meine Idee in Bildform:

Beachten Sie, dass der Algorithmus mit Rechtecken beliebiger Größe arbeitet. Es basiert auf der Tatsache, dass eine Ecke des Rechtecks immer zuerst mit einer Gitterlinie kollidiert. Dies bedeutet, dass Sie nur einen Strahl verfolgen und alle benötigten Schnittpunkte erhalten können.

Hier ist der Algorithmus Schritt für Schritt:

1. Wählen Sie die "vordere" Ecke Ihres Rechtecks. Im Bild liegt die Verfolgungsrichtung beispielsweise im oberen rechten Quadranten, daher wählen wir die obere rechte Ecke.
2. Verfolgen Sie den Strahl (mit der Breite Null) von dieser Ecke zu Ihrem Ziel. Sie müssten alle Schnittpunkte Ihres Strahls mit Gitterlinien durchlaufen.
3. Platzieren Sie für alle Schnittpunkte des Strahls mit Gitterlinien Ihr Rechteck am Schnittpunkt. Seine Seite würde genau entlang einer Gitterlinie liegen und eine Anzahl von Gitterzellen berühren. Dies sind die Kacheln, mit denen Ihr Rechteck an dieser Stelle kollidiert!

Es gibt hier einige Randfälle, z. B. wenn der Strahl genau vertikal / horizontal ist oder wenn er genau auf eine Ecke trifft, aber sie sind nicht schwierig.

Dieses Verfahren ist eine Adaption von Bresenham, die die ursprüngliche Frage löst.

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