Chunking the Grid?

[jHoldroyd]

We're working on a prototype at the moment to evaluate the posibilities of this library for a procedurally generated game world. The concept however is already creating more hexes than we are able to load and keep in memory at any one time without impacting performance.

Thus leading us to looking at chunking up the grid. Which was fairly straightforward to get into a working/rendering position however it has lead to the next issue - none of the traversal methods, line of sight, or navigation examples are setup to handle this scenario (which is to be expected).

I was wondering if you had any thoughts on if this is the library we should be looking at, or should we roll out own? If there was any advice you had on being able to overcome the issues, and ultimately if it's something you'd considered supporting out of the box?

Thank you for the work you've done on this, it's really been a nice project to work with, just unique scaling issues are holding us back.

[flauwekeul]

Thanks for your question (and the compliment 🙃). This is certainly something I'd like to solve with Honeycomb, or at least make an attempt.

Are you able to share some code that uses chunking and where a traverser doesn't work? I can imagine it not working, but I'd like to know the exact problem. Is it not working because the traverser needs to cross chunks which are loaded asynchronously? Or are the chunks in different grids and there's no apparent way to traverse multiple grids? Or something else?

[jHoldroyd]

I'll try and do my best to explain the setup, and if that doesn't work pull out the relevant methods to try and give you a reproducable example.

We have two primary classes, World and Chunk. Who's interfaces look like this:

interface World {
  chunks: { [key: string]: Chunk };
  chunkSize: number;
  renderDistance: number;

  // Update the player position, load, unload, and clean chunks
  updatePlayerPosition(x: number, y: number): void;

  // Loads a chunk at a given position, eg: 0,0 or -1,1
  loadChunk(x: number, y: number): void;

  // Reverse of load
  unloadChunk(x: number, y: number): void;

  // Unloads any chunks further from given position than renderDistance
  unloadDistantChunks(x: number, y: number): void;
}

interface Chunk {
  x: number;
  y: number;
  grid: Grid<Hex>;

  // Builds a new grid of a given size at dimensions, and assigns it to grid
  constructor(x: number, y: number, size: number): Chunk;
}

As you can see we have multiple individual grids which we render at a given world position based on the chunk x,y corrdinates, tileSize, and chunkSize. Which all works well enough, it renders what we expect, chunk loading happens fine, etc.

However due to the nature of dealing with multiple grids the traversers can't find a hex outside of their own grid and instead creates a "blank" Hex (without any of our custom properties). While that would normally be fine we need the "real" Hex from another grid. Which if we try and correct by traversing the chunk, normalising the tile it should have gone to, as the Position coords are now different the traverser gets confused when moving to the next tile and gets a bit unpredictable.

The more I've been working through the problem, the more it feels like we're going down the wrong path. I'm now trying to see if I can make the chunking system work within the same grid and load/unload Hexes rather than seperate grid chunks.

[flauwekeul]

I see the problem and as you already concluded, it's currently not possible to traverse multiple grids.

I'm now trying to see if I can make the chunking system work within the same grid and load/unload Hexes rather than seperate grid chunks.

I think you're on the right track here. You'd have to move the chunking functionality to the grid so that you can traverse a single grid. Please let me know if this works for you.

If you're unhappy with this approach and prefer multiple grids like you started with, I'm happy to consider looking into traversing multiple grids. If this is the case, please let me know what issues you ran into with the single grid approach.

[jHoldroyd]

I spent a few hours playing with some different approaches and this is a still a bit rudamentary but is working well enough as a proof of concept of how to do "in-grid" chunking.

import { Grid, Hex, HexConstructor, Point, rectangle } from 'honeycomb-grid';

interface GridChunkManagerOptions {
  hexSize: number;
  chunkSize: number;
  renderDistance: number;
}

interface IChunk {
  position: Point;
}

export class GridChunkManager<T extends Hex & { chunk: string }> {
  private grid: Grid<T>;
  private generator: HexConstructor<T>;
  private chunks: Map<string, IChunk>;

  private hexSize: number = 50;
  private chunkSize: number = 8;
  private renderDistance: number = 2;

  constructor(generator: HexConstructor<T>, options?: Partial<GridChunkManagerOptions>) {
    this.grid = new Grid(generator);
    this.chunks = new Map();
    this.generator = generator;

    this.hexSize = options?.hexSize || this.hexSize;
    this.chunkSize = options?.chunkSize || this.chunkSize;
    this.renderDistance = options?.renderDistance || this.renderDistance;
  }

  getGrid(): Grid<T> {
    return this.grid;
  }

  loadChunk(key: string): void {
    if (this.chunks.has(key)) return;

    const [x, y] = key.split(',').map(Number);
    const start = { col: x * this.chunkSize, row: y * this.chunkSize };

    const iterator = rectangle<T>({ width: this.chunkSize, height: this.chunkSize, start });

    const hexes = iterator((pos) => new this.generator(pos)).map((h) => {
      h.chunk = key;
      return h;
    });

    this.grid.setHexes(hexes);
    this.chunks.set(key, { position: { x, y } });
  }

  unloadChunk(key: string): void {
    if (this.chunks.has(key)) {
      const chunk = this.chunks.get(key);
      if (chunk) {
        this.grid = this.grid.filter((hex) => hex.chunk !== key);
        this.chunks.delete(key);
      }
    }
  }

  validChunks(position: T): Set<string> {
    let validChunks: Set<string> = new Set();

    const [x, y] = (position as T).chunk.split(',').map(Number);

    const startX = x - this.renderDistance;
    const endX = x + this.renderDistance;
    const startY = y - this.renderDistance;
    const endY = y + this.renderDistance;

    for (let x = startX; x <= endX; x++) {
      for (let y = startY; y <= endY; y++) {
        validChunks.add(`${x},${y}`);
      }
    }

    return validChunks;
  }

  updateChunks(position: T): void {
    const validChunks = this.validChunks(position);

    // Unload chunks outside the render distance
    this.chunks.forEach((_, key) => {
      if (!validChunks.has(key)) {
        this.unloadChunk(key);
      }
    });

    // Load chunks within the render distance
    validChunks.forEach((key) => {
      this.loadChunk(key);
    });
  }
}

Efficency could be improved, and there's some performance tuning to be looked at - rendering new chunks causes some micro stuttering but we've found a decent balance of working with more, smaller chunks works best. For example:

const Manager = new GridChunkManager<Hex>(defineHex({ dimensions: 50}), { chunkSize: 4, renderDistance: 4 });
Manager.updateChunks(new Hex({ x: 0, y: 0 }));

Will keep around 800 chunks in memory at any one time and allow you to traverse loading new chunks every few tile movements. Dealing with larger chunks causes more performance issues during rendering which was one of the main things we were trying to overcome with individual grids, but this seems workable.

Thank you again.