Quickly Iterate through 2D array manipulating contained structs

Question

I am hoping to streamline this bit of code better. This snippet does not cause my any slow downs in relation to other parts of the algorithm(?). I would just like guidance on making it better.

Some variables not given by code:

regionDimensions = whatever you want. (256)
hexagonArray[,] = new Hexagon[regionDimensions, regionDimensions];

The Struct:

public struct Hexagon
{
 private float height;
 private bool[] hasSides;
 public Hexagon(float height)
 {
 this.height = height;
 hasSides = new bool[] { true, true, true, true, true, true };
 }
 public float Height
 {
 get { return height; }
 }
 public bool[] HasSides
 {
 get { return hasSides; }
 set { hasSides = value; }
 }
 public bool this[int i]
 {
 get { return hasSides[i]; }
 set { hasSides[i] = value; }
 }
}

The Iterator:

 // Evaluate heights of hexagons and cull sides
 for (var x = 0; x < regionDimensions; x++)
 for (var y = 0; y < regionDimensions; y++)
 {
 var neighborHexes = new Dictionary<Hexagon, int>();
 // If it's not in bounds it doesn't need its side no matter what.
 if (y % 2 == 0)
 {
 if (CheckBounds(x, y + 1)) // 0
 neighborHexes.Add(hexagonArray[x, y + 1], 0);
 else
 hexagonArray[x, y].HasSides[0] = false;
 if (CheckBounds(x + 1, y)) // 1
 neighborHexes.Add(hexagonArray[x + 1, y], 1);
 else
 hexagonArray[x, y].HasSides[1] = false;
 if (CheckBounds(x, y - 1)) // 2
 neighborHexes.Add(hexagonArray[x, y - 1], 2);
 else
 hexagonArray[x, y].HasSides[2] = false;
 if (CheckBounds(x - 1, y - 1)) // 3
 neighborHexes.Add(hexagonArray[x - 1, y - 1], 3);
 else
 hexagonArray[x, y].HasSides[3] = false;
 if (CheckBounds(x - 1, y)) // 4
 neighborHexes.Add(hexagonArray[x - 1, y], 4);
 else
 hexagonArray[x, y].HasSides[4] = false;
 if (CheckBounds(x - 1, y + 1)) // 5
 neighborHexes.Add(hexagonArray[x - 1, y + 1], 5);
 else
 hexagonArray[x, y].HasSides[5] = false;
 }
 else
 {
 if (CheckBounds(x + 1, y + 1)) // 0
 neighborHexes.Add(hexagonArray[x + 1, y + 1], 0);
 else
 hexagonArray[x, y].HasSides[0] = false;
 if (CheckBounds(x + 1, y)) // 1
 neighborHexes.Add(hexagonArray[x + 1, y], 1);
 else
 hexagonArray[x, y].HasSides[1] = false;
 if (CheckBounds(x + 1, y - 1)) // 2
 neighborHexes.Add(hexagonArray[x + 1, y - 1], 2);
 else
 hexagonArray[x, y].HasSides[2] = false;
 if (CheckBounds(x, y - 1)) // 3
 neighborHexes.Add(hexagonArray[x, y - 1], 3);
 else
 hexagonArray[x, y].HasSides[3] = false;
 if (CheckBounds(x - 1, y)) // 4
 neighborHexes.Add(hexagonArray[x - 1, y], 4);
 else
 hexagonArray[x, y].HasSides[4] = false;
 if (CheckBounds(x, y + 1)) // 5
 neighborHexes.Add(hexagonArray[x, y + 1], 5);
 else
 hexagonArray[x, y].HasSides[5] = false;
 }
 EvaluateNeighbors(neighborHexes, ref hexagonArray[x, y]);
 }

Check Bounds:

 private bool CheckBounds(int x, int y)
 {
 if ((x >= 0) && (x < regionDimensions) &&
 (y >= 0) && (y < regionDimensions))
 return true;
 else
 return false;
 }

Evaluate Neighbors:

 private void EvaluateNeighbors(Dictionary<Hexagon, int> neighbors, ref Hexagon currentHexagon)
 {
 foreach (var neighbor in neighbors)
 {
 if (currentHexagon.Height < neighbor.Key.Height)
 currentHexagon.HasSides[neighbor.Value] = false;
 else if (MathExtensions.NearlyEqual(currentHexagon.Height, neighbor.Key.Height))
 currentHexagon.HasSides[neighbor.Value] = false;
 }
 }

Fix To Struct: Object is built once and is no longer mutable.

