| 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; | ||||||||||||||||||||||||||||
| 25 | 22 | $Game::Collisions::VERSION = '0.5'; | |||||||||||||||||||||||||||
| 26 | 22 | ▶ | use v5.14; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 27 | 22 | ▶ | use warnings; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 28 | 22 | ▶ | use List::Util (); | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 29 | |||||||||||||||||||||||||||||
| 30 | 22 | ▶ | use Game::Collisions::AABB; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 31 | |||||||||||||||||||||||||||||
| 32 | # ABSTRACT: Fast, pure Perl collision 2D detection | ||||||||||||||||||||||||||||
| 33 | |||||||||||||||||||||||||||||
| 34 | |||||||||||||||||||||||||||||
| 35 | sub new | ||||||||||||||||||||||||||||
| 36 | 10 | ▶ | { | ||||||||||||||||||||||||||
|
Subroutine
new: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||
| 37 | 10 | my ($class) = @_; | |||||||||||||||||||||||||||
| 38 | 10 | my $self = { | |||||||||||||||||||||||||||
| 39 | root_aabb => undef, | ||||||||||||||||||||||||||||
| 40 | all_aabbs => {}, | ||||||||||||||||||||||||||||
| 41 | }; | ||||||||||||||||||||||||||||
| 42 | 10 | bless $self => $class; | |||||||||||||||||||||||||||
| 43 | |||||||||||||||||||||||||||||
| 44 | |||||||||||||||||||||||||||||
| 45 | 10 | return $self; | |||||||||||||||||||||||||||
| 46 | } | ||||||||||||||||||||||||||||
| 47 | |||||||||||||||||||||||||||||
| 48 | |||||||||||||||||||||||||||||
| 49 | sub make_aabb | ||||||||||||||||||||||||||||
| 50 | 36 | ▶ | { | ||||||||||||||||||||||||||
|
Subroutine
make_aabb: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||
| 51 | 36 | my ($self, $args) = @_; | |||||||||||||||||||||||||||
| 52 | 36 | my $aabb = Game::Collisions::AABB->new( $args ); | |||||||||||||||||||||||||||
| 53 | 36 | $self->_add_aabb( $aabb ); | |||||||||||||||||||||||||||
| 54 | 36 | return $aabb; | |||||||||||||||||||||||||||
| 55 | } | ||||||||||||||||||||||||||||
| 56 | |||||||||||||||||||||||||||||
| 57 | sub get_collisions | ||||||||||||||||||||||||||||
| 58 | 5 | ▶ | { | ||||||||||||||||||||||||||
|
Subroutine
get_collisions: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||
| 59 | 5 | my ($self) = @_; | |||||||||||||||||||||||||||
| 60 | 5 | my @aabbs_to_check = values %{ $self->{all_aabbs} }; | |||||||||||||||||||||||||||
| 61 | 5 | my @collisions; | |||||||||||||||||||||||||||
| 62 | |||||||||||||||||||||||||||||
| 63 | 5 | foreach my $aabb (@aabbs_to_check) { | |||||||||||||||||||||||||||
| 64 | 20 | push @collisions => $self->get_collisions_for_aabb( $aabb ); | |||||||||||||||||||||||||||
| 65 | } | ||||||||||||||||||||||||||||
| 66 | |||||||||||||||||||||||||||||
| 67 | 5 | return @collisions; | |||||||||||||||||||||||||||
| 68 | } | ||||||||||||||||||||||||||||
| 69 | |||||||||||||||||||||||||||||
| 70 | sub get_collisions_for_aabb | ||||||||||||||||||||||||||||
| 71 | 20 | ▶ | { | ||||||||||||||||||||||||||
|
Subroutine
get_collisions_for_aabb: called CC=8 SCAR=20.8
Pod
documented
| |||||||||||||||||||||||||||||
| 72 | 20 | my ($self, $aabb) = @_; | |||||||||||||||||||||||||||
| 73 | 20 | ▶ | return () if ! defined $self->{root_aabb}; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 74 | 20 | my @collisions; | |||||||||||||||||||||||||||
| 75 | |||||||||||||||||||||||||||||
| 76 | 20 | my @nodes_to_check = ($self->{root_aabb}); | |||||||||||||||||||||||||||
| 77 | 20 | ▶ | while( @nodes_to_check ) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 78 | 95 | my $check_node = shift @nodes_to_check; | |||||||||||||||||||||||||||
| 79 | |||||||||||||||||||||||||||||
| 80 | 95 | ▶ | if( $check_node->is_branch_node ) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 81 | 63 | my $left_node = $check_node->left_node; | |||||||||||||||||||||||||||
| 82 | 63 | my $right_node = $check_node->right_node; | |||||||||||||||||||||||||||
| 83 | |||||||||||||||||||||||||||||
| 84 | 63 | ▶ | if( defined $left_node && $left_node->does_collide( $aabb ) ) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition66%2/3
defined $left_node and $left_node->does_collide($aabb)
MC/DC50%1/2
defined $left_node and $left_node->does_collide($aabb)
defined $left_node
$left_node->does_collide($aabb)
Truth table66%2/3
A and B
A= defined $left_nodeB= $left_node->does_collide($aabb)
| |||||||||||||||||||||||||||||
| 85 | 53 | push @nodes_to_check, $left_node; | |||||||||||||||||||||||||||
| 86 | } | ||||||||||||||||||||||||||||
| 87 | 63 | ▶ | if( defined $right_node && $right_node->does_collide( $aabb ) ) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
defined $right_node and $right_node->does_collide($aabb)
MC/DC100%2/2
defined $right_node and $right_node->does_collide($aabb)
defined $right_node
$right_node->does_collide($aabb)
Truth table100%3/3
A and B
A= defined $right_nodeB= $right_node->does_collide($aabb)
| |||||||||||||||||||||||||||||
| 88 | 22 | push @nodes_to_check, $right_node; | |||||||||||||||||||||||||||
| 89 | } | ||||||||||||||||||||||||||||
| 90 | } | ||||||||||||||||||||||||||||
| 91 | else { | ||||||||||||||||||||||||||||
| 92 | # We already know it collided, since it wouldn't be added | ||||||||||||||||||||||||||||
| 93 | # to @nodes_to_check otherwise. | ||||||||||||||||||||||||||||
| 94 | 32 | push @collisions, [ $aabb, $check_node ]; | |||||||||||||||||||||||||||
| 95 | } | ||||||||||||||||||||||||||||
| 96 | } | ||||||||||||||||||||||||||||
| 97 | |||||||||||||||||||||||||||||
| 98 | 20 | return @collisions; | |||||||||||||||||||||||||||
| 99 | } | ||||||||||||||||||||||||||||
| 100 | |||||||||||||||||||||||||||||
| 101 | sub get_collisions_for_aabb_bruteforce | ||||||||||||||||||||||||||||
| 102 | 0 | ▶ | { | ||||||||||||||||||||||||||
|
Subroutine
get_collisions_for_aabb_bruteforce: not called CC=1 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||
| 103 | 0 | my ($self, $aabb) = @_; | |||||||||||||||||||||||||||
| 104 | 0 | my @aabbs = values %{ $self->{all_aabbs} }; | |||||||||||||||||||||||||||
| 105 | |||||||||||||||||||||||||||||
| 106 | 0 | my @collisions = grep { $_->does_collide( $aabb ) } @aabbs; | |||||||||||||||||||||||||||
| 107 | 0 | return @collisions; | |||||||||||||||||||||||||||
| 108 | } | ||||||||||||||||||||||||||||
| 109 | |||||||||||||||||||||||||||||
| 110 | sub rebalance_tree | ||||||||||||||||||||||||||||
| 111 | 1 | ▶ | { | ||||||||||||||||||||||||||
|
Subroutine
rebalance_tree: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||
| 112 | 1 | my ($self) = @_; | |||||||||||||||||||||||||||
| 113 | 1 | my @aabbs = values %{ $self->{all_aabbs} }; | |||||||||||||||||||||||||||
| 114 | 1 | $self->{all_aabbs} = {}; | |||||||||||||||||||||||||||
| 115 | |||||||||||||||||||||||||||||
| 116 | 1 | my $new_root = $self->_new_meta_aabb({ | |||||||||||||||||||||||||||
| 117 | x => 0, | ||||||||||||||||||||||||||||
| 118 | y => 0, | ||||||||||||||||||||||||||||
| 119 | length => 1, | ||||||||||||||||||||||||||||
| 120 | height => 1, | ||||||||||||||||||||||||||||
| 121 | }); | ||||||||||||||||||||||||||||
| 122 | 1 | $self->{root_aabb} = $new_root; | |||||||||||||||||||||||||||
| 123 | 1 | $self->_add_aabb( $_ ) for @aabbs; | |||||||||||||||||||||||||||
| 124 | |||||||||||||||||||||||||||||
| 125 | 1 | return; | |||||||||||||||||||||||||||
| 126 | } | ||||||||||||||||||||||||||||
| 127 | |||||||||||||||||||||||||||||
| 128 | sub root | ||||||||||||||||||||||||||||
| 129 | 1 | ▶ | { | ||||||||||||||||||||||||||
|
Subroutine
root: called CC=1 SCAR=0.0
Pod
undocumented
| |||||||||||||||||||||||||||||
| 130 | 1 | my ($self) = @_; | |||||||||||||||||||||||||||
| 131 | 1 | return $self->{root_aabb}; | |||||||||||||||||||||||||||
| 132 | } | ||||||||||||||||||||||||||||
| 133 | |||||||||||||||||||||||||||||
| 134 | |||||||||||||||||||||||||||||
| 135 | sub _add_aabb | ||||||||||||||||||||||||||||
| 136 | 40 | ▶ | { | ||||||||||||||||||||||||||
|
Subroutine
_add_aabb: called CC=3 SCAR=11.0
| |||||||||||||||||||||||||||||
| 137 | 40 | my ($self, $new_node) = @_; | |||||||||||||||||||||||||||
| 138 | |||||||||||||||||||||||||||||
| 139 | 40 | ▶ | if(! defined $self->{root_aabb} ) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 140 | 10 | $self->{root_aabb} = $new_node; | |||||||||||||||||||||||||||
| 141 | } | ||||||||||||||||||||||||||||
| 142 | else { | ||||||||||||||||||||||||||||
| 143 | 30 | my $new_root = $self->{root_aabb}->insert_new_aabb( $new_node ); | |||||||||||||||||||||||||||
| 144 | 30 | ▶ | $self->{root_aabb} = $new_root if defined $new_root; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 145 | } | ||||||||||||||||||||||||||||
| 146 | |||||||||||||||||||||||||||||
| 147 | 40 | $self->{all_aabbs}{"$new_node"} = $new_node; | |||||||||||||||||||||||||||
| 148 | 40 | return; | |||||||||||||||||||||||||||
| 149 | } | ||||||||||||||||||||||||||||
| 150 | |||||||||||||||||||||||||||||
| 151 | sub _new_meta_aabb | ||||||||||||||||||||||||||||
| 152 | 1 | ▶ | { | ||||||||||||||||||||||||||
|
Subroutine
_new_meta_aabb: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 153 | 1 | my ($self, $args) = @_; | |||||||||||||||||||||||||||
| 154 | 1 | my $aabb = Game::Collisions::AABB->new( $args ); | |||||||||||||||||||||||||||
| 155 | 1 | return $aabb; | |||||||||||||||||||||||||||
| 156 | } | ||||||||||||||||||||||||||||
| 157 | |||||||||||||||||||||||||||||
| 158 | |||||||||||||||||||||||||||||
| 159 | 22 | 1; | |||||||||||||||||||||||||||
| 160 | __END__ | ||||||||||||||||||||||||||||