0

I have a 3D array with booleans and I need to check if there are "lines" that all contain true or false. With lines I mean horizontally, vertically and diagonally within the array. However I only need to check this when an element changes and I know the location of the changed element. The array is always equal on all 3 sides/dimensions.

I am looking for an efficient way to traverse the possible direction from the element that changed. What I'm currently doing is to first check the straight lines x, y and z which are easy. Then i check for the 2 horizontal diagonals:

if (element.x + element.y == arraySize || element.x == element.y)
    //Only now there can be a full diagonal line

And that for each side (x, y and z). Now I only need the 4 complete diagonals accros the array. But I'm wondering if there is a clever trick to make this more efficient.

  • I have trouble to understand what you mean. For example: "The array is always equal on all 4 sides." - what do you call a "side" in a 3D array, and why are the 4 of them? Or do you mean "the array size is equal in all 3 dimensions?" – Doc Brown Jan 18 '15 at 13:25
  • Moreover, are you just talking about the main diagonals? And if that is what you mean, do you have to omit the check when an element changes which is not part of any main diagonal? – Doc Brown Jan 18 '15 at 13:28
  • And a third unclear point: do you have an array where the checks have to be repeated every time one element changes, and do you want to optimize the total number of checks? Or do you have to run the check just once for a given array and a given location? – Doc Brown Jan 18 '15 at 13:33
  • @DocBrown Sorry, typo. Must be 3 sides or 3 dimensions. If the changed element cannot go from corner to corner then it mus be omited. When the array changes I have to check if that change "completes a line". So I have to run it each time an element changes and since I know the elements location I do not need to check all possibilities. – Madmenyo Jan 18 '15 at 14:20
  • If you know the slope of the diagonal line plus a point that is guaranteed to be on the diagonal line then you can calculate the distance between the known point + unknown point and then multiply out the distance by the slope. That answer will tell you if the unknown point is on the diagonal or not. – GlenH7 Jan 18 '15 at 22:43
2

From a theoretical standpoint, there's not a whole lot you can do because whether or not one line contains all trues or all falses doesn't tell you much about whether the other lines do, i.e. you have to "check all of them" no matter what.

What you can do is make sure you don't check anything twice. If you check whether there's a line from (0,0,0) to (8,8,8), then you should not also check whether there's a line from (8,8,8) to (0,0,0) later in your algorithm. For example, when checking for horizontal and vertical lines, only do the checks for three of the six sides of your cube.

The data structure you use is probably the most important factor in practice. You obviously need random access since the "lines" go in several different directions, so an ArrayList would be a lot better than a LinkedList (though I'm guessing you knew that already).

If those generic tips aren't enough, then we'd have to start talking about things like the actual size of your cube, the exact code you've tried, how you measured its performance, how the trues or falses tend to be distributed, and so on.

  • Yeah I figured it would take a lot of checks. However I came to the conclusion that i only need to check the array when a boolean changes and I know the location of that bool within the array. This make a big difference. I shall update my question. – Madmenyo Jan 18 '15 at 12:08
  • You obviously need random access since the "lines" go in several different directions That doesn't seem so obvious to me. Iterating in any direction other than to adjacent memory words is going to get you a cache miss, so checking a vertical or diagonal is going to have horrible performance. – Doval Jan 18 '15 at 15:23
  • That's assuming a very specific relationship between his cache size and cube size. I was merely referring to random access structures like arrays as opposed to sequential access structures like linked lists; traversing the diagonals would be even more horrible if you had to chase N pointers on top of the cache misses. – Ixrec Jan 18 '15 at 16:28
  • That's assuming a very specific relationship between his cache size and cube size. It's not the cache size that's the issue, it's the cache lines. Adjacent memory words are almost always in the same line. If you can't fit an entire array row in a single cache line then elements on different rows are definitely going to be on different cache lines and you're very likely to get a cache miss. – Doval Jan 18 '15 at 17:33
  • Anyways, it might be better to store the true/false lines themselves in an auxiliary data structure. Besides getting around the bad cache performance on two of the cube dimensions, there's the fact that changing a single cell in the cube can't change every line (and in some cases won't change any of them), so re-checking the whole thing is wasteful. – Doval Jan 18 '15 at 17:35
1

As Ixrec wrote in the asspect of performance there is not much to do, you will need to travers the array many times. However I can give you a tool that makes it simpler:

public class LineEnumerator
{
    int dx, dy, dz;
    public LineEnumerator(int dx, int dy, int dz)
    {
        this.dx = dx;
        this.dy = dy;
        this.dz = dz;
    }
    public IEnumerable<bool> GetLine(bool[, ,] arr, int x0, int y0, int z0)
    {
        int xLength = arr.GetLength(0);
        int yLength = arr.GetLength(1);
        int zLength = arr.GetLength(2);

        while (x0 >= 0 && x0 < xLength &&
               y0 >= 0 && y0 < yLength &&
               z0 >= 0 && z0 < zLength)
        {
            yield return arr[x0, y0, z0];
            x0 += dx;
            y0 += dy;
            z0 += dz;
        }
    }
}

This is a total general directional enumerator for a 3D array. Using this it is easy to wirte the treversing. For example traversing a line in the X direction can be writen like this:

var XEnumerator = new LineEnumerator(1, 0, 0);
foreach(bool b in XEnumerator.GetLine(arr, 0, 0, 0))
{
  //Do whatever
}

Or you can instantiate a diagonal enumerator like this:

var DiagonalEnumerator1 = new LineEnumerator(1, 1, 1);

or an other like this:

var DiagonalEnumerator2= new LineEnumerator(1, 1, -1);

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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