{{notification.text}}

MirGames

eXAAAXe
28.03.11 03:25
0
Всем привет!

Подскажите нубу как сделать QuadTree?
Теорию читал, в целом понял, но как реализовать - нет. :unsure:

Только сделал функцию, которая прямоугольник (Он же квад, да?)
делит на 4 части:

Код

type
  TQuad  = TRect;
  TQuad4 = array [0..3] of TQuad;

function QuadSub(Quad: TQuad): TQuad4;
var
  i           : byte;
  HalfW, HalfH: LongWord;
begin
  with Quad do
  begin
    HalfW:= ((Right  - Left) div 2);
    HalfH:= ((Bottom - Top)  div 2);

    SetRect(Result[0], Left, Top, Left + HalfW, Top + HalfH);
    SetRect(Result[1], Left, Top, Left + HalfW, Top + HalfH);
    SetRect(Result[2], Left, Top, Left + HalfW, Top + HalfH);
    SetRect(Result[3], Left, Top, Left + HalfW, Top + HalfH);

    OffSetRect(Result[0], 0,     0);
    OffSetRect(Result[1], HalfW, 0);
    OffSetRect(Result[2], HalfW, HalfH);
    OffSetRect(Result[3], 0,     HalfH);
  end;
end;


#1
28.03.11 16:06
0
Я делал класс ноды дерева:

Код

AQuadNode = class
   public
    Coord: TRectf;

    ChildType: TQNodeChild;
    // Branch
    Child: array [NS, WE] of AQuadNode;
    // Leaf
    Item: array [1 .. MaxP] of AObject;
    ItemCount: Integer;

    Parent: AQuadNode;
    constructor Plant(X, Y, Width, Height: Integer); overload;
    constructor Create(Parent: AQuadNode; NS: NS; WE: WE); overload;
    procedure Divide;
    procedure UnDivide;
    procedure AddItem(Appended: AObject; Node: PQuadNode);
    procedure RemoveItem(Removed: AObject);
    procedure Recalc;
    procedure Draw(Render: IRender2D);
  end;

constructor AQuadNode.Plant(X, Y, Width, Height: Integer);
begin
  Self.Coord.X := X;
  Self.Coord.Y := Y;
  Self.Coord.Width := Width;
  Self.Coord.Height := Height;
  Self.ChildType := Leaf;
end;

procedure AQuadNode.Divide;
var
  NS: North .. South;
  WE: West .. East;
begin
  for NS := North to South do
    for WE := West to East do
      Self.Child[NS, WE] := AQuadNode.Create(Self, NS, WE);
  Self.ChildType := Branch;
end;

constructor AQuadNode.Create(Parent: AQuadNode; NS: NS; WE: WE);
begin
  case NS of
    North:
      Self.Coord.Y := Parent.Coord.Y;
    South:
      Self.Coord.Y := Parent.Coord.Y + (Parent.Coord.Height / 2);
  end;
  case WE of
    West:
      Self.Coord.X := Parent.Coord.X;
    East:
      Self.Coord.X := Parent.Coord.X + (Parent.Coord.Width / 2);
  end;
  Self.Coord.Width := Parent.Coord.Width / 2;
  Self.Coord.Height := Parent.Coord.Height / 2;
  Self.Parent := Parent;
  Self.ChildType := Leaf;
end;

procedure AQuadNode.AddItem(Appended: AObject; Node: PQuadNode);
var
  NS: North .. South;
  WE: West .. East;
  I: Integer;
procedure Distribute;
var
  NS: North .. South;
  WE: West .. East;
begin
  for NS := North to South do
    for WE := West to East do
    begin
      if Lies(Appended, Self.Child[NS, WE]) then
      begin
        Self.Child[NS, WE].AddItem(Appended,@Self.Child[NS, WE]);
      end;
    end;