[Serializable]
public struct Hexagon
{
 private readonly float height;
 private readonly bool[] hasSides;
 public Hexagon(float height, bool[] sides)
 : this()
 {
 this.height = height;
 this.hasSides = (bool[])sides.Clone();
 }
 public float Height
 {
 get { return height; }
 }
 public bool[] HasSides
 {
 get { return hasSides; }
 }
 public bool this[int i]
 {
 get { return hasSides[i]; }
 }
}

Answer 1

1. Completely agree with Jesse concerning mutable structs - it's hard to always remember to mutate proper variable.
2. If you're very concerned about memory consumption (if that's the main reason for using mutable structs) I would rather use a bitmap for storing hasSides.
3. I'll also use simplification of CheckBounds proposed by Jesse (and ReSharper :)).
4. Dictionary (that MattDavey suggested to improve) is not needed at all... I don't see the reason for creating collection of hexagons just to iterate on it later, it's better to do the "EvaluateNeighbor" inline.
5. And the last simplification that will reduce most of the code: all your CheckBounds can be combined in a simple loop if you extract the definition of "neighbors" in a separate array.

As a result I've got the following code:

static readonly Tuple<int, int>[][] _neighbors = new[] //TODO: rename to whatever you find appropriate
{
 new[] 
 {
 Tuple.Create(0,1),
 Tuple.Create(1,0),
 Tuple.Create(0,-1),
 Tuple.Create(-1,-1),
 Tuple.Create(-1,0),
 Tuple.Create(-1,+1)
 },
 new[]
 {
 Tuple.Create(1,1),
 Tuple.Create(1,0),
 Tuple.Create(1,-1),
 Tuple.Create(0,-1),
 Tuple.Create(-1,0),
 Tuple.Create(0,+1)
 }
};
private static bool HasSide(Hexagon neighbor, Hexagon currentHexagon)
{
 return currentHexagon.Height >= neighbor.Height &&
 !MathExtensions.NearlyEqual(currentHexagon.Height, neighbor.Height);
}
private static bool CheckBounds(int x, int y)
{
 return (x >= 0) && (x < regionDimensions) &&
 (y >= 0) && (y < regionDimensions);
}

And the main iterator:

// Evaluate heights of hexagons and cull sides
for (var x = 0; x < regionDimensions; x++)
 for (var y = 0; y < regionDimensions; y++)
 {
 var activeMapping = _neighbors[y % 2]; //TODO: rename to whatever you find more appropriate
 for (int i = 0; i < activeMapping.Length; i++)
 {
 var shiftFromCurrentCell = activeMapping[i];
 var neighborX = x + shiftToCurrentCell.Item1;
 var neighborY = y + shiftToCurrentCell.Item2;
 hexagonArray[x, y].HasSides[i] = CheckBounds(neighborX, neighborY) &&
 HasSide(hexagonArray[neighborX, neighborY], hexagonArray[x, y]);
 }
 }

Answer 2

You will see a big improvement in performance if you swap the key/value types of your neighborHexes dictionary around..

var neighbourHexes = new Dictionary<int, Hexagon>();
neighborHexes.Add(0, hexagonArray[x, y + 1]); // etc...
private void EvaluateNeighbors(Dictionary<int, Hexagon> neighbors, ref Hexagon currentHexagon)
{
 foreach (var neighbor in neighbors)
 {
 if (currentHexagon.Height < neighbor.Value.Height)
 currentHexagon[neighbor.Key] = false;
 else if (NearlyEqual(currentHexagon.Height, neighbor.Value.Height))
 currentHexagon[neighbor.Key] = false;
 }
}

