Four Remaining Questions

[taibeled]

There are now only five questions left! That is, questions with clear icons. Unfortunately, the remaining questions are all difficult to implement. The remaining questions can all be put into three categories:

Easy to implement badly

In #28, I first attempted to attack the difficult measuring questions. These questions have so many nodes that doing the naive buffer strategy takes way too long. I was able to salvage those questions by making them end-game exclusive (mostly). This could be easily done with the two questions in this category: distance to Shinkansen and distance to body of water. However, those questions scopes aren't exclusive to the endgame. I have spent a while attempting to implement the measuring to high-speed train (Shinkansen) question, however, no matter what combination of simplifications, combines, buffers, and intersections, it would invariably crash the tab. Although I have not yet attacked body of water, in areas like Japan, it would almost certainly have a similar fate to that of high-speed train. Implementing these two questions would either require the solution from #28, which would make the seekers job more strenuous, or a lot of optimizations.

Line Voronoi

As I found out with the distance to Shinkansen question, Open Street Map likes to fragment its ways and relations into numerous chunks, each with slightly different properties. That's the first part of these questions, determining what line each way is part of. I wrote some somewhat efficient code for that:

const groupObjects = (objects: any[]): any[][] => {
    const filteredObjects = objects.filter(
        (obj) =>
            obj.properties.name !== undefined ||
            obj.properties["name:en"] !== undefined ||
            obj.properties.network !== undefined,
    );

    const n = filteredObjects.length;
    const parent: number[] = Array.from({ length: n }, (_, i) => i);

    const find = (i: number): number => {
        if (parent[i] !== i) {
            parent[i] = find(parent[i]);
        }
        return parent[i];
    };

    const union = (i: number, j: number): void => {
        const rootI = find(i);
        const rootJ = find(j);
        if (rootI !== rootJ) {
            parent[rootJ] = rootI;
        }
    };

    const keys = ["name", "name:en", "network"];
    const paramMap: Record<string, number> = {};

    for (let i = 0; i < n; i++) {
        const obj = filteredObjects[i];
        for (const key of keys) {
            const value = obj.properties[key];
            if (value !== undefined) {
                const mapKey = `${key}:${value}`;
                if (paramMap[mapKey] === undefined) {
                    paramMap[mapKey] = i;
                } else {
                    union(i, paramMap[mapKey]);
                }
            }
        }
    }

    const groups: Record<number, any[]> = {};
    for (let i = 0; i < n; i++) {
        const root = find(i);
        if (!groups[root]) {
            groups[root] = [];
        }
        groups[root].push(filteredObjects[i]);
    }
    return Object.values(groups);
};

As you might be able to deduce from the talk about ways, the two questions in this category are the tentacles metro line and matching Shinkansen question. Once the exact lines are found, the Voronoi polygons have to be found. However, these aren't points but a sequence of line segments (technically a sequence of great circle arcs, but I already spent five hours solving that 1c80a33). My naive thought was to perform the geoSpatialVoronoi on each coordinate in each way and then connect the Voronoi polygons forming a larger Voronoi polygon. The algorithm 1500ms for a 15 mile tentacles centered in Tokyo. I didn't have much success actually combining the Voronoi polygons, though. Furthermore, although 1500ms is fine on a desktop, in a scenario where someone was actually using this, on their phone, it would surely take much longer. Adding these questions are like adding the questions from the last category with an added hinderance.

Elevation

This category is the outlier compared to the above categories. It only contains the distance from sea level question. That question is very different from all the other questions added to the application. First off, OSM does not contain elevation. Therefore, the only approach I can envision is taking a database of rough elevations for given latitudes and longitudes and eliminating off that. Lots of eliminations is the problem from the first heading, so this would also probably be difficult. This is the only question, besides distance to body of water, that I have yet to try to complete.

[taibeled]

I have since added the distance to high-speed train question in 663145a.

[Shruichan]

Hi Hi! I've been working on a separate project for jet lag, that aims to emulate the entire game and uses their copyrighted assets so I wont be able to make it public without their permission from what I have been told (hopefully that comes soon tm though), anyway as part of working on that project I've ended up solving (for the most part) the elevation question, though its currently optimized for large games as that was the more difficult challenge in my opinion, I will be also making a more granular version for small games (also soon tm). As im sure you were expecting I ended up using a dataset in order to make it all work and sort elevations.

