Collisions/AABB.pm

filter: Statementstmt 92.3% 228 / 247 Branchbran 71.2% 67 / 94 Conditioncond 64.9% 37 / 57 MC/DCmcdc 41.3% 12 / 29 Subroutinesub 97.9% 48 / 49 Podpod 95.8% 23 / 24 totaltotal 83.0% 415 / 500 CC 68 SCAR 20.3
CC
68
Cov
83%
dump_tree
30.0
_prune
24.8
find_best_sibling_node
12.3
CRAP 7.7
↑ Summary Collisions.pm »
1 # Copyright (c) 2018 Timm Murray
2 # All rights reserved.
3 #
4 # Redistribution and use in source and binary forms, with or without
5 # modification, are permitted provided that the following conditions are met:
6 #
7 # * Redistributions of source code must retain the above copyright notice,
8 # this list of conditions and the following disclaimer.
9 # * Redistributions in binary form must reproduce the above copyright
10 # notice, this list of conditions and the following disclaimer in the
11 # documentation and/or other materials provided with the distribution.
12 #
13 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
14 # AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 # IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
16 # ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
17 # LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18 # CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19 # SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20 # INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21 # CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22 # ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
23 # POSSIBILITY OF SUCH DAMAGE.
24 package Game::Collisions::AABB;
25 22 $Game::Collisions::AABB::VERSION = '0.5';
26 22 ▶use utf8;
Subroutine BEGIN: called CC=1 SCAR=0.0
27 22 ▶use v5.14;
Subroutine BEGIN: called CC=1 SCAR=0.0
28 22 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
29 22 ▶use List::Util ();
Subroutine BEGIN: called CC=1 SCAR=0.0
30 22 ▶use Scalar::Util ();
Subroutine BEGIN: called CC=1 SCAR=0.0
31 22 ▶use Carp 'confess';
Subroutine BEGIN: called CC=1 SCAR=0.0
32  
33 22 ▶use constant _X => 0;
Subroutine BEGIN: called CC=1 SCAR=0.0
34 22 ▶use constant _Y => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
35 22 ▶use constant _LENGTH => 2;
Subroutine BEGIN: called CC=1 SCAR=0.0
36 22 ▶use constant _HEIGHT => 3;
Subroutine BEGIN: called CC=1 SCAR=0.0
37 22 ▶use constant _MAX_X => 4;
Subroutine BEGIN: called CC=1 SCAR=0.0
38 22 ▶use constant _MAX_Y => 5;
Subroutine BEGIN: called CC=1 SCAR=0.0
39 22 ▶use constant _PARENT_NODE => 6;
Subroutine BEGIN: called CC=1 SCAR=0.0
40 22 ▶use constant _LEFT_NODE => 7;
Subroutine BEGIN: called CC=1 SCAR=0.0
41 22 ▶use constant _RIGHT_NODE => 8;
Subroutine BEGIN: called CC=1 SCAR=0.0
42 22 ▶use constant _USER_DATA => 9;
Subroutine BEGIN: called CC=1 SCAR=0.0
43 22 ▶use constant _DO_CALL_USER_DATA => 10;
Subroutine BEGIN: called CC=1 SCAR=0.0
44  
45  
46 sub new
47 116 ▶{
Subroutine new: called CC=3 SCAR=11.0
Pod documented
48 116 my ($class, $args) = @_;
49 my $do_call_user_data = defined( $args->{user_data} )
50 && Scalar::Util::blessed( $args->{user_data} )
51 116 ▶ && $args->{user_data}->isa( 'Game::Collisions::UserData' );
Condition83%5/6
defined $args->{'user_data'} && builtin::blessed($args->{'user_data'}) && $args->{'user_data'}->isa('Game::Collisions::UserData')
!ll&&!rl&&r
11501
defined $args->{"user_data"} and builtin::blessed($args->{"user_data"})
!ll&&!rl&&r
11411
MC/DC66%2/3
defined $args->{'user_data'} && builtin::blessed($args->{'user_data'}) && $args->{'user_data'}->isa('Game::Collisions::UserData')
defined $args->{"user_data"} builtin::blessed($args->{"user_data"}) $args->{'user_data'}->isa('Game::Collisions::UserData')
Truth table75%3/4
A and B && C
A= defined $args->{"user_data"}B= builtin::blessed($args->{"user_data"})C= $args->{'user_data'}->isa('Game::Collisions::UserData')
ABCresult
0XX0
10X0
1100
1111
52 my $self = [
53 $args->{x},
54 $args->{y},
55 $args->{length},
56 $args->{height},
57 $args->{x} + $args->{length},
58 $args->{y} + $args->{height},
59 undef, # parent node
60 undef, # left node
61 undef, # right node
62 $args->{user_data},
63 116 $do_call_user_data,
64 ];
65  
66 116 bless $self => $class;
67 }
68  
69  
70 657 ▶sub x { $_[0]->[_X] }
Subroutine x: called CC=1 SCAR=0.0
Pod documented
71 656 ▶sub y { $_[0]->[_Y] }
Subroutine y: called CC=1 SCAR=0.0
Pod documented
72 298 ▶sub length { $_[0]->[_LENGTH] }
Subroutine length: called CC=1 SCAR=0.0
Pod documented
73 298 ▶sub height { $_[0]->[_HEIGHT] }
Subroutine height: called CC=1 SCAR=0.0
Pod documented
74 146 ▶sub left_node { $_[0]->[_LEFT_NODE] }
Subroutine left_node: called CC=1 SCAR=0.0
Pod documented
75 121 ▶sub right_node { $_[0]->[_RIGHT_NODE] }
Subroutine right_node: called CC=1 SCAR=0.0
Pod documented
76 185 ▶sub parent { $_[0]->[_PARENT_NODE] }
Subroutine parent: called CC=1 SCAR=0.0
Pod documented
77 3 ▶sub user_data { $_[0]->[_USER_DATA] }
Subroutine user_data: called CC=1 SCAR=0.0
Pod documented
78 2 ▶sub _do_call_user_data { $_[0]->[_DO_CALL_USER_DATA] }
Subroutine _do_call_user_data: called CC=1 SCAR=0.0
79  
80  
81 sub set_left_node
82 74 ▶{
Subroutine set_left_node: called CC=1 SCAR=0.0
Pod documented
83 74 my ($self, $node) = @_;
84 74 return $self->_set_node( $node, _LEFT_NODE );
85 }
86  
87 sub set_right_node
88 60 ▶{
Subroutine set_right_node: called CC=1 SCAR=0.0
Pod documented
89 60 my ($self, $node) = @_;
90 60 return $self->_set_node( $node, _RIGHT_NODE );
91 }
92  
93 sub set_parent
94 140 ▶{
Subroutine set_parent: called CC=1 SCAR=0.0
Pod documented
95 140 my ($self, $parent) = @_;
96 140 my $current_parent = $self->[_PARENT_NODE];
97 140 $self->[_PARENT_NODE] = $parent;
98 140 return $current_parent;
99 }
100  
101 sub set_user_data
102 1 ▶{
Subroutine set_user_data: called CC=3 SCAR=12.3
Pod documented
103 1 my ($self, $data) = @_;
104 1 ▶ my $do_call_user_data = defined( $data )
Condition33%2/6
defined $data && builtin::blessed($data) && $data->isa('Game::Collisions::UserData')
!ll&&!rl&&r
100
defined $data and builtin::blessed($data)
!ll&&!rl&&r
010
MC/DC0%0/3
defined $data && builtin::blessed($data) && $data->isa('Game::Collisions::UserData')
defined $data builtin::blessed($data) $data->isa('Game::Collisions::UserData')
Truth table25%1/4
A and B && C
A= defined $dataB= builtin::blessed($data)C= $data->isa('Game::Collisions::UserData')
ABCresult
0XX0
10X0
1100
1111
105 && Scalar::Util::blessed( $data )
106 && $data->isa( 'Game::Collisions::UserData' );
107 1 $self->[_USER_DATA] = $data;
108 1 $self->[_DO_CALL_USER_DATA] = $do_call_user_data;
109 1 return;
110 }
111  
112 sub resize_all_parents
113 32 ▶{
Subroutine resize_all_parents: called CC=3 SCAR=11.0
Pod documented
114 32 my ($self) = @_;
115  
116 32 my @nodes_to_resize = ($self);
117 32 ▶ while( @nodes_to_resize ) {
Branch: 1 branch
BranchTrueFalseTotal
if (@nodes_to_resize) 71 32 103
118 71 my $next_node = shift @nodes_to_resize;
119 71 ▶ push @nodes_to_resize, $next_node->parent
Branch: 1 branch
BranchTrueFalseTotal
if defined $next_node->parent 39 32 71
120 if defined $next_node->parent;
121 71 $next_node->_resize_to_fit_children;
122 }
123  
124 32 return;
125 }
126  
127 sub does_collide
128 123 ▶{
Subroutine does_collide: called CC=5 SCAR=16.1
Pod documented
129 123 my ($self, $other_object) = @_;
130 123 ▶ return 0 if $self == $other_object; # Does not collide with itself
Branch: 1 branch
BranchTrueFalseTotal
if $self == $other_object 20 103 123
131 103 my ($minx1, $miny1, $length1, $height1, $maxx1, $maxy1) = @$self;
132 103 my ($minx2, $miny2, $length2, $height2, $maxx2, $maxy2) = @$other_object;
133  
134 103 ▶ return $maxx1 >= $minx2
Condition88%8/9
$maxx1 >= $minx2 && $minx1 <= $maxx2 && $maxy1 >= $miny2 && $miny1 <= $maxy2
!ll&&!rl&&r
25078
$maxx1 >= $minx2 and $minx1 <= $maxx2 and $maxy1 >= $miny2
!ll&&!rl&&r
24178
$maxx1 >= $minx2 and $minx1 <= $maxx2
!ll&&!rl&&r
141079
MC/DC75%3/4
$maxx1 >= $minx2 && $minx1 <= $maxx2 && $maxy1 >= $miny2 && $miny1 <= $maxy2
$maxx1 >= $minx2 $minx1 <= $maxx2 $maxy1 >= $miny2 $miny1 <= $maxy2
Truth table80%4/5
A and B and C && D
A= $maxx1 >= $minx2B= $minx1 <= $maxx2C= $maxy1 >= $miny2D= $miny1 <= $maxy2
ABCDresult
0XXX0
10XX0
110X0
11100
11111
135 && $minx1 <= $maxx2
136 && $maxy1 >= $miny2
137 && $miny1 <= $maxy2;
138 }
139  
140 sub does_fully_enclose
141 4 ▶{
Subroutine does_fully_enclose: called CC=5 SCAR=16.8
Pod documented
142 4 my ($self, $other_object) = @_;
143 4 ▶ return 0 if $self == $other_object; # Does not collide with itself
Branch: 1 branch
BranchTrueFalseTotal
if $self == $other_object 0 4 4
144 4 my ($minx1, $miny1, $length1, $height1, $maxx1, $maxy1) = @$self;
145 4 my ($minx2, $miny2, $length2, $height2, $maxx2, $maxy2) = @$other_object;
146  
147 4 ▶ return $maxx1 >= $maxx2
Condition66%6/9
$maxx1 >= $maxx2 && $minx1 <= $minx2 && $maxy1 >= $maxy1 && $miny1 <= $miny2
!ll&&!rl&&r
202
$maxx1 >= $maxx2 and $minx1 <= $minx2 and $maxy1 >= $maxy1
!ll&&!rl&&r
202
$maxx1 >= $maxx2 and $minx1 <= $minx2
!ll&&!rl&&r
022
MC/DC25%1/4
$maxx1 >= $maxx2 && $minx1 <= $minx2 && $maxy1 >= $maxy1 && $miny1 <= $miny2
$maxx1 >= $maxx2 $minx1 <= $minx2 $maxy1 >= $maxy1 $miny1 <= $miny2
Truth table40%2/5
A and B and C && D
A= $maxx1 >= $maxx2B= $minx1 <= $minx2C= $maxy1 >= $maxy1D= $miny1 <= $miny2
ABCDresult
0XXX0
10XX0
110X0
11100
11111
148 && $minx1 <= $minx2
149 && $maxy1 >= $maxy1
150 && $miny1 <= $miny2;
151 }
152  
153 sub root
154 1 ▶{
Subroutine root: called CC=3 SCAR=11.0
Pod undocumented
155 1 my ($self) = @_;
156 1 ▶ return $self if ! defined $self->parent;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $self->parent 0 1 1
157
158 1 my $current_parent = $self->parent;
159 1 ▶ while( defined $current_parent->parent ) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $current_parent->parent) 2 1 3
160 2 $current_parent = $current_parent->parent;
161 }
162  
163 1 return $current_parent;
164 }
165  
166  
167  
168 sub find_best_sibling_node
169 34 ▶{
Subroutine find_best_sibling_node: called CC=10 SCAR=25.1
Pod documented
170 34 my ($self, $new_node) = @_;
171  
172 34 my @nodes_to_check = ($self);
173 34 ▶ while( @nodes_to_check ) {
Branch: 1 branch
BranchTrueFalseTotal
if (@nodes_to_check) 74 0 74
174 74 my $check_node = shift @nodes_to_check;
175 74 ▶ return $check_node if ! $check_node->is_branch_node;
Branch: 1 branch
BranchTrueFalseTotal
unless $check_node->is_branch_node 33 41 74
176  
177 41 my $left_node = $check_node->left_node;
178 41 my $right_node = $check_node->right_node;
179  
180 41 ▶ if(! defined $left_node ) {
Branch: 2 branches
BranchTrueFalseTotal
if (not defined $left_node) { } 1 40 41
elsif (not defined $right_node) { } 1 39 40
181 1 ▶ if(! $right_node->does_fully_enclose( $new_node ) ) {
Branch: 2 branches
BranchTrueFalseTotal
if (not $right_node->does_fully_enclose($new_node)) { } 1 0 1
elsif ($right_node->is_branch_node) { } 0 0 0
182 # No left node, and we don't enclose the right, so
183 # the right should be our sibling
184 1 return $right_node;
185 }
186 elsif( $right_node->is_branch_node ) {
187 # Since right node is a branch node, and we enclose it,
188 # descend further without doing anything else.
189 0 push @nodes_to_check, $right_node;
190 0 next;
191 }
192 else {
193 # Right node is a leaf and we enclose it, so it's our
194 # sibling now
195 0 return $right_node;
196 }
197 }
198 elsif(! defined $right_node ) {
199 1 ▶ if(! $left_node->does_fully_enclose( $new_node ) ) {
Branch: 2 branches
BranchTrueFalseTotal
if (not $left_node->does_fully_enclose($new_node)) { } 0 1 1
elsif ($left_node->is_branch_node) { } 1 0 1
200 # No right node, and we don't enclose the left, so
201 # the left should be our sibling
202 0 return $left_node;
203 }
204 elsif( $left_node->is_branch_node ) {
205 # Since left node is a branch node, and we enclose it,
206 # descend further without doing anything else
207 1 push @nodes_to_check, $left_node;
208 1 next;
209 }
210 else {
211 # Left node is a leaf and we enclose it, so it's our
212 # sibling now
213 0 return $left_node;
214 }
215 }
216  
217 # If we have both left and right nodes, then we have to decide which
218 # direction to go
219 39 my (undef, undef, $left_length, $left_height)
220 = $self->_calculate_bounding_box_for_nodes( $left_node, $new_node );
221 39 my (undef, undef, $right_length, $right_height)
222 = $self->_calculate_bounding_box_for_nodes( $right_node, $new_node);
223  
224 39 my $left_surface = $left_length * $left_height;
225 39 my $right_surface = $right_length * $right_height;
226 39 ▶ push @nodes_to_check,
Branch: 1 branch
BranchTrueFalseTotal
$left_surface > $right_surface ? : 7 32 39
227 ($left_surface > $right_surface) ? $right_node : $left_node;
228 }
229  
230 # How did we get here? It should have descended the tree until it
231 # came to the leaf and returned that. Just in case, return ourselves.
232 0 return $self;
233 }
234  
235 sub is_branch_node
236 265 ▶{
Subroutine is_branch_node: called CC=2 SCAR=6.9
Pod documented
237 265 my ($self) = @_;
238 265 ▶ return (defined $self->[_LEFT_NODE]) || (defined $self->[_RIGHT_NODE]);
Condition100%3/3
defined $self->[7] || defined $self->[8]
l!l&&r!l&&!r
184279
MC/DC100%2/2
defined $self->[7] || defined $self->[8]
defined $self->[7] defined $self->[8]
Truth table100%3/3
A || B
A= defined $self->[7]B= defined $self->[8]
ABresult
1X1
011
000
239 }
240  
241 sub dump_tree
242 0 ▶{
Subroutine dump_tree: not called CC=5 SCAR=34.0
Pod documented
243 0 my ($self, $spacing) = @_;
244 0 ▶ $spacing //= '';
Condition0%0/2
$spacing //= ""
l!l
00
MC/DC0%0/1
$spacing //= ""
$spacing
Truth table0%0/2
A
A= $spacing
Aresult
11
00
245  
246 0 ▶ my $draw_chars = $self->is_branch_node
Branch: 1 branch
BranchTrueFalseTotal
$self->is_branch_node ? : 0 0 0
247 ? '├┐'
248 : '│├';
249 0 my $str = "$spacing├┤ " . join( ', ',
250 "$self",
251 $self->x,
252 $self->y,
253 $self->length,
254 $self->height,
255 );
256 0 $str .= "\n";
257 0 ▶ $str .= $self->left_node->dump_tree( $spacing . '┼' )
Branch: 1 branch
BranchTrueFalseTotal
if defined $self->left_node 0 0 0
258 if defined $self->left_node;
259 0 ▶ $str .= $self->right_node->dump_tree( $spacing . '┼' )
Branch: 1 branch
BranchTrueFalseTotal
if defined $self->right_node 0 0 0
260 if defined $self->right_node;
261  
262 0 return $str;
263 }
264  
265 sub move
266 2 ▶{
Subroutine move: called CC=4 SCAR=13.9
Pod documented
267 2 my ($self, $args) = @_;
268 2 ▶ my $add_x = $args->{add_x} // 0;
Condition50%1/2
$args->{"add_x"} // 0
l!l
20
MC/DC0%0/1
$args->{"add_x"} // 0
$args->{"add_x"}
Truth table50%1/2
A
A= $args->{"add_x"}
Aresult
11
00
269 2 ▶ my $add_y = $args->{add_y} // 0;
Condition100%2/2
$args->{"add_y"} // 0
l!l
11
MC/DC100%1/1
$args->{"add_y"} // 0
$args->{"add_y"}
Truth table100%2/2
A
A= $args->{"add_y"}
Aresult
11
00
270  
271 2 $self->[_X] = $self->[_X] + $add_x;
272 2 $self->[_Y] = $self->[_Y] + $add_y;
273 2 $self->[_MAX_X] = $self->[_MAX_X] + $add_x;
274 2 $self->[_MAX_Y] = $self->[_MAX_Y] + $add_y;
275  
276 2 ▶ if( $self->_do_call_user_data ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->_do_call_user_data) 1 1 2
277 1 $self->user_data->on_aabb_move({
278 add_x => $add_x,
279 add_y => $add_y,
280 });
281 }
282 2 $self->_reinsert;
283 2 return;
284 }
285  
286 sub insert_new_aabb
287 32 ▶{
Subroutine insert_new_aabb: called CC=3 SCAR=11.0
Pod documented
288 32 my ($self, $new_node) = @_;
289 32 my $best_sibling = $self->find_best_sibling_node( $new_node );
290  
291 32 my $min_x = List::Util::min( $new_node->x, $best_sibling->x );
292 32 my $min_y = List::Util::min( $new_node->y, $best_sibling->y );
293  
294 32 my $new_branch = Game::Collisions::AABB->new({
295 x => $min_x,
296 y => $min_y,
297 length => 1,
298 height => 1,
299 });
300  
301 32 my $old_parent = $best_sibling->parent;
302 32 $new_branch->set_left_node( $new_node );
303 32 $new_branch->set_right_node( $best_sibling );
304  
305 32 my $new_root;
306 32 ▶ if(! defined $old_parent ) {
Branch: 1 branch
BranchTrueFalseTotal
if (not defined $old_parent) { } 10 22 32
307 # Happens when the root is going to be the new sibling. In this case,
308 # create a new node for the root.
309 10 $new_root = $new_branch;
310 }
311 else {
312 22 ▶ my $set_method = $best_sibling == $old_parent->left_node
Branch: 1 branch
BranchTrueFalseTotal
$best_sibling == $old_parent->left_node ? : 17 5 22
313 ? "set_left_node"
314 : "set_right_node";
315 22 $old_parent->$set_method( $new_branch );
316 }
317  
318 32 $new_branch->resize_all_parents;
319 32 return $new_root;
320 }
321  
322 sub suggested_rotation
323 3 ▶{
Subroutine suggested_rotation: called CC=3 SCAR=11.0
Pod documented
324 3 my ($self) = @_;
325 3 my $left_depth = $self->left_node->_depth(0);
326 3 my $right_depth = $self->right_node->_depth(0);
327 3 my $difference = abs( $left_depth - $right_depth );
328  
329 3 ▶ return $difference <= 1 ? 0 :
Branch: 2 branches
BranchTrueFalseTotal
$difference <= 1 ? : 2 1 3
$left_depth > $right_depth ? : 0 1 1
330 ($left_depth > $right_depth) ? -1 :
331 1;
332 }
333  
334 sub remove
335 5 ▶{
Subroutine remove: called CC=3 SCAR=11.0
Pod documented
336 5 my ($self) = @_;
337 5 ▶ confess "Can only remove leaf nodes" if $self->is_branch_node;
Branch: 1 branch
BranchTrueFalseTotal
if $self->is_branch_node 1 4 5
338  
339 4 my $parent = $self->parent;
340 4 $self->set_parent( undef );
341 # If there's only one node in the system, there will be no parent
342 4 ▶ $parent->_prune if defined $parent;
Branch: 1 branch
BranchTrueFalseTotal
if defined $parent 3 1 4
343  
344 4 return;
345 }
346  
347  
348 sub _prune
349 3 ▶{
Subroutine _prune: called CC=15 SCAR=32.1
350 3 my ($self) = @_;
351 3 ▶ return unless $self->is_branch_node;
Branch: 1 branch
BranchTrueFalseTotal
unless $self->is_branch_node 0 3 3
352 3 my $current_left = $self->left_node;
353 3 my $current_right = $self->right_node;
354  
355 # The main setters do things to try to keep things consistently
356 # connected, which isn't what we want here. Access internal strucutre
357 # directly.
358 3 ▶ if(
Branch: 1 branch
BranchTrueFalseTotal
if (defined $self->[7] and !defined($self->[7]->parent) || $self->[7]->parent != $self) 2 1 3
Condition66%4/6
defined $self->[7] and !defined($self->[7]->parent) || $self->[7]->parent != $self
!ll&&!rl&&r
012
not defined $self->[7]->parent or $self->[7]->parent != $self
l!l&&r!l&&!r
201
MC/DC33%1/3
defined $self->[7] and !defined($self->[7]->parent) || $self->[7]->parent != $self
defined $self->[7] not defined $self->[7]->parent $self->[7]->parent != $self
Truth table50%2/4
A and not(B) or C
A= defined $self->[7]B= not defined $self->[7]->parentC= $self->[7]->parent != $self
ABCresult
0XX0
1000
11X1
1011
359 (defined $self->[_LEFT_NODE])
360 && (
361 (! defined $self->[_LEFT_NODE]->parent)
362 || ($self->[_LEFT_NODE]->parent != $self)
363 )
364 ){
365 2 $self->[_LEFT_NODE][_PARENT_NODE] = undef;
366 2 $self->[_LEFT_NODE] = undef;
367 }
368 3 ▶ if(
Branch: 1 branch
BranchTrueFalseTotal
if (defined $self->[8] and !defined($self->[8]->parent) || $self->[8]->parent != $self) 1 2 3
Condition83%5/6
defined $self->[8] and !defined($self->[8]->parent) || $self->[8]->parent != $self
!ll&&!rl&&r
111
not defined $self->[8]->parent or $self->[8]->parent != $self
l!l&&r!l&&!r
101
MC/DC66%2/3
defined $self->[8] and !defined($self->[8]->parent) || $self->[8]->parent != $self
defined $self->[8] not defined $self->[8]->parent $self->[8]->parent != $self
Truth table75%3/4
A and not(B) or C
A= defined $self->[8]B= not defined $self->[8]->parentC= $self->[8]->parent != $self
ABCresult
0XX0
1000
11X1
1011
369 (defined $self->[_RIGHT_NODE])
370 && (
371 (! defined $self->[_RIGHT_NODE]->parent)
372 || ($self->[_RIGHT_NODE]->parent != $self)
373 )
374 ){
375 1 $self->[_RIGHT_NODE][_PARENT_NODE] = undef;
376 1 $self->[_RIGHT_NODE] = undef;
377 }
378  
379 # Don't need to continue if we're the root node
380 3 ▶ return if ! defined $self->parent;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $self->parent 2 1 3
381 1 ▶ if( (! defined $self->left_node) && (defined $self->right_node) ) {
Branch: 2 branches
BranchTrueFalseTotal
if (not defined $self->left_node and defined $self->right_node) { } 1 0 1
elsif (not defined $self->right_node and defined $self->left_node) { } 0 0 0
Condition33%1/3
not defined $self->left_node and defined $self->right_node
!ll&&!rl&&r
001
MC/DC0%0/2
not defined $self->left_node and defined $self->right_node
not defined $self->left_node defined $self->right_node
Truth table33%1/3
not(A) and B
A= not defined $self->left_nodeB= defined $self->right_node
ABresult
0X0
100
111
382 # Have right node but no left. Attach right node to our parent.
383 1 ▶ if( $self->parent->right_node == $self ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->parent->right_node == $self) { } 1 0 1
384 1 $self->parent->set_right_node( $current_right );
385 }
386 else {
387 0 $self->parent->set_left_node( $current_right );
388 }
389 }
390 ▶ elsif( (! defined $self->right_node) && (defined $self->left_node) ) {
Condition0%0/3
not defined $self->right_node and defined $self->left_node
!ll&&!rl&&r
000
MC/DC0%0/2
not defined $self->right_node and defined $self->left_node
not defined $self->right_node defined $self->left_node
Truth table0%0/3
not(A) and B
A= not defined $self->right_nodeB= defined $self->left_node
ABresult
0X0
100
111
391 # Have left node but no right. Attach left node to our parent.
392 0 ▶ if( $self->parent->right_node == $self ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->parent->right_node == $self) { } 0 0 0
393 0 $self->parent->set_right_node( $current_left );
394 }
395 else {
396 0 $self->parent->set_left_node( $current_right );
397 }
398 }
399  
400 1 $self->[_PARENT_NODE] = undef;
401 1 return;
402 }
403  
404 sub _depth
405 12 ▶{
Subroutine _depth: called CC=3 SCAR=11.0
406 12 my ($self, $depth_so_far) = @_;
407 # TODO reimplement in iterative way
408 12 ▶ return $depth_so_far + 1 if ! $self->is_branch_node;
Branch: 1 branch
BranchTrueFalseTotal
unless $self->is_branch_node 9 3 12
409 3 my $left_depth = $self->left_node->_depth( $depth_so_far + 1 );
410 3 my $right_depth = $self->right_node->_depth( $depth_so_far + 1 );
411  
412 3 ▶ return $left_depth > $right_depth
Branch: 1 branch
BranchTrueFalseTotal
$left_depth > $right_depth ? : 1 2 3
413 ? $left_depth
414 : $right_depth;
415 }
416  
417 sub _reinsert
418 3 ▶{
Subroutine _reinsert: called CC=3 SCAR=11.0
419 3 my ($self) = @_;
420 3 my $current_parent = $self->parent;
421 3 ▶ return if ! defined $current_parent;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $current_parent 1 2 3
422 2 $self->_detach_from_parent;
423  
424 2 ▶ while( defined( my $possible_root = $current_parent->parent ) ) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined(my $possible_root = $current_parent->parent)) 2 2 4
425 2 $current_parent = $possible_root;
426 }
427  
428 # $current_parent will now be the root of the tree
429 2 $current_parent->insert_new_aabb( $self );
430 2 return;
431 }
432  
433 sub _detach_from_parent
434 4 ▶{
Subroutine _detach_from_parent: called CC=6 SCAR=18.1
435 4 my ($self) = @_;
436 4 my $current_parent = $self->parent;
437 4 ▶ return unless defined $current_parent;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $current_parent 0 4 4
438  
439 4 my $current_grandparent = $current_parent->parent;
440 4 my $is_left = ($current_parent->left_node() == $self);
441 4 ▶ if(! defined $current_grandparent ) {
Branch: 1 branch
BranchTrueFalseTotal
if (not defined $current_grandparent) { } 2 2 4
442 # Parent must have been root. Just detach ourselves.
443 2 ▶ if( $is_left ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($is_left) { } 1 1 2
444 1 $current_parent->set_left_node( undef );
445 }
446 else {
447 1 $current_parent->set_right_node( undef );
448 }
449 }
450 else {
451 # Our parent is removed, and our sibling takes its place in the
452 # grandparent
453 2 ▶ my $sibling = $is_left
Branch: 1 branch
BranchTrueFalseTotal
$is_left ? : 2 0 2
454 ? $current_parent->right_node
455 : $current_parent->left_node;
456 2 my $is_parent_left
457 = ($current_grandparent->left_node == $current_parent);
458  
459 2 ▶ if( $is_parent_left ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($is_parent_left) { } 2 0 2
460 2 $current_grandparent->set_left_node( $sibling );
461 }
462 else {
463 0 $current_grandparent->set_right_node( $sibling );
464 }
465 }
466
467 4 $self->set_parent( undef );
468 4 return;
469 }
470  
471  
472  
473 sub _set_node
474 134 ▶{
Subroutine _set_node: called CC=3 SCAR=11.0
475 134 my ($self, $node, $index) = @_;
476 134 ▶ Scalar::Util::unweaken( $self->[$index] )
Branch: 1 branch
BranchTrueFalseTotal
if defined $self->[$index] 27 107 134
477 if defined $self->[$index];
478 134 $self->[$index] = $node;
479 134 Scalar::Util::weaken( $self->[$index] );
480 134 ▶ my $former_parent = defined $node
Branch: 1 branch
BranchTrueFalseTotal
defined $node ? : 132 2 134
481 ? $node->set_parent( $self )
482 : undef;
483 134 return $former_parent;
484 }
485  
486 sub _resize_to_fit_children
487 71 ▶{
Subroutine _resize_to_fit_children: called CC=2 SCAR=6.9
488 71 my ($self) = @_;
489 71 ▶ return if ! $self->is_branch_node;
Branch: 1 branch
BranchTrueFalseTotal
unless $self->is_branch_node 0 71 71
490 71 my ($x, $y, $length, $height) = $self->_calculate_bounding_box_for_nodes(
491 $self->[_LEFT_NODE],
492 $self->[_RIGHT_NODE],
493 );
494  
495 71 $self->[_X] = $x;
496 71 $self->[_Y] = $y;
497 71 $self->[_LENGTH] = $length;
498 71 $self->[_HEIGHT] = $height;
499 71 $self->[_MAX_X] = $x + $length;
500 71 $self->[_MAX_Y] = $y + $height;
501  
502 71 return;
503 }
504  
505 sub _calculate_bounding_box_for_nodes
506 149 ▶{
Subroutine _calculate_bounding_box_for_nodes: called CC=3 SCAR=11.0
507 149 my ($self, $node1, $node2) = @_;
508 149 ▶ return @$node1[_X, _Y, _LENGTH, _HEIGHT] if ! defined $node2;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $node2 1 148 149
509 148 ▶ return @$node2[_X, _Y, _LENGTH, _HEIGHT] if ! defined $node1;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $node1 0 148 148
510  
511 148 my $min_x = List::Util::min( $node1->x, $node2->x );
512 148 my $min_y = List::Util::min( $node1->y, $node2->y );
513 148 my $max_x = List::Util::max(
514 $node1->length + $node1->x,
515 $node2->length + $node2->x,
516 );
517 148 my $max_y = List::Util::max(
518 $node1->height + $node1->y,
519 $node2->height + $node2->y,
520 );
521  
522 148 my $length = $max_x - $min_x;
523 148 my $height = $max_y - $min_y;
524 148 return ($min_x, $min_y, $length, $height);
525 }
526  
527  
528 22 1;
529 __END__
↑ Summary Collisions.pm »