2
\$\begingroup\$

I just recently got into c# and Unity coding, and would like to put this algorithm and code up for review to check how I'm doing. I've only been working by myself, so it would be interesting to hear how my code design and style could be improved. The task is like so:

There's a 3D cubical grid (stateGrid) containing voxels that are either 1 or 0. It is stored as a flattened array. If multiple 1-voxels are neighboring eachother, they form an island together.

I want to detect islands smaller than a given size (blobMin), and convert those to 0's. The function returns the voxels that are part of islands up for deletion.

Checking if voxel is in an island is implemented with a breadth-first-search within the Walker function.

Performance is quite important, since the cube can be of size 64 or even bigger, and I think there's a bunch to gain still algorithmically.

Here's my code:

using System.Collections.Generic;
using UnityEngine;

public class IslandRemove{
    private int mapSize;
    private int mapCubeSize;
    private float[] state;
    private float[] result;
    private int index;
    private int connectCount;
    private int blobMin;

    private HashSet<Vector3Int> history;
    private Queue<Vector3Int> queue;
    private int blobSz;


    public IslandRemove(int mapSize, int mapCubeSize, int blobMin){
        this.mapSize = mapSize;
        this.mapCubeSize = mapCubeSize;
        this.blobMin = blobMin;
        result = new float[mapCubeSize];
    }

    private int getIdx(Vector3Int v){
        return v.z * mapSize * mapSize + v.y * mapSize + v.x;
    }

    private void ProcessNode(Vector3Int newVect){
        // if not already in history
        if (!history.Contains(newVect)){
            blobSz++;
            // add node to queue for later check
            queue.Enqueue(newVect);
            // mark node as counted so we don't count again, or check its connections
            history.Add(newVect);
        }
    }

    private bool walker(int x, int y, int z){

        blobSz = 0;
        queue = new Queue<Vector3Int>();
        history = new HashSet<Vector3Int>();
        ProcessNode(new Vector3Int(x, y, z)); // queue start position
        var loopcount = 0;

        while (blobSz < blobMin){
            loopcount++;
            var node = queue.Dequeue();
            var idx = getIdx(node);

            // check edges
            if (node.x != 0){ // edge x-
                if ((int)state[idx - 1] == 1)
                    ProcessNode(new Vector3Int(node.x - 1, node.y, node.z));
            }
            if (node.x != mapSize - 1){ // edge x+
                if ((int) state[idx + 1] == 1)
                    ProcessNode(new Vector3Int(node.x + 1, node.y, node.z));
            }
            if (node.y != 0){ // edge y-
                if ((int) state[idx - mapSize] == 1)
                    ProcessNode(new Vector3Int(node.x, node.y-1, node.z));
            }
            if (node.y != mapSize - 1){ // edge y+
                if ((int) state[idx + mapSize] == 1)
                    ProcessNode(new Vector3Int(node.x, node.y+1, node.z));
            }
            if (node.z != 0){ // edge z-
                if ((int) state[idx - mapSize*mapSize] == 1){
                    ProcessNode(new Vector3Int(node.x, node.y, node.z-1));           
                }
            }
            if (node.z != mapSize - 1){ // edge z+
                if ((int) state[idx + mapSize*mapSize] == 1)
                    ProcessNode(new Vector3Int(node.x, node.y, node.z+1));
            }

            if (queue.Count == 0){
                return true; // add to removelist
            }
        }
        return false; // target is reached, don't add to removelist
    }