end;
begin
  New(Appended.Parent);
  if Self.ChildType = Leaf then
  begin
    if Self.ItemCount < MaxP then
    begin
      if Lies(Appended, Self) then
      begin
        for I := 1 to MaxP do
        begin
          if Self.Item[i] = nil then
          begin
            Inc(Self.ItemCount);
            Self.Item[i] := Appended;
            Appended.Parent := Node;
          end;
        end;
      end
      else
      begin
        Appended.Pos := MakeVector(0,0,0);
        Self.AddItem(Appended,@Self);
      end;
    end
    else
    begin
      Self.Divide;
      for NS := North to South do
        for WE := West to East do
          for I := 1 to MaxP do
            if Self.Item[i] <> nil then
              if Lies(Self.Item[i],Self.Child[NS,WE]) then
              begin
                Self.Child[NS,WE].AddItem(Self.Item[i],@Self.Child[NS,WE]);
                Self.Child[NS,WE].RemoveItem(Self.Item[i]);
              end;
      Distribute;
    end;
  end
  else
    Distribute;
end;

procedure AQuadNode.Recalc;
var
NS : North..South;
WE : West..East;
I : Integer;
Count : Integer;
begin
  if Self.ChildType = Leaf then
  begin
    if Self.ItemCount > MaxP then
    begin
      Self.Divide;
      for NS := North to South do
        for WE := West to East do
          for I := 1 to MaxP do
            if Self.Item[i] <> nil then
              if Lies(Self.Item[i],Self.Child[NS,WE]) then
              begin
                Self.Child[NS,WE].AddItem(Self.Item[i],@Self.Child[NS,WE]);
                Self.Child[NS,WE].RemoveItem(Self.Item[i]);
              end;
    end;
  end
  else
  begin
    for NS := North to South do
      for WE := West to East do
        Inc(Count,Self.Child[NS,WE].ItemCount);
    if Count < MaxP then
      UnDivide;
  end;
end;

procedure AQuadNode.RemoveItem(Removed: AObject);
var
I : Integer;
Parent: PQuadNode;
begin
  Parent := Removed.Parent;
  for I := 1 to MaxP do
    if Parent.Item[i] = Removed then
    begin
      Parent^.Item[i] := nil;
      Dec(Parent^.ItemCount);
      Parent.Parent.Recalc;
    end;
end;

procedure AQuadNode.UnDivide;
var
NS : North..South;
WE : West..East;
i : Integer;
begin
  for NS := North to South do
    for WE := West to East do
    begin
      for I := 1 to MaxP do
        if Self.Child[NS,WE].Item[i] <> nil then
        begin
          Self.AddItem(Self.Child[NS,WE].Item[i],@Self);
          Self.Child[NS,WE].Item[i] := nil;
          Dec(Self.Child[NS,WE].ItemCount);
        end;
      Self.Child[NS,WE] := nil;
    end;
end;


Вот... но!
по-моему я там чёто не доделал. Так что не копируй это ни в коем случае. (Я вроде с указателями напутал, а с ними потом хрен чё разберёшь).

Ну и пользуясь случаем задам вопрос более опытным представителям форума.
Что я тут не так сделал :blush:
#2
eXAAAXe
01.04.11 01:22
0
ПРОСЬБА ОТВЕТИТЬ! СРОЧНО!

QuadTree мне нужен для 2Д игры, а не для 3Д. Заметьте.

Просьба объяснить следующее:
1) Допустим в списке ObjRects: TList хранятся все TRectы объектов на карте.
Как их добавлять в QuadTree?
2) Понимаю, что не хочется Вам копаться в говнокоде, тогда
может быть кратно покажите алгоритм?

Пока так:

Код

type
  TQuad     = TRect;
  TQuad4    = array [0..3] of TQuad;
  
  TQuadNode = class
    destructor Destroy; override;
  private
    FQuad  : TQuad;
    FChilds: array [0..3] of TQuadNode;
  public
    procedure Sub;
  end;

  TQuadTree = class
    constructor Create;
    destructor  Destroy; override;
  private
    FNodes   : TList;            // Список всех нодов.
    FRootNode: TQuadNode;        // Корневой, самый большой нод.
  public
    procedure Init(Quad: TQuad); // Размеры игрового поля.
  end;

var
  QuadTree: TQuadTree;


{ TQuadNode }

destructor TQuadNode.Destroy;
var
  i: byte;
begin
  inherited;
  For i:= 0 to 3 do
    FChilds[i].Free;
  inherited;
end;

