Doom - BSP tree implementation

21d3d08ea3c08e4df1a4f261119f32b3
0
Phi 101 Nov 30, 2006 at 18:50

Hey,
I’m looking to re-create a the orginal doom games, using bsp trees, i’ve studied many other types of tree’s but the concept of how the bsp tree’s are used escapes me for the moment. I’m not looking for a lesson as i can google bsp trees, but i can’t find any information about bsp trees in relation to the doom game. Can anyone help me find out more information about the implementation of bsp tree’s used to create doom style rooms.

Cheers.

5 Replies

Please log in or register to post a reply.

3f95f5a6d0212e02b72af2958595e130
0
Nyx 101 Nov 30, 2006 at 19:13

Rooms aren’t created using BSP trees, they’re created using some editor, and stored as a set of polygons in 2D or 3D space. BSP trees are used to store the polygons making those rooms to allow fast and efficient culling to reduce the overhead when rendering. They can also be used to speed up collision detection.

If you’re making a simple doom game, and this is your first game, you could just store all your polygons inside a big array. It will be fast enough on modern hardware, even for reasonably detailed scenes. Otherwise, you might want to look up portal-based engines, which probably corresponds more to what you need for a Doom-like game anyways (BSP trees can also be used with portals, but the benefits may not be significant in your case).

6cad28055d4af37574fe0d4064555e53
0
GroundKeeper 101 Nov 30, 2006 at 20:38

Infact the original doom was implemented in a 2D trick and fix ala Carmack which makes it somewhat hard to discuss bsp. The binary space partion algorithm simple is a way to divide the polygons of a scene. And says nothing of how it is implemented in Doom.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Dec 01, 2006 at 02:26

Well, the BSP tree was still the primary data-structure in Doom, it was just a 2D BSP tree instead of a 3D one, so only vertical planes and walls were in the tree, not floors and ceilings. Basically, the structure of a Doom map was a BSP tree that partitioned the map into convex rooms (sectors); the leaves of the tree would contain “linedefs” (walls and portals). Each sector had floor and ceiling heights and textures, and each linedef was either one-sided (a wall, with a texture) or two-sided (a portal connecting two sectors, with a pair of textures for the half-walls that would be produced if the sectors differed in floor or ceiling height).

46407cc1bdfbd2db4f6e8876d74f990a
0
Kenneth_Gorking 101 Dec 01, 2006 at 07:33

The wikipedia has an article on the bsp used in the doom engine: http://en.wikipedia.org/wiki/Doom_engine

21d3d08ea3c08e4df1a4f261119f32b3
0
Phi 101 Dec 02, 2006 at 19:15

cheers for the replys and information, at the moment i’m going throught the doom source code and reading more into bsp tree’s, your information was great, i might extend myself to k-d tree’s aswell. thanks for the info Kenneth and eveyone else.