 • entries
15
57
• views
7735

This journal is dedicated to my auto formation and my experimentations.

Entries in this blog Image Recognition by Equilateral Encoding

Context I recently started reading the book Artificial Intelligence for Humans, Volume 1: Fundamental Algorithms by Jeff Heaton. Upon finishing reading the chapter Normalizing Data, I decided to practice what I had just learnt to hopefully finally understand 100 % of a special algorithm : equilateral encoding. Equilateral Encoding The purpose of this algorithm is to normalize N categories by creating an equilateral triangle of N - 1 dimensions. Each vertex in that triangle is a category and so, because of the properties of the equilateral triangle, it's easy to construct this structure with medians of 1 unit.  For selecting a category, all you need is a location vector of N - 1 dimensions that's ideally inside the equilateral triangle. For example, consider the vertex C and point c. The vertex C is 100% of a specified category, whilst the point c is 0% of that category. The vertices A and B are also 0% of C's category. In other words, the further away a location vector is from a vertex along its median axis, the less it belongs to the vertex`s category. Also, if the mentioned axis distance is greater than the length of a median (all medians have the same length in an equilateral triangle, which is the range of values in this context), then the location vector absolutely does not belong to the specified category. The reason why we just don't select directly a category is because this algorithm is originally for machine learning. It quantifies qualitative data, shares the blame better and uses less memory than simpler algorithms, as it uses N - 1 dimensions. The Application First of, here's the link to my application : https://github.com/thecheeselover/image-recognition-by-equilateral-encoding How It Works To be able to know the similarities between two images, a comparison must be done. Using the equilateral encoding algorithm, a pixel versus pixel comparison is the only way to do so and thus shapes do not count towards the similarities between the two images. What category should we use to compare images? Well, colors of course! Here are the colors I specified as categories : Red Green Blue White Black The algorithm will select the closest category for each pixel according to the differences between both colors and save it's location vector in an array. Then, when both images are loaded, compare each image pixels against each other by computing the median distance, as mentioned before, between both of them. Simply project the first pixel's vector onto the other one and compute the Euclidean distance to get the median distance. Sum all computed median distances This way, it would also works if there were location vectors not totally on a vertex, even though it doesn't happen for the just described comparison algorithm. Preliminaries Of course, this can be really slow for immense images. Downscale the images to have a maximum width and height, 32 pixels in my case. Also, remove the transparency as it is not a color component in itself. If both images do not have the same aspect ratio and so not the same downscaled dimensions, then consider using extremely different location vectors and so just different categories for "empty" pixels against non-empty pixels.     The Code The equilateral encoding table : package org.benoitdubreuil.iree.model; import org.benoitdubreuil.iree.utils.MathUtils; /** * The image data for the image recognition by equilateral encoding. * <p> * See the author Jeff Heaton of this algorithm and his book that contains everything about it : * <a href="https://www.heatonresearch.com/book/aifh-vol1-fundamental.html">Artificial Intelligence for Humans, Vol 1: Fundamental Algorithms</a> * <p> * The base source code for the equilateral encoding algorithm : * <a href="https://github.com/jeffheaton/aifh/blob/master/vol1/java-examples/src/main/java/com/heatonresearch/aifh/normalize/Equilateral.java">Equilateral.java</a> */ public class EquilateralEncodingTable { // The algorithm with only one category does not make sense private static final int MIN_CATEGORIES_FOR_ENCODING = 2; private int m_categoryCount; private int m_dimensionCount; private double m_lowestValue; private double m_highestValue; private double m_valueRange; private double[][] m_categoriesCoordinates; public EquilateralEncodingTable(int categoryCount, double lowestValue, double highestValue) { if (categoryCount < MIN_CATEGORIES_FOR_ENCODING) { throw new ArrayIndexOutOfBoundsException("Not enough categories for equilateral encoding"); } this.m_categoryCount = categoryCount; this.m_dimensionCount = computeDimensionCount(categoryCount); this.m_lowestValue = lowestValue; this.m_highestValue = highestValue; this.m_valueRange = highestValue - lowestValue; this.m_categoriesCoordinates = computeEquilateralEncodingTable(); } /** * Encodes a supplied index and gets the equilaterally encoded coordinates at that index. * * @param equilateralCoordsIndex The index at which the equilaterally encoded coordinates are. * * @return The equilaterally encoded coordinates. */ public double[] encode(int equilateralCoordsIndex) { return m_categoriesCoordinates[equilateralCoordsIndex]; } /** * Decodes the supplied coordinates by finding its closest equilaterally encoded coordinates. * * @param coordinates The coordinates that need to be decoded. It should not be equilateral it doesn't matter, as the goal is simply to find the closest equilaterally encoded * coordinates. * * @return The index at which the closest equilaterally encoded coordinates are. */ public int decode(double[] coordinates) { double closestDistance = Double.POSITIVE_INFINITY; int closestEquilateralCoordsIndex = -1; for (int i = 0; i < m_categoriesCoordinates.length; ++i) { double dist = computeDistance(coordinates, i); if (dist < closestDistance) { closestDistance = dist; closestEquilateralCoordsIndex = i; } } return closestEquilateralCoordsIndex; } /** * Computes the Euclidean distance between the supplied coordinates and the equilaterally encoded coordinates at the supplied index. * * @param coordinates Coordinates of the first n-dimensional vector. * @param equilateralCoordsIndex Index for the equilaterally encoded coordinates. * * @return The Euclidean distance between the two vectors. */ public double computeDistance(double[] coordinates, int equilateralCoordsIndex) { return MathUtils.computeDistance(coordinates, m_categoriesCoordinates[equilateralCoordsIndex]); } /** * Computes the equilateral encoding table, which is used as a look up for table for the data. * * @return The equilateral encoding table. */ private double[][] computeEquilateralEncodingTable() { double negativeReciprocalOfN; double scalingFactor; final double[][] matrix = new double[m_categoryCount][m_dimensionCount]; matrix = -1; matrix = 1.0; if (m_categoryCount > 2) { for (int dimension = 2; dimension < m_categoryCount; ++dimension) { // scale the matrix so far scalingFactor = dimension; negativeReciprocalOfN = Math.sqrt(scalingFactor * scalingFactor - 1.0) / scalingFactor; for (int coordinate = 0; coordinate < dimension; ++coordinate) { for (int oldDimension = 0; oldDimension < dimension - 1; ++oldDimension) { matrix[coordinate][oldDimension] *= negativeReciprocalOfN; } } scalingFactor = -1.0 / scalingFactor; for (int coordinate = 0; coordinate < dimension; ++coordinate) { matrix[coordinate][dimension - 1] = scalingFactor; } for (int coordinate = 0; coordinate < dimension - 1; ++coordinate) { matrix[dimension][coordinate] = 0.0; } matrix[dimension][dimension - 1] = 1.0; // Scale the matrix for (int row = 0; row < matrix.length; ++row) { for (int col = 0; col < matrix.length; ++col) { double min = -1; double max = 1; matrix[row][col] = ((matrix[row][col] - min) / (max - min)) * m_valueRange + m_lowestValue; } } } } return matrix; } public static int computeDimensionCount(int categoryCount) { return categoryCount - 1; } public int getCategoryCount() { return m_categoryCount; } public int getDimensionCount() { return m_dimensionCount; } public double getLowestValue() { return m_lowestValue; } public double getHighestValue() { return m_highestValue; } public double getValueRange() { return m_valueRange; } public double[][] getCategoriesCoordinates() { return m_categoriesCoordinates; } }   The mathematics utilities : package org.benoitdubreuil.iree.utils; public final class MathUtils { /** * Computes the Euclidean distance between the supplied vectors. * * @param lhsCoordinates Coordinates of the first n-dimensional vector. * @param rhsCoordinates Coordinates of the second n-dimensional vector. * * @return The Euclidean distance between the two vectors. */ public static double computeDistance(double[] lhsCoordinates, double[] rhsCoordinates) { double result = 0; for (int i = 0; i < rhsCoordinates.length; ++i) { result += Math.pow(lhsCoordinates[i] - rhsCoordinates[i], 2); } return Math.sqrt(result); } /** * Normalizes the supplied vector. * * @param vector The vector to normalize. * * @return The same array, but normalized. */ public static double[] normalizeVector(double[] vector) { double squaredLength = 0; for (int dimension = 0; dimension < vector.length; ++dimension) { squaredLength += vector[dimension] * vector[dimension]; } if (squaredLength != 1.0 && squaredLength != 0.0) { double reciprocalLength = 1.0 / Math.sqrt(squaredLength); for (int dimension = 0; dimension < vector.length; ++dimension) { vector[dimension] *= reciprocalLength; } } return vector; } /** * Negates the vector. * * @param vector The vector to negate. * * @return The same array, but each coordinate negated. */ public static double[] negateVector(double[] vector) { for (int dimension = 0; dimension < vector.length; ++dimension) { vector[dimension] = -vector[dimension]; } return vector; } /** * Multiplies the vector by a scalar. * * @param vector The vector to multiply. * @param scalar The scalar by which to multiply the vector. * * @return The same array, but each coordinate multiplied by the scalar. */ public static double[] multVector(double[] vector, double scalar) { for (int dimension = 0; dimension < vector.length; ++dimension) { vector[dimension] *= scalar; } return vector; } /** * Computes the dot product of the two supplied points. * * @param lhsVector The first point. * @param rhsVector The second point. * * @return The dot product of the two points. */ public static double dotProductVector(double[] lhsVector, double[] rhsVector) { double dotResult = 0; for (int dimension = 0; dimension < lhsVector.length; ++dimension) { dotResult += lhsVector[dimension] * rhsVector[dimension]; } return dotResult; } private MathUtils() { } }   The image data that shows how to encode pixels : package org.benoitdubreuil.iree.model; import org.benoitdubreuil.iree.controller.ControllerIREE; import org.benoitdubreuil.iree.gui.ImageGUIData; import org.benoitdubreuil.iree.pattern.observer.IObserver; import org.benoitdubreuil.iree.pattern.observer.Observable; import java.awt.*; import java.awt.image.BufferedImage; public class ImageData extends Observable<ImageData> implements IObserver<ImageGUIData> { private double[][] m_encodedPixelData; /** * Encodes the pixel data of the supplied image data. * * @param newValue The new value of the observed. */ @Override public void observableChanged(ImageGUIData newValue) { if (newValue.getDownScaled() != null) { encodePixelData(newValue); modelChanged(this); } } private void encodePixelData(ImageGUIData imageGUIData) { EquilateralEncodingTable encodingTable = ControllerIREE.getInstance().getEncodingTable(); EquilateralEncodingCategory[] categories = EquilateralEncodingCategory.values(); BufferedImage image = imageGUIData.getDownScaled(); int width = image.getWidth(); int height = image.getHeight(); m_encodedPixelData = new double[width * height][]; for (int x = 0; x < width; ++x) { for (int y = 0; y < height; ++y) { int orignalPixel = image.getRGB(x, height - 1 - y); int r = (orignalPixel >> 16) & 0xff; int g = (orignalPixel >> 8) & 0xff; int b = orignalPixel & 0xff; int minColorDistance = 255 * 3; int minColorDistanceCategory = 0; for (int category = 0; category < encodingTable.getCategoryCount(); ++category) { Color categoryColor = categories[category].getColor(); int colorDistance = Math.abs(r - categoryColor.getRed()) + Math.abs(g - categoryColor.getGreen()) + Math.abs(b - categoryColor.getBlue()); if (colorDistance < minColorDistance) { minColorDistance = colorDistance; minColorDistanceCategory = category; } } m_encodedPixelData[x * height + y] = encodingTable.encode(minColorDistanceCategory).clone(); } } } public int getPixelCount() { return m_encodedPixelData.length; } double[][] getEncodedPixelData() { return m_encodedPixelData; } }   The actual image data recognition algorithm : package org.benoitdubreuil.iree.model; import org.benoitdubreuil.iree.controller.ControllerIREE; import org.benoitdubreuil.iree.utils.MathUtils; public final class ImageDataRecognition { /** * Compares two images and return how similar they are. * * @param lhs The first image to compare. * @param rhs The second image to compare. * * @return Inclusively from 0, totally different, to 1, the same. */ public static double compareImages(ImageData lhs, ImageData rhs) { double meanDistance = 0; double[][] lhsEncodedPixelData = lhs.getEncodedPixelData(); double[][] rhsEncodedPixelData = rhs.getEncodedPixelData(); if (lhsEncodedPixelData != null && rhsEncodedPixelData != null) { EquilateralEncodingTable table = ControllerIREE.getInstance().getEncodingTable(); int maxPixelCount = Math.max(lhs.getPixelCount(), rhs.getPixelCount()); double emptyPixelMeanValue = 1.0; for (int pixel = 0; pixel < maxPixelCount; ++pixel) { double[] lhsVector; double[] rhsVector; if (pixel < lhs.getPixelCount()) { lhsVector = lhsEncodedPixelData[pixel]; } else { meanDistance += emptyPixelMeanValue; continue; } if (pixel < rhs.getPixelCount()) { rhsVector = rhsEncodedPixelData[pixel]; } else { meanDistance += emptyPixelMeanValue; continue; } double rhsDotLhs = MathUtils.dotProductVector(rhsVector, lhsVector); double[] rhsProjectedOntoLhs = MathUtils.multVector(lhsVector.clone(), rhsDotLhs); meanDistance += MathUtils.computeDistance(lhsVector, rhsProjectedOntoLhs) / table.getValueRange() / maxPixelCount; } } return meanDistance; } private ImageDataRecognition() { } } Pathfinding Navigation Mesh : Wall Collision Avoidance Simple organic and brute force dungeon generation

Subscribe to our subreddit to get all the updates from the team! Last month, I made a pretty simple dungeon generator algorithm. It's an organic brute force algorithm, in the sense that the rooms and corridors aren't carved into a grid and that it stops when an area doesn't fit in the graph. Here's the algorithm : Start from the center (0, 0) in 2D Generate a room Choose a side to extend to Attach a corridor to that side If it doesn't fit, stop the generation Attach a room at the end of the corridor If it doesn't fit, stop the generation Repeat from steps 3 to 7 until enough rooms are generated It allowed us to test out our pathfinding algorithm (A* & String pulling). Here are some pictures of the output in 2D and 3D : Unit Vision

Subscribe to our subreddit to get all the updates from the team! First off, here's a video that shows the unit vision in action :    So, what is the unit vision? It's a simple mechanism that notifies a unit when another unit enters its vision field. It also takes into account if the vision is blocked by entities. This is how it is implemented step by step : A cone ghost control is attached to the unit's head All units intersecting with the cone's AABB fire events (AABB because of how Bullet Physics work) Cast a ray towards the visible unit and then adjust the angle so that it fits in the cone If the ray cast touches the supposedly visible unit, then it is truly visible   Using the debug view of Bullet Physics in the jMonkey Engine 3.1, we're able to see what the vision cone actually looks like.   And when inside the cone we can't see it because of culling. However, we can see the enemy's arm moving, which is a test I did for when a unit see another unit.   Behind a box, the enemy does not move its arm because he can't see me.   But when I leave my hiding spot, he can see me again. Zone generation

Subscribe to our subreddit to get all the updates from the team! I have integrated the zone separation with my implementation of the Marching Cubes algorithm. Now I have been working on zone generation. A level is separated in the following way : Shrink the zone map to exactly fit an integer number of Chunk2Ds, which are of 32² m². For each Chunk2D, analyse all zones inside its boundaries and determine all possible heights for Chunk3Ds, which are of 32³ m³. Imagine this as a three dimensional array as an hash map : we are trying to figure out all keys for Chunk3Ds for a given Chunk2D. Create and generate a Chunk3D for each height found. Execute the Marching Cubes algorithm to assemble the geometry for each Chunk3D.   In our game, we want levels to look like and feel like a certain world. The first world we are creating is the savanna. Even though each Chunk3D is generated using 3D noise, I made a noise module to map 3D noises into the 2D to able to apply 2D perturbation to the terrain.   I also tried some funkier procedural noises :  An arch!   The important thing with procedural generation, it's to have a certain level of control over it. With the new zone division system, I have achieved a minimum on that path for my game. Zone division Low poly terrain

Subscribe to our subreddit to get all the updates from the team! Recently I've been tackling with more organic low poly terrains. The default way of creating indices for a 3D geometry is the following (credits) :   A way to create simple differences that makes the geometry slightly more complicated and thus more organic is to vertically swap the indices of each adjacent quad. In other words, each adjacent quad to a centered quad is its vertical mirror.   Finally, by not sharing the vertices and hence by creating two triangles per quad, this is the result with a coherent noise generator (joise) : It is called flat shading. Behavior Tree - Follow, Search And Retreat

I integrated LibGDX's Behavior Tree AI module into our roguelite, vaporwave and procedural game, which is made use the jMonkey Engine 3.1. I then created the following behavior : - Follow enemy - Search the enemy's last recorded position - Return back to initial chase position - Stop the chase after a certain amount of time - Attacking the enemy resets the timer   Here's the behavior tree logic. Beware that it's possible there are still bugs. subtree name:"notIsReturningToInitialChasePosition" invert isReturningToInitialChasePosition subtree name:"notIsMovingToFollowingEnemyLastPosition" invert isMovingToFollowingEnemyLastPosition subtree name:"notHaveSpottedEnemies" invert haveSpottedEnemies subtree name:"followEnemy" selector parallel lookOutForEnemies alwaysSucceed lookAtClosestSeenEnemy alwaysSucceed (isPlayingAnimation animation:"look_around") stopAnimation animation:"look_around" followClosestSeenEnemy parallel policy:"selector" alwaysFail wait seconds:10 attackClosestSeenEnemy root selector $followEnemy (isFollowingEnemyAlive) (knowFollowingEnemyLastPosition) ($notHaveSpottedEnemies) sequence resetLookAt moveToFollowingEnemyLastPosition parallel policy:"selector" alwaysFail playAnimation animation:"look_around" lookOutForEnemies alwaysFail resetLookAt returnToInitialChasePosition
I'm new to AI programming and still have a lot of work to do for making better behavior trees. I think it's really easy to make spaghetti behaviors. Do you have any tutorials on how to create a "good" behavior tree? Adding and Destroying Voxels

Today, I finally finished the following features : Add new solid voxels at the selected position Destroy voxels at the selected position Generate chunks on the fly Remove chunks on the fly   Here is a video demonstrating those features : Voxel Traversal Algorithm (Ray Casting)

For more information and updates about the game, which is a voxel colony simulation / survival, please subscribe to r/CheesyGames. World Generation   This is a simple world made of chunks of 32³ voxels. The world itself is not static : as you can see on the top of the image, chunks only exist if there is at least one solid voxel in them. In other words, the world is dynamic and can contain as many chunks as the player's computer can handle.   In this particular screenshot, the world is generated with the simple vectorial gradient equation that I invented in high school but which I suppose already existed. Here's the basic equation :   $$\overrightarrow{ \textit{voxel value} } = \frac{ \overrightarrow{\textit{position} } \cdot \overrightarrow{ \textit{gradient}}}{ \overrightarrow{\textit{gradient} } \cdot \overrightarrow{ \textit{gradient}} }$$ That's the equation I came up with and remembered. The gradient * gradient can be simplified for the magnitude (length) of the gradient power squared. $$\overrightarrow{ \textit{voxel value} } = \frac{ \overrightarrow{\textit{position} } \cdot \overrightarrow{ \textit{gradient}}}{ \left \| \overrightarrow{ \textit{gradient}} \right \| ^{2} }$$   In conclusion, this gives an N dimensional gradient which gives a single decimal number.   Voxel Traversal Algorithm As for the voxel traversal algorithm, I decided to go with the most popular one, which was made by John Amanatides and Andrew Woo. As much as I like research papers, I also despise them because they lack simplicity, examples and full source code. That's why I had to google implementations of it and later on remembered that I had actually already implemented this algorithm a few years ago. Summary The simplest way to understand the algorithm is to imagine a line in an 3D world made of blocks. Which blocks does the line touch? Then, in which order are they touched based on the line's start and end positions? The goal is to traverse iteratively the blocks that are touched by the line . More simply, the logic of the algorithm can be summed making a distinction between the ray's direction's components. Those three define the importance of their axes in terms of how many blocks need to be traversed in what direction. Think of this with integers : two people are running to reach a goal; the fastest runs a 5 km/h, while the slowest runs at 1 km/h. For each time step, i.e. an hour, how many kilometers have each runner traveled? The ratio is 5 : 1, so, to merge the analogy, a ray would traverse each step 5 blocks on the X axis and 1 block on the Y axis. Of course, it's more complicated than that, as there are more parameters to it, especially because of exceptions such as what to do when each component is equal with one another? Implementation The first thing to know about my implementation is that each voxel index is centered within the voxel itself. In other words, the voxel at the position (0, 0, 0) starts at (-0.5, -0.5, -0.5) inclusively and ends at (0.5, 0.5, 0.5) exclusively. This is for a cube extent of 1, naturally. The original research paper doesn't work that way as it starts at the lowest corner, i.e. the voxel spans from (0, 0, 0) to (1, 1, 1). Without any further delay, here is the class for the VoxelRay :  import com.cheesygames.colonysimulation.math.MathExt; import com.cheesygames.colonysimulation.math.vector.Vector3i; import com.cheesygames.colonysimulation.world.World; import com.jme3.math.Vector3f; import com.jme3.scene.plugins.blender.math.Vector3d; import java.util.function.Function; /** * Ray for ray casting inside a voxel world. Each voxel is considered as a cube within this ray. A ray consists of a starting position, a direction and a length. The voxel distance * is computed once the method {@link #rayCastLocal(double, Function, Vector3i)} or {@link #rayCast(double, Function)} is called. */ public class VoxelRay { private Vector3d m_start; private Vector3d m_offsettedStart; private Vector3d m_direction; private double m_length; private int m_voxelDistance; private boolean m_wasStopped; /** * Constructs an invalid {@link VoxelRay} as its direction and length are null. The setters must be called after constructing a {@link VoxelRay} with this constructors. */ public VoxelRay() { this.m_start = new Vector3d(); this.m_offsettedStart = new Vector3d(); this.m_direction = new Vector3d(); this.m_length = 0; } /** * Constructs a {@link VoxelRay} from two points : start and end. * * @param start The absolute starting position of the ray. * @param end The absolute ending position of the ray. */ public VoxelRay(Vector3d start, Vector3d end) { this.m_start = new Vector3d(start); this.m_offsettedStart = new Vector3d(); this.m_direction = end.subtract(start); this.m_length = m_direction.length(); this.m_direction.normalizeLocal(); } /** * Constructs a {@link VoxelRay} from two points : start and end. * * @param start The absolute starting position of the ray. * @param end The absolute ending position of the ray. */ public VoxelRay(Vector3f start, Vector3f end) { this.m_start = new Vector3d(start); this.m_offsettedStart = new Vector3d(); this.m_direction = new Vector3d(end).subtractLocal(m_start); this.m_length = m_direction.length(); this.m_direction.normalizeLocal(); } /** * Constructs a {@link VoxelRay} from a start, a direction and a length. * * @param start The absolute starting position of the ray. * @param direction The direction of the ray. Must be normalized. * @param length The length of the ray. */ public VoxelRay(Vector3d start, Vector3d direction, double length) { this.m_start = new Vector3d(start); this.m_offsettedStart = new Vector3d(); this.m_direction = new Vector3d(direction); this.m_length = length; } /** * Constructs a {@link VoxelRay} from a start, a direction and a length. * * @param start The absolute starting position of the ray. * @param direction The direction of the ray. Must be normalized. * @param length The length of the ray. */ public VoxelRay(Vector3f start, Vector3f direction, float length) { this.m_start = new Vector3d(start); this.m_offsettedStart = new Vector3d(); this.m_direction = new Vector3d(direction); this.m_length = length; } /** * Casts the ray from its starting position towards its direction whilst keeping in mind its length. A lambda parameter is supplied and called each time a voxel is traversed. * This allows the lambda to stop anytime the algorithm to continue its loop. * * @param onTraversingVoxel The operation to execute when traversing a voxel. This method called the same number of times as the value of {@link #getVoxelDistance()}. The * supplied {@link Vector3i} parameter is not a new instance but a local instance, so it is a reference. The return value {@link Boolean} defines if * the algorithm should stop. * * @see <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.42.3443&rep=rep1&type=pdf">A Fast Voxel Traversal Algorithm</a> */ public void rayCast(Function<Vector3i, Boolean> onTraversingVoxel) { rayCastLocal(World.VOXEL_HALF_EXTENT, onTraversingVoxel, new Vector3i()); } /** * Casts the ray from its starting position towards its direction whilst keeping in mind its length. A lambda parameter is supplied and called each time a voxel is traversed. * This allows the lambda to stop anytime the algorithm to continue its loop. * * @param voxelHalfExtent The half extent (radius) of a voxel. * @param onTraversingVoxel The operation to execute when traversing a voxel. This method called the same number of times as the value of {@link #getVoxelDistance()}. The * supplied {@link Vector3i} parameter is not a new instance but a local instance, so it is a reference. The return value {@link Boolean} defines if * the algorithm should stop. * * @see <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.42.3443&rep=rep1&type=pdf">A Fast Voxel Traversal Algorithm</a> */ public void rayCast(double voxelHalfExtent, Function<Vector3i, Boolean> onTraversingVoxel) { rayCastLocal(voxelHalfExtent, onTraversingVoxel, new Vector3i()); } /** * Casts the ray from its starting position towards its direction whilst keeping in mind its length. A lambda parameter is supplied and called each time a voxel is traversed. * This allows the lambda to stop anytime the algorithm to continue its loop. * <p> * This method is local because the parameter voxelIndex is locally changed to avoid creating a new instance of {@link Vector3i}. * * @param onTraversingVoxel The operation to execute when traversing a voxel. This method called the same number of times as the value of {@link #getVoxelDistance()}. The * supplied {@link Vector3i} parameter is not a new instance but a local instance, so it is a reference. The return value {@link Boolean} defines if * the algorithm should stop. * @param voxelIndex The voxel index to locally modify in order to traverse voxels. This parameter exists simply to avoid creating a new {@link Vector3i} instance. * * @see <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.42.3443&rep=rep1&type=pdf">A Fast Voxel Traversal Algorithm</a> */ public void rayCastLocal(Function<Vector3i, Boolean> onTraversingVoxel, Vector3i voxelIndex) { rayCastLocal(World.VOXEL_HALF_EXTENT, onTraversingVoxel, voxelIndex); } /** * Casts the ray from its starting position towards its direction whilst keeping in mind its length. A lambda parameter is supplied and called each time a voxel is traversed. * This allows the lambda to stop anytime the algorithm to continue its loop. * <p> * This method is local because the parameter voxelIndex is locally changed to avoid creating a new instance of {@link Vector3i}. * * @param voxelHalfExtent The half extent (radius) of a voxel. * @param onTraversingVoxel The operation to execute when traversing a voxel. This method called the same number of times as the value of {@link #getVoxelDistance()}. The * supplied {@link Vector3i} parameter is not a new instance but a local instance, so it is a reference. The return value {@link Boolean} defines if * the algorithm should stop. * @param voxelIndex The voxel index to locally modify in order to traverse voxels. This parameter exists simply to avoid creating a new {@link Vector3i} instance. * * @see <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.42.3443&rep=rep1&type=pdf">A Fast Voxel Traversal Algorithm</a> */ public void rayCastLocal(double voxelHalfExtent, Function<Vector3i, Boolean> onTraversingVoxel, Vector3i voxelIndex) { assert !Double.isNaN(voxelHalfExtent); assert !Double.isNaN(m_start.x); assert !Double.isNaN(m_start.y); assert !Double.isNaN(m_start.z); assert !Double.isNaN(m_direction.x); assert !Double.isNaN(m_direction.y); assert !Double.isNaN(m_direction.z); assert !Double.isNaN(m_length); m_wasStopped = false; final double voxelExtent = voxelHalfExtent * 2; // This id of the first/current voxel hit by the ray. m_offsettedStart.set(m_start).addLocal(voxelHalfExtent, voxelHalfExtent, voxelHalfExtent); VoxelWorldUtils.getVoxelIndexNoOffsetLocal(voxelExtent, m_offsettedStart, voxelIndex); computeVoxelDistance(voxelExtent, voxelIndex); assert !Double.isNaN(m_voxelDistance); // In which direction the voxel ids are incremented. int stepX = (int) MathExt.getSignZeroPositive(m_direction.x); int stepY = (int) MathExt.getSignZeroPositive(m_direction.y); int stepZ = (int) MathExt.getSignZeroPositive(m_direction.z); // Distance along the ray to the next voxel border from the current position (tMaxX, tMaxY, tMaxZ). double nextVoxelBoundaryX = (voxelIndex.x + (MathExt.getNegativeSign(stepX) + 1)) * voxelExtent; double nextVoxelBoundaryY = (voxelIndex.y + (MathExt.getNegativeSign(stepY) + 1)) * voxelExtent; double nextVoxelBoundaryZ = (voxelIndex.z + (MathExt.getNegativeSign(stepZ) + 1)) * voxelExtent; // tMaxX, tMaxY, tMaxZ -- distance until next intersection with voxel-border // the value of t at which the ray crosses the first vertical voxel boundary double tMaxX = (m_direction.x != 0) ? (nextVoxelBoundaryX - m_offsettedStart.x) / m_direction.x : Double.MAX_VALUE; double tMaxY = (m_direction.y != 0) ? (nextVoxelBoundaryY - m_offsettedStart.y) / m_direction.y : Double.MAX_VALUE; double tMaxZ = (m_direction.z != 0) ? (nextVoxelBoundaryZ - m_offsettedStart.z) / m_direction.z : Double.MAX_VALUE; // tDeltaX, tDeltaY, tDeltaZ -- // how far along the ray we must move for the horizontal component to equal the width of a voxel // the direction in which we traverse the grid // can only be FLT_MAX if we never go in that direction double tDeltaX = (m_direction.x != 0) ? stepX * voxelExtent / m_direction.x : Double.MAX_VALUE; double tDeltaY = (m_direction.y != 0) ? stepY * voxelExtent / m_direction.y : Double.MAX_VALUE; double tDeltaZ = (m_direction.z != 0) ? stepZ * voxelExtent / m_direction.z : Double.MAX_VALUE; if (onTraversingVoxel.apply(voxelIndex)) { m_wasStopped = true; return; } int traversedVoxelCount = 0; while (++traversedVoxelCount < m_voxelDistance) { if (tMaxX < tMaxY && tMaxX < tMaxZ) { voxelIndex.x += stepX; tMaxX += tDeltaX; } else if (tMaxY < tMaxZ) { voxelIndex.y += stepY; tMaxY += tDeltaY; } else { voxelIndex.z += stepZ; tMaxZ += tDeltaZ; } if (onTraversingVoxel.apply(voxelIndex)) { m_wasStopped = true; break; } } } /** * Computes the voxel distance, a.k.a. the number of voxel to traverse, for the ray cast. * * @param voxelExtent The extent of a voxel, which is the equivalent for a cube of a sphere's radius. * @param startIndex The starting position's index. */ private void computeVoxelDistance(double voxelExtent, Vector3i startIndex) { m_voxelDistance = 1 + MathExt.abs(VoxelWorldUtils.getVoxelIndexNoOffset(voxelExtent, m_offsettedStart.x + m_direction.x * m_length) - startIndex.x) + MathExt.abs(VoxelWorldUtils.getVoxelIndexNoOffset(voxelExtent, m_offsettedStart.y + m_direction.y * m_length) - startIndex.y) + MathExt.abs(VoxelWorldUtils.getVoxelIndexNoOffset(voxelExtent, m_offsettedStart.z + m_direction.z * m_length) - startIndex.z); } public Vector3d getStart() { return m_start; } public Vector3d getDirection() { return m_direction; } public double getLength() { return m_length; } public int getVoxelDistance() { return m_voxelDistance; } public void setStart(Vector3d start) { m_start.set(start); } public void setStart(Vector3f start) { m_start.set(start); } /** * Sets the direction. * * @param direction The direction to set to the ray. Must be normalized. */ public void setDirection(Vector3d direction) { m_direction.set(direction); } /** * Sets the direction. * * @param direction The direction to set to the ray. Must be normalized. */ public void setDirection(Vector3f direction) { m_direction.set(direction); } /** * Sets the length of the ray. * * @param length The new length of the ray. Must be positive. */ public void setLength(double length) { m_length = length; } /** * Sets the end position of the ray, which is not a real variable but a way to set the direction and the length at the same time. The start position does matter for this * method. * * @param end Where the ray ends. */ public void setEnd(Vector3d end) { m_direction.set(end).subtractLocal(m_start); m_length = m_direction.length(); m_direction.normalizeLocal(); } /** * Gets if the voxel ray cast was stopped by the "onTraversingVoxel" method call. * * @return True if the voxel ray cast was stopped by the "onTraversingVoxel" method call, false otherwise. */ public boolean wasStopped() { return m_wasStopped; } }   Here are the external static methods : /** * Gets the voxel index of the specified position. This method suppose that the parameter position is already offsetted with + voxel half extent. This method local because the * supplied voxel index will be locally modified and returned. * * @param voxelExtent The extent of a voxel, which is the equivalent to a cube of a sphere's diameter. * @param position The position to get the voxel index from. Must already be offsetted with + voxel half extent * @param voxelIndex Where to store the voxel index. * * @return The voxel index parameter that is set to the supplied position's voxel index. */ public static Vector3i getVoxelIndexNoOffsetLocal(double voxelExtent, Vector3d position, Vector3i voxelIndex) { return voxelIndex.set(getVoxelIndexNoOffset(voxelExtent, position.x), getVoxelIndexNoOffset(voxelExtent, position.y), getVoxelIndexNoOffset(voxelExtent, position.z)); } /** * Gets the sign of the supplied number. The method being "zero position" means that the sign of zero is 1. * * @param number The number to get the sign from. * * @return The number's sign. */ public static long getSignZeroPositive(double number) { assert !Double.isNaN(number); return getNegativeSign(number) | 1; } /** * Gets the negative sign of the supplied number. So, in other words, if the number is negative, -1 is returned but if the number is positive or zero, then zero is returned. It * does not check if the parameter is NaN. * * @param number The number to get its negative sign. * * @return -1 if the number is negative, 0 otherwise. */ public static long getNegativeSign(double number) { assert !Double.isNaN(number); return Double.doubleToRawLongBits(number) >> BIT_COUNT_EXCLUDING_SIGN_64; }   The important parts to adjust the algorithm to fit my voxel boundaries are the following : m_offsettedStart.set(m_start).addLocal(voxelHalfExtent, voxelHalfExtent, voxelHalfExtent); It is mandatory to add the half extent to the starting position.   double nextVoxelBoundaryX = (voxelIndex.x + (MathExt.getNegativeSign(stepX) + 1)) * voxelExtent; double nextVoxelBoundaryY = (voxelIndex.y + (MathExt.getNegativeSign(stepY) + 1)) * voxelExtent; double nextVoxelBoundaryZ = (voxelIndex.z + (MathExt.getNegativeSign(stepZ) + 1)) * voxelExtent; What the MathExt method call does could be programmed as : (stepX >= 0 ? 1 : 0).   I don't know how to express how it is delightful when everything starts to fit and work properly :') Here are some screenshots : Our first hater

