QuadTree_Tips.lua 4.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145
  1. --构建四叉树
  2. ---@class quadTree
  3. QuadTree = class()
  4. function QuadTree:ctor(rect, max_objects, max_level, level)
  5. self._rect = rect
  6. self._max_objects = max_objects or 8
  7. self._max_level = max_level or 4
  8. self._level = level
  9. self._trees = {}
  10. self._objects = {}
  11. end
  12. --分裂树
  13. function QuadTree:SplitTree()
  14. local width = self._rect.width/2
  15. local height = self._rect.height/2
  16. local x = self._rect.x + width
  17. local y = self._rect.y + height
  18. local level = self._level + 1
  19. self._trees[1] = QuadTree({ x = x + width, y = y + height, width = width, height = height},self._max_objects,self._max_level,level)
  20. self._trees[2] = QuadTree({ x = x, y = y + height, width = width, height = height},self._max_objects,self._max_level,level)
  21. self._trees[3] = QuadTree({ x = x, y = y, width = width, height = height},self._max_objects,self._max_level,level)
  22. self._trees[4] = QuadTree({ x = x + width , y = y, width = width, height = height},self._max_objects,self._max_level,level)
  23. end
  24. --
  25. --- y—————————————————h
  26. --- | | |
  27. --- | 2 | 1 |
  28. --- | | |
  29. --- |————————————————
  30. --- | | |
  31. --- | 3 | 4 |
  32. --- | | |
  33. --- x—————————————————w
  34. ---
  35. --所属子树index
  36. function QuadTree:GetTreeIndexs(rect)
  37. local treeIndexs = {}
  38. local c_x = self._rect.x + self._rect.width/2
  39. local c_y = self._rect.y + self._rect.height/2
  40. local is_left = rect.x < c_x
  41. local is_top = rect.y > c_y
  42. local end_left = rect.x + rect.width < c_x
  43. local end_top = rect.y + rect.height > c_y
  44. --1
  45. if (is_top and not end_left) or (not is_left and end_top) then
  46. table.insert( treeIndexs,1)
  47. end
  48. --2
  49. if (is_top and end_left) or (is_left and end_top ) then
  50. table.insert( treeIndexs,2)
  51. end
  52. --3
  53. if (not is_top and end_left) or (is_left and not end_top) then
  54. table.insert( treeIndexs,3)
  55. end
  56. --4
  57. if (not is_top and not end_left) or (not is_left and not end_top) then
  58. table.insert( treeIndexs,4)
  59. end
  60. return treeIndexs
  61. end
  62. --插入
  63. function QuadTree:Insert(rect)
  64. if self._trees and next(self._trees) then
  65. local treeIndexs = self:GetTreeIndexs(rect)
  66. for k,index in ipairs(treeIndexs) do
  67. self._trees[index]:insert(rect)
  68. end
  69. return
  70. end
  71. table.insert( self._objects,rect)
  72. if #self._objects > self._max_objects and self._level <= self._max_level then
  73. if not (self._trees and next(self._trees)) then
  74. self:SplitTree()
  75. end
  76. for i,k in ipairs(self._objects) do
  77. local k_indexs = self:GetTreeIndexs(k)
  78. for _,index in ipairs(k_indexs) do
  79. self._trees[index]:insert(k)
  80. end
  81. end
  82. self._objects = {}
  83. end
  84. end
  85. --
  86. function QuadTree:HashCode(_object)
  87. local tag = _object.x..'_'.._object.y.."_".._object.width.."_".._object.height
  88. return tag
  89. end
  90. --列表相加 并且去重
  91. function QuadTree:TableAdd(table1, table2)
  92. local hashTags = {}
  93. local newTables = table1 or {}
  94. for _,value in ipairs(newTables) do
  95. hashTags[self:HashCode(value)] = true
  96. end
  97. if table2 and next(table2) then
  98. for _,value in ipairs(table2) do
  99. local hashtag = self:HashCode(value)
  100. if not hashTags[hashtag] then
  101. hashTags[hashtag] = true
  102. table.insert( newTables,value)
  103. end
  104. end
  105. end
  106. return newTables
  107. end
  108. --取回同一组object
  109. function QuadTree:Retrieve(rect)
  110. local newObjects = self._objects
  111. if self._trees and next(self._trees) then
  112. local treeIndexs = self:GetTreeIndexs(rect)
  113. for _,index in ipairs(treeIndexs) do
  114. newObjects = self:TableAdd(newObjects,self._trees[index]:retrieve(rect))
  115. end
  116. end
  117. return newObjects
  118. end
  119. function QuadTree:clearTree()
  120. self._objects = {}
  121. for _,tree in pairs(self._trees) do
  122. tree:clearTree()
  123. end
  124. end
  125. function QuadTree:dumpTree()
  126. sys.log("[quadTree]-level="..self._level)
  127. if self._objects and next(self._objects) then
  128. sys.log("[quadTree]-objects:")
  129. sys.dump(self._objects)
  130. end
  131. for index,child_tree in pairs(self._trees) do
  132. sys.log("[quadTree]-index="..index)
  133. child_tree:dumpTree()
  134. end
  135. end