Investigate possible link between binary search trees in scenario BMSCD and scenario BMSNAV

randovania / mercury-engine-data-structures

Construct type definitions for Mercury Engine.

MIT License

2 stars 11 forks source link

Investigate possible link between binary search trees in scenario BMSCD and scenario BMSNAV #244

Open steven11sjf opened 5 days ago

steven11sjf commented 5 days ago

Seem like very similar structures:

both have a rectangle to check if a point is in
the second value in the tree seems to have 0x8000 in it sometimes, which I think is pointing at polys similar to how navmesh with the inverse flag point at areas
the bmscd contains a bunch of room borders, which i think could be the "source" for the map? (both the bmsnav and the bmmap).
unsure what the material_attribute is but it changes along w/ points, could be something extrapolated to create the contained geometry?

duncathan commented 4 days ago

btw these "binary search trees" you're talking about are probably octrees, which is a more specific and more concise name

steven11sjf commented 4 days ago

btw these "binary search trees" you're talking about are probably octrees, which is a more specific and more concise name

Octrees are 8 square cubes right? These are closer to quadtrees, but I think they're generated based on subdividing the area of the areas or something. Unless I misunderstood how octrees work in Wikipedia. (Also I renamed it based on the bmscd files using bst instead of quadtree).

duncathan commented 4 days ago

ah yeah if they're ignoring the Z axis they'd be quadtrees