User:Evil4Zerggin/Explosion algorithm proposals

From From the Depths Wiki
Jump to: navigation, search

Explosions on multiple (sub)constructs[edit | edit source]

Problem[edit | edit source]

Explosions have extremely unintuitive behavior with respect to subconstructs, as described in this forum thread and this Imgur album. In fact, between explosions that start on subconstructs phasing through the deck of ships and the extreme fragility of barrels, I've determined that against explosive damage it's best not to armour turrets at all---the best defence is not to get hit in the turret! Really, it's the only defence, since any hit will almost surely destroy the barrels no matter how much armour there is. BlackHandHUN and I are demonstrated this in Menti's Battleship Brawl Tournament Season 2.

Objectives[edit | edit source]

We propose an explosion propagation algorithm that:

  • Handles subconstructs nearly correctly, and far more so than the current system.
  • Hopefully runs faster than the current explosion algorithm, which would make a larger maximum explosion radius feasible.

The basic idea:

  • Track the explosion on the main construct grid only.
  • Blocks on other grids will be projected onto this grid.
  • The angle rule allows us to precompute the order in which to process the grid cells.

Static precomputation[edit | edit source]

At current explosions cannot travel to a new cell if the direction from the current block is 90 degrees or greater. This is actually equivalent to saying that every step the explosion takes must take it further from the origin. So there is no need to compute the angle explicitly. In fact, since the result of a nearer cell never depends on the result of any farther cell, it's possible to process the cells in a fixed order, namely the order of their distance from the explosion origin, without having to keep an explicit queue of cells to process.

Code sketch to precompute that order:

public static class ExplosionUtility {
    protected struct ExplosionVector : IComparable {
        // sbyte to save space. Explosions probably won't exceed 127 m radius...
        // Compiler will probably pad with one more byte but that's fine.
        public sbyte x;
        public sbyte y;
        public sbyte z;
        
        public int sqrMagnitude {
            get {
                return (int) x*x + (int) y*y + (int) z*z;
            }
        }
        
        // Sort by (squared) Euclidean distance.
        public int CompareTo(object obj) {
            ExplosionVector other = (ExplosionVector) obj;
            return this.sqrMagnitude - other.sqrMagnitude;
        }
    }
    
    // Or whatever radius we decide.
    public const float maxRadius = 20.5;
    // Should be no greater than cubeUsableDiameter^3.
    // maxRadius shouldn't be much larger than cubeUsableRadius anyways, as this will cause the sides to be overly flattened.
    public const int maxVolume = (int) ((4.0 / 3.0) * Math.PI * maxRadius * maxRadius * maxRadius);
    // Fixed sequence of cells to examine.
    protected static readonly ExplosionVector[] sequence = new ExplosionVector[maxVolume];
    
    // Usable radius of penetrated. Should be almost as large as maxRadius.
    protected const sbyte cubeUsableRadius = (sbyte) maxRadius;
    // Index of the central element of penetrated.
    protected const int cubeOffset = cubeUsableRadius + 1;
    // Includes a one-element border, necessary if we don't check which cell the explosion could propagate from.
    protected const int cubeDiameter = 2 * cubeOffset + 1;
    // Elements are true iff that cell has been penetrated by the current explosion.
    protected static bool penetrated[,,] = new bool[cubeDiameter,cubeDiameter,cubeDiameter];
    
    static ExplosionUtility () {
        const int cubeUsableDiameter = 2 * cubeUsableRadius + 1;
        const int cubeUsableVolume = cubeUsableDiameter*cubeUsableDiameter*cubeUsableDiameter;
        
        Assert(maxVolume <= cubeUsableVolume);
        
        // Set up the sequence of cells by taking all cells in the cube and sorting by Euclidean distance.
        ExplosionVector[] fullSequence = new ExplosionVector[cubeUsableVolume];
        
        int i = 0;
        for (sbyte x = -cubeUsableRadius; x <= cubeUsableRadius; x++) {
            for (sbyte y = -cubeUsableRadius; y <= cubeUsableRadius; y++) {
                for (sbyte z = -cubeUsableRadius; z <= cubeUsableRadius; z++) {
                    fullSequence[i].x = x;
                    fullSequence[i].y = y;
                    fullSequence[i].z = z;
                    i++;
                }
            }
        }
        
        // Keep only the cells within the maxVolume.
        Array.Sort(fullSequence);
        Array.Copy(fullSequence, sequence, maxVolume);
    }
}

Note that this only has to be computed once ever---you could store it as a fixed binary file that is loaded into the game if you so wished.

Computing the blocks that could be affected[edit | edit source]