So we had our first hater... but first please listen to one of our music we think we was bashing against. After that, let's hear the context. Context Our development blogs on gamedev mainly focus on the actual development of our game(s) and any related research that we've done. So, our target audience is other video game developers. We also have our own subreddit where our target audience is everyone. Thus, we decided to make our subreddit public and allow subscribers to post content that follows the rules, which they are mainly about posting relevant content.  Recently, we've been gaining more popularity and finally gained our 25th subscriber! 🎉 However, with popularity means more human attention. One thing I know about humans is that there are among them douchebag, troll, egoist, evil [and so forth] people. Inevitably, we were bound to attract the attention of one of those toxic people and so we had our first experience with what we call a hater. The Hater The hater firstly unannouncedly posted this on our subreddit : The person actually posted music of his game [I suppose]. It is an electronic music video. While it's true that we post vaporwave music videos on our subreddit, they follow the rule that it's about our game and our company.

So I decided to remove his post and send him a warning as a message : Now, I don't clearly understand exactly what he meant by "Someone better than you, and wanted to make you feel better" but I do understand that this guy is saying he's better than us and that him posting his content on our subreddit would make us feel better (lol). I suppose the "better than us" part is related to our music, which is meant to be that way to fit into the game design of the game. Anyway, as you can see, this guy is so cool because he breaks rules. Wow. But wait, there's more! Just before I banned him, he posted this on our subreddit :  Of course we banned you for posting content about your game on our subreddit to gain popularity. Our subreddit specifies precisely through rules that it is meant to be a platform of communication for our company and a way to keep our subscribers in touch with the development of our games. Just look at r/fallout for example. Their first rule says that all posts must be directly related to Fallout. Are they not cool to ban people who disrespect that rule? No, it does not make sense. Reddit is a magnificent social network that allows specific sub-forums as ours and it's actually what defines it. Anyway, I decided to ban him and then ignore him. I've always been more of an observer than someone who needs to express his opinion loudly and publicly on social networks but because this is the first time we had a hater for our game, I just needed to post about this. What we learned from this : Added a rule about not spamming that allows us to give warnings and ban people from our subreddit. Ignore banned people. Made our subreddit restricted instead of public. Now, only approved redditors are able to post on our subreddit. Toxic people take time from us video game developers that we could put into making our game(s) Voxels

