Hex Casting

Hex Casting

6M Downloads

Locator's Distillation and/or Uniqueness Purification can freeze servers with O(n^2) hexes

object-Object opened this issue ยท 1 comments

commented

As discussed on Discord.

I made a hex that works roughly like this (implementing BFS):

while there are blocks in the queue (a list):
  pop the first block from the queue
  for each offset in a list of 18 vectors:
    get the block at that offset
    use locator's to see if the block has already been visited (!!)
    insert the block into the visited list, using uniqueness prfn (!!)
    optionally insert the block into the queue

The implementation of Locator's Distillation's and/or Uniqueness Purification makes this have O(n^2) time complexity. Here's what happens when you run it on too many blocks:

uhhhhhhhh.mp4

My suggestion was to have lists maintain an internal hashmap (iota -> first index), and possibly also a set, and use those to implement Locator's and the set patterns.

commented

A less user-friendly but simpler solution could be to make list scanning operations add to the op limit?

I was thinking it would be fun to make a hash table in hex, but there's not much point if lists efficiently act as one too...