Random Algorithms and BSP

If you are concerned with how quickly a program runs, beware of being too optimistic. If you start thinking about the best-case scenario, you might choose bad algorithms. For example, imagine the problem of sorting a list of numbers into order, a common job for computers. One algorithm for doing this goes:

1. Permute the list randomly.

2. Return to 1 if the list is not sorted.

In the best case, your random “guess” is right first time, and sorting the list only takes as long as checking the list is in order. However, you should actually expect to take n! guesses before the list is correctly sorted, which is much too slow for any reasonable sized list.

This post is not about how fast our algorithm goes, but the idea that you can randomise things in an algorithm: they don’t have to be deterministic. Sometimes the compilation process feels random, as small changes to a map can move us a long way towards the BSP format limits. However, if we make no changes to the map the result should be the same each time. Until now. We’re going to try to randomise some elements of the compilation process, to see if we can reduce the marksurfaces in the BSP compared to the deterministic algorithms.

We do need to adjust to this randomness, to avoid drawing a wrong conclusion from a single throw of the dice. Once we’ve added the randomisation we will run our compilation repeatedly, and then pick out the most successful bsp from the batch. You might be worrying by now that my casual attitude to algorithm speed today is going to make any results from today only useful in theory. So here’s my justification why we can extend BSP times so much without care: VIS is still so much worse. On huge maps, even using multithreading computers many times faster than anything Quake was built on, VIS can take weeks of solid compilation. BSP is practically nothing by comparison, running it 50 times will still not compare. If optimising our target stat pays off, the 50 compilations might save more time at the VIS step than they cost. And if it’s the difference between a map that breaks the limits and one which doesn’t, it has paid off already.

Today you need a copy of the source to Rebb’s BSP tools and a nice simple map. If you don’t have the mapping skills to make a box containing a cube, or want to play along with exactly the same map as me, paste the hidden code into a file called s1.map:

{
"classname" "worldspawn"
"sounds" "1"
"mapversion" "220"
"wad" "\hammer\quake101.wad"
{
( -128 0 0 ) ( 0 0 0 ) ( 0 -512 0 ) CITY2_5 [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1 
( -128 -512 -512 ) ( 0 -512 -512 ) ( 0 0 -512 ) CITY2_5 [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1 
( -128 0 0 ) ( -128 -512 0 ) ( -128 -512 -512 ) CITY2_5 [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1 
( 0 0 -512 ) ( 0 -512 -512 ) ( 0 -512 0 ) CITY2_5 [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1 
( 0 0 0 ) ( -128 0 0 ) ( -128 0 -512 ) CITY2_5 [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1 
( 0 -512 -512 ) ( -128 -512 -512 ) ( -128 -512 0 ) CITY2_5 [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1 
}
{
( 512 0 0 ) ( 640 0 0 ) ( 640 -512 0 ) CITY2_5 [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1 
( 512 -512 -512 ) ( 640 -512 -512 ) ( 640 0 -512 ) CITY2_5 [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1 
( 512 0 0 ) ( 512 -512 0 ) ( 512 -512 -512 ) CITY2_5 [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1 
( 640 0 -512 ) ( 640 -512 -512 ) ( 640 -512 0 ) CITY2_5 [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1 
( 640 0 0 ) ( 512 0 0 ) ( 512 0 -512 ) CITY2_5 [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1 
( 640 -512 -512 ) ( 512 -512 -512 ) ( 512 -512 0 ) CITY2_5 [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1 
}
{
( -128 128 0 ) ( 640 128 0 ) ( 640 0 0 ) CITY2_5 [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1 
( -128 0 -512 ) ( 640 0 -512 ) ( 640 128 -512 ) CITY2_5 [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1 
( -128 128 0 ) ( -128 0 0 ) ( -128 0 -512 ) CITY2_5 [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1 
( 640 128 -512 ) ( 640 0 -512 ) ( 640 0 0 ) CITY2_5 [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1 
( 640 128 0 ) ( -128 128 0 ) ( -128 128 -512 ) CITY2_5 [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1 
( 640 0 -512 ) ( -128 0 -512 ) ( -128 0 0 ) CITY2_5 [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1 
}
{
( -128 -512 0 ) ( 640 -512 0 ) ( 640 -640 0 ) CITY2_5 [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1 
( -128 -640 -512 ) ( 640 -640 -512 ) ( 640 -512 -512 ) CITY2_5 [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1 
( -128 -512 0 ) ( -128 -640 0 ) ( -128 -640 -512 ) CITY2_5 [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1 
( 640 -512 -512 ) ( 640 -640 -512 ) ( 640 -640 0 ) CITY2_5 [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1 
( 640 -512 0 ) ( -128 -512 0 ) ( -128 -512 -512 ) CITY2_5 [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1 
( 640 -640 -512 ) ( -128 -640 -512 ) ( -128 -640 0 ) CITY2_5 [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1 
}
{
( -128 128 128 ) ( 640 128 128 ) ( 640 -640 128 ) CITY2_5 [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1 
( -128 -640 0 ) ( 640 -640 0 ) ( 640 128 0 ) CITY2_5 [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1 
( -128 128 128 ) ( -128 -640 128 ) ( -128 -640 0 ) CITY2_5 [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1 
( 640 128 0 ) ( 640 -640 0 ) ( 640 -640 128 ) CITY2_5 [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1 
( 640 128 128 ) ( -128 128 128 ) ( -128 128 0 ) CITY2_5 [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1 
( 640 -640 0 ) ( -128 -640 0 ) ( -128 -640 128 ) CITY2_5 [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1 
}
{
( -128 128 -512 ) ( 640 128 -512 ) ( 640 -640 -512 ) CITY2_5 [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1 
( -128 -640 -640 ) ( 640 -640 -640 ) ( 640 128 -640 ) CITY2_5 [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1 
( -128 128 -512 ) ( -128 -640 -512 ) ( -128 -640 -640 ) CITY2_5 [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1 
( 640 128 -640 ) ( 640 -640 -640 ) ( 640 -640 -512 ) CITY2_5 [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1 
( 640 128 -512 ) ( -128 128 -512 ) ( -128 128 -640 ) CITY2_5 [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1 
( 640 -640 -640 ) ( -128 -640 -640 ) ( -128 -640 -512 ) CITY2_5 [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1 
}
{
( 128 -64 -448 ) ( 256 -64 -448 ) ( 256 -192 -448 ) COLUMN1_4 [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1 
( 128 -192 -512 ) ( 256 -192 -512 ) ( 256 -64 -512 ) COLUMN1_4 [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1 
( 128 -64 -448 ) ( 128 -192 -448 ) ( 128 -192 -512 ) COLUMN1_4 [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1 
( 256 -64 -512 ) ( 256 -192 -512 ) ( 256 -192 -448 ) COLUMN1_4 [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1 
( 256 -64 -448 ) ( 128 -64 -448 ) ( 128 -64 -512 ) COLUMN1_4 [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1 
( 256 -192 -512 ) ( 128 -192 -512 ) ( 128 -192 -448 ) COLUMN1_4 [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1 
}
}

OK, so open up the solidbsp.c file and find this section of code

	for( p = surfaces; p; p = p->next ) {
		// if surface has not yet been assigned to a node
		if( !p->onnode ) {
			i++;
			bestsurface = p;
		}
	}

	// all surfaces have been assigned to nodes already
	if( i == 0 )
		return NULL;

	if( i == 1 ) {
		#ifdef FEATURE_DETAIL
		if( !bestsurface->has_struct && !usemidsplit )
			*detail = 1;
		#endif

		return bestsurface; // this is a final split
	}

The first section counts all the surfaces that have yet to be processed. The next two deal with the special cases when zero or one surface remain. After these we will stick our randomisation code:

	i = 1 + (rand() % i);
	for(p=surfaces;i>0;p=p->next) {
		if( !p->onnode ) {
			i--;
			bestsurface = p;
		}
	}
	return bestsurface;

We take the count of remaining surfaces i and replace it with a randomly chosen number between 1 and i. Then we repeat the loop through the surfaces, this time decreasing i when we find a pending surface, until i reaches zero. In effect we take our random number, and select the corresponding unprocessed surface.

The only other change we need to make is right at the bottom of qbsp.c. Just below the line with startMS = GetMilliCount();, add srand(startMS);. This seeds the random number generator, so that we get a different ordering of surfaces each time.

Because today is purely research mode, we aren’t spitting out production grade code, that’s all the changes we’re going to make – compile and go! In proper mode we would write a loop into the compiler to run our randomisation multiple times. The pragmatic approach is just to run the executable lots instead. I used the following command line (in windows) to execute 100 compiles and log the results.

for /L %i in (1,1,99) DO txqbsp s1 out%i >> log.txt

Your results may vary due to the randomness, but my best run got marksurfaces down to 160. Here’s the graph marksur1
The red dotted line is the basis for comparison, where I compiled the map with rebb’s compiler in -forcegoodtree mode. As you can see, it’s better than the average run, but we have managed to beat it. I would temper this with a warning: my best compile for marksurfaces did come with trade-offs. Vertices, nodes, edges and leafs all increased a little, although clipnodes was way down – from 110 down to 61.

So that’s great in our toy example with one room and little detail, but how about with a proper sized map? I grabbed scampsp1 as the nearest source to hand and ran it through the randomiser a few dozen times. Here’s the graph.marksur2
That…that’s not so great. The randomisation has taken a map comfortably within quake’s limits, and moved it entirely outside of them! Obviously our crude strategy does not scale very well. Still, if we could replicate the success seen on the scale of a small room several times over in a map it would pay dividends! To do that we will need a more thorough reworking of the compiler internals, so it will be for another day. Until then…

Advertisements

One thought on “Random Algorithms and BSP

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 )

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