I also moved the dictionary construction var neighborHexes = new Dictionary<int, Hexagon>(); outside of the loop, and replaced it with neighbourHexes.Clear() inside the loop (we don't need 65536 individual dictionaries, we can just create one and re-use it).

In my tests that small change resulted in about a 72% improvement.

Here are my test results (regionDimensions = 256, 100 iterations)

Unoptimized Average 
0.091637207 
Optimized Average 
0.025620268 

And here is the code in Linqpad

Answer 3

First off, mutable structs are evil. Next, why expose the array via a property and have an iterator when one or the other will do? And since exposing array fields directly via a property leaks the implementation, let's expose the iterator only instead:

public struct Hexagon
{
 private readonly float height;
 private readonly bool[] hasSides;
 public Hexagon(float height)
 {
 this.height = height;
 this.hasSides = new[] { true, true, true, true, true, true };
 }
 public float Height
 {
 get
 {
 return this.height;
 }
 }
 public bool this[int i]
 {
 get
 {
 if ((i < 0) || (i >= this.hasSides.Length))
 {
 throw new IndexOutOfRangeException("Index is out of bounds for the array.");
 }
 return this.hasSides[i];
 }
 set
 {
 if ((i < 0) || (i >= this.hasSides.Length))
 {
 throw new IndexOutOfRangeException("Index is out of bounds for the array.");
 }
 this.hasSides[i] = value;
 }
 }

So now with that, we can also simplify the CheckBounds method into a more succinct, yet still wholly readable single-line (also made static as I don't see instance variables in play):

private static bool CheckBounds(int x, int y)
{
 return (x >= 0) && (x < RegionDimensions)
 && (y >= 0) && (y < RegionDimensions);
}

Throw in MattDavey's dictionary switcher-arounder (oh, yes, note that there is zero reason for you to be using the ref keyword anywhere in your code):

private static void EvaluateNeighbors(IEnumerable<KeyValuePair<int, Hexagon>> neighbors, Hexagon currentHexagon)
{
 foreach (var neighbor in neighbors)
 {
 if (currentHexagon.Height < neighbor.Value.Height)
 {
 currentHexagon[neighbor.Key] = false;
 }
 else if (MathExtensions.NearlyEqual(currentHexagon.Height, neighbor.Value.Height))
 {
 currentHexagon[neighbor.Key] = false;
 }
 }
}

Finally, the driver looks like this:

var hexagonArray = new Hexagon[RegionDimensions, RegionDimensions];
// Make sure the hexagonArray is filled with valid Hexagons here.
var neighborHexes = new Dictionary<int, Hexagon>();
// Evaluate heights of hexagons and cull sides
for (var x = 0; x < RegionDimensions; x++)
{
 for (var y = 0; y < RegionDimensions; y++)
 {
 // If it's not in bounds it doesn't need its side no matter what.
 if (y % 2 == 0)
 {
 // 0
 if (CheckBounds(x, y + 1))
 {
 neighborHexes.Add(0, hexagonArray[x, y + 1]);
 }
 else
 {
 hexagonArray[x, y][0] = false;
 }
 // 1
 if (CheckBounds(x + 1, y))
 {
 neighborHexes.Add(1, hexagonArray[x + 1, y]);
 }
 else
 {
 hexagonArray[x, y][1] = false;
 }
 // 2
 if (CheckBounds(x, y - 1))
 {
 neighborHexes.Add(2, hexagonArray[x, y - 1]);
 }
 else
 {
 hexagonArray[x, y][2] = false;
 }
 // 3
 if (CheckBounds(x - 1, y - 1))
 {
 neighborHexes.Add(3, hexagonArray[x - 1, y - 1]);
 }
 else
 {
 hexagonArray[x, y][3] = false;
 }
 // 4
 if (CheckBounds(x - 1, y))
 {
 neighborHexes.Add(4, hexagonArray[x - 1, y]);
 }
 else
 {
 hexagonArray[x, y][4] = false;
 }
 // 5
 if (CheckBounds(x - 1, y + 1))
 {
 neighborHexes.Add(5, hexagonArray[x - 1, y + 1]);
 }
 else
 {
 hexagonArray[x, y][5] = false;
 }
 }
 else
 {
 // 0
 if (CheckBounds(x + 1, y + 1))
 {
 neighborHexes.Add(0, hexagonArray[x + 1, y + 1]);
 }
 else
 {
 hexagonArray[x, y][0] = false;
 }
 // 1
 if (CheckBounds(x + 1, y))
 {
 neighborHexes.Add(1, hexagonArray[x + 1, y]);
 }
 else
 {
 hexagonArray[x, y][1] = false;
 }
 // 2
 if (CheckBounds(x + 1, y - 1))
 {
 neighborHexes.Add(2, hexagonArray[x + 1, y - 1]);
 }
 else
 {
 hexagonArray[x, y][2] = false;
 }
 // 3
 if (CheckBounds(x, y - 1))
 {
 neighborHexes.Add(3, hexagonArray[x, y - 1]);
 }
 else
 {
 hexagonArray[x, y][3] = false;
 }
 // 4
 if (CheckBounds(x - 1, y))
 {
 neighborHexes.Add(4, hexagonArray[x - 1, y]);
 }
 else
 {
 hexagonArray[x, y][4] = false;
 }
 // 5
 if (CheckBounds(x, y + 1))
 {
 neighborHexes.Add(5, hexagonArray[x, y + 1]);
 }
 else
 {
 hexagonArray[x, y][5] = false;
 }
 }
 EvaluateNeighbors(neighborHexes, hexagonArray[x, y]);
 neighborHexes.Clear();
 }
}

• almaz: I find range checking in indexing property quite useless here... this.hasSides[i] will throw the same exception anyway, it's like throwing NullReferenceException...
• Jesse C. Slicer: I'm a stickler on getting Pex to shut the heck up.