The Genius of Binary Space Partitioning in Doom

Re:The Genius of Binary Space Partitioning in Doom by YesBox on Monday November 21, 2022 @04:15PM (#33698030)

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).

[ Parent | on HN ]

Re:The Genius of Binary Space Partitioning in Doom by kqr on Tuesday November 22, 2022 @01:09AM (#33702608)

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.

[ Parent | on HN ]