A Crash Course in Binary Space Partitioning

Name: A Crash Course in Binary Space Partitioning
Rating: 4.8 (124 reviews)

Learn about 3D space division for game map generation and fast rendering

Created byPenny de Byl, Penny Holistic3D

Last updated 4/2021

English

What you'll learn

Students will learn about Binary Space Partitioning and how it works.
Students will learn how to write an algorithm to create a binary tree which divides 3D space.
Students will learn how to use recursion to traverse a binary tree and create a 3D dungeon map.

Course content

2 sections • 13 lectures • 2h 0m total length

A Quick Welcome1:05
This video introduces the course with a short message from Penny.

Building a Binary Tree from a Polygon World8:09
In this lecture students will learn how to perform binary space partitioning to create a binary tree of a scene constructed with polygons.
Traversing a Binary Tree8:53
In this lecture students will learn how to traverse a BSP to draw out a polygon scene given the location of a player character within the map that is represented.
Dividing a Game Map with a BSP Part 115:43
In this lecture students will learn how a BSP will be used to represent a game would and then divided up to create rooms with corridors in a dungeon. The first part of the code to create this in Unity will be examined.
Dividing a Game Map with a BSP Part 29:22
In this lecture students will learn how to divide the game map into two sections with random sizes but still fill the size of the map.
Dividing a Game Map with a BSP Part 311:26
In this lecture students will learn how to create random divisions in a leaf in either a width wise or depth wise direction.
Dividing a Game Map with a BSP Part 411:48
In this lecture students will learn how to write a recursive method to run the BSP algorithm and create a larger binary tree.
Drawing Final Divisions Only4:56
In this lecture students will be challenged to draw only the final level of the BSP.
Controlling Division Sizes7:03
In this lecture students will learn how to control the sizes of the divisions as well as create better proportioned horizontal and vertical splits.
Carving Rooms11:24
In this lecture students will learn how to add rooms into the divisions to create a game environment map.
Joining Rooms with Corridors13:38
In this lecture students will learn how to draw corridors from one leaf to another.
Forcing Vertical and Horizontal Corridors6:49
In this lecture students will learn how to enforce that all corridors run horizontally and vertically and touch on each leaf node.
Adding Random Corridors and Rooms10:06
In this lecture students will be challenged to modify the map building functionality to add random corridors and adjust the size of rooms.

Requirements

Students should have a firm understanding of C#
Students should be familiar with the Unity Game Engine

Description

Binary Space Partitioning is a technique that's been around for a while and has been used for a number of purposes, in particular 3D polygon divisions, optimised physics collisions, and world map creation within games. Most notably it was used by John Carmack in the creation of the game engine for Doom.

This course uses Unity 2020.

Learn how to program and work with:

space division
polygon ordering for fast rendering and occlusion
binary trees
recursive search algorithms
dungeon map creation

What people are saying about Penny's courses:

Dr. Penny is a wonderful person and a true expert. All of her courses I've taken have been top notch and in my opinion there is no better teacher out there.
Allow me to say how hugely important this is for a person who is interested in certain types of game design. Creating games where you can create AI behaviors that support emergent situations.
I honestly love Holistic's teaching approach and I've never learned so much within a few hours about coding effectively with such detailed explanations!

In this short course, you will gain an overview of the algorithm and how it is used to partition 3D space for optimised polygon drawing as well as get your hands dirty using BSPs to create a game environment dungeon map

Who this course is for:

Anyone interested in learning about the binary space partititioning technique.
Anyone wanting to expand their skill set in procedural game environment generation.

A Crash Course in Binary Space Partitioning

What you'll learn

Explore related topics

Course content

Introduction1 lecture • 1min

Section 112 lectures • 1hr 59min

Requirements

Description

Who this course is for: