I have a terrain with procedurally generated heightmap of 513x513px with a bit over a thousand trees on it, clustered into forest areas. There are also open areas with no trees. There is a lot of height variation over the terrain - rolling hills type.
I want to test Line-of-Sight (LOS) from one section of the terrain to another, but have areas where the trees block LOS. I don’t need or even want to test each individual tree, just test against the forest areas. LOS blocking will not be yes/no - at the fringes of forests I want a small chance of seeing.
So far I have tried 2 methods, both using raycasting:
At runtime, generate cube primitives for each height sample (512x512) where there are trees and test if they block the ray. This worked well in a small test but when I got up to 512x512 grid the generation times were minutes.
- Is there any way to make this faster? Like not creating a full cube, just a cube collider?
//surfacegrid is an array of Surfaces. Surface contains the height of the trees at that hieghtmap point
//elevations is the heightmap
cube_height = 20;
for (int x = 0; x < losheight; x++) {
for (int y = 0; y < loswidth; y++) {
...check if this grid contains trees. if not skip this
GameObject cube = GameObject.CreatePrimitive (PrimitiveType.Cube);
cube.name = "los"+x+"-"+y;
cube.layer = LOSLayer;
cube.transform.parent = los_parent; //so outliner doesn't seize up
//make the cube the size of one heightmap sample, currently 2048/512
Vector3 p = new Vector3(y*cube_width,0,x*cube_width);
//calculate where to lookup height in hieghtmap array
int hx = (int)(ewidth * (x/(float)loswidth));
int hy = (int)(eheight * (y/(float)losheight));
float e = elevations[hx,hy] * terrain_max_elevation;
p.y = e+cube_height/2f;
cube.transform.localScale = new Vector3(cube_width,cube_height,cube_width);
cube.transform.position = p;
}
}
so, instead I am currently generating a second terrain that takes into account the added height of the trees. It can be lower res than the actual terrain. This seems to work OK.
2) Is is raycasting against a 513x513 terrain faster or slower than raycast marching through a 513x513 grid of cubes?
3) Does terrain heightmap res have any effect on the speed of tracing against it?
Unfortunately the cube technique above had the advantage that I could know how far into a forest I had traced based on the number of cubes I hit. ONce I was over a certain threshold of hits, I could stop tracing as full opacity was reached.
Using the LOS terrain I have to cast from see-er to target and then also backwards from target to see-er and account for more special cases such as if the two are in the same forest patch, or the LOS goes through multiple forest areas.
The other option is to write my own Bresenham marcher and just step through see-er postion and target position and calculate LOS based on the elevations in the array. Obviously this would be a bit of coding work on my end and I’d like to avoid it if there is no advantage.
4) would grid marching in C# be faster than raycasting against a terrain or cubes?
- Any other ideas?
Long post, I know, so thanks if you;ve bothered to take a look at it.
