phi at November 30th, 2006 13:50 — #1
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.
nyx at November 30th, 2006 14:13 — #2
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).
groundkeeper at November 30th, 2006 15:38 — #3
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.
reedbeta at November 30th, 2006 21:26 — #4
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).
kenneth_gorking at December 1st, 2006 02:33 — #5
The wikipedia has an article on the bsp used in the doom engine: http://en.wikipedia.org/wiki/Doom\_engine
phi at December 2nd, 2006 14:15 — #6
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.