procedure TQuadNode.Sub;

  function QuadDiv4: TQuad4; // Делит квад на 4 суб-квада.
  var
    i           : byte;
    HalfW, HalfH: LongWord;
  begin
    with FQuad do
    begin
      HalfW:= ((Right  - Left) div 2);
      HalfH:= ((Bottom - Top)  div 2);

      SetRect(Result[0], Left, Top, Left + HalfW, Top + HalfH);
      SetRect(Result[1], Left, Top, Left + HalfW, Top + HalfH);
      SetRect(Result[2], Left, Top, Left + HalfW, Top + HalfH);
      SetRect(Result[3], Left, Top, Left + HalfW, Top + HalfH);

      OffSetRect(Result[0], 0,     0);
      OffSetRect(Result[1], HalfW, 0);
      OffSetRect(Result[2], HalfW, HalfH);
      OffSetRect(Result[3], 0,     HalfH);
    end;
  end;

var
  i    : byte;
  Quad4: TQuad4;
begin
  Quad4:= QuadDiv4;
  For i:= 0 to 3 do // Создаем 4 дочерних нода.
  begin
    FChilds[i]:= TQuadNode.Create;
    FChilds[i].FQuad:= Quad4[i];

    QuadTree.FNodes.Add(FChilds[i]); // Добавляем нод в октри.
  end;
end;


{ TQuadTree }

constructor TQuadTree.Create;
begin
  inherited;
  FNodes   := TList.Create;
  FRootNode:= TQuadNode.Create;
end;

destructor TQuadTree.Destroy;
begin
  FRootNode.Free;
  FNodes.Free;
  inherited;
end;

procedure TQuadTree.Init(Quad: TQuad);
begin
  FRootNode.FQuad:= Quad;
  FRootNode.Sub;          // Делим на четыре.
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
  QuadTree:= TQuadTree.Create;
  QuadTree.Init(Rect(0, 0, 800, 600));
end;

procedure TForm1.FormDestroy(Sender: TObject);
begin
  QuadTree.Free;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  i: byte;
begin
  For i:= 0 to 3 do       // Отрисовываем дочерние ноды корневого нода.
  with QuadTree.FRootNode do
  begin
    Canvas.Rectangle(FChilds[i].FQuad);

  end;
end;





#3
01.04.11 02:37
0
Ну во-первых забудь про списки и динамические массивы. То есть если конкретнее я не понял зачем тебе в структуре TQuadTree поле FNodes.
Из моего "примера" (стыдно мне за тот код :blush: ) ты не взял то, что нод может быть листом (то есть его потомки - точки или объекты, смотря что ты там хранишь), а может быть веткой (где у него не будет дочерних объектов, а будут 4 дочерние ноды).

Теперь по вопросам:
1) ИМХО сразу пиши объекты в дерево и не заморачивайся со списками. А как добавить? Так в чём собственно вопрос? Кидаешь создаваемый объект в корень дерева, а там процедура AddItem или AddObject (не важно) проверяет последовательно в какой ноде относительно центра находится объект. Потом проверяет на заполненность "слоты" ноды, проверяет лист ли нода или ветвь... блин в примере же всё это есть. Я конечно понимаю, что копаться в чужом коде сущий ад, но вряд ли кто тут выложит готовую реализацию, по всем параметрам подходящую под твою задачу...
2) Это не вопрос

Пост не претендует на нобелевку, так что прошу не пинать
Отредактировано: 01.04.11 03:43
#4
eXAAAXe
01.04.11 03:46
0
2 mgames

> То есть если конкретнее я не понял зачем тебе в структуре TQuadTree поле FNodes.
Просто так сделал, на всякий.

> з моего "примера" (стыдно мне за тот код blush.gif ) ты не взял то
Из твоего примера я ничего и брал аще то.

> нод может быть листом (то есть его потомки - точки или объекты, смотря что ты там хранишь), а может быть веткой (где у него не будет дочерних объектов, а будут 4 дочерние ноды).
Да без разницы, пусть пока так, все потенциальные ветки.
Ты перепутал ветки с листиками, кстати.

> Кидаешь создаваемый объект в корень дерева
Как это?
К примеру есть 2 объекта (R1, R2: TRect);
И что с ними делать?

[code]
QuadTree.Init(R1);
QuadTree.Init(R2);
[code]

Так что ли?

> 2) Это не вопрос
Почему не вопрос?
Эту ветку просматривают, но не отвечают почему-то.
Наверно думают, что я требую от них кода, поэтому пусть
направят на верный путь.
К тому же сам алгоритм QuadTree не особо понял из английской Википедии.


