As outlined previously, the 3D implementation was suffering from a bug which caused an index out of bounds exception when attempting to implement the quadrants. The linear part was being implemented fine however it was not scaling up in O(n) time as expected (MUCH worse in fact which led to significant concern for the algorithm as a whole)
Continue work on 3D viewshed implementation.
- Reviewed index out of range bug for 3D viewshed
- Conducted benchmarking of algorithm in current form
The bug causing the array index exception was located and corrected (I believe at least!). The algorithm itself is still not calculating the quadrant heights correctly (ie. The logic inside it is still failing) however it IS executing over the correct range now at least. The culprit was an error in calculating the intersection point for coordinates on an angle (Not using the inverse of a value when I should have, resulting in very large numbers when they should be ratios).
This was fixed through the use of UnityEngine debug log statements; the engine maintains a console where the debug statements print out. It is a very handy method for debugging however a major drawback is it is quite slow. Not an issue for single statements but where a statement is inside a loop which is executing many times, it causes significant slowdown. I realised I had rather foolishly left the debug statements in while benchmarking it. Commenting them out led to much better results…
I was also able to run calculations over the entire grid (as opposed to just the X and Y linear line of sight from viewer location as required previously.) which is good as it is more representative of the algorithm running time as a whole (correcting the math logic errors should have negligible impact on the magnitude of the running time)
The results obtained were:
- 16.6k calculations (1m spacing on a 129×129 grid) – 25ms
- 66.5k calculations – 74ms
- 1.66 million calculations – 1646ms
Note the last test would correspond to a a ~1.3km square terrain with heights sampled every meter or over 6km square with 5m sampling! This is great news as it means the current algorithm (when correctly implemented) will work well within the problem scope!
From here…. fix the error in the algorithm (downsize sample to be able to work by hand)
2 hours (30 hours running total)
Updated time spent:
3 hours (33 hours running total)
More work continued on the implementation of the 3D algorithm. Progress is being made but there are still bugs to work through. Still…. even if the bugs always tinge it with disappointment… slow progress is encouraging.