Home

Map Explorer implementation notes


Line-of-Sight algorithm

Line-of-sight is defined in the DDM rules as follows:

Two creatures can see each other if they can trace at least one unblocked straight line between any part of one creature's space to any part of the other creature's space. This line is unblocked if it does not intersect or even touch squares that block line of sight.

While point-to-point line of sight is easy to solve, area-to-area line of sight, as used in DDM, is harder. I'm only aware of probabilistic solutions. These work by randomly or systematically testing lines between the spaces (using a point-to-point algorithm) until either an unblocked line is found or a maximum number of tests has been done, in which case there is a certain (high) probability that no line of sight exists. This is implemented in Map Explorer.

This works and does not seem to miss any lines on the official maps, but I still find it somewhat unsatisfactory. While general area-to-area line of sight seems to be hard, the two-dimensional square grid of finite (and usually small) size used in DDM might allow a better solution.

The LOS computation is currently done in floating-point. It should be converted to use integer arithmetic. There are two reasons for this:


Geometric Objects

Java contains geometric objects such as points, lines, and polygons in the java.awt and java.awt.geom packages. These even have methods for testing for intersections. There are two reasons why I did not use these classes:

  1. I don't like these types to be mutable.
  2. Performance: they are slower than my more special-purpose classes, in particular on the default client VM. Using -server and -XX:CompileThreshold mostly closes the gap, but many systems don't even have a server VM installed.