    public List<Vector3Int> IslandRemover(float[] stateGrid){
        state = stateGrid;
        var remove = new List<Vector3Int>();
        var removeThis = false;
        var lastOneWasOne = false; // start with false
        // iterate through cube
        for (int z = 0; z < mapSize; z++){
            for (int y = 0; y < mapSize; y++){
                for (int x = 0; x < mapSize; x++){
                    var idx = z * mapSize * mapSize + y * mapSize + x;
                    if ((int) state[idx] == 1 && !lastOneWasOne){ 
                        removeThis = walker(x, y, z);
                        if (removeThis)
                            remove.Add(new Vector3Int(x,y,z));
                        else{
                            lastOneWasOne = true;
                        }
                    }
                    else{
                        lastOneWasOne = false;
                    }

                    if ((int)state[idx] == 0){
                        lastOneWasOne = false;
                    }
                }
            }
        }
        return remove;
    }
}

Thank you in advance!

\$\endgroup\$

1 Answer 1

2
\$\begingroup\$
private int mapSize;
private int mapCubeSize;
private float[] state;
private float[] result;
private int index;
private int connectCount;
private int blobMin;

You should clean up unused members: mapCubeSize, result, index and connectCount are unused.


Be consistent with your naming: methods and properties of a class are named with PascalCase, while fields are named with camelCase (e.g. walker() should be Walker() (BTW: walker() is a strange and mysterious name saying nothing about its behavior))


private HashSet<Vector3Int> history;
private Queue<Vector3Int> queue;
private int blobSz;

These members represent partial states inside walker(). I don't like them to be class members. Instead you could provide them as parameters to ProcessNode(), or you could define ProcessNode() as a nested method inside walker():

private bool walker(int x, int y, int z)
{

  int blobSz = 0;
  Queue<Vector3Int> queue = new Queue<Vector3Int>();
  HashSet<Vector3Int> history = new HashSet<Vector3Int>();
  ProcessNode(new Vector3Int(x, y, z)); // queue start position
  var loopcount = 0;

  void ProcessNode(Vector3Int newVect)
  {
    // if not already in history
    if (!history.Contains(newVect))
    {
      blobSz++;
      // add node to queue for later check
      queue.Enqueue(newVect);
      // mark node as counted so we don't count again, or check its connections
      history.Add(newVect);
    }
  }

  while (blobSz < blobMin)
  {
    loopcount++;
    var node = queue.Dequeue();
    var idx = getIdx(node);
    ...

private void ProcessNode(Vector3Int newVect){
    // if not already in history
    if (!history.Contains(newVect)){
        blobSz++;
        // add node to queue for later check
        queue.Enqueue(newVect);
        // mark node as counted so we don't count again, or check its connections
        history.Add(newVect);
    }
}

The HashSet<T>.Add() method returns a bool indicating if the value was added (true) or already present. You can use that to simplify ProcessNode():

  void ProcessNode(Vector3Int newVect)
  {
    // if not already in history
    if (history.Add(newVect))
    {
      blobSz++;
      // add node to queue for later check
      queue.Enqueue(newVect);
    }
  }

All the calls to ProcessNode() creates a new Vector3Int instance from coordinates (x, y, z). Consider to change its signature to: ProcessNode(int x, int y, int z) and then create the vector inside ProcessNode(...) instead:

ProcessNode(int x, int y, int z)
{
  newVect = new Vector3Int(x, y, z);
  ...
}

Instead of this:

    // check edges
    if (node.x != 0)
    { // edge x-
      if ((int)state[idx - 1] == 1)
        ProcessNode(new Vector3Int(node.x - 1, node.y, node.z));
    }

I think, I would prefer:

    // check edges (x-)
    if (node.x != 0 && (int)state[idx - 1] == 1)
    { 
      ProcessNode(new Vector3Int(node.x - 1, node.y, node.z));
    }

      removeThis = walker(x, y, z);
      if (removeThis)

You only use removeThis once, so no need to define it as a variable:

if (walker(x, y, z))
   ...

is clear enough.

\$\endgroup\$
1
  • \$\begingroup\$ Woah, I learned a lot! Also gained a speedup it seems, maybe because of not creating so many Vector3Int() variables after changing to ProcessNode(int x, int y, int z). Many thanks \$\endgroup\$ Feb 20, 2020 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.