Game dev, procedural generation, and general coding ideas I come up with and want to make sure others can consider as well. I try to cover a lot of the details / use cases that come to mind, but it would be difficult to cover them all. Not all of these ideas are fully thought through, but they might still be pretty close to usable implementation descriptions. I'll try to update this whenever I think of something to add to it. If you use one of these ideas directly, and you got it here first, credit is appreciated but certainly not required! Credit is whatever, just please stop adding to the development and creativity obstacle minefield that is the sea of software patents.
- Generate procedural noise, or perform another function on a particular lattice in N-dimensions, by constructing the lattice as a union of copies of its reciprocal lattice.
- Look at the points that each reciprocal lattice misses on the original lattice. Keep placing reciprocal lattices until those are covered.
- They could be straight down the main diagonal, they could be circulantly offset per coordinate, etc.
- The union of N+1 OpenSimplex lattices forms an isometry with a Simplex lattice.
- Wildly different technique.
- Use the original lattice to derive the offsets.
- Perhaps pick one point on each, using hyperplane comparisons or (equivalently) dot products.
- It seems that dot(a, b) = dot(M * a, inv(M) * b) where M is the lattice (or other) transform.
- To pick multiple points on each, choose the desired radius and find which points are mutually exclusive or not, and what the properties of the clusters and conditions are.
- Sometimes a lattice can be divided in ways other than into copies of its reciprocal, such as Simplex -> two cubics.
- Check the set and number of reciprocal lattices and look at how they can be grouped together.
- e.g. If it takes four copies, ABCD, maybe group AC and BD.
- 7D simplex would take 8 copies of OpenSimplex to mimic, ABCDEFGH. Consider AE+BF+CG+DH, ACEG+BDFH
- "AE" in the above example could be the cubic lattice stretched by a different amount.
- Check the set and number of reciprocal lattices and look at how they can be grouped together.
- Instead of parameterizing it as multiple copies of the other lattice type, consider one copy with extra non-integer points in each cell.
- Or more than one copy, each of which have extra points in each cell.
- Orient lattice so one set of lattice vectors is parallel to one of the coordinates (e.g. noise3XZBeforeY). Then consider the base lattice in the plane that the vectors line up with, and the vectors as extensions/offsets originating from those points.
- Five overlapping offset A4 (original OpenSimplex) lattices, form A4*.
- Find closest point on first.
- Consider that point as the center of the simplex on the next. Pick one surrounding point.
- Repeat until you have all 5 points.
- Replace A4 with An and find n+1 points.
- When finding the closest point on the first lattice copy, for even dimensions start by finding the closest point on the central N-1 dimensional cell. In odd dimensions start by finding the closest point on the centeral N dimensional cell.
- Pair opposite points (e.g. 100 vs 011 for 3D, 1010 vs 0101 for 4D, etc.) using abs() to get score for the closest of the two.
- Pit all pairs against each other. Then pick best out of the pair.
- Then successively check the best directions to go as you try to move towards <1,1,1,1> or <0, 0, 0, 0>
- In even dimensions, flipping the +/- direction to look comes from the hyperplane the central cell is on. In odd dimensions, it comes from the closest shape's winning point itself.
- Parameterize noise lattice in whichever way desired (e.g. skew formula, overlapping lattices, both, etc).
- Divide the unit cell(s) along each dimension independently (e.g. 4x4x4x4 for 4D noise), to create a lookup index.
- Each index points to a list of all points that could contribute to that subdivided area, but not others.
- 4x4x4x4=256 indices.
- In general, doesn't have to be "each dimension independently". It can be decided via other hyperplanes. The point is that it's ok for an index to contain more contributions than actually ever overlap on the noise, as long as it's within reason.
- Could also use an octree-style lookup instead of a fixed grid.
- When identifying a lattice to generate noise on, or perform another operation on, derive a circulant basis matrix.
- Many of the bases provided here are not circulant. http://www.math.rwth-aachen.de/~Gabriele.Nebe/LATTICES/A3.html
- Circulant basis matrices seem to make the skew/unskew transforms more simplifiable. Skew is inverse of basis. They can make point picking more straightforward too.
- Conversely, use non-circulant basis matrices for noise traditionally computed using circulant bases. Study the hyperplanes that decide which points to pick between.
- Hide grid in cardinal plane slices if constructing an otherwise-good lattice out of unions of hypercubics.
- In 3D: X = dot(vec3(0.666...), X) - X
- In general, pick the vector-populating constant so that all the matrix vectors become orthogonal.
- In matrix form, it is always symmetric, and also always orthonormal. So it would be its own inverse.
- Can bake into existing lattice transforms or use separately.
- (N-1)-dimensional OpenSimplex skew matrix, with added vector and coordinates so that it becomes an orthonormal NxN matrix.
- (N-k)-dimensional OpenSimplex skew matrix, with the remaining k vectors rotated until they are symmetric w.r.t the lattice and matrix is orthonormal.
- (N-k1-k2-...)-dimensional OpenSimplex skew matrix, next k1 vectors grouped like above, next k2 vectors grouped like above, etc. Optimizing each group independently to look best as a plane or hyperplane.
- In 3D, rotated BCC is isomorphic to Simplex. Rotated FCC is isomorphic to OpenSimplex.
- After rotation, the lattices repeat in cubic groups, albeit larger ones. 3x3x3 for Cubic or BCC, 6x6x6 for FCC.
- This means, each individual point inside those repeating cells can be used as an offset for a cubic lattice.
- While we're at it, we can shrink the lattices and offsets to 1x1x1 and adjust our frequency accordingly, where we use it.
- Some groups of lattices might be condensible into higher frequency lattices in at least one axis, but maybe not.
- The 3D noise oriented to point down the main diagonal, seems to repeat in triangular prism or hexagonal-prism blocks too.
- Might facilitate efficient generation. Might facilitate efficient seamless-tiled-noise generation.
- Many lattices in higher dimensions, whose basis / inverse basis matrices have all-rational (or at least commensurable) values, should have this property.
- In Simplex noise 3D, instead of picking path sort order e.g. 000 -> 100 -> 101 -> 111 to find four vertices, pick: 000, 111, 100 vs 011, 010 vs 101, 100 vs 011.
- Five vertices instead of four, but logic to pick points can be simpler.
- Would extend to higher dimensions like 1000 vs 0111 and 1010 vs 0101, but would not have the same complexity scaling.
- In 3D, this still needs (x+y+z)/3 type skew on the input. But in 4D+ (and also 3D), it does not decompose a hypercube into simplices by checking sort order.
- Identical in 2D.
- Can reduce lookup table size and index complexity.
- Bonus: If you've already found N+1 vertices, you can skip the rest.
- In CPU code, we often have the freedom to use decently-sized lookup tables for gradients. So, we should make the best of it.
- We don't want vectors that point towards other nearby lattice points, or point towards cell boundaries, to avoid "clumping" (source "Improving Noise")
- Start with the "neighbor figure" of the lattice. It's like a vertex figure, but the directions to the vertices are proportional to the distance of the neighbor.
- Expand it so that the new edges become as long as the shortest existing edges.
- Normalize it, or otherwise make all the new vectors the same length.
- In GLSL code (or other places where it's better to not use lookup tables), perhaps pick a facet, pick between the facet's vertices, and expand it outward.
- Related: When producing dx,dy,dz,etc. can use normal unskew transform, or something else
- e.g. unskew transform which rotates 180 degrees about the main diagonal (compose it with the "Rotating a lattice about the main diagonal" transform)
- Generate two noise values simultaneously. The vectors chosen at each vertex are as follows:
- First vector chosen normally
- Second vector chosen to be orthogonal, or within a certain degree of orthogonality from a subset of the noise's gradient set.
- See if this improves zero-surface-intersection cave generation, or other features that require two noise values.
- To generalize: Can be done to pick up to N (nearly-)orthogonal gradients in N dimensional noise.
- Can also choose any polytope to relatively match the gradients to, e.g. a (nearly-)regular tetrahedron in 3D. Choose 4 gradient directions which intersect the unit sphere to form a tetrahedron.
- Hexagon in 2D, rhombic dodecahedron in 3D, rhombic 20-cell in 4D, ...
- For OpenSimplex: hexagon, cuboctahedron, runcinated 5-cell, ...
- Find it for your lattice of choice.
- It looks like for N-dimensions, the figure has (N)(N-1) faces, so (N)(N-1)/2 pairs
- [(r-t1^2)(r-t2^2)...]^2 where each t is the direction across the pairs
- Parameterize in unskewed coords, or in skewed coords with proper rescaling
- Should eliminate inherent zero-space for An* lattices in high enough dimensions
- But will all the multiplies push things too close to zero anyway?
- Applying noise to a surface where you want to change the direction of the pattern (like Gabor noise)
- Unit vector map on the surface of the object, rotated 90 degrees in tangent plane
- Dot product of unit vector with noise derivative
- Derivative itself is like an anisotropic kernel on gradient noise. Experiment with custom kernels.
- But derivatives have the advantage that dF/dt = <dF/dx, dF/dy> dot <dx/dt, dy/dt> (chain rule) so the noise itself doesn't need to care about the direction, just output the derivative.
- Approximate sine with piecewise splines: split by half or full wavelength.
- Approximate sine with taylor polynomials. Perhaps bake them into the kernel.
- Noise on a simplex lattice or otherwise, with fixed-center kernels. The sine direction is either provided or generated, and its domain is offset.
- Gabor noise and Voronoi noise might use cubic grids with N points per cell. Apply techniques from one, to the other.
- Instead of a cubic grid, use another lattice. The points could be considered as within each lattice point's Voronoi cell.
- The offset could be spherical, within the neighborhood figure, or within the maximum range enabled by how you pick the points on the lattice.
- Start with a noise (or other) heightmap
- Place your Gabor noise points on the heightmap. Get the slope/derivative at each. Orient the sine of the gabor kernel so that the waves go perpendicular to that.
- If generating an area, you probably want to cache these points, either in a hashmap or an array.
- Additively and/or multiplicatively "erode" the heightmap, using the Gabor noise. You might need to erode most near where the gabor noise is near zero, and least when it's far from zero.
- Paths formed by noise-near-0 tend to split off only in multiples of two. Could consider taking three instances of Gabor noise and a min/smin of the three squared values, to address that.
- Multiple iterations. Each takes the derivative of the previous, after the previous step has been factored in. Each iteration would typically have a new frequency and amplitude.
- Could approximate the full derivative by using the previous derivative stored in the Gabor kernel.
- Either directly stored, or indirectly stored in the form of the sine's rotated direction.
- Combined with the derivative of the sine.
- If approximate spline-sine is used, approximate derivative could be an offset of the spline (like d/dx sin = cos, and cos(x)=sin(x+k)) instead of the actual derivative.
- Could approximate the full derivative by using the previous derivative stored in the Gabor kernel.
- Try the "controllable anisotropy using noise derivative" technique instead of actual Gabor noise.
- Extend to 3D by picking the Gabor sines in 3D the same way, just ignoring the vertical direction (one option).
- Gabor noise. Either 1D noise, or higher dimensional noise stretched in different directions.
- Superformula. Replace sin() by noise(sin, cos) and Replace cos() by noise(cos, -sin). Add extra dimensions too.
- The list goes on.
- Been done before?
- Fourier transform of texture
- Fourier transform of noise at multiple scales
- Fit the Fourier transform of the multiple scales of noise to the Fourier transform of the texture
- Apply the noise at each of those scales at each of the amplitudes
- Multiple channels. Can be separated as RGB or other.
- Gabor, Voronoi, etc. Each point has some base lattice point (or cell) that it was offset from, which can be put into the queue.
- It seems that not all of the neighbors are necessary for successful propagation throughout the generated region.
- Experiment with removing some neighbor-map points.
- Probably a generalizable scheme, along the lines of removing one of each pair of opposite points.
- Likely not the only generalizable scheme of what can be done.
- Transform once, then scale the frequencies on skewed coordinates.
- All you need to cover all of 3D space with more than one point at a time, is a BCC lattice, and a cube around each point that stops its corner at the nearest lattice neighbor.
- Bump function [(0.5-dx^2)(0.5-dy^2)(0.5-dz^2)]^3 or similar, for each kernel.
- Rotate the noise, because cardinal planes will not look great.
- In Cubic Value Noise, you pick values at each point, and blend between them using a cubic spline. This is equivalent to picking the spline's slope at each point based on surrounding points.
- Generalize to simplex (or other) grid: Pick value, pick gradient based on neighbor values (and possibly current value).
- Neighbors e.g. surrounding hexagon in 2D, cube or rhombic dodecahedron in 3D BCC lattice.
- Compute gradient, e.g. compute slopes of all neighbor points from the current, and average them. Might cancel out the value of the current point from the equation entirely.
- Blend or add contributions using any known technique.
- Pick gradients first, then pick values.
- Pick values, e.g. the average gradient extrapolation from a neighbor to the current point.
- Or, average of the results of each pairing of the current point with a neighbor, where the extrapolation is as if the neighbor's gradient were (neighbor.grad - current.grad).
- Pick values, e.g. the average gradient extrapolation from a neighbor to the current point.
- In any case, consider weighted average instead of average. Weighted average can come from inverse neighor distance, a distance falloff curve, etc.
- Replace the grid from any conceived noise algorithm, with poisson disc sampling.
- Keep simplex-style noise generation.
- Pick a falloff function from each point, e.g.
(1-dist^2)^k - Either find points in range of a given evaluation point, by maintaining in any suitable data structure,
- or do "area generation" where you go over each point and loop over the area it covers.
- Pick a falloff function from each point, e.g.
- Perhaps size the falloff range as the minimum distance between points. They could be any size, though.
- Replace Poisson with any other nice point distribution you can use, e.g. may be described as blue noise or low-discrepancy and/or also isotropic.
- Compare each point A to others B. Start with the closest and move outward, sorted by distance / squared distance.
- Draw a segment from A to B. Then draw a line going through B that's perpendicular to the segment AB.
- Anything on the opposite side of that line as A is removed from the running as a neighbor to A in this algorithm.
- Repeat until there are no points remaining.
- This can be optimized with gridcells or lookup trees for local lookup etc.
- Sometimes there will be points where only one counts the other as a neighbor, and not vice-versa.
- You can either keep this data or discard it, depending on your use case.
- There may be faces or facets (up to whatever your dimensionality is) that aren't simplices.
- If you need to address these as simplices, you can triangulate them. Otherwise you can leave them as-is.
- Would be interesting to compute the dual graph of this, which may resemble Voronoi but not be quite like it.
- Been done before?
- Instead of finding the centroid, you want move each point towards being the circumcenter of its closest neighors.
- Could calculate exactly, but better: Each step is approximate, so the movement towards the circumcenter can be approximate too.
- Move each point away from its closest point. Could be constant. Could be directly proportional to distance. Could be proportional to any power of distance, positive or negative, whole or fractional. Could use physical repulsion formulas too and/or instead and/or equivalently.
- Could also be scaled by smallest, largest, average, or other function on the closest neighbor from each. Or by some power thereof, similar to what's described above.
- Then, it may not technically converge, because points still jittering around. So actually find N+1 closest neighbors (where N is the number of dimensions) and scale the amount moved by the difference between closest and furthest points, so that it's zero when they're the same.
- Regardless of whether using this or another relaxation algorithm, constrain to an area by considering reflected copies of the current point being processed, across the container boundaries.
- For a polygon/polyhedron/etc., reflect over each edge and consider a copy.
- For a circle/sphere/etc., reflect a copy over the closest point on its surface.
- Maybe also the point opposite if necessary.
- May need to spawn dummy points in the form of a regular simplex to achieve convergence if you don't have enough points already in the diagram.
- For a cylinder, do that for the circular part and reflect over the top/bottom normally. Generalizes to any cartesian product of any shapes you already know how to do.
- Start with http://johanneskopf.de/publications/blue_noise/
- Optionally omit the fresh point set for each tile. Instead aim to create seams close to the edges inside the tiles.
- One idea: First overlay all 4. Choose boundaries to pre-cut them such that there is some overlap.
- e.g. expanding borders of each subtile color out by some configurable amount
- e.g. e.g cutting in half horizontally or vertically down the middle, perhaps also with that padding.
- Then use the Voronoi edge path search approach described in the paper to cut the seams.
- Can take the point in the center as the common endpoint, or can move it around until it is in a good position.
- Jumping to neighbors, trying cell centers/centroids by any metric, dart throwing, or other method.
- One idea: First overlay all 4. Choose boundaries to pre-cut them such that there is some overlap.
- Optionally replace the Voronoi neighbor algorithm with Delaunay, or the simple Delaunay approximation described above.
- Use a weight function based on the edge length iself, since that is the length of the neighbor being split.
- It will zig-zag between points. Need a way to determine which are on which side.
- One option: Keep points on the side where the angle is obtuse, discarding where acute.
- Triangles/Hexagons: Place triangles, with 3 colors each.
- The colored sub-regions come from the hexagonal Voronoi cells of the triangular grid, which play the same role as the 45-degree squares seen when adjoining wang tiles.
- 6 triangles join together at each vertex to form a hexagon of all the same color.
- Either generate a new point set for each triangle to do the seams, or translate the no-fresh-point-set technique.
- Subdivide each triangle into more triangles. Then adapt the processes from the paper for subdivision.
- Generalize to higher dimensions, through the A or A* lattices, their cells, and their Voronoi cells. (Probably more ideally A*)
- Both ideas build off of https://www.seedofandromeda.com/blogs/29-fast-flood-fill-lighting-in-a-blocky-voxel-game-pt-1 and https://www.seedofandromeda.com/blogs/30-fast-flood-fill-lighting-in-a-blocky-voxel-game-pt-2
- Difference in both: The items on the queue should be the cells which need light values, not the cells whose light values were just set
- You can also keep track of which cells are already on the queue, and avoid adding them twice. That can become an issue here. One way would be to store a temporary value into its cell that indicates such.
- Old Idea:
- Derive the formula that computes the current euclidean distance or attenuation from a light, given the values of its neighbors.
- A To handle cells affected by multiple light sources, mix the values, or parameterize the formula to accept every neighbor, and to blend.
- Should work for cubic and non-cubic, in various dimensionalities.
- New Idea:
- Common flood-fill lighting effectively calculates manhattan distance, as it curves aroun corners. Since we want Euclidean distance, we want to know the general form of the distance value from a light source.
- It's composed of "pythagorean" segments added together like
sqrt(x1^2+y1^2+z1^2)+sqrt(x2^2+y2^2+z2^2)+.... - Can reduce to
c1*sqrt(s1)+c2*sqrt(s2)+c3*sqrt(s3)+...where we optionally only consider valid values ofs1, s2, ... - Also optionally only consider reducible square roots (e.g.
sqrt(8)=2sqrt(2))
- It's composed of "pythagorean" segments added together like
- Find all the possibilities we want to store. Can be done recursively or by considering all combinations that don't exceed a maximum. Create some lookup tables.
- One that converts the value index to the actual brightness
- One that associates each value index with the index of its "manhattan" attenuation (basically
value+sqrt(1)) - One that associates the brightest in a pair or triplet of neighbors which should attenuate in a euclidean fashion, with a entries that describes the one or two other necessary neighbors, and the value index to attenuate to.
- The above can be replaced with any fitting data structure used in software development, game development, computer graphics, etc. Basically you have sparsely defined 2->1 and 3->1 value associations. HashMaps and various tree structures come to mind.
- Could combine / separate tables in multiple of ways. One way could be to store the entries in a second table, reserve a bit that marks the end of a given set, and add an index to a starting entry to the same table as the manuattan attenuations.
- You probably want to clamp any attenuations that would be greater than the minimum distance which no longer produces a light value, to that minimum distance, so you don't have to store more than necessary.
- Common flood-fill lighting effectively calculates manhattan distance, as it curves aroun corners. Since we want Euclidean distance, we want to know the general form of the distance value from a light source.
- Smooth distance field from trunk and/or branches modulated by 3D noise.
- Could add to tree by propagation from trunk, so we don't get floating leaves.
- Could also be applied to generating boulders, ore deposits, or anything.
- Modulate by distance from center or other distance field / approx distance field, either significantly, moderately, or not at all.
- Each blocktype assigned weight from noise (or whatever). Best weight wins.
- Could be one noise value per block.
- Could be multiple blocks assigned to different value ranges on one noise. Convert it into a per-block weight.
- Probably needs to be a standard for weight such as 0 to 1, which everything is assigned to.
- Interpolate blocktype weights over region boundaries.
- Same block type present in both: interpolates between two regions' definitions.
- Block type only in one: fades to zero
- Generalized, can blend between different noise types.
- Problem: When a region has large values for some parameters, and near-zero values for others, the expected derivative of the noise is different. This causes region to become elongated.
- Basic idea for a solution: Stretch regions' cells in lookup space to compensate for this.
- Solution idea 1: Modify Voronoi to angle the boundaries arbitrarily.
- Solution idea 2: Give each biome an extra coordinate to represent where it is on a surface/hypersurface, which creates th e desired effect.
- e.g.
(1-t*t)*(1-p*p), or similar formula. Perhaps one more tuned to the actual derivatives of the noise.- Raise it to a power, raise the squared terms to higher powers, etc.
- Distance gets bigger faster along the axis that needs it the most, to compensate for noise derivative tendencies.
- e.g.
- f(noise) > height -> compare(noise, invF(height))
- > stays as > or becomes < depending on increasing or decreasing function.
- May need to be split into multiple components for a non-monotonic function (e.g. f(x)=abs(x))
- Use this to split up individual noise evaluations and stop evaluating (or never start evaluating) noise when it won't affect the final comparison (block vs no block)
- Also helps avoid computing costly f(x) such as exp or tanh
- Region blending may need special interpolator, or may need to override this. If most of your world is constant regions rather than transition/blended regions, might be worth tradeoff!
- Base idea: When generating multiple instances of noise per block/cell/etc to decide if that cell is there, you don't always need to calculate every instance to be certain there is or isn't a block. I originally got this idea from melodive who created Fugl.
- The extension:
- Keep track of recent noise evaluations, in a tree or per column/row, and either the position or distance.
- Noise typically has a max slope, so you have a bound on the min/max value that noise instance could take. Maybe it stops you from needing to compute it at the current block.
- Of course, works for functions other than noise, and works for reduction operators other than addition.
- Give each block extra bits to correspond to liquid, presence/quantity/type/etc.
- Blocks which are the full cube / other shape can use those bits for other things, like color.
- Parameterize, (approximately) preserving volume, a noise or a placer that deposits ores more spread out and less deep when a surface is near.
- Generate caves using a differentiable noise formula.
- One choice: Domain-warping the ore generator, esp. if it's noise.
- Or, upon deciding the base point for placement, determine approximate distance and direction to surface, and generate accordingly
- Distance + direction can come from pre-generated blocks, or from a differentiable formula.
Adapting grid-based cellular automata or "diamond-square" based biome generation to arbitrary point distributions
- Point distributions, e.g. blue noise or jittered grids.
- Need way to determine which points are neighbors of a given point. Delaunay, approximate delaunay described earlier, Voronoi, etc.
- If a rule previously looked at neighbors N/E/S/W, a few options to adapt include:
- Pick 4 closest neighbors, optionally in sequential order. Can vary CW/CCW or preserve.
- Pick 4 neighbors closest to forming a "+" w.r.t their angles
- If a rule previously looked at NE/NW/SW/SE, a few options to adapt include:
- Pick 4 furthest neighbors that are still considered neighbors by this metric
- Pick 5th-8th closest neighbors....
- Pick 4 neighbors closest to forming a "+" w.r.t their angles, biased to the further neighbors
- ... in either case above, overflowing can start repeating closest neighbors, or jumping into neighbors of neighbors and neighbors of those, etc. I wouldn't take this as a first choice though.
- Or, adapt the ruleset to take arbitrary numbers of points, perhaps up to some reasonable maximum. Have a way to indicate the number, or that a supplied neighbor values (and perhaps all the rest) aren't to be used (e.g. set to -1 or other numerical indicator)
- Zoom can be based on any possible method for increasing the density of blue noise point distributions preserving the existing points. For neighbors, you can either calculate directly in the next set, or in a manner that only considers the previous zoom layer's points as if each new point were added individually to it.
- Either add a number of points defined by how much you want to zoom, or add them until you stop seeing enough neighbor points that wered defined by the previous zoom amount.
- I use the 3D terms "sphere" and "rhombohedron", but this can be applied to the corresponding shapes in any number of dimensions.
- Construct rhombohedron as diagonally compressed or expanded cube, as in Simplex or original OpenSimplex noise.
- Check if the sphere center lies inside the rhombohedron. This can be skipped if you know the sphere is always larger than the rhombohedron.
- For each vertex...
- Check the vertex for intersection.
- If no intersection, check the edges that lead negative from from that vertex in cubic coordinate space, where applicable.
- e.g. skewed point (0, 0, 0) will have no edges leading negative, but (1, 1, 0) will have edges (1, 1, 0)->(0, 1, 0) and (1, 1, 0)->(1, 0, 0)
- Parameterize formula for squared distance to center of sphere as quadratic of one variable t=0..1 along the edge, and minimize over the line.
- There's an intersection when the minimum squared distance is below the sphere's radius (squared) and 0<t<1.
- Note: if the minimum distance on the line is outside the edge, but there is a small enough distance on the edge, it would already be caught during the vertex checks.
- If no intersection, then for each dimension applicable, check from the edge negative to the opposing edge in cubic coordinate space, towards another edge, to look for an intersection on the face.
- e.g. Edge (1, 1, 1, 0)->(0, 1, 1, 0) has faces [(1, 1, 1, 0)->(0, 1, 1, 0)]->[(1, 0, 1, 0)->(0, 0, 1, 0)] and [(1, 1, 1, 0)->(0, 1, 1, 0)]->[(1, 1, 0, 0)->(0, 1, 0, 0)]
- Check from the fully extrapolated line containing the edge, not just the segment. Then correct for this by verifying the resulting point is within the bounds of the face.
- To do this, convert to cubic/skewed space and check only the necessary dimensions, but not the ones expected to stay constant on the face. This avoids roundoff errors from producing false negatives.
- It should be equivalent to either cast the new line perpendicular to the edge line along the face, or draw the line between the already-computed minimzing points on both edge lines.
- At this point you've already computed the minimizing points for both edges, so you can just store them and use them.
- Again, parameterize the distance formula as a univariate quadratic along this bridging line, and minimize.
- For 4D and higher, repeat for cells etc. No need to repeat for the full shape as that is already accomplished in the first, center-checking step.
- For the above steps, it should suffice as an optimization to constrain the order of checked dimensions and avoid repeats, using a triangular style nested for-loop.
for (int i = 0; i < N; i++) for (int j = i + 1; ...) for (int k = j + 1...)etc. rather thanfor (int i = 0; ...) for (int j = 0; ...) for (int k = 0...)etc.- If only an intersection between a sphere and cube is needed, it becomes simpler. This may already be a common algorithm, I didn't check.
- Moving up edge -> face -> cell -> etc. can immediately return false, the moment a minimizing point does not lie in the edge/face/cell/etc.
- Lines between minimizing points on opposing edges/faces/etc. are always parallel to the perpendicular edges. No extra computations, minimizing point storage, or precomputed direction vectors are needed.
- No skew/unskew formula needed either.
- Fade curves
t * t * (3 - 2 * t),t * t * t * (10 + t * (-15 + t * 6))follow a scheme: solve for polynomial coefficients by enforcingF(0)=0,F(1)=1andF'(0)=0F'(1)=0, then also enforceF''(0)=0F''(1)=0to get the second case, and so-on. - You can also get these curves by taking
G(x) =the integral from0toxofF(x) = (1-(2x-1)^2)^k = (1-x)^k (4x)^kdxwherekrepresents the highest degree derivative you force to zero, then dividing the result byG(1).- If you prefer a fade curve for the range
[-1, 1], you can useF(x) = (1-x^2)^k. - These integrals can be computed straightforwardly enough, and this is probably the simplest way to pre-compute the coefficients. However there's another way that's more friendly toward computation on the fly for arbitrary
k.
- If you prefer a fade curve for the range
F(x, 0) = xF(x, k) = lerp(x^(k+1), 1 - (1 - x)^(k+1), F(x, k - 1))wherelerp(a, b, t) = a + (b - a) * t. This is easily computable with a simple Θ(k) for-loop.
float fade(float x, int k) {
float baseA = x;
float baseB = 1 - x;
float powerA = baseA;
float powerB = baseB;
float value = x;
for (int i = 0; i < k; i++) {
powerA *= baseA;
powerB *= baseB;
value = lerp(powerA, 1 - powerB, value);
}
return value;
}
Aim at player/object's predicted future state, by extrapolating a function of their position, and finding an intersection
- e.g. a polynomial that fits recent positions over time by regression.
- Fixed number of points, weighted constantly
- All points, decreasing in regression weight as they go further back in time
- Derive a quick way to update the function instead of recomputing it
- Could find matrix that determines coefficients of the function, use it to derive a matrix that converts the current coefficients to what they would be if all the data points were one or N steps older, and introduce the new data point(s).
- Possibly the new matrix will incorporate the new data point(s), as the data that will be considered as the old data points will be with the oldest one(s) discarded to make room for the new one(s).
- Might be a quick formula for adjusting the existing coefficients when a new data point(s) come in.
- Polynomial coefficients could be standard, Bernstein, etc.
- Could be a non-polynomial, but regression is performed in a space that can generate coefficients for it.
- e.g. like you can do log least squares to fit data points to an exponential.
- Not sure if an exponential is a good fit for this, just a tool to illustrate the generality.
- Intersect path/curve/function of projectile or movement, with player's extrapolated movement, over time. Vary the path of projectile movement (e.g. by angle) until they intersect at a common time. Possibly vary it smoothly with a limited velocity, or other limiting factors such as acceleration.
- Will probably need to be multiple polynomials/functions, or a function that outputs a vector, because a player's position is probably within 2D space or higher.