If you have problems with an algorithm, it usually helps to give a short description of how you think the algorithm should work, and to also show examples where your implementation of the algorithm fails to behave like you expect it to.

Your Octree divides the world into same-sized octants, but you never seem to check the subdivision of an octant into smaller octants. This will not give you the benefit of using an octree at all.

You have left the interesting parts of the octree implementation empty or I can't find them. You don't really show where you insert objects into the world, and you don't describe what ->update and ->draw should do. You only need to update an octree if objects actually move between octants.

Your collision checker only checks the top level of the octree for collisions, but if you find a potential collision of the object with an octant, you need to look into the objects within that octant for further collisions.

In your situation, I would read a book that discusses the algorithms for spatial trees, and inserting elements and updating the octree, and then reimplement that in Perl. Maybe it is easier and more instructive to start with a "quadtree" that only subdivides the plane instead of 3D space.

For your code, what is this line supposed to do:

$self->{rootnodes}{$level} .= $obj;
[download]

This is a $obj from @worldobjects :

use lib "../../HollyGame";

package Ultima8::WorldObject;

sub WorldObject {
        my ($class, $x, $y, $z, $w, $h, $d) = @_;

        $self = { x => $x, y => $y, z => $z, w => $w, h => $h, d => $d
+ };

        return bless $self, ref($class) || $class;
}
[download]

This is a instantiation of the hash octtree, which has an object in it which is collisioned against at 4000 / (2 * 20):

$self->{octtree} = Ultima8::OctTree->OctTree(4000,4000,200,(WorldObjec
+t->WorldObject(100,100,100,100,100,100)));
[download]

The line :

$self->{rootnodes}{$level} .= $obj;
[download]

concatenates an world object to the member rootnodes with a key which is a level in subdivision of the space (in 2) You check for 8 collisions which are the intersection of 2 squares, one above the other in an cube subdivision. The methods draw and update I haven't done yet.

Why do you "concatenate" objects?

I would assume that you keep a list of nodes, which is not done with the string concatenation operator ".", but by using push on an array(ref).

Also, the idea behind an octree is to have a hierarchical organisation (a tree), so that you don't have to check all octants but ideally only the top-level octant and not even all octants that actually contain the object(s) you want to check for collision.

sub build_rec {
        my ($self, $middlex, ...) = @_;

        my $middlex /= 2;
        ...;

        if ($middlex <= 1 or ...) {
                return;
        }
        
        ...;
        
}
[download]

Do yourself a big favor and use warnings and strict. Even if these modules do not explicitly identify all of them, they will at least alert you to many questionable practices in your code:

c:\@Work\Perl\monks>perl -MData::Dump -le
"use warnings;
 use strict;
 ;;
 my $br = build_rec(100);
 dd 'build_rec returned', $br;
 ;;
 sub build_rec {
   my ($middlex) = @_;
   ;;
   my $middlex /= 2;
   if ($middlex <= 1) { return; }
   ;;
   print qq{did not return. will do something useful.};
   return $middlex * 1_000;
   }
"
"my" variable $middlex masks earlier declaration in same scope at -e l
+ine 1.
Use of uninitialized value in division (/) at -e line 1.
("build_rec returned", undef)
[download]

• How do I post a question effectively?
• Markup in the Monastery

especially the <p> tag would help making your posts somehow readable.