3
\$\begingroup\$

Am looking for a solution (algorithm) to check if an object in a neighbor tile can be connected (i.e transfer power). Best example I could come up with to make this more clear, is pipes.

I am using a fixed 1 x 1 grid size. So only one object can occupy that space. I do not store where objects are in the world, as there could be a lot of them placed down by the player.

Let's say you can place down 4 different types of pipe connectors. Straight, Right angle, Cross, and T. These can all be rotated by 90 degrees each rotation on the Y (up) axis.

Like in this example I put together quickly:

enter image description here

In that case above, they all connect correctly, but how do I check that when a pipe is placed down in its final position, it is a valid connection?

So in this image, the Straight pipe is not connected correctly to the T pipe to the right or the Straight pipe above it. So in a pipe example that might be transferring power, the Straight pipe would not be powered.

enter image description here

If it helps because it's Unity. I added the directions (I tested by drawing a ray to the direction that it can connect).

enter image description here

Spent some time playing with the "pipe" prototype a bit more.

Each pipe has 4 booleans. Forward, Back, Left, Right. These indicate which side the pipe can be connected too. So for example, a straight pipe that hasn't been rotated can connect left and right. If the straight pipe gets rotated, then forward and back becomes true, and left and right become false. This is applied to all pipe types.

When placing a pipe down, a raycast is done in all 4 directions to see if there is another pipe nearby. So I have access to the neighbor pipes to see which side they can be connected on. My problem now, is the logic to do the check.

Note: The 4 raycasts are a one time deal. It's just to check the neighbors on placement.

enter image description here

\$\endgroup\$
  • \$\begingroup\$ The abstract is that you check neighbors on the grid. Depending on what you find, you know on what directions it connect, and if it doesn't connect in the direction of the new pipe section, then it is wrong... However, I have no idea how do you check what is in a position of the grid on Unity. \$\endgroup\$ – Theraot Feb 8 '18 at 19:08
  • \$\begingroup\$ If you're using a fixed grid, event driven logic would most likely be enough. You know the orientation of the pipes and therefor know where the end points are located on the grid. It's simply a matter of checking if the connection is valid and either keep track of it externally or pass the pipes respectively to one and other.. \$\endgroup\$ – Sidar Feb 9 '18 at 15:44
  • \$\begingroup\$ I've made an edit or two to my answer. Please have a look. You should be able to solve your problem. \$\endgroup\$ – Engineer Feb 9 '18 at 16:28
4
\$\begingroup\$

Forget GameObjects and pretty colours for now. Let's deal with this in the abstract, as pure data.

Your most notable finding is discovering that each tile has 4 booleans noting whether that side is "open" to connections or not. OK, so...

struct Tile
{
   bool[] directions; //if all 4 are false i.e. "closed", this is an empty tile; skip it.

   //any other members like colour, rotation status, or whatever

   void Tile()
   {
       directions = new bool[4];
   }
}

class Game()
{
    Tile[,] tiles = new Tile[WORLD_WIDTH, WORLD_HEIGHT];

}

Why do I use a bool array of directions as above, rather than 4 members like this?...

struct Tile
{
    bool north;
    bool south;
    bool east;
    bool west;
}

...Because we could not then iterate over those members (well, we could, using C# reflection, but that would be slow and painful).

Instead we can give our directions name like this, above all existing code:

public const int NORTH = 0;
public const int EAST = 1;
public const int SOUTH = 2;
public const int WEST = 3;

//...or...

enum Direction
{
   NORTH, //0
   EAST, //1
   SOUTH, //2
   WEST //3
}

Now we can cycle through the directions, like this:

for (int z = 0; z < WORLD_HEIGHT; z++) //use z rather than y for unity's axes
    for (int x = 0; x < WORLD_WIDTH; x++)
    {
        for (int d = 0; d < 4; d++) //cycle clockwise around compass: N,E,S,W
        {
            if (tile.directions[d] == true)
            {
                //...do something important...
            }

        }

        //..or...

        int startDir = SOUTH;
        for (int d = 0; d < 4; d++)
        {
            int dd = (startDir + d) % 4; //gets back into the 0-3 valid range: 4=0, 5=1...
            if (tile.directions[dd] == true)
            {
                //...do something important...
            }
        }
    }
}

Obviously, end goal is to see whether any neighbours are connected to the currently-evaluated tile. Change the Tile:

struct Tile
{
   bool[] directions; //if all 4 are false, this is an empty tile.
   bool[] connections; //reflects directions, but stores whether hooked up.
   //any other members like colour, rotation status, or whatever