We choose one (sub)construct to propagate the explosion on. The entire explosion will be tracked on this grid, henceforth referred to as the "primary" grid. This could be the nearest (sub)construct, or always the main construct; I could see arguments being made for both. We then precompute all the blocks that fall into each cell that could be affected by the explosion. As an approximation, we limit the maximum number of blocks that can be assigned to each cell to one, or maybe two.

  1. Loop through all secondary constructs that could be affected by the explosion.
    1. Loop through all cells in the secondary construct in the cube that could be in range of the explosion. Note that we can use the loop bounds to exclude areas outside the construct's bounding box.
      1. If there is an alive block there, add it to the cell. Since the grids are not aligned, we will have to transform the cell position to the primary grid coordinate system to determine which primary cell it falls into. This can either be done via matrix multiplication, or we can keep a running position in the primary grid.
  2. Loop through all cells in the primary construct in the cube that could be in range of the explosion. Note that we can use the loop bounds to exclude areas outside the construct's bounding box.
    1. If there is an alive block there, add it to the cell. Since this is the primary grid it's a simple offset in each index.

WIP code sketch:

protected static void PopulateBlocksToHit(ExplosionDamageDescription DD) {
    Array.Clear(blocksToHit, 0, penetrated.Length);
    
    AllConstruct primaryConstruct = DD.primaryConstruct;

    for (AllConstruct secondaryConstruct within range of explosion) {
        PopulateSecondaryConstruct(primaryConstruct, secondaryConstruct);
    }
    
    Vector3i primaryLocalOrigin = round(primaryConstruct.transformToLocal(DD.origin));
    Vector3i minBound, maxBound;
    
    ComputeBounds(primaryConstruct, primaryLocalOrigin, DD.radius, minBound, maxBound);
    
    for (int x = minBound.x; x <= maxBound.x; x++) {
        for (int y = minBound.y; y <= maxBound.y; y++) {
            for (int z = minBound.z; z <= maxBound.z, z++) {
                if (x*x + y*y + z*z > maxRadius) continue;
                Block block = C.block(x,y,z);
                if (block != null && block.isAlive) {
                    int xIndex = x - primaryLocalOrigin.x;
                    int yIndex = y - primaryLocalOrigin.y;
                    int zIndex = z - primaryLocalOrigin.z;
                    blocksToHit[xIndex,yIndex,zIndex] = block; // By doing the primary after the secondaries this ensures primary has priority.
                } 
            }
        }
    }
}

protected PopulateSecondaryConstruct(AllConstruct primaryConstruct, AllConstruct secondaryConstruct) {
    Vector3i minBound, maxBound;
    
    Vector3i secondaryLocalOrigin = round(primaryConstruct.transformToLocal(DD.origin));
    ComputeBounds(secondaryConstruct, DD.radius, minBound, maxBound);
    Transform transformToPrimary = primaryConstruct.toLocal * secondaryConstruct.toWorld;
    
    for (int x = minBound.x; x <= maxBound.x; x++) {
        for (int y = minBound.y; y <= maxBound.y; y++) {
            for (int z = minBound.z; z <= maxBound.z, z++) {
                if (x*x + y*y + z*z > maxRadius) continue;
                Block block = C.block(x,y,z);
                if (block != null && block.isAlive) {
                    Vector3i index = round(transformToPrimary * Vector3(x, y, z)) - primaryLocalOrigin;
                    blocksToHit[index.x,index.y,index.z] = block;
                } 
            }
        }
    }
}

protected ComputeBounds(AllConstruct C, Vector3i localOrigin, float radius, ref Vector3i minBound, ref Vector3i maxBound) {
    radius = min(radius, maxRadius);

    int minX = max(C.minX, localOrigin.x - DD.radius);
    int maxX = min(C.maxX, localOrigin.x + DD.radius);
    int minY = max(C.minY, localOrigin.y - DD.radius);
    int maxY = min(C.maxY, localOrigin.y + DD.radius);
    int minZ = max(C.minZ, localOrigin.z - DD.radius);
    int maxZ = min(C.maxZ, localOrigin.z + DD.radius);
    
    minBound = Vector3(minX, minY, minZ);
    maxBound = Vector3(maxX, maxY, maxZ);
}

Accuracy[edit | edit source]

For a one-axis spinblock turret with a relative translation drawn uniformly at random and a relative rotation \theta \in \left[ 0, 45^\circ \right], the probability that a particular primary cell will have two secondary cells fall into it is

\left( \frac{1}{\cos \theta} - 1 \right)^2

The worst case is at 45°, where there is a 17.16% chance of this happening.

For the average case, if the angle between the grids is also drawn uniformly at random, the chance for a double drops to just 2.88%.

Interpenetrating constructs could also cause more than one block to fall in the same primary cell.

But overall, I don't think these cases are common enough to justify considering more than one block per cell, or two at most.

Propagation[edit | edit source]

With the cell sequence precomputed, we need only iterate straight through it to compute the effects of an explosion.

