Quadtree In Game
- 2. Agenda ? History ? Definitions QuadTree ? Types QuadTree ? Intention QuadTree ? Using QuadTree ? Implementation of the operations ? Example
- 3. Agenda ? History ? Definitions QuadTree ? Types QuadTree ? Intention QuadTree ? Using QuadTree ? Implementation of the operations ? Example
- 4. History ? Quadtree was named by Raphael Finkel and J.L. Bentley in 1974. "Quad Trees: A Data Structure for Retrieval on Composite Keys".
- 5. Agenda ? History ? Definitions QuadTree ? Types QuadTree ? Intention QuadTree ? Using QuadTree ? Implementation of the operations ? Example
- 6. Definitions QuadTree ? L¨¤ c?u tr¨²c c?y d¨´ng l?u tr? c¨¢c kh¨®a tr¨ºn mi?n kh?ng gian.Th??ng d¨´ng cho kh?ng gian 2 chi?u ho?c 3 chi?u (oct-trees). ? Ph?n chia kh?ng gian th¨¤nh 4 ch? nh?t(ho?c vu?ng) kh?ng giao nhau (T?ng qu¨¢t: ph?n chia th¨¤nh 2d mi?n trong kh?ng gian d chi?u). ? C¨¢c d?ng c? th? qu? quad tree d¨´ng cho t?ng lo?i d? li?u c? th?: ?i?m, ???ng th?ng (???ng cong, g?p kh¨²c)
- 7. Agenda ? History ? Definitions QuadTree ? Types QuadTree ? Intention QuadTree ? Using QuadTree ? Implementation of the operations ? Example
- 8. Types QuadTree ? Point QuadTree ? D?ng c?y t¨¬m ki?m nh? ph?n ? H¨¬nh d?ng c?a c?y ph? thu?c v¨¤o th? t? ch¨¨n
- 9. Types QuadTree ? Point Region ( PR ) QuadTree ?D? li?u l¨¤ ?i?m, ???c l?u tr? ? node l¨¢. ?Node trong c¨® 4 node con. ?Trong qu¨¢ tr¨¬nh th¨ºm, n?u g?p node l¨¢ ?ang l?u d? li?u kh¨¢c node hi?n t?i ta t?o th¨ºm 1 node trong v¨¤ th¨ºm 2 d? li?u n¨¤y v¨¤o
- 10. Agenda ? History ? Definitions QuadTree ? Types QuadTree ? Intention QuadTree ? Using QuadTree ? Implementation of the operations ? Example
- 11. Intention QuadTree ? Quadtree d¨´ng ?? qu?n l? to¨¤n b? c¨¢c ??i t??ng c?a b?n trong game, gi¨²p cho vi?c x? l? va ch?m ???c ch¨ªnh x¨¢c v¨¤ hi?u qu? h?n. ? Quadtree gi¨²p gi?m thi?u s? l?n x¨¦t va ch?m gi?a c¨¢c ??i t??ng, gi¨²p t?ng t?c ?? x? l? c?a m?i chu tr¨¬nh game ? Quadtree gi¨²p b?n nhanh ch¨®ng x¨¢c ??nh ???c nh?ng ??i t??ng n¨¤o c¨® kh? n?ng x?y ra va ch?m, t? ?¨® s? d?ng c¨¢c thu?t to¨¢n x? l? va ch?m cho ch¨²ng.
- 12. Agenda ? History ? Definitions QuadTree ? Types QuadTree ? Intention QuadTree ? Using QuadTree ? Implementation of the operations ? Example
- 13. Using QuadTree ? T?i m?i chu k? c?a game, v?i m?i ??i t??ng c?n x? l? va ch?m, ta ki?m tra Quadtree xem nh?ng ??i t??ng n¨¤o c¨® th? x?y ra va ch?m v?i n¨®, t? ?¨® s? ti?n h¨¤nh c¨¢c thu?t to¨¢n ki?m tra va ch?m ph?c t?p h?n ??i v?i c¨¢c ??i t??ng n¨¤y.
- 14. Using QuadTree ? V?i m?i node trong Quadtree, node s? ti?p t?c ???c chia nh? cho ??n khi kh?ng qu¨¢ n ??i t??ng ch?a b¨ºn trong node ?¨®, ho?c chi?u c?y ??t ??n m?t gi?i h?n n¨¤o ?¨®. ? Trong ?¨® n th??ng nh?, 1 ho?c 2. ? Khi m?t node ti?p t?c b? chia nh?, n¨® ???c chia th¨¤nh 4 h¨¬nh ch? nh?t. ??ng th?i, c¨¢c ??i t??ng thu?c node m¨¤ thu?c m?t trong 4 h¨¬nh ch? nh?t con ?¨® s? ???c chuy?n xu?ng node con t??ng ?ng c?a node hi?n t?i
- 15. Using QuadTree ??i t??ng m¨¤u ?? s? n?m tr¨ºn 1 trong 4 node ? m?c 2 c?a QuadTree. ( th?c t? v?i tr??ng h?p n¨¤y, ta ch? c?n l?u ??i t??ng ? node m?c 1, v¨¤ ch? chia l?i Quadtree sau khi c¨® c¨¢c ??i t??ng kh¨¢c ???c th¨ºm v¨¤o)
- 16. Using QuadTree ??i t??ng s? n?m ? node g?c, v¨¬ n¨® kh?ng n?m trong b?t k? h¨¬nh ch? nh?t con n¨¤o.
- 17. Using QuadTree - 2 ??i t??ng tr¨ºn n¨¤y s? n?m ? m?c 2 c?a QuadTree, v¨¬ m?i ??i t??ng n?m tr¨ºn 1 node ri¨ºng bi?t, ta kh?ng c?n ph?n chia th¨ºm n?a.
- 18. Using QuadTree 3 ??i t??ng nh? h¨¬nh b¨ºn tr¨¢i s? ???c ??a v¨¤o Quadtree. H¨¬nh ch? nh?t g¨®c tr¨ºn b¨ºn tr¨¢i c¨® 2 ??i t??ng n¨ºn h¨¬nh ch? nh?t n¨¤y s? ???c chia nh? th¨ºm 1 l?n n?a. (??i v?i Quadtree ch?a t?i ?a 1 ??i t??ng trong 1 ?)
- 19. Agenda ? History ? Definitions QuadTree ? Types QuadTree ? Intention QuadTree ? Using QuadTree ? Implementation of the operations ? Example
- 20. Implementation of the operations 1. Insert an object into the quadtree: Check if the object intersects the current node. If so, recurse. If you've reached the leaf level, insert the object into the collection. 2. Delete an object from the quadtree: Execute the exact same steps as if inserting the object, but when you've reached the leaf level delete it from the collection. 3. Test if an object intersects any object inside the quadtree: Execute the exact same steps as if inserting the object, but when you've reached the leaf level check for collision with all the objects in the collection. 4. Test for all collisions between all objects inside the quadtree: For every object in the quadtree execute the single object collision test. 5. Update the quadtree: Delete all objects from the quadtree whose position has been modified and insert them again.
- 21. Agenda ? History ? Definitions QuadTree ? Types QuadTree ? Intention QuadTree ? Using QuadTree ? Implementation of the operations ? Example
- 22. Example X¨¦t v¨ª d? nh? h¨¬nh d??i. Ta c?n ki?m tra va ch?m c?a h¨¬nh ch? nh?t m¨¤u xanh v?i c¨¢c ??i t??ng m¨¤u ??.
- 23. Example 1. H¨¬nh ch? nh?t xanh va ch?m v?i h¨¬nh ch? nh?t v¨¤ng l?n( node m?c 1), nh?ng kh?ng c¨® ??i t??ng n¨¤o ? m?c 1 2. H¨¬nh ch? nh?t xanh va ch?m v?i 2 h¨¬nh ch? nh?t v¨¤ng nh? ? m?c 2 (2 node ? m?c 2): C?ng kh?ng c¨® ??i t??ng n¨¤o. Ta ti?p t?c ki?m tra c¨¢c node con. 3. H¨¬nh ch? nh?t xanh va ch?m v?i 4 h¨¬nh ch? nh?t v¨¤ng nh? ? m?c 3 (4 node ? m?c 3): c¨® 1 ??i t??ng, ta ??a ??i t??ng v¨¤o danh s¨¢ch tr? v? (danh s¨¢ch c¨¢c ??i t??ng c¨® x?y ra va ch?m v?i h¨¬nh ch? nh?t xanh) 4. H¨¬nh ch? nh?t xanh va ch?m v?i 4 h¨¬nh ch? nh?t v¨¤ng nh? ? m?c 4 (6 node ? m?c 4): c¨® 1 ??i t??ng, ta ??a ??i t??ng v¨¤o danh s¨¢ch tr? v?.