Greedy Algorithms and BSP

When struggling to compile a map under the BSP limits, it can be frustrating to encounter cases where deleting geometry consumes more marksurfaces, or adding brushes causes the number to go down. It makes it hard to optimise, and also suggests that perhaps the compiler is doing something sub-optimal. To understand why this happens, we need to know about another Computer Science idea: the Greedy Algorithm.

Imagine we are shipping aeroplane components in trucks, and they have to cross a bridge with a 10 tonne limit. We want to use as few trucks as possible, and the components have the following weights in tonnes:

5, 4, 5, 4, 2

One algorithm to solve this problem is called “First Fit”. We take the components in order, and put them on the first truck which still has capacity, opening a new truck if nowhere else has space. If we perform this on the weights above, the first two components are shipped on truck number 1, but that doesn’t have space for the second 5 tonne component so we start truck 2. Again we can fit a 4 tonne alongside, but now neither truck has room for the 2 tonne component, so that goes on a third truck instead.

We’ve done it in 3 trucks, but could we do better? The components weigh 20 tonnes in total, so we might fit them on 2 trucks. You can check by inspection that this is possible. So where did First Fit go wrong? With hindsight we can see that putting the second component on a separate truck lets us pack the two 5-tonners together, then the 4’s and the 2 make an even 10 as well. So the placement of the first 4 tonne is the critical error.

You’ve probably guessed now that First Fit is an example of a Greedy Algorithm. The algorithm is greedy because at each step it does whatever minimises the current cost, regardless of the longer-term impact of that decision. First Fit packs the 4 tonne component on the first truck to avoid adding a second one now, even though the end result is 3 trucks where 2 might have sufficed.

As I recently learnt, depending on your compiler and settings, the BSP algorithm is sometimes or always choosing the plane which intersects the fewest faces as the next split to add. This is a Greedy Algorithm for minimizing splits – and so knock-on effects can arise from a choice that looks good at the time. This also scuppers an idea I had for areas of improvement: the First Fit algorithm is improved if you sort the weights from largest to smallest. The BSP algorithm considers all the brushes at each step, so the order they were loaded doesn’t have an effect*.

Greedy Algorithms do explain how removing a brush can increase marksurfaces: Suppose that at some stage the compiler has to choose between a “good” split and a “bad” split which will cause major headaches later in the compilation. Imagine that an ugly brush intersects the bad split. It might be that the extra intersections with the ugly brush are enough to make the compiler prefer the good split. Once we decide to delete the ugly brush, the bad split looks preferable to the compiler at the crucial juncture, because it cannot see the future, and only sees that at this stage it costs less to add. Bang! The deleted brush increases marksurfaces!

This all sounds a bit doom-and-gloom, but we must leave it here today, and be satisfied knowing a bit about why the BSP Algorithm can behave badly. As I mentioned one avenue of attack has been closed, but I still have a few ideas, and if any of them pan out there will be a follow up to this post…

*With two major exceptions. Firstly in the func_ post I linked I mention the “fast” method of split selection. The fast method loads all the non-axial faces strictly in brush order, so unless you have all square brushes, or use rebb’s -forcegoodtree switch, the order has an impact wherever the fast method is used. The other time that order can matter is when brushes are tied for the number of splits they cause. The arbitrary choice the compiler makes is dependent on brush order.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s