Quasi-Randomised Algorithms and BSP

Last time we saw that in theory, randomisation of choices can improve BSP compilation. We also saw that the method we chose wasn’t practical on a large map. This follow up describes a compromise between the purely randomised compilation process and the existing heuristic for choosing a split. We will be retaining the same spirit of investigation as last time – do the simplest thing that might work and see what results we get. Production-worthy code is still a little way off.

My first experiment after the last post was to try and divide the surfaces into axial and non-axial, randomise all of the former in the first instance, then all of the latter afterwards. This offered some improvement, but still not enough to keep the test map under the Quake limits (recall that before we randomised, it happily did). Afterwards, I was convinced that we still needed something of the algorithm which selected better splits; allowing the chance of very inefficient splits was being too harmful.

The existing selection algorithm runs each time a surface is added to the BSP. It goes through each remaining surface, and counts how many surfaces it will intersect with. If it scores less than the previous best, it becomes the new best candidate. If it scores the same, the new surface wins if it is axial (even if the old was too!). Here there is a simple way to introduce randomness – simply add a random amount of made-up intersections to each surface whenever the algorithm runs.

If you want to code along tonight, grab a fresh copy of the source to Rebb’s BSP tools. Also make the same change to qbsp.c as last time – after startMS = GetMilliCount();, add srand(startMS);. Now we’re ready.

The change today is even simpler than the one from last time. Simply open up ChoosePlaneFromList and look for the line k = 0;. Replace that with

	k = rand() % 20;
	if(!(PlaneIsAxial( plane )))
		k = k + (rand() % 20);

That’s really simple to explain: add a random penalty 0 – 19 to all surface scores, plus a further 0-19 penalty to non-axial planes. Since we’ve only changed one of the Plane Selection algorithms, it’s important to compile with the -forcegoodtree options to ensure you get the most out of the changes.

Compile the code up, let it run a few dozen times and…it’s not much better than fully random. With penalties that high, the signal from the algorithm gets completely lost in the noise we’ve introduced. You can try different values, or you can skip all that compiling to the conclusion that a value of 2 for both penalties works nicer than anything else. That means a 50% chance of adding 1, or otherwise adding nothing. Here’s the scoreboard:
The nice feature to my mind is that the average run of this algorithm is better than the comparison line – you wouldn’t have to run it multiple times to expect an improvement (although it helps). Now technically we’re only looking at a 1% improvement on this map, but who knows when that might just tip the balance.

What might be nicer is if we could use our previous best run as the basis for our next pass of randomisation. The problem is that we’d need the compiler to know the exact order of surfaces to start from. That means taking the multiple compilation passes inside the compiler, which means a big rewrite. So keep your eyes peeled for the next installment…


Leave a Reply

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

WordPress.com Logo

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.