Computational geometry techniques for terrain reasoning and data distribution problems in distributed battlefield simulation

In a distributed battlefield simulation, computer generated forces (CGF) systems generate battlefield entities that are primarily controlled by software rather than humans. To produce tactically realistic behavior CGF systems must algorithmically reason about the battlefield terrain. Data distribution is the process of maintaining network connectivity to deliver simulation data among the CGF and other systems in the distributed simulation. We show that practical problems of distributed battlefield simulation can be effectively addressed using computational geometry and geometric terrain reasoning.; Conventional intervisibility algorithms traverse the line of sight, checking terrain polygons for intersection. We developed a different approach, the sieve overlap algorithm, from the insight that only those polygons whose axis projections overlap a minimal axis-parallel bounding box for the line of sight along all three coordinate axes can block the line of sight. An experimental evaluation in the ModSAF CGF system showed the sieve overlap algorithm to be measurably faster than the current algorithm, but to require more memory.; The High Level Architecture (HLA) is a standard for constructing distributed simulations. Data distribution in HLA reduces data transmissions by basing communications connections on the data requirements of the simulations. At the core of determining which connections to make is a geometric problem: finding the intersection of d-dimensional rectilinear hyperrectangles in d-space. Four data distribution algorithms, including the current HLA algorithm and a new one we developed based on interval trees, were compared on both intersection performance and connectivity efficiency. The existing algorithm was fastest but produced large numbers of spurious and redundant network connections. Our new algorithm performed well and produced no spurious or redundant connections.; The fire zone defense problem is to select deployment locations on the terrain for the individual entities of a CGF unit so as to defend an engagement area. Geometric terrain analysis to produce a graph representation of the terrain and a greedy optimization algorithm on that graph are combined to produce a new algorithm to select deployment locations. Based on cumulative observation of the engagement area from the selected deployment, our algorithm was found to consistently outperform the ModSAF algorithm for the same task.