Bitmap of Bastion

[IAPark]

Last map things like Pistons introduced a significant amount of lag because of their O(log(n)*m) complexity where n is the number of Bastions and m is the number of pistons. Something we may want to consider doing is building a rough bit map of whether Bastions cover columns or not, this would only take about an additional byte per column and would save a significant amount of calculation time as most events Bastion currently tracks could be filtered in constant time. Similar trade offs between Ram and time could also be made if needed

[ProgrammerDan]

Very good suggestion, I or Max will look into it while we touch things up

[ProgrammerDan]

So, considering the volume of changes already in PR #41, I'll address this in future improvements.

[IAPark]

Yea, this is pretty substantial all on it's own, but it (in general more efficient bastion look up) and test cases are the two things I'd really like to add to Bastion.

[ProgrammerDan]

One thought I just had, is we could simply keep a bitmap of chunks with bastions in them. So any "events" can simply check that bitmap first, and if their chunk-of-residence or interaction has no bastions, fail-fast.

[ProgrammerDan]

This may be what you meant by "columns" -- if so, I finally got your idea :P

[ProgrammerDan]

So we do something similar in some other plugins -- track data within "chunk" buckets.

Example:

UUID world = loc.getWorld().getUID();
Chunk chunk = loc.getChunk();
long chunk_id = ((long)chunk.getX() << 32L) + (long)chunk.getZ();

then use the world UUID and artificial chunk_id to store in some HashMaps whatever chunk-specific data you need. Could easily have a boolean or counter for each chunk indicating presence of a bastion field.

This would roughly approximate a Bloom Filter; we could do a bit more work and probably directly implement a very fast bloom filter, if we wanted.

[IAPark]

Basically, I was thinking of having the bitmap on a the column level (so x, z, but not y), probably doing it on chunk level would be better, but the problem in both cases would be figuring out what columns actually are covered by a Bastion and not just has a Bastion on it. It could be done only once and then stored in a file so complexity could probably be kept manageable.

[ProgrammerDan]

My thought was just add it to the BastionBlock constructors -- we can recreate the map in memory on each startup, and when a new bastion is created in-game. Storing it wouldn't provide many gains, imho.

In any case, the check should be simple as approximate is all that's needed, with a focus on no false-negatives, but false-positives are acceptable. A rough sketch of the algorithm is something like:

For each bastion:
  set northWestCorner = bastion.centerLocation.add(-radius, 0, -radius);
  int x, z = 0;
  for (x = 0; x <= radius * 2; x += (x + 16 < radius * 2 ? 16 : radius * 2 - x)) {
    for (z = 0; z <= radius * 2; z += (z + 16 < radius * 2 ? 16 : radius * 2 - z)) {
      markChunk(nortWestCorner.clone().add(x, 0, z));
    }
 }

basically "mark" each chunk that the bastion overlaps, assuming a square field (b/c good enough), with special increment logic to always "add" the chunks at the east and south edges of the bastion field.