Namely I used this dataset ETOPO1, which is a flat binary file with global elevation stored as 2-byte signed ints at about 1.5km resolution resolution. It does calculate quite fast so I will likely be integrating a more detailed dataset in a more finalized version, but this one is about half a gigabyte.

I treated this as just a grid classification problem, as all the data we have that isnt basically terabytes in size is stored in this kind of way.

Reading the ETOPO1 dataset

The binary file has a fixed grid layout, so a single point lookup is just an offset calculation followed by a 2-byte read:

const ETOPO1_ROWS = 10801;
const ETOPO1_COLS = 21601;
const ETOPO1_BYTES_PER_CELL = 2;

// Row 0 = +90°, Row 10800 = -90°
// Col 0 = -180°, Col 21600 = +180°
function getElevationOffline(lat, lng) {
  lat = Math.max(-90, Math.min(90, lat));
  lng = Math.max(-180, Math.min(180, lng));

  const row = Math.round((90 - lat) * 60); 
  const col = Math.round((lng + 180) * 60);
  if (row < 0 || row >= ETOPO1_ROWS || col < 0 || col >= ETOPO1_COLS) return null;

  const offset = (row * ETOPO1_COLS + col) * ETOPO1_BYTES_PER_CELL;
  const buf = Buffer.alloc(2);
  fs.readSync(etopo1Fd, buf, 0, 2, offset);
  return buf.readInt16LE(0); // elevation meters
}

Classifying

Here I just sampled the entire play boundarys bbox at ca resolution, thats capped at the max density of the ETOPO1 dataset, and each cell is given a binary classification.

function _classifyElevation(elevation, referenceAltitude) {
  if (!Number.isFinite(elevation)) return 0;
  if (elevation >= referenceAltitude) return 1;   // HIGHER
  return -1;                                       // LOWER
}

Row-strip merging using GeoJSON MultiPolygon

Trying to call 'turfUnion' was super slow and basically made even coarse resolutions on small areas entirely infeasible, so as per usual the solution was to ignore it. I just use Row-strip merging in order to merge adjacent same class cells into horizontal strips then merge them vertically to make rectangles. Code is:

function buildElevationGeometryFromAnalysis(artifact, answer = 'higher') {
  const { signedClassGrid, bbox, width, height, maskGrid } = artifact;
  const lngStep = (bbox.east - bbox.west) / width;
  const latStep = (bbox.north - bbox.south) / height;

  // Build horizontal runs per row
  const rowRuns = [];
  for (let row = 0; row < height; row++) {
    const rowBase = row * width;
    const runs = [];
    let runStart = -1;
    let runClass = null;

    for (let col = 0; col <= width; col++) {
      const inBounds = col < width;
      const cellVisible = inBounds && (!maskGrid || maskGrid[rowBase + col]);
      const cls = cellVisible ? _classForAnswer(signedClassGrid[rowBase + col], answer) : null;
      if (cls === runClass && inBounds) continue;
      if (runClass && runStart >= 0) {
        runs.push({ cls: runClass, colStart: runStart, colEnd: col });
      }
      runStart = cls ? col : -1;
      runClass = cls;
    }
    rowRuns.push(runs);
  }

  // Merge vertically adjacent runs with the same column bounds
  const allRects = [];
  const openRects = new Map();
  for (let row = 0; row < height; row++) {
    const currentKeys = new Set();
    for (const run of rowRuns[row]) {
      const key = `${run.cls}:${run.colStart}:${run.colEnd}`;
      currentKeys.add(key);
      const existing = openRects.get(key);
      if (existing && existing.rowEnd === row) {
        existing.rowEnd = row + 1; // extend rectangle downward
      } else {
        if (existing) allRects.push(existing);
        openRects.set(key, { cls: run.cls, colStart: run.colStart,
          colEnd: run.colEnd, rowStart: row, rowEnd: row + 1 });
      }
    }
    for (const [key, rect] of openRects.entries()) {
      if (!currentKeys.has(key) && rect.rowEnd <= row) {
        allRects.push(rect);
        openRects.delete(key);
      }
    }
  }
  for (const rect of openRects.values()) allRects.push(rect);

  // convert to geojson
  const feasibleCoords = [];
  const excludedCoords = [];
  for (const rect of allRects) {
    const w = bbox.west + rect.colStart * lngStep;
    const e = bbox.west + rect.colEnd * lngStep;
    const s = bbox.south + rect.rowStart * latStep;
    const n = bbox.south + rect.rowEnd * latStep;
    const coords = [[[w, s], [e, s], [e, n], [w, n], [w, s]]];
    if (rect.cls === 'f') feasibleCoords.push(coords);
    else if (rect.cls === 'x') excludedCoords.push(coords);
  }

  return {
    feasible: feasibleCoords.length
      ? { type: 'Feature', properties: {}, geometry: { type: 'MultiPolygon', coordinates: feasibleCoords } }
      : null,
    excluded: excludedCoords.length
      ? { type: 'Feature', properties: {}, geometry: { type: 'MultiPolygon', coordinates: excludedCoords } }
      : null,
  };
}