   void Tile()
   {
       directions  = new bool[4];
       connections = new bool[4];
   }
}

Then:

class Game
{
    Tile[,] tiles = new Tile[WORLD_WIDTH, WORLD_HEIGHT];

    bool DetermineConnectionsAt(int xSelf, int zSelf)
    {
        Tile tileSelf = tiles[xSelf, zSelf];

        //now we walk west/east neighbours
        for (int xo = -1; xo < 2; xo +=2) //skips 0, goes from -1 -> +1
        {
            Tile tileNeighbour = tiles[xSelf + xo, zSelf];

            if (tileSelf     .directions[SOUTH - xo] == true &&
                tileNeighbour.directions[SOUTH + xo] == true) //opp. side of neighbour
            {
                tileSelf     .connections[SOUTH - xo] = true;
                //you could set neighbour's connection on opp. side = true
                //as well, but not much point as you will evaluate neighbour 
                //later as you loop through the xz grid.
            }
            //...you will also have to make sure you are not checking outside
            //the grid's indices here (e.g. < 0, or > WORLD_WIDTH).
        }
        //...and walk North/South neighbours exactly the same way, but in z.
        //...instead of SOUTH, use EAST. This is to avoid negative modulo.
    }
}

This leaves several things up to you; for example, how you want to store / manage rotated representations of the same "glyph"; store them all in one large enum or something else? Have a method on Tile Rotate(+1) or Rotate(-1) to adjust directions / connections arrays accordingly? That's all up to you.

There are more graph-like ways of doing this (such as your comment about dictionaries, or pure reference linkage as in linked-lists) than using a 2D array. They are more efficient in some ways (smaller memory footprint) but less efficient in others (cache access, typically). But I'll leave that one for you, now that you understand the basic principle you can do whatever pleases you. :)

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ I know I should avoid posting comments like this. But thank you. I've been trying to solve this problem for about a week. Your sample code made it more clear on where I was going wrong with my logic. \$\endgroup\$ – JacketPotatoeFan Feb 10 '18 at 18:44
  • 1
    \$\begingroup\$ @JacketPotatoeFan I know the feeling. Glad you can continue to enjoy your coding, now. :) \$\endgroup\$ – Engineer Feb 10 '18 at 18:48
0
\$\begingroup\$

This solution assumes that your pieces are not locked to a grid and can move around freely. When your game uses a grid where each piece occupies exactly one tile and can only be placed exactly on the center of a tile, then this solution is overengineering.

Add a "Connector" child-object to each connection-point of your piece-prefabs. Add sphere colliders to these "Connectors". This collider represents the area in which it snaps together with the "Connector" child objects of other pieces. Rotate the connector child-objects to face into the correct direction.

When you move a piece, use Physics.OverlapSphere or the OnTriggerEnter event to find out if one of its connectors overlaps with a connector of another piece. When you detected such a collision, check if the rotations of the connectors are in opposite directions. When the orientations match too, then the two objects connect.

You might want to adjust the position of the placed piece so the positions of the Connectors are at the same point. In other words, have the new object "snap" into place.

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ @Quentin The solution described in this answer would be overengineering if your game has a fixed grid. The solution I described also works if pieces can have any size and can move around freely. But another answer which works under the assumption that you have a fixed grid could also be helpful. \$\endgroup\$ – Philipp Feb 9 '18 at 14:50
  • \$\begingroup\$ @Philipp I am using a fixed grid size. But I do appreciate the solution. I implemented it as a test, and it works perfectly. \$\endgroup\$ – JacketPotatoeFan Feb 9 '18 at 15:08
  • \$\begingroup\$ @Quentin So what's the issue with the raycast solution? 4 rays are fired out in each direction to check for a neighbor when the object is placed. I don't store where anything is in an array, as there could be 1000's of objects placed down. Maybe I should add that to my question? \$\endgroup\$ – JacketPotatoeFan Feb 9 '18 at 15:11
  • 1
    \$\begingroup\$ @JacketPotatoeFan an array access is a trivial operation that is achieved with a couple machine instructions. A raycast requires examining all of the existing objects (or traversing a spatial-partitioning structure, if Unity has that), and solving 3D equations against arbitrary collision meshes. Even if it seems counter-intuitive at first, the raycast is unbelievably more expensive, and will only get worse as objects multiply (while an array access is constant-time, barring cache). \$\endgroup\$ – Quentin Feb 9 '18 at 15:17
  • 1
    \$\begingroup\$ Can you please keep the comments relevant to this answer? If you would like to discuss an alternative approach, please write a new answer which describes it. \$\endgroup\$ – Philipp Feb 9 '18 at 16:29

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.