Hi fellow monks, I've tried to alleviate an octtree by using a hash of levels where each level stands for 8 smaller cubes within the first. I show you the code with keeping in mind that if I add each worldobject ($obj) to a lower level I should gain speed. This code was used for remaking Ultima8 - pagan, the dos game. The meaning is to add world objects to the level's hash number with a collision detection on the side. I do not know if I made any mistakes or if it works out of the box but if you can help out the algorithm I'd be glad. The thing is you walk around in ultima 8 on mostly non-enormously mountainous areas, even if this would be coded into an octtree after my build method you can hash out enemies and use e.g. another real octtree for the level of platforms you're at. Especially you walk around on a a level which are mostly done with calculation in a thread where you know where you are as you walk around upper levels when you are on a mostly plain area and where you walk on lower levels which are more subdivided cubes containing more world objects with each cube corner a collision with a world object and thus that world object shall be put into the hash of rootnodes at the specified level of collision. You walk around levels with only collisions on its subsides which leaves you walking on a higher dimensional cube without colliding except when you exit the cube. As withi an octtree you only have to check 8 sides of your cube when colliding as the corner may be contained by your world object. If you have a world object which is intersected by a cube you can immediately check for a collision (also you do not encounter world objects which are bigger than your cube as you walk on cube's sides. Thus a thread can check for collision only when your game timer only _can_ encounter any cubes without objects e.g. when you are walking in a cube without objects in it (the $level) you can not check collision detection. The lower the level, the higher dimensions of your cube, the less you encounter as you are generally more away from its sides (corners enveloped by world objects). 
use lib "../../HollyGame";

package Ultima8::OctTree;

sub OctTree {
        my ($class, $worldwidth, $worldheight, $worlddepth, @worldobje
+cts) = @_;

        $self = { worldwidth => $worldwidth, worldheight => $worldheig
+ht, worlddepth => $worlddepth };
        $self->{level} = 0;
        $self->{rootnodes} = {};

        bless $self, ref($class) || $class;
        $self->build_rec($self->{worldwidth}, $self->{worldheight},
                        $self->{worlddepth}, $self->{worldwidth},
                        $self->{worldheight}, $self->{worlddepth},
                        $self->{level}, @worldobjects);

        return $self;
}

sub build_rec {
        my ($self, $middlex, $middley, $middlez, $worldwidth, $worldhe
+ight, $worlddepth, $level, @worldobjects) = @_;

        my $middlex /= 2;
        my $middley /= 2;
        my $middlez /= 2;
        my $worldwidth /= 2;
        my $worldheight /= 2;
        my $worlddepth /= 2;

        if ($middlex <= 1 or $middley <= 1 or $middlez <= 1) {
                return;
        }


        my @nextobjects = @worldobjects;

        foreach $obj (@worldobjects) {
                if (collision_object_with_divisor($obj, $middlex, $mid
+dley, $middleyz)) {
                        $self->{rootnodes}{$level} .= $obj;
                        splice(@nextobjects, $obj, 1);
                }
        }

        $self->build_rec($middlex, $middley, $middlez,$worldwidth, $wo
+rldheight, $worlddepth, $level++, @nextobjects);
        $self->build_rec($middlex + $worldwidth, $middley - $worldheig
+ht, $middlez - $worlddepth,$worldwidth, $worldheight, $worlddepth, $l
+evel, @nextobjects);
        $self->build_rec($middlex - $worldwidth, $middley + $worldheig
+ht, $middlez - $worlddepth,$worldwidth, $worldheight, $worlddepth, $l
+evel, @nextobjects);
        $self->build_rec($middlex + $worldwidth, $middley + $worldheig
+ht, $middlez - $worlddepth,$worldwidth, $worldheight, $worlddepth, $l
+evel, @nextobjects);
        $self->build_rec($middlex - $worldwidth, $middley - $worldheig
+ht, $middlez + $worlddepth,$worldwidth, $worldheight, $worlddepth, $l
+evel, @nextobjects);
        $self->build_rec($middlex + $worldwidth, $middley - $worldheig
+ht, $middlez + $worlddepth,$worldwidth, $worldheight, $worlddepth, $l
+evel, @nextobjects);
        $self->build_rec($middlex - $worldwidth, $middley + $worldheig
+ht, $middlez + $worlddepth,$worldwidth, $worldheight, $worlddepth, $l
+evel, @nextobjects);
        $self->build_rec($middlex + $worldwidth, $middley + $worldheig
+ht, $middlez + $worlddepth,$worldwidth, $worldheight, $worlddepth, $l
+evel, @nextobjects);
}

sub collision_object_with_divisor {
        my ($self, $obj, $x, $y, $z) = @_;

                if ($obj->{x} > $x and $obj->{x} + $obj->{w} < $x) {
                        return 0;
                }
                if ($obj->{y} > $y and $obj->{y} + $obj->{h} < $y) {
                        return 0;
                }
                if ($obj->{z} > $z and $obj->{z} + $obj->{d} < $z) {
                        return 0;
                }
        return 1;
}


sub update {
}

sub draw {
}

[download]

In reply to octtree using hashes by holyghost

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.