While I was testing the temp obstacle handling, I noticed that some locations would take quite a bit more time to process than others. For example in the level that is shown in the video above, the rebuild times would range from 1 ms to 15 ms depending on how many tiles the obstacle would affect and how many layers there were in that particular location. The number of obstacle affect the build time too. The added performance cost is pretty linear to the number of obstacles (and their size). In my tests each obstacle takes about 0.05-0.1ms to process.
To fight the variance I implemented a time-sliced version of the generation process. In the above video, the temporary obstacles are updated incrementally so that on each update the process consumes 1 ms. The code will find its way to the SVN later this week.