Quad - Tree Literatur??

DaRpH

Ich denk mal du meinst klassiche Wegpunkte / nodes. Dazu findest du eigentlich in jedem Computerspiele KI/AI Buch was.

Ich habe da mal was zusammengestümpert. Aber bitte nicht gleich die Hände überm Kopf zusammenschlagen ... ich lerne die Sprache noch ;P und bin über hinweise Dankbar.

Das Buch das mich auf diese Idee gebracht hat, erwähnte einen solchen Algorithmus nur ganz beiläufig.

Ich habe bereits mehrere Varianten von Wegfindungsalgorithmen Programmiert. Alle haben Vor- und Nachteile! (Wie auch der Aktuelle!)

Dieser schein aber für mein Vorhaben am meisten geeignet zu sein. Leider habe ich dafür wie schon gesagt keine/kaum Informationen gefunden und habe das alles mit ein wenig gesunden Menschenverstand programmiert.

//******************CPUNKT******************************************************
class CPunkt
{
   public:
      int x,y;

      CPunkt() : x(0), y(0)
       {}
      CPunkt(const int &X) : x(X), y(X)
       {}
      CPunkt(const int &X, const int &Y) : x(X), y(Y)
       {}

      Zeichnen(TColor color)
         {
            Form1->Image1->Canvas->Pen->Color   = clWhite;
            Form1->Image1->Canvas->Brush->Color = color;
            Form1->Image1->Canvas->Ellipse(x-3, y-3, x+3, y+3);
         }
};

//******************CQUAD*******************************************************
class CQuad
{
   public:
      CQuad  *ChildrenQuads;
      CPunkt Position;
      int    points_in;

      CQuad()
       {
          points_in = 0;
       };

      InsertQuad(const CPunkt &P);
      DeleteQuad(const CPunkt &P);
      bool Search(const CPunkt &P);
};
      CQuad::InsertQuad(const CPunkt &P)
       {
          points_in++;
          if (ChildrenQuads)
           {
              if (P.y < Position.y)
               {
                  if (P.x < Position.x)
                     ChildrenQuads[0].InsertQuad(P);
                  else
                     ChildrenQuads[1].InsertQuad(P);
               }
              else
               {
                  if (P.x < Position.x)
                     ChildrenQuads[2].InsertQuad(P);
                  else
                     ChildrenQuads[3].InsertQuad(P);
               }
           }
       };

      CQuad::DeleteQuad(const CPunkt &P)
       {
          points_in--;
          if (ChildrenQuads)
           {
              if (P.y < Position.y)
               {
                  if (P.x < Position.x)
                     ChildrenQuads[0].DeleteQuad(P);
                  else
                     ChildrenQuads[1].DeleteQuad(P);
               }
              else
               {
                  if (P.x < Position.x)
                     ChildrenQuads[2].DeleteQuad(P);
                  else
                     ChildrenQuads[3].DeleteQuad(P);
               }
           }
       };

      bool CQuad::Search(const CPunkt &P)
       {
          if (ChildrenQuads && points_in)
           {
              if (P.y < Position.y)
               {
                  if (P.x < Position.x)
                     return ChildrenQuads[0].Search(P);
                  else
                     return ChildrenQuads[1].Search(P);
               }
              else
               {
                  if (P.x < Position.x)
                     return ChildrenQuads[2].Search(P);
                  else
                     return ChildrenQuads[3].Search(P);
               }

           }
          else
             return points_in>0?1:0;
       };

//******************CQUADTREE***************************************************
class CQuadTree
{
   private:
      unsigned int Width;
      CQuad Quad;

      CQuad BuildTree(const unsigned int &X, const unsigned int &Y, const unsigned int &W);
      DrawTree(const CQuad &Quad, const unsigned int &W);

   public:
      CQuadTree();
      ~CQuadTree();