#5
eXAAAXe
01.04.11 03:50
0
2 mgames

Кстати, ты делаешь QuadTree для 3D? (Слышал так делают)
Лично мне он нужен ТОЛЬКО для 2D.
#6
MirGames Dev
01.04.11 05:06
0
Цитата
Как их добавлять в QuadTree?
Ну как бы находишь подходящий листок и добавляешь.

Грубо говоря, предположим, что мы не создаём ноды динамически, и дерево мапится строго на определенную площадь, т.е. у нас целиком инициализировано дерево некоторой глубины. При добавлении объекта идём из корня, определяя, в какой из нод попадает наш объект. Добираемся до листьев - и добавляем объект в список объектов этого листа.

При необходимости получения списка объектов на некоторой площади - опять-таки идём из корня и постепенно определяем все ноды, попадающие в эту площадь. Т.е. если нода попадает целиком, то глубже не идём.

Достаточно простой механизм, который можно изменять под свои нужды. Например, сделать таблицу соответствий между нодой и объектом, чтобы зная объект можно было быстро определить его ноду.
#7
01.04.11 18:14
0
eXAAAXe
Цитата

QuadTree.Init(R1);
QuadTree.Init(R2);

Так что ли?


Я так понял, что процедура Init вызывается 1 раз для "посадки" дерева, задания его размеров. Так?
Тогда для добавления объекта в ноду должна быть ещё одна процедура для добавления, только в классе TQuadNode. Примерно так:

Код
procedure TQuadNode.Add(Что добавляем: TRect);
var
i : Integer;
СЮ : Север .. Юг;
ЗВ : Запад .. Восток;
begin
  Если Self.Тип_Ноды = Лист тогда
  begin
    Если Self.Количество дочерних объектов < максимально допустимого тогда
    begin
      for i:=1 to максимально допустимое количество объектов в ноде do
        Если Self.Массив дочерних объектов[i] = пусто тогда
          Self.Массив дочерних объектов[i] := Что добавляем;
          Inc(Self.Количество дочерних объектов);
    end
    иначе
    begin
      Self.Поделить на 4 дочерние ноды;
      for СЮ := Север to Юг do
        for ЗВ := Запад to Восток do
          for i := 1 to максимально допустимое количество объектов в ноде do
            Если Self.Массив дочерних объектов[i] <> пусто тогда
              Если Self.Массив дочерних объектов[i] находится в Self.Дочерняя нода[СЮ, ЗВ] тогда
                Self.Дочерняя нода[СЮ, ЗВ].Add(Self.Массив дочерних объектов[i]);
                Self.Массив дочерних объектов[i] := пусто;
                Dec(Self.Количество дочерних объектов);
                // Это мы распределили объекты ноды по дочерним.
      for СЮ := Север to Юг do
        for ЗВ := Запад to Восток do
          Если Что добавляем находится в Self.Дочерняя нода[СЮ, ЗВ] тогда
            Self.Дочерняя нода[СЮ, ЗВ].Add(Что добавляем);
    end;
  end
  иначе
    for СЮ := Север to Юг do
      for ЗВ := Запад to Восток do
        Если Что добавляем находится в Self.Дочерняя нода[СЮ, ЗВ] тогда
          Self.Дочерняя нода[СЮ, ЗВ].Add(Что добавляем);
end;

Так понятно?

Процедура Поделить на 4 дочерние ноды предполагает не только создание дочерних нод, но и изменение типа главной ноды с листа, на ветку. Ну и нужно написать процедуру, проверяющую находится ли объект в ноде.
Если задуматься, построение квадродерева задача довольно тривиальная...
#8
eXAAAXe
03.04.11 04:54
0
>>> Я так понял, что процедура Init вызывается 1 раз для "посадки" дерева, задания его размеров. Так?
Да.
Про Init я по глупости написал.

>>> Если задуматься, построение квадродерева задача довольно тривиальная...
Ну не знаю, что-то я понять не могу ни как.

