şükela:  tümü | bugün
  • octree'nin iki boyutlu analogu.
  • binary tree nin 2 boyutlu verilere uyarlanmış hali. binary tree de sağ ya da sol dallar varken, quadtree de sol üst, sağ üst, sol alt ve sağ alt olmak üzere 4 dal vardır.

    yardım isteyen yeşillendirsin veya:

    yazilim.odevi@gmail.com
  • diyelim ki kuşbakışı kameralı 2d shooter bir oyun yaptınız. ortamda 1000 tane düşman hareket ediyor. bizim karakterimiz ateş ettiğinde çıkan mermi hangisini vurmuş olacak? 1000 tane düşmanla tek tek collision detection mı yapacaksınız?

    burada yardımımıza quadtree koşar. önce düşmanlarımızı quadtree içine güzelce dizeriz, oyun ilerledikçe bunların quadtree konumlarını da güncelleriz, karakterimiz ateş ettiğinde ise yalnızca bu ağaç yapısının ilgili dallarındaki düşmanlarla collision check yaparız. böylece 1000 adet coll. dtc. yerine 3-5 coll. dtc. ile paçayı yırtarız.

    tabi bu quadtree ile ortamı bölümleme, oyunun diğer parçalarını hesaplarken de işe yarayacaktır, sadece karakterin ateş ettiği merminin hedefini bulmada değil.

    bir yerlerden daş yuvarlanıyor olabilir mesela. veya ortamdaki savaş "karakter vs the world" değildir de, "karakter vs faction 1 vs faction 2" şeklinde dönüyor olabilir falan.

    velhasıl özetle, ortamda n adet irili ufaklı cisim hareket ediyorsa ve bunların birbiriyle olan çarpımaları hesaplanacaksa, quadtree sayesinde karmaşıklığı n^2 mertebelerinden daha aşağı çekebilirsiniz.

    güzeldir quadtree.