First Person Game - Data Structure Techniques

Hi there,

I’m looking for some guidance on the best approach to developing a first person game. The game will be in a retro style (low detail, low resolution) and a combination of corridor / open-world (it takes place in a City so both inside buildings and city streets).

My thought being that an Octree data structure would probably be ok for both the city streets sections as well as the inside sections - though I guess a BSP structure might technically be more performant for indoors I think the technical overhead is too high for me to comtemplate it. I see that Babylon supports the Octree structure and wanted to check with you peeps as to whether I’m on the right track? I presume a ‘city’ could be created inside the Octree and it would be reasonably simple to do with Babylon? (Or maybe even Octree is overkill and Quadtree would be better).

Assuming Octree is the way to go, I guess I would create the buildings in something like Blender and export for use by Babylon, I presume it wouldn’t be too hard to then add them to the Octree? I’m not entirely sure how to go about division of roads, sidewalks and alleyways with regards to insertion into the Octree… Last time I played with game design was using Hammer from Half-Life 1, so you just designed the level in 1 big chunk and Hammer divided it according via BSP and all you had to do was load the file in the engine. I’m assuming there is nothing similar for Babylon that would let me put 1 large mesh into an Octree automatically?

Thanks for the help, I appreciate that the question is somewhat high-level so any help is appreciated.


Hi JayBeeDeku,

First of all, welcome to Babylon!

How big is this world you’re developing? If the world isn’t too big, or if we only ever participate in a little of it at a time, the data structures you’re talking about might be a little more low-level than you need to go. Unless your world is extremely detailed, or you can travel through it at ludicrous speed such that you can “experience” a large amount of world in a short time, you can probably fit a reasonable amount of playable area into memory at the same time.

One fairly common approach to this problem is chunking, which organizes the world spatially into “chunks” that get loaded and unloaded as the player traverses the world. This is kind of similar to the spatial trees you mentioned, but it’s usually implemented as a 2D (or 3D) array rather than a tree, since chunks can be identified uniquely just from player coordinates. If you’re looking for an example of this in action, check out the NOA Engine, a voxel engine built on Babylon.js that’s used to power Minecraft Classic.

As for the rest of the question… Sounds like an awesome (but big) project. :smiley: Depending on where you want to take this, you could approach the city problem a lot of different ways. Creating buildings in Blender and loading them into Babylon should work (Babylon has a bunch of importers, including for glTF, OBJ, and custom .babylon files). Cities are also one of the classic procedural generation use cases, which is complicated but might be more practical if you’re considering really big environments. Looks like somebody wrote an article a long time ago about a fairly simplistic procedural city in JavaScript. That project used 2013-era Three.js, but something similar should be at least as easy or easier in modern Babylon.js. :smile:

Hey SyntheticMagus!

Thanks for your detailed reply, much appreciated! My concern was CPU/GPU time to render as much as memory. In my mind, at a minimum, I want to avoid sending anything “to Babylon” that I don’t want rendered. Either Babylon or WebGL will (I assume) make optimisations to avoid any processing of data outside the viewing frustum - but thats still a lot of processing ‘my side’ to send it that direction… am I making sense?

Also, what about items that are within the viewing frustum but that are not visible… that are obscured? Is there an algorithmic method to avoid sending these to be rendered in any regard? In my particular scenario I’m thinking, for example, of a grid of buildings/skyscapers 100x100. Now when I’m between buildings in the middle of the street looking down the road, I can see all the buildings either side of the road all the way towards the far edge of the frustum. But those buildings in view, are completely obscuring all other buildings beside them. Now I could ‘hack’ together an algorithm that presumes all buildings are of equal height - but what if they aren’t?

I’m getting rather ahead of myself I guess, but I’d like to lay a good foundation :slight_smile: . Also, I don’t want to reinvent the wheel, if we’re talking about open-world here, how does something like GTAV work?


if(checkHit(user.shoot(), target)){
target.dead = true

haha jk…

Yes, I wouldn’t worry so much about optimization at this point in your project.