>>> При добавлении объекта идём из корня, определяя, в какой из нод попадает наш объект. Добираемся до листьев - и добавляем объект в список объектов этого листа.
Как определить попадает или нет?
К примеру добавляем квад, начиная с корня определяем куда попадает.
Но он попадает полностью в корневой нод! На этом рекурсия прекращается.
Бле*ть, понять не могу. :(



Что значит: "Юг, Восток и проч."?

Пока код такой:

Код

type
  TQuadNode = class
    constructor Create;
    destructor  Destroy; override;
  private
    FQuad : TRect;
    FObjs : TList;                     // Список Rect'ов данного нода.
    FIsSub: boolean;                   // Есть ли суб-ноды.
    FSubs : array [0..3] of TQuadNode;
  public
    procedure Sub;
    procedure Add(Quad: TRect);
  end;

  TQuadTree = class
    constructor Create;
    destructor  Destroy; override;
  private
    FRootNode: TQuadNode;              // Корневой, самый большой нод.
  public
    procedure Init(RootQuad: TRect);   // Размеры игрового поля.
    procedure Add(Quad: TRect);
  end;

var
  QuadTree: TQuadTree;


{ TQuadNode }

constructor TQuadNode.Create;
begin
  inherited;
  FObjs:= TList.Create;
end;

destructor TQuadNode.Destroy;
var
  i: byte;
begin
  inherited;
  If FIsSub then
  For i:= 0 to 3 do
    FSubs[i].Free;

  FObjs.Free;
  inherited;
end;

procedure TQuadNode.Sub;
var
  i           : byte;
  HalfW, HalfH: LongWord;
begin
  FIsSub:= True;
  HalfW:= ((FQuad.Right  - FQuad.Left) div 2);
  HalfH:= ((FQuad.Bottom - FQuad.Top)  div 2);

  For i:= 0 to 3 do // Создаем 4 дочерних нода.
  begin
    FSubs[i]:= TQuadNode.Create;
    With FSubs[i], FQuad do
    begin
      SetRect(FQuad, Left, Top, Left + HalfW, Top + HalfH);
      Case i of
        0: OffSetRect(FQuad, 0,     0);
        1: OffSetRect(FQuad, HalfW, 0);
        2: OffSetRect(FQuad, HalfW, HalfH);
        3: OffSetRect(FQuad, 0,     HalfH);
      end;
    end;
  end;
end;

procedure TQuadNode.Add(Quad: TRect);
var
  i: byte;
  R: TRect;
begin
  If FIsSub then
  For i:= 0 to 3 do
    If InterSectRect(R, Quad, FSubs[i].FQuad) then
    begin
      FSubs[i].Add(Quad); // Типа рекурсия. (?)
      // FObjs.Add(@Quad);
      Exit;
    end;
end;

{ TQuadTree }

constructor TQuadTree.Create;
begin
  inherited;
  FRootNode:= TQuadNode.Create;
end;

destructor TQuadTree.Destroy;
begin
  FRootNode.Free;
  inherited;
end;

procedure TQuadTree.Init(RootQuad: TRect);
begin
  FRootNode.FQuad:= RootQuad;
  FRootNode.Sub;
end;

procedure TQuadTree.Add(Quad: TRect);   // Добавляем объект в QuadTree.
begin
  FRootNode.Add(Quad);
end;

var
  R1, R2: TRect;

procedure TForm1.FormCreate(Sender: TObject);
begin
  QuadTree:= TQuadTree.Create;
  QuadTree.Init(Rect(100, 100, 800, 600)); // Размеры игрового поля. (880 x 600)

  SetRect(R1, 10,   10, 90, 130);          // Позиции 2-х объектов.
  SetRect(R2, 100, 200, 70, 150);

  QuadTree.Add(R1);
  QuadTree.Add(R2);
end;



#9
03.04.11 21:50
0
Код
Но он попадает полностью в корневой нод! На этом рекурсия прекращается.


Если объект один, то мы действительно не делим корневой нод, но использование деревьев имеет смысл только тогда, когда не приемлем по причине низкой производительности метод "каждый с каждым".
В случае, если объектов много и их количество превышает максимально допустимое количество объектов в ноде, начинается деление.

Изображение

Север, юг итд это положение дочерний ноды, относительно центра родительской. То есть верхняя-левая это северо-западная, нижняя-правая - юго-восточная.
#{{post.Index}}
{{post.Author.Login}}
{{post.CreatedDate | date:'dd.MM.yy HH:mm'}}
{{post.VotesRating}}
Отредактировано: {{post.UpdatedDate | date:'dd.MM.yy HH:mm'}}