I'm developing an isometric city builder game. I've figured out how to depth sort everything on the CPU efficiently, though there were some ugly workarounds I had to implement. Suffice to say, for anything outside of buildings, sorting on the screen.y position of the texture works perfectly (so long as each asset is one tile in size, or broken up into multiple tiles).
But, I am starting to implement vehicles, first time adding assets that are multiple tiles in size. It would be really nice if I could create one asset for the vehicles, but the sorting on screen.y will not work for 3D rectangles, so I am breaking the up into multiple tiles...
Do you think BSP trees will work with thousands of moving assets? i.e., I would have to recreate the BSP tree every frame.
Somewhere between one to $tile_size pixels. Tile size depends on the zoom level (I'm using SFML, had to add a separate sprite sheet for each zoom level cause SFML's built in zoom out method is awful).
This is the first time of hearing BSP, and I read most of the OP's article to have a very basic understanding how it works.
Since this is a tree, reordering N elements would be approach N^2 complexity, would it not? (edit: I assumed you would have to find each node from the root, which could very well be a bad premise).
Yes, it would average nlogn and worst case would be n², unless I'm thinking about it incorrectly.
But this is one of those cases where asymptotic complexity seems a bit too reductive. One of the "n" in the complexity is really a fraction of the n.
That said, if I understand your use case correctly, you might not benefit much from having a binary subdivision of space for this. It sounds like what you need is more of a plain ordered list. One of the ways to implement that is as a binary tree, but an array that is kept ordered may be fast enough due to locality etc.
there's probably some optimization that you can do, but you can't know that the second frame isn't the conclusion to a move from 10 frames ago that is what reveals a giant area.
frame 0: open door
frame 10: still can't see past edge of door
frame 11: door opens enough to see big new area
between 10 and 11 it turns out there's a huge difference, even though they're only two frames apart.
The door being open or closed shouldn’t change the order of most elements. So it’s only relevant if you haven’t been sorting occluded objects.
Which gets into one of the major tradeoffs in rendering engines, do you try to minimize the average effort per frame or the worst case effort per frame.
This works perfectly for isometric cubes, and is what I do currently.
If you imagine two long rectangles, one in each of your two hands, and pretend they are two cars passing each other in an isometric world, you will see that pretty soon, one car's screen.y position will be below the other before it's clear of the vehicle which should actually be occluding part of it.
I thought about this for a bit, and I have a feeling that as long as everything is touching the ground, then making covering loops is impossible, and so there exist a simple ordering you can compute.
The ordering is as follows: I'm assuming the isometric rendering of a map as a 45 degrees tilted square, and I'm only considering tile ordering just for simplicity but it should generalize fine. The uppermost tile is where you want to start rendering. From there, you render following the two 45 degree diagonals until you are done (so you don't only look at the y axis). Once this is done, you restart the process from the tile just below the uppermost corner, and so on. This ordering makes sure that all rectangular objects that are aligned with the 45 degree diagonals are rendered correctly.
Now you need an additional trick to render rectangular objects that are transversal to those diagonals correctly. What you do is you keep track of the boundaries of all such objects, so that the rendering loop described above can tell when it encounters one. Once it encounters it, it pauses rendering the current diagonal and considers it temporarily complete. The diagonal on the other side still needs to be rendered fully though --- or at least as far as possible with the same stopping condition. The next rendering pass will likely at some point re-encounter the same transversal object, just at a further point. Stop again, start the next diagonal. Once the rendering encounters the lowest and last part of the transversal object, then that object can be rendered, and the first stopped diagonal can be resumed (and after this resume all the paused diagonals in order).
This should always give you the correct order to render everything without errors. Let me know if this made sense, otherwise I can try to clarify.
This is an interesting approach, though I dont think it will work. Vehicles/units move pixel by pixel, not tile by tile. Each wall tile in my game takes up one tile, and walls sit on the edge of a tile. I dont think this will handle unit/wall rendering order properly unless I also form larger shapes from the walls.
I forget the exact algorithm, but you can factor in your x with y. For right-facing sides, anything at the same y with a greater x is in front of a lesser x, and vice versa for left-facing sides.
But, I am starting to implement vehicles, first time adding assets that are multiple tiles in size. It would be really nice if I could create one asset for the vehicles, but the sorting on screen.y will not work for 3D rectangles, so I am breaking the up into multiple tiles...
Do you think BSP trees will work with thousands of moving assets? i.e., I would have to recreate the BSP tree every frame.