I put pathfinding on hold because when implementing a hexagonal coordinate based path finding algorithm, I realized that there would be various difficulties with dealing with constructs imposed on the world such as the terrain grid or quadtree and any other space partitioning systems.
So to know whether it’s really worth it to use hexagonal path finding, I decided to delay it until I have some other space partitioning data structures in place.
Most of today was spent on class work, in particular I made progress on the SMT solver due on Monday.
I did find a few hours today and yesterday to begin writing the terrain engine.
I’ve built a terrain in XNA before, however where I previously used quadtrees, this time I will use a grid based block partitioning scheme (more on this later).
The reasons for partitioning the terrain into fixed size blocks rather than a quadtree are:
- Simpler to texture terrain as all blocks are always the same size.
- Simpler to calculate lighting as the grid will match the geographic grid registration which I intend to use to partition scene lights.
- Closer to circular level of detail degradation around the camera, as blocks are a fixed size.
For example, all blocks might represent a 16×16 unit size of terrain (therefore, each block would represent 256 height points on the terrain). The inner most blocks in this case would then use 16×16 triangles and take up 16×16 units of space. The next blue ring would use 8×8 blocks but still take up 16×16 units of space. The next red ring would use 4×4 blocks, but still take up 16×16 units of space, and so on.
In the quadtree implementation, all blocks are the same size. The inner most green block would be a 16×16 grid, representing 256 height points. The next blue blocks surrounding it would also be 16×16 grids, but these blocks would each take up four times as much space (32×32 units large, but still using 256 triangles). The next teal blocks would be 64×64 large, but still use the same 16×16 triangle grid.
Using fixed size blocks means more draw calls, but I will use hardware instancing, so really there will only be one draw call per level of detail.
The biggest drawback is that there are many more blocks that the CPU must examine (cull/light/texture) compared to a quadtree.
More class work tomorrow, but after this assignment, I’ll have lots of time to finish up the terrain engine.