Voxels! Unlike my old Xna application, this one's code is way more beautiful to the eye. Zero "switch" or "if and else" for cube faces, as I did with my cubic planet faces. My only problem with voxels is that it's a 3D grid. A 3D grid take a lot longer to compute than six 2D grids.
250 * 6 = 1500 quads to compute and draw.
2503 = 15,625,000 voxels to compute and maybe draw. As I use more and more complex objects to abstract the computation and the drawing part, the code slows. Following this entry, I'll make another one but with two videos:
1) Spherical planet made of voxels
2) Cubic planet made of voxels

Grouping of my [new] work so far

I'm an amateur and hobbyist video game developer. I've been programming for 9 years now even though I'm almost 21. When I started, it was rough being extremely bad with the english language and a noob programmer. Instead of helping me, people over multiple forums were only degrading my lack of skills and so I stopped being an active user. I have now finished what we call in Quebec a "technique". A technique is an academic degree of 3 years that is the equivalent of college degree. The technique I've done was called "Technique de l'informatique de gestion", which is a computer science technique applied to management softwares. As I finished college, I noticed I've improved my programming competencies and so I started again to research and program for fun, which I did 4 years ago. See I'm currently working on planet generation. Everything was done using the jMonkey Engine 3, Java 8, Eclipse Mars and Joise (a java adaptation of the accidental noise library from JTippetts). The following videos sum up what I've done so far: