java - Data Structure and Algorithm for a 3D Volume? -

java - Data Structure and Algorithm for a 3D Volume? -

i've been tinkering minecraft bukkit plugin development, , working on need able define "volume" of space , determine when entity (player) moves outside volume within (or vice versa).

if restrict "volume" boxes, should simple. info construction can maintain x/y/z bounding integers (so 6 total integers) , calculating entry/exit given 2 points (movement , motion to) should matter of determining if a) 3 values within 3 ranges , b) @ to the lowest degree 1 value outside corresponding range.

(though if there's better, more performant way of storing , calculating this, i'm ears.)

however, if "volume" isn't simple box? suppose have oddly-shaped room , want enclose volume of room. could arrange multiple "volumes" individually fill overall space, result in false positives when entity moves 1 another.

not having worked in gaming or 3d engines before, i'm drawing blank on how might able construction this. occurs me problem has been solved , has known established patterns. essentially, i'm trying to:

define info construction can represent oddly-shaped volume of space (albeit @ to the lowest degree based on block coordinates). define algorithm which, given source , destination of movement, can determine if motion crossed boundary of defined space.

are there established patterns , practices this?

i don't know if has been used in kind of video game before, first thing came mind classic sieve of eratosthenes implementation, alter create boolean array 3d, , utilize keys coordinates. though x , y values can huge in minecraft, you'd want save space saving offset between world 0,0 position , selection, this:

class oddarea { static final int max_selection_size = 64; //or whatever public final int xoffset, yoffset; // 256 = chunk height public final boolean[][][] squares = new boolean[max_selection_size][max_selection_size][256]; oddarea() { this(0, 0); } oddarea(final int xoffset, final int yoffset) { this.xoffset = xoffset; this.yoffset = yoffset; } void addblock(final int x, final int y, final int z) { this.squares[x - this.xoffset][y - this.yoffset][z] = true; } boolean isinsidearea(final int x, final int y, final int z) { homecoming this.squares[x - this.xoffset][y - this.yoffset][z]; } }

z doesn't require offset minecraft world 256 blocks high.

the issue can think of setup you'd have know lowest x,y coordinates before start filling object

java algorithm data-structures 3d minecraft