I’m creating a FPS (not COD but almost !), and i need to handle players collisions with the objects on the map, terrain etc…
I chose to use an Octree because of the good performance it offers.
In fact, each time i open my game, i generate an octree based on the map and its childs
Then i manage all the collisions with the octree and a capsule for each player which handles their position
I’m checking the intersections between the capsule and the octree on each frame.
Everything works great, but the problem is the time it takes to generate the octree.
I have a large map (a city), and the octree’s generation takes at least 30 secs.
The map is static so it’s kind of stupid to generate it again and again, because it will always remains the same.
That’s why i was wondering if it was possible to store it somewhere.
I’ve tried to store it as a JSON but it doesn’t work.
As i’m building a multiplayer game, i tried to calculate it in the back, and send it to the front with a websocket, or a basic http request, but the octree is too heavy for that.
What do you mean by “it doesn’t work”? It’s possible to store pretty much any kind of data in a JSON, even binary if you’re into that - storing octree should actually be quite easy, since it’s just boundaries.
Not directly an answer to the question, but most likely an answer to your challenge overall (ie. there’s little reason for reinventing the wheel, if there’s a ready robust opensource alternative )
three-mesh-bvh: see this example and this example. Three-mesh-bvh runs on pure optimised magic, so using it may not only spare you all the unnecessary coding, but will also likely work faster
recast-navigation-js: this is a different approach to navigation in games (although a better one compared to raycasting, if you want to implement character movement and AI navigation.) You can combine it together with raycast collisions, since these are generally more expensive.
EDIT : Note it still takes a few seconds to load, but it’s only due to assets in the game (png, gltf etc…)
Before that, i needed to wait a 30s more only for the octree to be generated
I recommend storing an octree in a cool dry place, out of reach of children.
Sometimes it makes sense to store a spatial index, but in most cases like games - it’s typically faster to just rebuild it from scratch. Something like a morton code (spatial hash) bottom-up tree build is going to be ridiculously fast. That’s generally how raytracing GPU APIs do it.
However, if you are pressed to store a tree-like structure that references some objects. I recommend converting these references to integer IDs. In case of three.js - you already have an id field on Object3D that carries a unique integer value. So that might be a good start.
The tree itself can be stored in many different ways, one is to store a it as a flat list of nodes like so:
"nodes": [
{
"children": [2,3], // references indices of other nodes in this list
"data": [1337] // references IDs of objects stored in the tree
},
{
"children": [7,8],
"data": [555]
}
....
]
This is somewhat similar to how GLTF stores its data. For those curious, see spec.
I happen to have a need to store BVH data on occasion, when I do - I tend to go with binary serialization. My current BVH implementations ( yes, plural ) also work on binary data directly (ArrayBuffer) so serialization and deserialization is as simple as just reading/writing an ArrayBuffer and you’re done.
The advantage is obvious - you don’t need to copy data into a different format, you don’t need to “build” a new object structure etc. You just reference that binary data directly and use it, no parsing or any other complex logic required.
)
curious…