protected static void Explosion(ExplosionDamageDescription DD) {
    PopulateBlocksToHit(DD);
    int volume = Math.Min((int) ((4.0 / 3.0) * Math.PI * DD.radius * DD.radius * DD.radius), maxVolume);
    
    // Necessary if we don't check which side the explosion could propagate to a cell from.
    Array.Clear(penetrated, 0, penetrated.Length);
    
    penetrated[cubeOffset, cubeOffset, cubeOffset] = processCell(0, 0, 0); // always hit the orgin cell
    
    for (int i = 1; i < volume; i++) {
        ExplosionVector cell = sequence[i];
        int xIndex = cell.x + cubeOffset;
        int yIndex = cell.y + cubeOffset;
        int zIndex = cell.z + cubeOffset;
        
        // Cells closer to the origin are guaranteed to have already been processed;
        // cells further away are guaranteed NOT to have already been processed.
        // So the angle/distance rule is implicitly enforced with no explicit check!
        // However if we do check as shown here, we don't need to clear the penetrated[] array or include a 1-block border.
        if ((x > 0 && penetrated[xIndex-1, yIndex, zIndex]) || 
            (x < 0 && penetrated[xIndex+1, yIndex, zIndex]) ||
            (y > 0 && penetrated[xIndex, yIndex-1, zIndex]) ||
            (y < 0 && penetrated[xIndex, yIndex+1, zIndex]) ||
            (z > 0 && penetrated[xIndex, yIndex, zIndex-1]) ||
            (z < 0 && penetrated[xIndex, yIndex, zIndex+1])) {
                penetrated[xIndex, yIndex, zIndex] = processCell(xIndex, yIndex, zIndex);
                if (DD.DamagePotential <= 0.0f) return;
        }
    }
}

Hopefully this will reduce the space and time cost enough to support a significantly larger radius:

  • The current code requires one int and one Vector4i per cell, for a total of 20 bytes per cell. Assuming ExplosionVector is padded to four bytes each and bool is one byte, this proposal uses 5 bytes per cell, a factor of 4 less. Actually, with sequence being sized to the sphere rather than the entire cube, it's probably closer to a factor of 6.
  • There is almost no math remaining in the runtime loop (apart from actually damaging cells). Indexing/dereferencing is probably going to be the major cost.

Cell processing[edit | edit source]

To process a cell, we try to destroy the prepopulated block there (if any). If the cell is empty or the block is destroyed, the cell is penetrated. Otherwise it is not.

private bool processCell(int xIndex, int yIndex, int zIndex) {
    Block blockToHit = blocksToHit[xIndex,yIndex,zIndex];
    if (blockToHit == null) return true;
    tryToDestroyBlock(blockToHit);
    return !blockToHit.isAlive;
}

Barrel damage[edit | edit source]

One side-effect of making the subconstruct explosion rules more accurate is that the barrel damage situation---which already often results in most cannons being disabled in the first few seconds of a battle without a commensurate amount of damage dealt to the rest of the ship---is only going to be exacerbated since turrets will no longer be ignored by deck hits. Options include:

  • Make barrel blocks much more durable. Unfortunately it's going to be hard not to make them useful as armour while making them durable enough so that it's worth armouring other parts of a turret.
Some variants that have been proposed:
  • Base hit points and/or AC on gauge.
  • Pool barrel hit points together.
  • Multicell barrel pieces.
  • Make barrels not blocks at all, and instead simply draw a non-colliding barrel based on sliders or such. Perhaps require an unobstructed ray trace from the firing piece to the end of the barrel in order to traverse outwards/fire if you still want a small weak point at the firing piece.

People may have other ideas as well. IMO even against non-explosives barrels get cut far too easily right now.

Containment damage boost[edit | edit source]

I suggest we nix this unless we can come up with a better idea:

  • It's not a very realistic model.
  • I don't think anybody who hasn't read the source code even notices.
  • It's taking up processor cycles.

Early termination via Russian Roulette[edit | edit source]

This is supposing we keep the current explosive damage pool mechanics.

I refer to Russian Roulette (RR) as used in the context of ray tracing: a method of reducing the number of iterations spent on low-contribution branches of the computation. Here's how it would work with regards to explosions:

Current behavior[edit | edit source]

Whenever an explosion deals damage to a cell, its damage potential is reduced by 10% (explosionReductionCoefficient) of the (pre-armour) damage dealt. If no blocks were destroyed, damage potential would fall (roughly) exponentially as cells take damage, but never reach zero. If blocks are destroyed it falls slower (since only the damage needed to destroy the block is being taken off rather than the full amount). Thus every visible block within the radius will always be explored.

Proposal[edit | edit source]

Choose a RR threshold damage level, which would be a fixed number (say 50) or a proportion of the starting damage potential (say 5%), or the greater of the two. The benefit will be that for every iteration we spend time computing (apart from air), we are guaranteed to produce a minimum gameplay effect (i.e. damage) in return. As a side benefit, this would also result in less clutter of the damage display.

While the damage potential is above the RR threshold, the computation behaves as it does now.

If the damage potential Y is below the RR threshold, when it comes time to subtract X damage from the damage potential, instead do the following:

  • With probability X / Y, terminate the explosion immediately. This skips the remaining iterations, which makes the computation cheaper.
  • Otherwise, continue the explosion with no reduction in damage potential.

The expected damage to any cell (ignoring the effect of block destruction opening new paths) remains the same.

Deterministic variant[edit | edit source]

If we are willing to give up the above property, we can use a deterministic variant instead. This is very simple: always deal at least the RR threshold damage even if it is greater than the damage potential (but no more than 1 / explosionReductionCoefficient times the damage potential). This will cause the damage potential to reach 0 and terminate within a finite number of steps.