From the Depths Wiki
Explore
Main Page
All Pages
Interactive Maps
navigation
Main page
Community portal
Recent changes
Random page
Admin noticeboard
Links
Official Website
Steam Forums
Steam Store Page
Facebook Page
Reddit
Twitter Page
YouTube Channel
Discord
Useful pages
Components
Weapon Design
Guides
Items And Skills
Gamepedia
Gamepedia support
Report a bad ad
Help Wiki
Contact us
FANDOM
Fan Central
BETA
Games
Anime
Movies
TV
Video
Wikis
Explore Wikis
Community Central
Start a Wiki
Don't have an account?
Register
Sign In
Sign In
Register
From the Depths Wiki
474
pages
Explore
Main Page
All Pages
Interactive Maps
navigation
Main page
Community portal
Recent changes
Random page
Admin noticeboard
Links
Official Website
Steam Forums
Steam Store Page
Facebook Page
Reddit
Twitter Page
YouTube Channel
Discord
Useful pages
Components
Weapon Design
Guides
Items And Skills
Gamepedia
Gamepedia support
Report a bad ad
Help Wiki
Contact us
Editing
User:Evil4Zerggin/Explosion algorithm proposals
(section)
Back to page
Edit
VisualEditor
View history
Edit Page
User:Evil4Zerggin/Explosion algorithm proposals
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
== Explosions on multiple (sub)constructs == === Problem === Explosions have extremely unintuitive behavior with respect to subconstructs, as described in [http://www.fromthedepthsgame.com/forum/showthread.php?tid=22694 this forum thread] and [http://imgur.com/a/EBFgS 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 [http://www.fromthedepthsgame.com/forum/showthread.php?tid=23504 Menti's Battleship Brawl Tournament Season 2]. === Objectives === 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 === 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: <pre> 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); } } </pre> 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 === 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. # Loop through all secondary constructs that could be affected by the explosion. ## 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. ### 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. # 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. ## 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: <pre> 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); } </pre> ==== Accuracy ==== For a one-axis spinblock turret with a relative translation drawn uniformly at random and a relative rotation <math>\theta \in \left[ 0, 45^\circ \right]</math>, the probability that a particular primary cell will have two secondary cells fall into it is <math>\left( \frac{1}{\cos \theta} - 1 \right)^2</math> 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 === With the cell sequence precomputed, we need only iterate straight through it to compute the effects of an explosion. <pre> 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; } } } </pre> Hopefully this will reduce the space and time cost enough to support a significantly larger radius: * The current code requires one <code>int</code> and one <code>Vector4i</code> per cell, for a total of 20 bytes per cell. Assuming <code>ExplosionVector</code> is padded to four bytes each and <code>bool</code> is one byte, this proposal uses 5 bytes per cell, a factor of 4 less. Actually, with <code>sequence</code> 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 === 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. <pre> 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; } </pre>
Summary:
Please note that all contributions to the From the Depths Wiki are considered to be released under the CC BY-NC-SA
Cancel
Editing help
(opens in new window)
Follow on IG
TikTok
Join Fan Lab