      DrawTree() {Form1->Image1->Picture = NULL; DrawTree(Quad, Width);};
      Init(const unsigned int &X);
      InsertQuad(const CPunkt &P) {if (!Quad.Search(P)) Quad.InsertQuad(P);};
      DeleteQuad(const CPunkt &P) {if (Quad.Search(P)) Quad.DeleteQuad(P);};
      bool Search(const CPunkt &P) {return Quad.Search(P);};
};
   CQuadTree::CQuadTree()
    {};
   CQuadTree::~CQuadTree()
    {};

   CQuad CQuadTree::BuildTree(const unsigned int &X, const unsigned int &Y, const unsigned int &W)
    {
       CQuad new_Quad;
       new_Quad.points_in = 0;

       new_Quad.Position      = CPunkt(X - W/2, Y - W/2);
       new_Quad.ChildrenQuads = NULL;

       if (W > 0)
        {
           new_Quad.ChildrenQuads    = new CQuad[4];

           new_Quad.ChildrenQuads[0] = BuildTree(X - W/2, Y - W/2, W/2);
           new_Quad.ChildrenQuads[1] = BuildTree(X      , Y - W/2, W/2);
           new_Quad.ChildrenQuads[2] = BuildTree(X - W/2, Y,       W/2);
           new_Quad.ChildrenQuads[3] = BuildTree(X,       Y,       W/2);
        }
     return new_Quad;
    };

   CQuadTree::DrawTree(const CQuad &Quad, const unsigned int &W)
    {
       if (Quad.ChildrenQuads && Quad.points_in > 0)
        {
           Form1->Image1->Canvas->MoveTo(Quad.Position.x - W/2, Quad.Position.y - W/2);
           Form1->Image1->Canvas->LineTo(Quad.Position.x + W/2, Quad.Position.y - W/2);
           Form1->Image1->Canvas->LineTo(Quad.Position.x + W/2, Quad.Position.y + W/2);
           Form1->Image1->Canvas->LineTo(Quad.Position.x - W/2, Quad.Position.y + W/2);
           Form1->Image1->Canvas->LineTo(Quad.Position.x - W/2, Quad.Position.y - W/2);

           Form1->Image1->Canvas->MoveTo(Quad.Position.x, Quad.Position.y - W/2);
           Form1->Image1->Canvas->LineTo(Quad.Position.x, Quad.Position.y + W/2);

           Form1->Image1->Canvas->MoveTo(Quad.Position.x - W/2, Quad.Position.y);
           Form1->Image1->Canvas->LineTo(Quad.Position.x + W/2, Quad.Position.y);

           DrawTree(Quad.ChildrenQuads[0], W/2);
           DrawTree(Quad.ChildrenQuads[1], W/2);
           DrawTree(Quad.ChildrenQuads[2], W/2);
           DrawTree(Quad.ChildrenQuads[3], W/2);
        }
    };

   CQuadTree::Init(const unsigned int &X)
    {
       Width = X;
       Quad  = BuildTree(X, X, X);
    };

//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
CQuadTree Welt;
void __fastcall TForm1::FormKeyPress(TObject *Sender, char &Key)
{
 if (Key == 13)
    {
       Welt.Init(Image1->Width);
    }
 if (Key == 32)
    {

    }
}
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------