function _classForAnswer(signedClassValue, answer) {
  if (answer === 'lower') {
    return signedClassValue < 0 ? 'f' : signedClassValue > 0 ? 'x' : 'u';
  }
  return signedClassValue > 0 ? 'f' : signedClassValue < 0 ? 'x' : 'u';
}

For california this produces only about 4k rectangles rather than the roughly 400k I was getting trying to use 'turfUnion', which I then used to make a mask to signify the exclusion zone. As I mentioned this probably isnt the final form I will be implementing but it works for now, and is especially usefull in large games.

Here is an image of it working on all of california (calc time abt 3 secs )

[MKuranowski]

Re: matching high speed line and metro line tentacles

My naive thought was to perform the geoSpatialVoronoi on each coordinate in each way and then connect the Voronoi polygons forming a larger Voronoi polygon.

That's not the equivalent to creating a Voronoi diagram with line segments. In particular, a boundary where the closest part of one feature is a segment, and another is the endpoint, becomes a parabola. I find this pretty difficult to wrap my head around, but I can pretty easily generate a counter-example with raster graphics.

Script

from math import dist
from PIL import Image
from itertools import product

Pt = tuple[float, float]
Color = tuple[int, int, int]

def distance_to_line_segment(a: Pt, b: Pt, x: Pt) -> float:
    dx = b[0] - a[0]
    dy = b[1] - a[1]
    magnitude = dx*dx+dy*dy
    projection = (dx * (x[0] - a[0]) + dy * (x[1] - a[1])) / magnitude
    projection = clamp(projection, 0, 1)
    projected = a[0] + projection * dx, a[1] + projection * dy
    return dist(x, projected)


def clamp(x: float, min: float, max: float) -> float:
    if x < min:
        return min
    if x > max:
        return max
    return x

BLACK = (0, 0, 0)
BLUE = (0, 0, 255)
BLUE_DIM = (0, 0, 136)
RED = (255, 0, 0)
RED_DIM = (136, 0, 0)

IMAGE_SIZE = (2000, 2000)
LINE_BLUE = ((200, 200), (200, 800))
LINE_RED = ((100, 100), (1800, 1800))

def pixel_color(pt: Pt) -> Color:
    blue_dist = distance_to_line_segment(*LINE_BLUE, pt)
    red_dist = distance_to_line_segment(*LINE_RED, pt)

    if blue_dist < 3:
        return BLUE
    elif red_dist < 3:
        return RED
    elif blue_dist < red_dist:
        return BLUE_DIM
    else:
        return RED_DIM


def make_image() -> Image.Image:
    im = Image.new("RGB", IMAGE_SIZE)
    for pt in product(range(IMAGE_SIZE[0]), range(IMAGE_SIZE[1])):
        im.putpixel(pt, pixel_color(pt))
    return im


if __name__ == "__main__":
    make_image().save("voronoi_segments.png")

In particular, on a 2000 by 2000 canvas we have two lines: red coming diagonally from [100, 100] to [1800, 1800], and
blue coming down from [200, 200] to [200, 800] /note that in images the "y" axis grows downwards/. For y coordinates above 800 the boundary becomes a parabola.