in reply to octtree using hashes

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]

Replies are listed 'Best First'.
Re^2: octtree using hashes
by holyghost (Beadle) on Nov 09, 2017 at 10:40 UTC
    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.
[reply]
[d/l]
[select]

      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.

[reply]
        Indeed, I needed the push operator to push a world object onto the key $level of the hash of levels. My system is not a general octtree but using octants which have world objects contained on their crossings. My level 0 in the hash of $self->{rootnodes} is the topmost octant. if there are any world objects in it such as a non-player character it has to switch octants for which walking around just diminishes the $self->{rootnodes}{$level} then should put it in a larger octant and so on. Now when you are walking around a low level (so bigger octants) you can turn off collision detection by measuring the corners contained in the rootnodes hash. This calculation can be done in a thread e.g. on a sorted list of world objects walking around in octants. The fact is if you are on a level within the rootnodes hash it might be that there are no objects within that octant as the values array of the $level key is empty, and so the thread can work further on. My octant subdivisor now goes to pixel level, it stops at e.g. $middlex <= 1, you can also stop at the intersection multiplicity where you cross a world object contained in 9 upper level cubes.
[reply]

In Section Seekers of Perl Wisdom