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
Please log in or register to post a reply.
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).
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.
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).
The wikipedia has an article on the bsp used in the doom engine:
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.