WEBVTT 1 00:00:06.379 --> 00:00:09.963 Game Basic Understanding of Partial Partitioning Algorithm: Quadtree and Octree 2 00:00:27.431 --> 00:00:28.965 Hello everyone 3 00:00:28.965 --> 00:00:31.272 This is Lee Deukwoo from game algorithm 4 00:00:31.272 --> 00:00:35.649 In this lesson, we will talk about factors used for game optimization 5 00:00:35.649 --> 00:00:39.579 which are called quadtree and octree 6 00:00:39.579 --> 00:00:42.609 This spatial partitioning algorithm quadtree lecture 7 00:00:42.609 --> 00:00:45.936 introduces the overview of quadtree and how it works 8 00:00:45.936 --> 00:00:48.678 Let's find out ways to implement quadtree 9 00:00:49.094 --> 00:00:52.985 Overview of Quadtree and How It Works 10 00:00:53.480 --> 00:00:56.050 First, I will introduce the overview of quadtree 11 00:00:56.050 --> 00:00:58.500 and how the operation works 12 00:01:00.193 --> 00:01:03.252 Quadtree isn't a algorithm but instead 13 00:01:03.252 --> 00:01:06.704 a word that describes a general 14 00:01:06.704 --> 00:01:09.569 tree structured data structure with four children 15 00:01:09.569 --> 00:01:13.233 This term of quadtree started in 1974 16 00:01:13.233 --> 00:01:17.140 from a thesis of Raphael Finkel and Jon Louis Bentley 17 00:01:17.140 --> 00:01:19.332 It was first used in the thesis 18 00:01:19.332 --> 00:01:22.961 As you can see from the picture, a quadtree is 19 00:01:22.961 --> 00:01:25.421 always filled up with 4 children 20 00:01:25.421 --> 00:01:28.084 it is a complete form of a tree 21 00:01:30.500 --> 00:01:32.460 This quadtree data structure is 22 00:01:32.460 --> 00:01:37.807 used to divided a 2D plane efficiently 23 00:01:37.807 --> 00:01:41.766 depending on the usage, point quadtree and range quadtree are 24 00:01:41.766 --> 00:01:44.708 the two ways that it can be divided into 25 00:01:44.708 --> 00:01:48.251 Point quadtree is used to control the point data in a plane 26 00:01:48.251 --> 00:01:51.807 through a efficient method 27 00:01:51.807 --> 00:01:53.954 In the early stages of quadtree 28 00:01:53.954 --> 00:01:56.926 there were mostly point quadtree types 29 00:01:56.926 --> 00:01:59.463 It was commonly used to manage information about the location on the map 30 00:01:59.463 --> 00:02:02.876 through an effective way 31 00:02:02.876 --> 00:02:06.233 The closest neighbor from the current location or 32 00:02:06.233 --> 00:02:09.470 Searching for neighbors that are located in a certain classification was 33 00:02:09.470 --> 00:02:12.431 what the point quadtree was mainly used for 34 00:02:14.114 --> 00:02:17.646 Range quadtree was utilized for objects with a defined area 35 00:02:17.646 --> 00:02:20.500 and managing it efficiently 36 00:02:20.500 --> 00:02:23.723 It is often used to determine whether 37 00:02:23.723 --> 00:02:26.827 the objects with defined areas overlap 38 00:02:26.827 --> 00:02:30.023 In games, the second one introduced 39 00:02:30.023 --> 00:02:32.015 which is the range quadtree is used often 40 00:02:33.777 --> 00:02:36.860 For games, it is used to detect collision between two objects 41 00:02:36.860 --> 00:02:40.629 in a 2D plane 42 00:02:40.629 --> 00:02:42.048 In a platformer game 43 00:02:42.048 --> 00:02:45.233 the collision handling between the character and the platform 44 00:02:45.233 --> 00:02:47.487 In a shooter game with a Top Down view 45 00:02:47.487 --> 00:02:50.896 it is used for visibility determination or collision handling 46 00:02:50.896 --> 00:02:53.351 The basic data used for this process 47 00:02:53.351 --> 00:02:57.678 AABB, also known as Axis-Aligned Bounding Box 48 00:02:57.678 --> 00:03:03.183 It uses rectangular data arranged through the world axis 49 00:03:03.183 --> 00:03:05.056 But quadtree itself 50 00:03:05.056 --> 00:03:08.342 does not stand for an algorithm that detects collision 51 00:03:08.342 --> 00:03:11.169 When operating collision detection algorithm 52 00:03:11.169 --> 00:03:14.213 Not every object goes trough census 53 00:03:14.213 --> 00:03:17.516 only the objects near the target objects have to go through census 54 00:03:17.516 --> 00:03:20.193 which is a role played in order to detect collision effectively 55 00:03:20.193 --> 00:03:23.946 by reducing target data 56 00:03:23.946 --> 00:03:25.748 I have prepared a video 57 00:03:25.748 --> 00:03:29.411 This is a video of a program that I have developed 58 00:03:29.411 --> 00:03:32.436 In a wide space, I have placed 59 00:03:32.436 --> 00:03:35.470 15,000 objects randomly 60 00:03:35.470 --> 00:03:39.431 Theses objects and the area on the screen 61 00:03:39.431 --> 00:03:41.936 and as a mean to detect collision 62 00:03:41.936 --> 00:03:43.896 I have utilized quadtree 63 00:03:45.153 --> 00:03:49.342 The numeric value on the bottom which shows rendering object 64 00:03:49.342 --> 00:03:51.278 uses quadtree currently 65 00:03:51.278 --> 00:03:55.094 These are the number of objects that show in the camera viewport 66 00:03:55.094 --> 00:03:57.675 If quadtree isn't used 67 00:03:57.675 --> 00:04:01.302 we would have to compare all 15,000 objects 68 00:04:01.302 --> 00:04:04.541 If we examine through this method for every frame 69 00:04:04.541 --> 00:04:06.243 It would operate very slowly 70 00:04:06.243 --> 00:04:09.685 Therefore, only the objects needed to detect collision 71 00:04:09.685 --> 00:04:12.233 should picked out efficiently 72 00:04:12.233 --> 00:04:15.649 which is why quadtree is being used 73 00:04:15.649 --> 00:04:18.292 Now let's check the video 74 00:04:30.015 --> 00:04:32.671 Next, how the quadtree works 75 00:04:32.671 --> 00:04:34.777 We will take a look at its mechanism 76 00:04:37.292 --> 00:04:40.313 As I mentioned before, quadtree 77 00:04:40.313 --> 00:04:42.847 has a tree structure consisted with nodes 78 00:04:42.847 --> 00:04:45.414 Every node consisting the quadtree 79 00:04:45.414 --> 00:04:49.652 has a unique AABB of the rectangle and 80 00:04:49.652 --> 00:04:53.104 the list of objects 81 00:04:53.104 --> 00:04:55.809 In order to construct a quadree 82 00:04:55.809 --> 00:05:00.559 create a rectangular AABB that encloses the whole area 83 00:05:00.559 --> 00:05:03.936 and refer to this as the root node 84 00:05:03.936 --> 00:05:05.795 And the lower it gets to the child node 85 00:05:05.795 --> 00:05:07.863 The structure of having 4 child nodes 86 00:05:07.863 --> 00:05:11.124 should be maintained as a complete tree structure 87 00:05:11.124 --> 00:05:14.170 Quadtree that is set should fundamentally 88 00:05:14.170 --> 00:05:18.312 implement insertion and query functions 89 00:05:18.312 --> 00:05:21.838 Insertion means adding objects with defined range 90 00:05:21.838 --> 00:05:24.089 into a object list of a 91 00:05:24.089 --> 00:05:28.401 suitable node inside the quadtree 92 00:05:28.401 --> 00:05:33.149 And query allows effective determination 93 00:05:33.149 --> 00:05:36.953 of the AABB region given for performing the check 94 00:05:36.953 --> 00:05:41.609 along with the collision object 95 00:05:44.371 --> 00:05:46.609 First, how the insertion 96 00:05:46.609 --> 00:05:49.401 operates will be explained 97 00:05:49.401 --> 00:05:52.679 When insertion is operating 98 00:05:52.679 --> 00:05:55.975 the root node is the only factor that is set 99 00:05:55.975 --> 00:05:58.394 It searches for objects to insert 100 00:05:58.394 --> 00:06:01.064 and performs division if necessary 101 00:06:01.064 --> 00:06:03.561 For the case of division, the inserting object 102 00:06:03.561 --> 00:06:07.046 has to be completely enclosed 103 00:06:07.046 --> 00:06:09.916 in one of the four regions created by dividing the root node 104 00:06:09.916 --> 00:06:14.127 If it is not completely enclosed and lies on the boundary 105 00:06:14.127 --> 00:06:18.025 add it to the list of the root node and end the insertion 106 00:06:19.569 --> 00:06:24.599 If the inserting object is completely enclosed in one of the four regions 107 00:06:24.599 --> 00:06:28.262 Look back at the region 108 00:06:28.262 --> 00:06:30.922 Take a look at the node and object 109 00:06:30.922 --> 00:06:33.619 that recursively encloses the entire object 110 00:06:33.619 --> 00:06:36.806 If it is entirely enclosed, operate the division again 111 00:06:36.806 --> 00:06:38.483 If it lies on the boundary 112 00:06:38.483 --> 00:06:41.579 Expand the depth of the tree structure while continuing the division 113 00:06:41.579 --> 00:06:43.717 If the depth is set too deep 114 00:06:43.717 --> 00:06:46.508 the memory usage could increase 115 00:06:46.508 --> 00:06:50.272 Generally, the depth is regulated 116 00:06:50.272 --> 00:06:54.872 When dividing the quadtree, length of the divided side 117 00:06:54.872 --> 00:07:00.252 is always the half of the original length of the parent side 118 00:07:00.252 --> 00:07:03.140 In case of a side length of the quadrant with a particular depth 119 00:07:03.140 --> 00:07:06.074 It has a following formula 120 00:07:06.074 --> 00:07:09.967 The W stands for the length of one side of the node 121 00:07:09.967 --> 00:07:12.079 When the depth increases 122 00:07:12.079 --> 00:07:16.748 It decreases by the factor of 2 to the power of the depth 123 00:07:19.391 --> 00:07:21.416 Now let's take a look at the picture 124 00:07:21.416 --> 00:07:24.757 to see the insertion progress of a quadtree 125 00:07:24.757 --> 00:07:26.786 First, including the game map 126 00:07:26.786 --> 00:07:30.916 A giant square region will be set 127 00:07:30.916 --> 00:07:33.738 This is the region of a root node 128 00:07:36.302 --> 00:07:41.015 And I will place the first object on the upper right side 129 00:07:41.015 --> 00:07:46.314 Out of the root node and child node that is divided into four 130 00:07:46.314 --> 00:07:51.559 Whether the inserted object's region is completely enclosed has to be checked 131 00:07:51.559 --> 00:07:55.143 If the inserted object lies on the boundary 132 00:07:55.143 --> 00:07:59.173 It is completely enclosed in the child node on the upper right side 133 00:07:59.173 --> 00:08:02.987 So, we have to operate the division to create four child nodes 134 00:08:02.987 --> 00:08:04.827 and allocate it to the root node 135 00:08:06.104 --> 00:08:11.381 The inserted object is enclosed in the child region on the upper right side 136 00:08:11.381 --> 00:08:14.713 Since it is enclosed in the second child node over here 137 00:08:14.713 --> 00:08:18.292 We will take a look at the second child node 138 00:08:21.332 --> 00:08:23.729 Now for the node on the upper right side 139 00:08:23.729 --> 00:08:28.431 We only have to take a look at the second child node 140 00:08:28.431 --> 00:08:31.278 the process that was carried out recursively 141 00:08:31.278 --> 00:08:33.985 has to be repeated once again 142 00:08:33.985 --> 00:08:38.814 We have to check whether child node that divided the node on the upper right into four 143 00:08:38.814 --> 00:08:42.282 encloses with the object 144 00:08:42.282 --> 00:08:45.961 If you look here now, it's completely contained 145 00:08:45.961 --> 00:08:47.955 within one of the four child node areas 146 00:08:47.955 --> 00:08:53.351 The inserted object is enclosed with the child region on the upper right side 147 00:08:53.351 --> 00:08:56.480 This is where we will take a look 148 00:08:56.480 --> 00:08:58.802 We have came down to depth 2 149 00:08:58.802 --> 00:09:01.617 How it operates from depth 2 will be 150 00:09:01.617 --> 00:09:03.777 the next step that we take a look at 151 00:09:05.609 --> 00:09:09.287 For this depth 2 region 152 00:09:09.287 --> 00:09:14.728 we have checked the region divided into four and the AABB of the object 153 00:09:14.728 --> 00:09:16.742 the result was that it is overlapping 154 00:09:16.742 --> 00:09:19.965 In this case, we don't continue the division 155 00:09:19.965 --> 00:09:23.547 in the object list of the depth 2 node region 156 00:09:23.547 --> 00:09:27.688 add the current object and terminate the insertion process 157 00:09:29.718 --> 00:09:33.361 Now, we will insert one more 158 00:09:33.361 --> 00:09:37.223 This object is completely enclosed with 159 00:09:37.223 --> 00:09:39.153 the region which divided root node into four 160 00:09:39.153 --> 00:09:44.694 For this case, do not go below the depth of the child node 161 00:09:44.694 --> 00:09:48.381 and add to the object list of the root node 162 00:09:48.381 --> 00:09:51.777 We have seen the process of quadtree insertion process 163 00:09:54.351 --> 00:09:57.431 Now let's go over the query process 164 00:09:57.431 --> 00:10:00.812 Query is a function that determines whether the given AABB 165 00:10:00.812 --> 00:10:06.213 collides with the objects controlled by the quadtree 166 00:10:06.213 --> 00:10:08.412 To operate query 167 00:10:08.412 --> 00:10:12.462 First, the quadrant node that AABB used for query belongs in 168 00:10:12.462 --> 00:10:14.827 needs to be observed 169 00:10:14.827 --> 00:10:17.698 When every node that could possibly collide is understood 170 00:10:17.698 --> 00:10:20.380 It is compared with the object list that each node has 171 00:10:20.380 --> 00:10:22.322 This is to operate a collision detection 172 00:10:23.649 --> 00:10:25.371 To learn more about the process 173 00:10:25.371 --> 00:10:30.015 I have prepared an example that already inserted 10 objects 174 00:10:30.015 --> 00:10:34.285 Following the insertion rule that was previously mentioned 175 00:10:34.285 --> 00:10:38.018 We can see that 10 objects are added into 176 00:10:38.018 --> 00:10:40.470 the object list of various nodes 177 00:10:40.470 --> 00:10:45.827 In this situation, let's check the object that 178 00:10:45.827 --> 00:10:48.807 collides with the region colored in red dotted line 179 00:10:48.807 --> 00:10:51.850 From the picture, 3,8, and 7 180 00:10:51.850 --> 00:10:55.757 These three objects are colliding with the current region 181 00:10:55.757 --> 00:10:59.291 To check which object is colliding 182 00:10:59.291 --> 00:11:03.688 We could go through census for all 10 of them 183 00:11:03.688 --> 00:11:07.964 Since it's only 10, it doesn't matter right now 184 00:11:07.964 --> 00:11:11.540 but if this increases to 100, 1000, and 10,000 185 00:11:11.540 --> 00:11:14.500 It will start to slow down 186 00:11:14.500 --> 00:11:18.787 So we have to utilize the tree structure in order to reduce the search volume 187 00:11:18.787 --> 00:11:21.588 Then let's check the nodes 188 00:11:21.588 --> 00:11:23.955 that have the possibility of being searched 189 00:11:25.500 --> 00:11:27.916 First, the root node 190 00:11:27.916 --> 00:11:32.246 If there is a blue object in the object list of the root node 191 00:11:32.246 --> 00:11:35.282 Let's say the blue object has been inserted 192 00:11:35.282 --> 00:11:38.645 The rectangular region that will carry out an assessment 193 00:11:38.645 --> 00:11:41.144 could be overlapped 194 00:11:41.144 --> 00:11:44.943 Therefore, the object list that root node has 195 00:11:44.943 --> 00:11:46.861 there is a possibility of collision 196 00:11:46.861 --> 00:11:48.698 It needs to be added to the list of assessment 197 00:11:50.193 --> 00:11:53.670 Next, going deeper 198 00:11:53.670 --> 00:11:58.654 since it is one of the four child that is enclosed on the upper right side 199 00:11:58.654 --> 00:12:03.094 We should search for the child that is on the upper right side with a depth of 1 200 00:12:03.094 --> 00:12:05.631 In the object list of the upper right side 201 00:12:05.631 --> 00:12:09.856 if there is a blue object like so 202 00:12:09.856 --> 00:12:11.161 this UpperRight 203 00:12:11.161 --> 00:12:15.144 The upper right side should be added to the list of assessment 204 00:12:16.599 --> 00:12:20.712 Going one step below, lower right side 205 00:12:20.712 --> 00:12:25.441 This encloses the lower right side that will be divided into four 206 00:12:25.441 --> 00:12:28.599 We could check the lower right side region 207 00:12:28.599 --> 00:12:31.252 For the case of lower right side 208 00:12:31.252 --> 00:12:35.074 This object could be in the object list of the lower right side 209 00:12:35.074 --> 00:12:36.908 That would lead to overlapping 210 00:12:36.908 --> 00:12:39.208 The object list of the lower right side 211 00:12:39.208 --> 00:12:41.500 should be added to the list of assessment 212 00:12:43.718 --> 00:12:46.751 Moving on to the next dept 213 00:12:46.751 --> 00:12:50.344 Every object list that has been divided into four 214 00:12:50.344 --> 00:12:52.312 should be added to the list of assessment 215 00:12:53.668 --> 00:12:57.460 If the tree structure goes deeper, then we would need to continue 216 00:12:57.460 --> 00:13:01.262 But let's say that this is the final depth 217 00:13:01.262 --> 00:13:04.243 Then the search would end here 218 00:13:08.391 --> 00:13:11.035 To wrap up the process until now 219 00:13:11.035 --> 00:13:14.480 The following nodes are the ones we need to assess 220 00:13:14.480 --> 00:13:17.990 UpperRight of root and the first depth 221 00:13:17.990 --> 00:13:21.671 LowerRight of the second depth 222 00:13:21.671 --> 00:13:24.748 Every child of the LowerRight from the third depth 223 00:13:24.748 --> 00:13:30.480 These are the 7 nodes we could screen out 224 00:13:30.480 --> 00:13:32.530 From the lists that nodes have 225 00:13:32.530 --> 00:13:34.312 When we look at it 226 00:13:34.312 --> 00:13:36.937 it has the overlapping part of the given region 227 00:13:36.937 --> 00:13:42.401 which was 3, 8, and 7 228 00:13:42.401 --> 00:13:45.708 If the quadtree has the depth of 3 229 00:13:45.708 --> 00:13:49.916 A total of 85 nodes will be created 230 00:13:49.916 --> 00:13:53.847 We only need to operate the search for 7 of them 231 00:13:53.847 --> 00:13:58.252 This is called having a logarithmic time complexity 232 00:13:58.252 --> 00:14:00.541 When there are more objects 233 00:14:00.541 --> 00:14:03.074 it is more efficient to determine the overlapping 234 00:14:06.460 --> 00:14:09.332 Next, for the case that is shown on the screen 235 00:14:09.332 --> 00:14:13.084 When the region that should be assessed is overlapped in the middle 236 00:14:14.688 --> 00:14:17.063 When it is overlapped in the middle 237 00:14:17.063 --> 00:14:19.268 As you can see, the root node 238 00:14:19.268 --> 00:14:21.888 and every child enclosed in the root node 239 00:14:21.888 --> 00:14:23.856 counts as an object to be compared 240 00:14:26.698 --> 00:14:31.900 Next, children with a depth of 1 241 00:14:31.900 --> 00:14:33.837 If depth 1 is researched 242 00:14:33.837 --> 00:14:37.167 The upper left side, Upper Left 243 00:14:37.167 --> 00:14:41.173 The child node of lower right encloses the scope 244 00:14:41.173 --> 00:14:44.650 Child node of the lower left for the upper right 245 00:14:44.650 --> 00:14:47.916 Child node of the upper left for the lower right 246 00:14:47.916 --> 00:14:51.597 And child node of the upper right for the lower left 247 00:14:51.597 --> 00:14:53.500 They enclose the given scope 248 00:14:53.500 --> 00:14:56.193 Let's go one step deeper into the next depth 249 00:14:56.193 --> 00:14:58.185 Going in one step deeper on to the next depth 250 00:14:58.185 --> 00:15:01.153 Looking in to the lower right region of depth 2 251 00:15:01.153 --> 00:15:04.955 The two child region encloses the given scope 252 00:15:04.955 --> 00:15:07.453 One child region for the lower left 253 00:15:07.453 --> 00:15:09.858 Two child region for the upper right 254 00:15:09.858 --> 00:15:12.401 They are enclosing the given scope 255 00:15:12.401 --> 00:15:15.293 When operating query like so, it is different from insertion 256 00:15:15.293 --> 00:15:18.615 Including both the overlapping and enclosing region 257 00:15:18.615 --> 00:15:20.589 Every node needs to be identified 258 00:15:20.967 --> 00:15:24.838 Implementing Quadtree 259 00:15:24.838 --> 00:15:28.089 Extract the given sample project 260 00:15:28.089 --> 00:15:34.351 and this project will show up when operating Unity 261 00:15:34.351 --> 00:15:36.421 The Unity version used to run this project is 262 00:15:36.421 --> 00:15:41.619 the 2021.3 version 263 00:15:41.619 --> 00:15:43.850 As you can see, the project is 264 00:15:43.850 --> 00:15:46.213 consisted with multiple scenes 265 00:15:46.213 --> 00:15:49.521 In this lecture, we will take a look at what is assigned as number 1 266 00:15:49.521 --> 00:15:53.094 which is the implementation of a general quadtree 267 00:15:54.827 --> 00:15:59.965 Moving to the first folder, there are insertion and query request 268 00:15:59.965 --> 00:16:02.728 There are two scenes like so 269 00:16:02.728 --> 00:16:04.850 First this insertion scene 270 00:16:04.850 --> 00:16:10.292 I will open up insert scene and explain functions related to it 271 00:16:11.213 --> 00:16:13.843 For this case of insert scene 272 00:16:13.843 --> 00:16:17.399 If you look at the Hierarchy tab on the left 273 00:16:17.399 --> 00:16:20.064 There is a administrator called quadtree manager 274 00:16:20.064 --> 00:16:22.873 In this game object manager 275 00:16:22.873 --> 00:16:25.698 the quadtree spatial partitioning is proceeded 276 00:16:27.777 --> 00:16:30.929 This quadtree manager component is 277 00:16:30.929 --> 00:16:33.015 arranged over here as you can see 278 00:16:33.015 --> 00:16:36.047 In this quadtree manager component 279 00:16:36.047 --> 00:16:40.480 there is an assigned size of a whole map that sets the quadtree 280 00:16:40.480 --> 00:16:42.980 As you can see x and y 281 00:16:42.980 --> 00:16:45.896 64 is set for both vertical and horizontal 282 00:16:47.292 --> 00:16:51.223 And in the bottom of quadtree manager game object 283 00:16:51.223 --> 00:16:52.912 There is an insert 284 00:16:52.912 --> 00:16:56.906 which is placed with a total of 9 objects 285 00:16:56.906 --> 00:16:59.045 Let's take a look at each arrangement 286 00:16:59.045 --> 00:17:03.896 Number 1 on the lower left, number to in the middle 287 00:17:03.896 --> 00:17:06.995 These game objects called insert 288 00:17:06.995 --> 00:17:11.302 As you can see there is a special tag called insert 289 00:17:11.302 --> 00:17:15.872 Through this tag, the objects to be inserted will be chosen 290 00:17:15.872 --> 00:17:18.322 It is designed in code 291 00:17:18.322 --> 00:17:20.496 As you can see in the screen 292 00:17:20.496 --> 00:17:23.896 The scene view and game view is separated 293 00:17:23.896 --> 00:17:25.372 Normally it would be over here but 294 00:17:25.372 --> 00:17:28.262 It is separated intentionally 295 00:17:28.262 --> 00:17:31.204 So that the functions could be operated in the game view 296 00:17:31.204 --> 00:17:35.361 and the result could be seen in the scene view 297 00:17:35.361 --> 00:17:39.173 There is a button created in the game view 298 00:17:39.173 --> 00:17:41.856 Usually a command is made in the game view but 299 00:17:41.856 --> 00:17:43.048 The structure of a quadtree 300 00:17:43.048 --> 00:17:46.827 is designed to be done through scene view 301 00:17:46.827 --> 00:17:49.291 So for the scene view 302 00:17:49.291 --> 00:17:52.678 It is designed that the camera view doesn't show 303 00:17:52.678 --> 00:17:57.530 And the UI area doesn't show as well 304 00:18:01.134 --> 00:18:04.173 Now I will press the play button 305 00:18:09.500 --> 00:18:14.064 If we press the play button, the first on the lower left side 306 00:18:14.064 --> 00:18:17.220 This object called Insert 1 307 00:18:17.220 --> 00:18:19.767 pops up as a rectangle 308 00:18:19.767 --> 00:18:24.599 This is the target rectangle that will proceed with the insertion 309 00:18:24.599 --> 00:18:28.530 If we press the Insert button from the game view on the right 310 00:18:28.530 --> 00:18:32.668 The quadtree to hold the rectangle 311 00:18:32.668 --> 00:18:36.728 it will continue to divide until the node is found 312 00:18:36.728 --> 00:18:41.500 And the rectangle object will be added to the mode object list which is divided 313 00:18:41.500 --> 00:18:44.401 Let's press the button to see the result 314 00:18:44.401 --> 00:18:49.510 As you can see in the bottom left quadrant 315 00:18:49.510 --> 00:18:52.658 And from the top right quadrant 316 00:18:52.658 --> 00:18:55.866 Again in the top left quadrant 317 00:18:55.866 --> 00:19:02.450 The bottom right quadrant, this is the bottom most 318 00:19:02.450 --> 00:19:05.886 It is currently overlapping, right? 319 00:19:05.886 --> 00:19:08.746 The boundary is overlapping 320 00:19:08.746 --> 00:19:10.193 which is why it ends here 321 00:19:12.045 --> 00:19:19.795 Considering the depth, 1 Depth, 2 Depth, 3 Depth, and 4 Depth 322 00:19:19.795 --> 00:19:22.054 We can see that it has proceeded until 4 Depth 323 00:19:23.787 --> 00:19:26.390 So if you look over here 324 00:19:26.390 --> 00:19:28.395 In the 4 Depth area 325 00:19:28.395 --> 00:19:32.233 Do you see the number 1? 326 00:19:32.233 --> 00:19:37.134 If the number is located in the middle of the fourth Depth 327 00:19:37.134 --> 00:19:42.757 One object has been inserted in to the whole node 328 00:19:42.757 --> 00:19:45.708 It means that one object has been inserted 329 00:19:48.520 --> 00:19:50.807 I will press the next button 330 00:19:50.807 --> 00:19:57.193 In the case of this red insertion object that is in the middle 331 00:19:57.193 --> 00:20:00.371 It lies on the boundary of the quadrant that is divided 332 00:20:00.371 --> 00:20:04.549 This means that it doesn't enclose in any child node 333 00:20:04.549 --> 00:20:06.104 So it goes into the root node 334 00:20:06.104 --> 00:20:09.391 It goes into root node if you press the insert button 335 00:20:09.391 --> 00:20:13.421 You can see the number of root node being marked as 1 336 00:20:13.421 --> 00:20:16.292 I will press next 337 00:20:16.292 --> 00:20:22.422 Same as before, top left number 1, 2, 3, 4 338 00:20:22.422 --> 00:20:26.817 It has been divided four times as before 339 00:20:28.807 --> 00:20:34.916 The depth 1 is included but it lies on the boundary 340 00:20:34.916 --> 00:20:38.332 which is why it goes into the lower right node 341 00:20:39.470 --> 00:20:43.391 Like so, if it is continuously added one by one 342 00:20:43.391 --> 00:20:48.064 A total of 9 objects as you can see 343 00:20:48.064 --> 00:20:51.943 A node to store these objects 344 00:20:51.943 --> 00:20:54.757 a node that is divided into 4 will be assigned 345 00:20:54.757 --> 00:20:58.550 A number will be marked on the node 346 00:20:58.550 --> 00:21:01.287 which shows that 347 00:21:01.287 --> 00:21:02.678 spatial partitioning is efficiently done 348 00:21:04.094 --> 00:21:06.660 This is the demo of the prepared program 349 00:21:06.660 --> 00:21:09.025 which included 9 insertions 350 00:21:09.025 --> 00:21:12.847 Now let's take a look at the code ourselves 351 00:21:12.847 --> 00:21:15.038 Go to the script folder 352 00:21:15.038 --> 00:21:18.282 In the first folder, which is quadtree folder 353 00:21:18.282 --> 00:21:19.570 Quadtree manager 354 00:21:19.570 --> 00:21:24.589 The manager component code which has been set to the game object 355 00:21:24.589 --> 00:21:27.282 Let's double click it and take a look 356 00:21:28.678 --> 00:21:31.500 The quadtree manager that we are trying to take a look at 357 00:21:31.500 --> 00:21:33.990 It is included in the last project 358 00:21:33.990 --> 00:21:36.262 which is the quadtree project 359 00:21:36.262 --> 00:21:38.926 So remove everything else 360 00:21:38.926 --> 00:21:41.856 The last quadtree project 361 00:21:41.856 --> 00:21:46.480 The quadtree manager is what we will double click to find out 362 00:21:46.480 --> 00:21:49.153 We will move to the top to take a look 363 00:21:50.946 --> 00:21:53.045 For this quadtree manager 364 00:21:53.045 --> 00:21:58.015 It is a script designed to manage quadtrees directly in Unity 365 00:21:58.015 --> 00:22:00.728 So that it would operate as the Unity component 366 00:22:00.728 --> 00:22:04.054 Inherited from the MonoBehaviour class 367 00:22:04.054 --> 00:22:09.460 This script does not develop actual quadtree operation 368 00:22:09.460 --> 00:22:13.381 It plays the role of controlling communication between 369 00:22:13.381 --> 00:22:15.366 quadtree object that is designed from C Sharp through Unity 370 00:22:15.366 --> 00:22:18.510 and the quadtree object over here 371 00:22:18.510 --> 00:22:22.876 Let's look over the detailed information 372 00:22:22.876 --> 00:22:26.787 First on the top of the class, something that will be dealt later 373 00:22:26.787 --> 00:22:30.896 ways to classify query function and drawing method 374 00:22:30.896 --> 00:22:33.500 A enumeration called Draw Mode has been declared 375 00:22:33.500 --> 00:22:36.480 So that drawing in insert mode and 376 00:22:36.480 --> 00:22:38.757 query mode could be distinguished 377 00:22:38.757 --> 00:22:41.302 It is why this enumeration has been declared 378 00:22:41.302 --> 00:22:43.282 For this enumeration 379 00:22:43.282 --> 00:22:45.896 as you can see, from the quadtree manager 380 00:22:45.896 --> 00:22:48.025 we can assign it like so 381 00:22:48.025 --> 00:22:51.193 It has been pulled out to the interface 382 00:22:53.550 --> 00:22:55.639 The default value is insertion 383 00:22:55.639 --> 00:22:59.332 but it should be replaced when implementing query functions 384 00:22:59.332 --> 00:23:03.817 Next, the size of the whole area that would be controlled from quadtree 385 00:23:03.817 --> 00:23:06.064 has been designed so that it could be assigned manually 386 00:23:06.064 --> 00:23:09.936 Over here, it has been set as 64 for both horizontal and veritcal 387 00:23:11.480 --> 00:23:14.767 Next, the object to operate the actual quadtree 388 00:23:14.767 --> 00:23:18.045 has been declared as member variable _tree 389 00:23:18.045 --> 00:23:22.599 It has been initialized as null value so that it would be created when necessary 390 00:23:22.599 --> 00:23:26.510 In the bottom, operate insertion function 391 00:23:26.510 --> 00:23:31.183 The index variable which shows the list of inserting object list 392 00:23:31.183 --> 00:23:35.332 And every objects with the insert tag 393 00:23:35.332 --> 00:23:38.748 The variable to save this array has been declared 394 00:23:41.510 --> 00:23:46.153 Other variables will be explained later on 395 00:23:46.153 --> 00:23:48.589 when the query function is explained 396 00:23:49.896 --> 00:23:54.252 Next, the initialization function of manager class 397 00:23:54.252 --> 00:23:57.460 Let's take a look at Awake function 398 00:23:57.460 --> 00:23:59.569 When there is no objects 399 00:23:59.569 --> 00:24:02.015 An object called quadtree is created 400 00:24:02.015 --> 00:24:06.371 At this point, you can see that the entire area info is entered as an factor 401 00:24:08.282 --> 00:24:13.035 Next over here, FindGameObjectsWithTag 402 00:24:13.035 --> 00:24:17.441 Using Unity API, a tag has been assigned as an insert 403 00:24:17.441 --> 00:24:20.708 Every game object is brought to the array 404 00:24:20.708 --> 00:24:22.688 and they are assigned here 405 00:24:22.688 --> 00:24:28.243 Using this, the objects that will be inserted 406 00:24:28.243 --> 00:24:31.153 can be searched one at a time as well as being inserted 407 00:24:32.955 --> 00:24:35.839 Now for the insertion function 408 00:24:35.839 --> 00:24:38.094 Let's take a look at Insertion function 409 00:24:38.094 --> 00:24:42.639 For the Insert function, in Unity 410 00:24:42.639 --> 00:24:47.837 There are buttons that say mapping and binding in the UI of Unity 411 00:24:47.837 --> 00:24:50.698 So if you press this Insert button 412 00:24:50.698 --> 00:24:55.233 The Insert function of the quadtree manager is invoked 413 00:24:55.233 --> 00:24:59.569 And if the object list is complete 414 00:24:59.569 --> 00:25:03.718 A defensive code has been declared to prevent additional insertion 415 00:25:03.718 --> 00:25:07.004 If there isn't a problem, object 416 00:25:07.004 --> 00:25:10.094 Invoke the Insert function of an object 417 00:25:10.094 --> 00:25:13.649 which actually controls the quadtree 418 00:25:13.649 --> 00:25:19.649 The index value of the object which we will be inserting 419 00:25:19.649 --> 00:25:21.955 Put it into the Insert function over here 420 00:25:21.955 --> 00:25:24.678 We are adding one more 421 00:25:24.678 --> 00:25:28.332 It is a method of adding one more after being inserted 422 00:25:28.332 --> 00:25:30.767 When every object is finished 423 00:25:30.767 --> 00:25:35.167 The value that is same as the length of the insert object 424 00:25:35.167 --> 00:25:37.074 will be set as an index 425 00:25:39.866 --> 00:25:43.510 Next, we will look at the quad tree class 426 00:25:45.837 --> 00:25:50.265 Quadtree class has rootNode 427 00:25:50.265 --> 00:25:52.312 as a member variable 428 00:25:52.312 --> 00:25:56.886 And it assigned maxDepth as a member variable 429 00:25:56.886 --> 00:25:59.639 It is set as 5 430 00:25:59.639 --> 00:26:02.930 So that it doesn't go below the depth 5 431 00:26:02.930 --> 00:26:04.599 This is why the variable was set 432 00:26:04.599 --> 00:26:06.841 If there isn't a limit 433 00:26:06.841 --> 00:26:11.490 The memory, space, and recursive calls will increase significantly 434 00:26:11.490 --> 00:26:14.104 It is best to regulate it below a certain value 435 00:26:15.252 --> 00:26:18.214 And the constructor of quadtree class 436 00:26:18.214 --> 00:26:22.045 as I mentioned before, takes a size 437 00:26:22.045 --> 00:26:25.342 It starts creating after taking the size of a quadtree 438 00:26:25.342 --> 00:26:29.470 In this case, root node is created right after taking the size 439 00:26:29.470 --> 00:26:30.970 When creating the root node 440 00:26:30.970 --> 00:26:32.391 various arguments need to be inserted 441 00:26:32.391 --> 00:26:35.564 Let's check it out later on 442 00:26:35.564 --> 00:26:38.302 when explaining Node class 443 00:26:38.302 --> 00:26:42.589 This Insert function which quadtree manager invokes 444 00:26:42.589 --> 00:26:45.827 Brings out the Insert function from the root node 445 00:26:45.827 --> 00:26:50.510 It is designed as a structure that passes the argument right away 446 00:26:50.510 --> 00:26:54.252 I will explain other functions later on 447 00:26:54.252 --> 00:26:57.382 The main logic in the quadtree 448 00:26:57.382 --> 00:27:01.837 We will take a look at Node class 449 00:27:01.837 --> 00:27:06.767 The name for this Node class of the quadtree is QNode 450 00:27:06.767 --> 00:27:10.292 Many different operations are done through this node 451 00:27:10.292 --> 00:27:13.273 First, the enumeration called QNodeIndex 452 00:27:13.273 --> 00:27:14.876 has been declared 453 00:27:14.876 --> 00:27:18.609 This enumeration is used for insertion or query 454 00:27:18.609 --> 00:27:23.148 to find out which quadrant the current 455 00:27:23.148 --> 00:27:25.797 area is enclosed in 456 00:27:25.797 --> 00:27:29.668 I specified IntType so that it can be easily converted to Integer type 457 00:27:29.668 --> 00:27:32.094 The enumeration value starts from 0 458 00:27:32.094 --> 00:27:36.035 We have to be cautious of the order 459 00:27:36.035 --> 00:27:39.037 Top left side for number 0 460 00:27:39.037 --> 00:27:41.390 and then top right side 461 00:27:41.390 --> 00:27:42.777 next bottom right side 462 00:27:42.777 --> 00:27:45.573 followed by bottom right side 463 00:27:45.573 --> 00:27:46.731 then bottom left side 464 00:27:46.731 --> 00:27:49.936 These are the order assigned for four 465 00:27:49.936 --> 00:27:52.548 This order doesn't need to be kept but 466 00:27:52.548 --> 00:27:55.787 Later on when you create the partitioned surface 467 00:27:55.787 --> 00:27:59.642 It is easy to code when 468 00:27:59.642 --> 00:28:02.688 you follow the order for the partitioned node 469 00:28:02.688 --> 00:28:07.579 That is why I mentioned the order as a priority 470 00:28:07.579 --> 00:28:10.955 And there are two exceptional cases 471 00:28:10.955 --> 00:28:14.894 There is a case where it isn't enclosed in a quadrant completely 472 00:28:14.894 --> 00:28:17.025 and lies on the boundary 473 00:28:17.025 --> 00:28:21.700 In that case, a enumeration called STRADDING 474 00:28:21.700 --> 00:28:23.728 can be declared 475 00:28:23.728 --> 00:28:26.361 There might be a case when it moves outside the area, right? 476 00:28:26.361 --> 00:28:30.351 This is an exceptional case so 477 00:28:30.351 --> 00:28:32.499 to indicate this exceptional case 478 00:28:32.499 --> 00:28:35.104 an enumeration called OUTOFAREA 479 00:28:35.104 --> 00:28:38.450 an enumeration will be additionally added 480 00:28:39.748 --> 00:28:41.093 Next, this time 481 00:28:41.093 --> 00:28:43.520 we will look over the constructor code of the node 482 00:28:43.520 --> 00:28:47.990 In a node,there is Quadtree,Parent, Bounds,Depth 483 00:28:47.990 --> 00:28:50.292 which are four variables 484 00:28:50.292 --> 00:28:54.301 These are set so that it is directly assigned with each member variable 485 00:28:54.301 --> 00:28:56.767 by the constructor 486 00:28:56.767 --> 00:28:59.639 Now, we will take a look at the member variable 487 00:28:59.639 --> 00:29:00.999 Child of the node 488 00:29:00.999 --> 00:29:04.550 A list that stores the child of a divided quadrant 489 00:29:04.550 --> 00:29:06.579 has been declared 490 00:29:06.579 --> 00:29:08.579 If these children are created 491 00:29:08.579 --> 00:29:12.332 there will always be four 492 00:29:12.332 --> 00:29:15.629 Next, in order to store every list of object 493 00:29:15.629 --> 00:29:18.866 set in the current node 494 00:29:18.866 --> 00:29:22.995 I have created another list called items 495 00:29:22.995 --> 00:29:25.309 And to show the current depth of the node 496 00:29:25.309 --> 00:29:28.282 A Depth member variable has been declared 497 00:29:28.282 --> 00:29:32.154 Next, managing the whole quadtree 498 00:29:32.154 --> 00:29:34.599 meaning the quadtree object 499 00:29:34.599 --> 00:29:38.500 A variable Tree has been declared to save the reference 500 00:29:38.500 --> 00:29:40.287 To find the parent node 501 00:29:40.287 --> 00:29:43.500 I have added another reference called Parent 502 00:29:43.500 --> 00:29:45.639 But it isn't actually used 503 00:29:45.639 --> 00:29:48.104 I made it just in case 504 00:29:48.104 --> 00:29:51.361 Next, in order to assign the area of the current node 505 00:29:51.361 --> 00:29:52.812 AABB area 506 00:29:52.812 --> 00:29:55.969 To save the Bounding Box area 507 00:29:55.969 --> 00:29:59.401 I have added it as a member variable 508 00:29:59.401 --> 00:30:00.639 Then, let's take a look at the process of 509 00:30:00.639 --> 00:30:03.926 adding an item to the node 510 00:30:03.926 --> 00:30:07.500 It is proceeded through an Insert function 511 00:30:07.500 --> 00:30:10.322 The first step for an Insert function 512 00:30:10.322 --> 00:30:13.757 to invoke a function called TestRegion 513 00:30:13.757 --> 00:30:17.330 To check out the condition of the AABB area 514 00:30:17.330 --> 00:30:19.658 of the given item 515 00:30:19.658 --> 00:30:22.649 The output will be put as result 516 00:30:22.649 --> 00:30:26.470 Press F12 for the given code 517 00:30:26.470 --> 00:30:29.025 To enter the function code 518 00:30:29.025 --> 00:30:33.500 This code is invoking a function called GetQuads 519 00:30:33.500 --> 00:30:36.619 This is a function called GetQuads 520 00:30:36.619 --> 00:30:40.757 It is declared right on top when you press F12 521 00:30:40.757 --> 00:30:45.256 The role of this function is to determine 522 00:30:45.256 --> 00:30:49.540 information about the overlapping quadrant with the AABB area 523 00:30:49.540 --> 00:30:53.688 So first, the overlapping output 524 00:30:53.688 --> 00:30:57.049 This index 525 00:30:57.049 --> 00:31:00.361 The value of top left side and top right side as I mentioned 526 00:31:00.361 --> 00:31:03.487 It is designed so that 527 00:31:03.487 --> 00:31:05.639 the lists overlapping the index is returned 528 00:31:05.639 --> 00:31:06.925 To determine this 529 00:31:06.925 --> 00:31:11.500 First, we have to calculate the four separated value 530 00:31:11.500 --> 00:31:16.005 So using minimum and maximum value 531 00:31:16.005 --> 00:31:21.134 We should check which area it overlaps with 532 00:31:21.134 --> 00:31:26.134 And combining these together 533 00:31:26.134 --> 00:31:31.431 The list of quadrant should be added over here 534 00:31:31.431 --> 00:31:37.500 Considering the negative x and positive y, it should be a top left side 535 00:31:37.500 --> 00:31:42.203 Then positive x, positive y will be a top right side 536 00:31:42.203 --> 00:31:46.046 Searching for every area that is overlapping 537 00:31:46.046 --> 00:31:49.520 We make a list and return it 538 00:31:49.520 --> 00:31:51.401 This is how it is returned 539 00:31:51.401 --> 00:31:55.391 It is impossible to have no return value 540 00:31:55.391 --> 00:31:57.777 But I have just inserted it 541 00:31:57.777 --> 00:32:01.221 If there is one returned value 542 00:32:01.221 --> 00:32:05.243 It means that it is enclosed in a certain area 543 00:32:05.243 --> 00:32:09.183 The list has been invoked only one time out of four 544 00:32:09.183 --> 00:32:11.594 In this case, out of the four areas 545 00:32:11.594 --> 00:32:13.668 It means that it is completely enclosed in one 546 00:32:14.916 --> 00:32:19.013 If it isn't the case, it means that 547 00:32:19.013 --> 00:32:21.015 it has to be enclosed in two or more areas 548 00:32:21.015 --> 00:32:23.500 For this instance, it will overlap for sure 549 00:32:23.500 --> 00:32:26.837 At this point, an enumeration value called STRADDLING 550 00:32:26.837 --> 00:32:29.015 will be returned to mark the overlapping 551 00:32:30.342 --> 00:32:35.896 We have taken a look at how the TestRegion function is used 552 00:32:35.896 --> 00:32:39.361 The output is either STRADDLING 553 00:32:40.609 --> 00:32:44.629 or a quadrant value that is completely enclosed will be return 554 00:32:44.629 --> 00:32:46.876 For the case of overlapping 555 00:32:46.876 --> 00:32:50.609 I have mentioned that you can just add to the object list of the current node 556 00:32:50.609 --> 00:32:54.767 So add the object list of the current node 557 00:32:54.767 --> 00:32:57.672 And for cases where it doesn't overlap 558 00:32:57.672 --> 00:32:59.807 Except for the situation of OUTOFAREA 559 00:32:59.807 --> 00:33:01.657 It will be one out of four 560 00:33:01.657 --> 00:33:03.906 It would be one out of four 561 00:33:03.906 --> 00:33:07.587 so we can first operate the partitioning 562 00:33:07.587 --> 00:33:09.876 We will operate the quarter division 563 00:33:09.876 --> 00:33:13.817 I will press F12 to take a look at the division code 564 00:33:13.817 --> 00:33:16.850 If the depth of the current node is 565 00:33:16.850 --> 00:33:20.797 at the maximum depth which was set by the tree 566 00:33:20.797 --> 00:33:22.617 The division is unnecessary 567 00:33:22.617 --> 00:33:26.728 therefore return the false 568 00:33:26.728 --> 00:33:29.573 But if that is not the case 569 00:33:29.573 --> 00:33:31.797 There is a need for additional division 570 00:33:31.797 --> 00:33:35.639 But there is a possibility that this node has already been divided 571 00:33:35.639 --> 00:33:41.124 So I have added a property called IsSplitted 572 00:33:41.124 --> 00:33:43.304 If children 573 00:33:43.304 --> 00:33:45.642 In other words, list that manages the divided node 574 00:33:45.642 --> 00:33:47.629 The value of children isn't null 575 00:33:47.629 --> 00:33:50.252 It will always be four 576 00:33:50.252 --> 00:33:53.599 If the count is bigger than 0, it means it is already divided 577 00:33:53.599 --> 00:33:58.104 In that case, the child node doesn't need to be created 578 00:33:58.104 --> 00:34:03.173 Press Ctrl - to go back to the previous code 579 00:34:03.173 --> 00:34:05.640 If it hasn't been divided 580 00:34:05.640 --> 00:34:07.312 Just operate the division 581 00:34:07.312 --> 00:34:11.009 So if it has not been divided 582 00:34:11.009 --> 00:34:17.074 Create half the size of the current node 583 00:34:17.074 --> 00:34:19.576 Half of each side 584 00:34:19.576 --> 00:34:24.777 Create an AABB area with half the length 585 00:34:24.777 --> 00:34:30.104 Add another value that will move the center of AABB 586 00:34:30.104 --> 00:34:34.718 There will always be four children 587 00:34:34.718 --> 00:34:38.177 List objects with 4 Capacity 588 00:34:38.177 --> 00:34:40.441 Create a list object 589 00:34:40.441 --> 00:34:42.887 Then using the Offset value 590 00:34:42.887 --> 00:34:46.358 Each divided child node's area 591 00:34:46.358 --> 00:34:49.084 has to be assigned 592 00:34:49.084 --> 00:34:53.500 Previously, I said the order needs to be same as the enumeration 593 00:34:53.500 --> 00:34:56.163 I will start creating from the top left side 594 00:34:56.163 --> 00:34:59.917 The top left side has a x value of minus 595 00:34:59.917 --> 00:35:04.718 I will multiply (-2) to the x value in order to convert to a plus 596 00:35:04.718 --> 00:35:09.985 So the root and itself which is a parent node 597 00:35:09.985 --> 00:35:13.849 Then a bounding volume of a new child node 598 00:35:13.849 --> 00:35:16.262 AABB area needs to be assigned 599 00:35:16.262 --> 00:35:19.876 In this case, the center of the current node I have 600 00:35:19.876 --> 00:35:24.381 moved as much as the Offset value will be the center of the child node 601 00:35:24.381 --> 00:35:28.198 And reduced to half the length 602 00:35:28.198 --> 00:35:31.441 Create a node based on the assigned size of the area 603 00:35:31.441 --> 00:35:35.035 but lastly add 1 to the depth value 604 00:35:38.134 --> 00:35:40.631 Next, the top right side 605 00:35:40.631 --> 00:35:44.759 The b Offset value which was used for the 606 00:35:44.759 --> 00:35:47.678 original top left side will be reused 607 00:35:47.678 --> 00:35:49.940 Since we multiplied a minus, it would be -1 608 00:35:49.940 --> 00:35:53.411 So we multiply a minus again to make it into a plus 609 00:35:53.411 --> 00:35:56.337 And assign it in the same way 610 00:35:56.337 --> 00:35:59.213 The top right node is created 611 00:35:59.213 --> 00:36:01.917 Next, to get to the bottom right side 612 00:36:01.917 --> 00:36:06.450 Multiply -1 to the y value and move it to the bottom 613 00:36:06.450 --> 00:36:11.040 and multiply -2 to the x value 614 00:36:11.040 --> 00:36:12.943 and move it to the left 615 00:36:12.943 --> 00:36:16.243 It will lead to a bottom left node 616 00:36:16.243 --> 00:36:18.833 If we have finished everything 617 00:36:21.001 --> 00:36:23.926 Go back to the code before 618 00:36:23.926 --> 00:36:28.958 If the Split is operated, add to the child 619 00:36:28.958 --> 00:36:31.817 Since the output has been produced 620 00:36:31.817 --> 00:36:34.633 The child which has been set as one of the four 621 00:36:34.633 --> 00:36:37.005 will be invoked recursively 622 00:36:37.005 --> 00:36:40.037 to the Insert function 623 00:36:40.037 --> 00:36:41.480 If it meets the limit 624 00:36:41.480 --> 00:36:43.400 goes until maxDepth 625 00:36:43.400 --> 00:36:45.213 It would return the false 626 00:36:45.213 --> 00:36:49.255 Then it could be implemented by 627 00:36:49.255 --> 00:36:52.437 adding to the current object list 628 00:36:53.714 --> 00:36:55.946 We have learned how the insertion function of quadtree 629 00:36:55.946 --> 00:36:58.738 can be implemented 630 00:36:58.738 --> 00:37:03.153 Now we will take a look at drawing functions related to insertion 631 00:37:03.153 --> 00:37:06.081 Double click the quadtree manager 632 00:37:06.081 --> 00:37:10.856 Let's take a look at a function placed in the bottom called onDrawGizmos 633 00:37:10.856 --> 00:37:14.092 This function has ExecuteinEditMode 634 00:37:14.092 --> 00:37:16.233 which is an attribute that has been declared 635 00:37:16.233 --> 00:37:20.599 We don't need to press play 636 00:37:20.599 --> 00:37:26.114 instead, it is set to draw the entire area of the quadtree on the editor 637 00:37:29.381 --> 00:37:33.654 If you look over here, marked with gray 638 00:37:33.654 --> 00:37:38.748 The function is invoked so that it would draw the entire area of the quadtree 639 00:37:38.748 --> 00:37:44.038 And for cases where there is a quadtree 640 00:37:44.038 --> 00:37:48.163 Using a function of quadtree called DrawBounds 641 00:37:48.163 --> 00:37:50.700 The entire area that quadtree has 642 00:37:50.700 --> 00:37:52.827 will be drawn by the function being invoked 643 00:37:52.827 --> 00:37:56.598 If it isn't being operated, the tree value is null 644 00:37:56.598 --> 00:37:57.995 so they won't be drawn 645 00:37:59.510 --> 00:38:03.668 Now let's take a look at the DrawBounds function of quadtree 646 00:38:03.668 --> 00:38:06.781 For the case of DrawBounds function of quadtree 647 00:38:06.781 --> 00:38:10.441 It is simply delivering commands to root node 648 00:38:10.441 --> 00:38:16.005 It invokes the DrawBounds function that root node has 649 00:38:16.005 --> 00:38:19.705 If we take a look at this DrawBounds function that root node has 650 00:38:21.309 --> 00:38:23.678 It is placed in the bottom 651 00:38:23.678 --> 00:38:27.266 First, it draws the Wirecube of itself 652 00:38:27.266 --> 00:38:30.955 In other words, only the boundary 653 00:38:30.955 --> 00:38:35.589 It assigns the center and size to draw only the boundary 654 00:38:35.589 --> 00:38:42.420 Next, mark the object list in the center 655 00:38:42.420 --> 00:38:45.292 The object list which the current node has 656 00:38:45.292 --> 00:38:46.772 Using Label function 657 00:38:46.772 --> 00:38:50.550 Mark the object list in the center of the node 658 00:38:50.550 --> 00:38:53.322 Let's say there is a child to the node 659 00:38:53.322 --> 00:38:55.173 and if it is separated 660 00:38:55.173 --> 00:38:57.115 It gives an order to explore every child 661 00:38:57.115 --> 00:39:00.243 and draw a boundary 662 00:39:00.243 --> 00:39:03.224 But if this is the terminal node 663 00:39:03.224 --> 00:39:07.361 Only for the cases with current item 664 00:39:07.361 --> 00:39:12.233 a crosshair of the x-axis and y-axis 665 00:39:12.233 --> 00:39:15.500 A code that draws the crosshair has been added 666 00:39:19.371 --> 00:39:21.971 If every node has been drawn through this process 667 00:39:21.971 --> 00:39:24.520 Go back to the quadtree manager 668 00:39:24.520 --> 00:39:28.244 First, for the objects that have been inserted 669 00:39:28.244 --> 00:39:31.243 with this sky blue color, a bright blue color 670 00:39:31.243 --> 00:39:35.561 Color the inside through the DrawCube function 671 00:39:35.561 --> 00:39:37.530 and mark it 672 00:39:37.530 --> 00:39:40.238 For the objects that will be inserted later on 673 00:39:40.238 --> 00:39:45.995 A code has been implemented to color it red 674 00:39:45.995 --> 00:39:49.203 We have looked over the insert function of the quadtree 675 00:39:49.203 --> 00:39:54.540 Let's look over the result by implementing it once again 676 00:39:54.540 --> 00:39:55.866 Press play 677 00:39:59.005 --> 00:40:01.983 It being added one by one by dividing 678 00:40:01.983 --> 00:40:04.480 and the procedure of the drawing 679 00:40:04.480 --> 00:40:06.547 We have explained the code 680 00:40:06.547 --> 00:40:08.827 so I believe that you will be able to understand 681 00:40:08.827 --> 00:40:12.955 If you inspect it one step at a time by debugging it on your own 682 00:40:12.955 --> 00:40:14.827 It will be better for you 683 00:40:14.827 --> 00:40:19.757 Let's take a look at the implementation of query function 684 00:40:19.757 --> 00:40:25.718 For the query function, first go over to the scene 685 00:40:25.718 --> 00:40:29.312 Let's double click the quadtree query scene and open it 686 00:40:29.312 --> 00:40:32.906 Open the given scene and play it 687 00:40:36.084 --> 00:40:39.777 The 9 objects that we have set 688 00:40:39.777 --> 00:40:43.144 can be seen and already inserted 689 00:40:43.144 --> 00:40:47.787 The AABB area that is marked red on the screen and 690 00:40:47.787 --> 00:40:50.599 A query button on the game view 691 00:40:50.599 --> 00:40:53.520 I will press this 692 00:40:53.520 --> 00:40:54.991 If you press the query button 693 00:40:54.991 --> 00:40:58.540 The area will be marked yellow 694 00:40:58.540 --> 00:41:01.119 The object that overlaps with the area 695 00:41:01.119 --> 00:41:03.550 will be marked as purple 696 00:41:03.550 --> 00:41:07.876 And to every node that was searched to detect this 697 00:41:07.876 --> 00:41:11.946 The boundary has been colored with purple 698 00:41:11.946 --> 00:41:15.296 And next the area to proceed the query 699 00:41:15.296 --> 00:41:16.777 was marked red 700 00:41:16.777 --> 00:41:21.193 If you press the Query button, to determine the collision detection 701 00:41:21.193 --> 00:41:24.926 between the object that overlaps and the area 702 00:41:24.926 --> 00:41:26.485 The nodes that have been searched 703 00:41:26.485 --> 00:41:29.866 will be colored as purple 704 00:41:29.866 --> 00:41:34.550 This is the three query area that I have prepared 705 00:41:34.550 --> 00:41:37.767 For these query areas, as you can see 706 00:41:37.767 --> 00:41:40.340 It is assign from Query 1, 2, 3 707 00:41:40.340 --> 00:41:43.579 which is a game object 708 00:41:43.579 --> 00:41:47.094 Similar to what I did previously, this game project 709 00:41:47.094 --> 00:41:51.094 has a special tag attached called Query 710 00:41:51.094 --> 00:41:54.310 Then how this query function is implemented 711 00:41:54.310 --> 00:41:56.926 will be taught through looking at the code 712 00:41:56.926 --> 00:42:01.134 Going back to the quadtree manager 713 00:42:01.134 --> 00:42:03.007 For the query function 714 00:42:03.007 --> 00:42:05.510 This variable called DrawMode 715 00:42:05.510 --> 00:42:08.777 was assigned as a Query instead of Insert 716 00:42:08.777 --> 00:42:11.756 If you go to the actual Unity, this DrawMode 717 00:42:11.756 --> 00:42:14.490 can be seen set as a Query 718 00:42:14.490 --> 00:42:18.030 Then, during the initialization process 719 00:42:18.030 --> 00:42:21.926 Every object of the game object which is set as Query 720 00:42:21.926 --> 00:42:25.213 is saved in this place called queryObjects 721 00:42:25.213 --> 00:42:27.629 If the drawing mode is set as Query 722 00:42:27.629 --> 00:42:30.163 It invokes the InsertAll function 723 00:42:30.163 --> 00:42:33.031 It adds every game objects 724 00:42:33.031 --> 00:42:36.530 in this current insert object 725 00:42:36.530 --> 00:42:40.837 Then, we can start from every object being added 726 00:42:40.837 --> 00:42:44.351 when we operate query 727 00:42:44.351 --> 00:42:46.609 After the preparation is finished 728 00:42:46.609 --> 00:42:51.074 We invoke the Query function that is provided 729 00:42:51.074 --> 00:42:53.807 to operate the query 730 00:42:53.807 --> 00:42:58.252 The general mechanism is similar to what I explained 731 00:42:58.252 --> 00:43:00.922 So, it will proceed to a total of three objects 732 00:43:00.922 --> 00:43:04.470 Every time the button is pressed, it will proceed 733 00:43:04.470 --> 00:43:08.361 If you look at the canvas here, the button 734 00:43:08.361 --> 00:43:11.590 You can see the binding to the Query function 735 00:43:11.590 --> 00:43:12.955 You can see it over here 736 00:43:16.550 --> 00:43:20.589 For the case of Query function, the query has to be done now 737 00:43:20.589 --> 00:43:24.213 Every list of node that is possible needs to be brought 738 00:43:24.213 --> 00:43:26.990 Therefore, the ones with possibility 739 00:43:26.990 --> 00:43:29.886 to save the list of nodes 740 00:43:29.886 --> 00:43:31.953 A List object needs to be created 741 00:43:31.953 --> 00:43:35.906 and it is designed to pass as an argument 742 00:43:35.906 --> 00:43:40.619 And the instance of quadtree 743 00:43:40.619 --> 00:43:43.618 which actually executes the quadtree 744 00:43:43.618 --> 00:43:47.431 invokes the Query function 745 00:43:47.431 --> 00:43:52.361 Looking at the Query function, as we did before 746 00:43:52.361 --> 00:43:55.911 It invokes the Query function of root node 747 00:43:55.911 --> 00:44:00.441 bringing in every list of the node that is possible 748 00:44:00.441 --> 00:44:04.381 If the list of every node that is possible is brought in 749 00:44:04.381 --> 00:44:09.738 Every item in the list, every object list 750 00:44:09.738 --> 00:44:16.163 identifies every item that overlaps with the assigned area 751 00:44:16.163 --> 00:44:21.569 Adds to intersects which is a List object 752 00:44:21.569 --> 00:44:24.896 and the code is designed so that it will return 753 00:44:27.351 --> 00:44:31.629 Now, the function that searches for every possible node 754 00:44:31.629 --> 00:44:34.856 We will take a look at the Query function of this node 755 00:44:34.856 --> 00:44:37.876 Let's move over to the node's Query function 756 00:44:43.757 --> 00:44:49.005 Over here, it adds the current self first 757 00:44:49.005 --> 00:44:52.599 It adds the node of itself first 758 00:44:52.599 --> 00:44:56.193 And if it is divided 759 00:44:56.193 --> 00:44:59.378 Every child that is divided will 760 00:44:59.378 --> 00:45:02.252 invoke the Query function again 761 00:45:02.252 --> 00:45:05.021 It will proceed the call recursively 762 00:45:05.021 --> 00:45:08.401 using the GetQuads function that I've mentioned before 763 00:45:08.401 --> 00:45:14.500 Making sure that it will operate on the quadrant area that encloses the given area 764 00:45:14.500 --> 00:45:19.975 The logic was designed so that it could be operated in such effective way 765 00:45:19.975 --> 00:45:22.507 Through this, every node information 766 00:45:22.507 --> 00:45:25.500 that has overlapping possibility was acquired 767 00:45:25.500 --> 00:45:28.866 Now we will take a look at the drawing function 768 00:45:28.866 --> 00:45:31.246 The List that was brought 769 00:45:31.246 --> 00:45:35.936 will be saved to a variable of the manager called intersectObjects 770 00:45:35.936 --> 00:45:40.827 This could help with the drawing 771 00:45:40.827 --> 00:45:43.225 When drawing the queried area first 772 00:45:43.225 --> 00:45:45.203 Mark it with a red color 773 00:45:45.203 --> 00:45:46.888 For the queried area 774 00:45:46.888 --> 00:45:52.094 the logic was designed to mark it as yellow 775 00:45:52.094 --> 00:45:55.500 Next a variable called possibleNodes 776 00:45:55.500 --> 00:45:58.792 It meant every node 777 00:45:58.792 --> 00:46:00.866 that had the possibility of overlapping with the queried area 778 00:46:00.866 --> 00:46:05.500 So every node of that area was colored as purple 779 00:46:05.500 --> 00:46:09.960 Areas that are actually determined to overlap with the queried area 780 00:46:09.960 --> 00:46:12.639 which are called AABB area 781 00:46:12.639 --> 00:46:17.777 It was designed to be drawn with purple coloring 782 00:46:17.777 --> 00:46:19.830 This is it for today's lecture 783 00:46:19.830 --> 00:46:21.804 I appreciate your effort to take the class 784 00:46:21.804 --> 00:46:22.678 Thank you 785 00:46:22.966 --> 00:46:24.635 Quadtree Overview Overview of Quadtree In space partitioning, it refers to a tree-like data structure with four children Always has a complete tree form with all children filled 786 00:46:24.635 --> 00:46:26.133 Point quadtree: Used to find close location in a 2D plane efficiently Range quadtree: Used to find objects with overlapping areasin a 2D plane 787 00:46:26.133 --> 00:46:27.604 Usage of quadtree in games Detects collision handling of two objects in a 2D plane space Used for collision handling in 2D platformer 788 00:46:27.604 --> 00:46:28.754 Used for visibility check and collision handling in Top Down view shooter games Often use AABB bounding volume for collision handling 789 00:46:28.754 --> 00:46:29.887 Primarily used to filter unnecessary objects for detection 790 00:46:29.887 --> 00:46:32.810 Mechanism of Quadtree The basics of Quadtree Every node of quadtree has a unique rectangular AABB area and object list Creates rectangular AABB area that surrounds the area and assigns it as node 791 00:46:32.810 --> 00:46:35.114 The further it moves down to the child, it maintains the complete tree form with four children Object Insertion: Adds object with AABB area to a node's object List 792 00:46:35.114 --> 00:46:36.896 Collision query: Identifies the AABB area given from the object list of the node and the colliding object 793 00:46:36.896 --> 00:46:38.324 Mechanism of Quadtree Mechanism of Insert function Comparison of AABB area to insert the object and the AABB area of a quadtree 794 00:46:38.324 --> 00:46:39.500 Partitioning: Dividing the quadtree area into an even 4 and assigning each as a child node Partitioning is operated when the AABB area of the inserting object is enclosed of the child node's area 795 00:46:39.500 --> 00:46:40.639 When it lies on the boundary of current and child node's area, add to the object list of the current node Repeat recursively from the child node that is completely enclosed 796 00:46:40.639 --> 00:46:41.619 Generally regulated to a certain extent of depth The side length of a quadrant with certain depth Ldepth=W/2depth (W is the side length of root node) 797 00:46:41.619 --> 00:46:42.312 Mechanism of Query function Function to identify if the AABB area collides with the object inside the Quadtree Identifies the Quadrant node that encloses the AABB area which will be queried 798 00:46:42.312 --> 00:46:42.882 Searches for collision in the object list of each quadrant node