int Maus = 0;
void __fastcall TForm1::Image1MouseDown(TObject *Sender,
      TMouseButton Button, TShiftState Shift, int X, int Y)
{
   Maus = (Button == mbLeft)?1:2;
   Image1MouseMove(Sender, Shift, X, Y);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Image1MouseUp(TObject *Sender, TMouseButton Button,
      TShiftState Shift, int X, int Y)
{
   Maus = 0;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Image1MouseMove(TObject *Sender, TShiftState Shift,
      int X, int Y)
{
   if (X < 0) X=0;
   if (X >= Image1->Width) X = Image1->Width-1;
   if (Y < 0) Y=0;
   if (Y >= Image1->Height) Y = Image1->Height-1;

   Form1->Caption = IntToStr(X) + ":" + IntToStr(Y) + (Welt.Search(CPunkt(X, Y))?" - belegt":" - frei");

   if (Maus == 1)
      {
         Welt.InsertQuad(CPunkt(X, Y));
         Welt.DrawTree();
      }

   if (Maus == 2)
      {
         Welt.DeleteQuad(CPunkt(X, Y));
         Welt.DrawTree();
      }
}
//---------------------------------------------------------------------------

Wenn man nun noch einen Wegfindungsalgorithmus über die Mittelpunkte (=Position) eines jeden Vierecks laufen lässt, so müsste man einen recht kurzen Weg bekommen.

@Jester wie du richtig gesagt hast ... die Anzahl der Nachbarn hängt von dem Winkel ab, denn man erlaubt zu gehen

Grüße

rapso

T.Jay03 schrieb:

Ich möchte das für eine Wegfindung verwenden.

Grüße

fuer wegfindung benutzt man eher selten quadtrees, quadtrees werden eher dazu benutzt um im 2d-raum schnell ein query zu machen, so wie binaertrees in 1D (z.b. std::map) oder octrees in 3d.

fuer wegfindung eignen sich grids besser, weil du dann direct auf einen der 4 nachbaren zugreifen kannst. muestest du das durch einen quadtree machen, wuerdest du O(log n) and zeit brauchen statt O(1) wie beim Grid, und das ist eines der zeitkritischen dinge.

fuer einen guten algorithmus kannst du dir A* anschauen, ist z.b. bei wikipedia eklaert.

Kannst du mir bitte das mit den grids genauer erklären oder mir Links mitteilen, wo sowas erklärt wird. Vorzugsweise auf Deutsch.

Danke!

Jester

rapso schrieb:

muestest du das durch einen quadtree machen, wuerdest du O(log n) and zeit brauchen statt O(1) wie beim Grid

Man kann den Quadtree ohne weiteres so implementieren, dass die Nachbarn in O(1) gefunden werden können.

@Jester

Genau vor dem Problem stehe ich gerade.

Ich weiß nicht, wie ich feststellen kann, wieviele Nachbarn ein Quadrat hat.

Rein theoretisch könnten es doch unendlich viele sein, je feiner die Rasterung ist (Baumtiefe).

Oder sehe ich das flasch?

Jester

T.jay03: Du hast immer noch keine genaueren Angaben zur Problemstellung gemacht. Soweit ich es verstanden habe würde ich wie rapso einfach den A* empfehlen. Ich verstehe nicht wirklich wozu Du nen Quadtree haben willst.

Mein Hinweis war eher theoretischer Natur und hat nichts mit Deiner konkreten Aufgabenstellung (die ich ja nicht kenne) zu tun.

Man kann den A* auf ein gerastertes Gitter anwenden. Hierbei werden jedoch nur horizontale/vertikale/diagonale Zick-Zack Wege gefunden. Der 2. Nachteil ist, die extrem lange Rechenzeit. Durch einen QuadTree kann man dieses Feld ebenso Rastern und alle Bereiche indenen kein Hindernis ist, zu einem großen Feld zusammenfassen. Dies sollte doch die Rechenzeit reduzieren. Weiterhin erhoffe ich mir, dass zwar immernoch Zick-Zack Wege entstehen, jedoch diese natürlicher aussehen.

Jetzt habe ich 2 Ansätze. Ich gebe dem A* alle Mittelpunkte der im QuadTree befindlichen Quadrate. Nun muss ich allerdings Wissen, wieviele und welche Nachbarn jedes Quadrat hat. Dies könnte man vorberecnen und zusätzlich Zeit sparen.
Der 2. Ansatz: Ich kombiniere diesen QuadTree mit dem Sichtbarkeitsalgorithmus, was aber wie ich denke zu komplex werden würde.

Also nochmal ganz konkret:
Wie kann ich prüfen, welche und wieviele Nachbar Quadrate jedes Quadrat hat, damit ich dann z.B. den A damit füttern kann.*

Zwischen zwei benachbarten Quadraten muss immer eine direkte Verbindung existieren.

Ich hoffe das war verständlich

rapso

Jester schrieb:

rapso schrieb:

muestest du das durch einen quadtree machen, wuerdest du O(log n) and zeit brauchen statt O(1) wie beim Grid

Man kann den Quadtree ohne weiteres so implementieren, dass die Nachbarn in O(1) gefunden werden können.

ja, fuer den sonderfall das die unterste eben ein grid ist. das bringt's natuerlich dann einen quadtree drueber zu packen.

Jester

rapso schrieb:

ja, fuer den sonderfall das die unterste eben ein grid ist. das bringt's natuerlich dann einen quadtree drueber zu packen.

nein und ja.

Auch wenn in dem Grid einige Punkte fehlen geht das noch prima.

Den Quadtree drüberzupacken kann Sinn machen, wenn man erst ne grobe und anschließend ne feine Suche macht. Beispielsweise könnte man in nem Vorverarbeitungsschritt einige Quads gleich ganz rauswerfen für bestimmte Suchanfragen.

rapso

Jester schrieb:

Auch wenn in dem Grid einige Punkte fehlen geht das noch prima.

sobald punkte fehlen, musst du ueber die node darueber nehmen, oder noch eine darueber, aber um ueberhaupt festzustellen wie weit du runtergehen kannst bis keine nodes mehr da sind muesstest du von der root ausgehen.

somit hast du O(log n) sobald kein prefektes grid drunter liegt.

Den Quadtree drüberzupacken kann Sinn machen, wenn man erst ne grobe und anschließend ne feine Suche macht. Beispielsweise könnte man in nem Vorverarbeitungsschritt einige Quads gleich ganz rauswerfen für bestimmte Suchanfragen.

Dafuer benutzt man multi-resolution-grids (ist glaub ich in irgendeinem gem programming games zu beschrieben). hat viel weniger verwaltungsaufwand als ein tree.

Jester

rapso schrieb:

Jester schrieb:

Auch wenn in dem Grid einige Punkte fehlen geht das noch prima.

sobald punkte fehlen, musst du ueber die node darueber nehmen, oder noch eine darueber, aber um ueberhaupt festzustellen wie weit du runtergehen kannst bis keine nodes mehr da sind muesstest du von der root ausgehen.

somit hast du O(log n) sobald kein prefektes grid drunter liegt.

Ich erklär's einfach mal am 1D-Beispiel:

Du hast eine gerasterte Linie und einige Punkte fehlen. Die sortierste in nen (balancierten) binären Baum ein. Nun willste den Nachbarn eines gegebenen Punktes finden. Das kostet O(log n).

Führst Du aber gleichzeitig die Blätter geordnet in einer doppelt verketten Liste mit (das kann man beim Einfügen/Löschen miterledigen), dann kannste die Nachbarn in O(1) finden, indem Du Deiner Liste einfach nach links/rechts folgst.

Allerdings ist natürlich klar, dass im 2D-Fall logarithmisch viele Nachbarn haben kann. Die alle zu betrachten braucht also Zeit. Finden geht aber trotzdem schnell.

Jester schrieb:

Führst Du aber gleichzeitig die Blätter geordnet in einer doppelt verketten Liste mit (das kann man beim Einfügen/Löschen miterledigen), dann kannste die Nachbarn in O(1) finden, indem Du Deiner Liste einfach nach links/rechts folgst.

Wie ich schon sagte,

wenn die ganze unterste ebene vorhanden ist, hast du nicht mehr als ein sehr aufwendiges (multiresolution) grid.

wenn die unterste ebene nicht komplett vorhanden ist, kannst du nicht einfach einen nachbarn nehmen, da eine node dann mehrere nachbarn an einer seite haben kann

+---+++-+
|   +++ |
|   +++-+
|   | | |
+---+-+-+

wie findest du nun von der linken Node ausgehend in O(1) den richtigen rechten nachbarn?