An issue with my game logic

Hello!

This is my first thread here, so douzo yoroshiku :pray:

I have started to learn programming and game design as a hobby not long ago, and I’m working on my first ever puzzle game using Monogame. The game logic is fairly simple:

  1. The game consists of a 5x7 board.
  2. At the start of the game, a setpiece is added on each of the 35 board tiles.
  3. All of the setpieces a “type” randomly assigned from these five:
    fire,
    water,
    nature,
    stone,
    gem (currently represented by a star, don’t ask me why).
  4. The player can move any of the pieces from its current tile to one of the four directly neighbouring tiles (above, below, left, right). The moved setpiece is then swapped with the setpiece from that tile.
  5. If moving the pieces creates a chain of 5 or more neighbouring pieces of the same type, these pieces will be “replaced” with pieces of a new type (in fact the chained pieces are simply assigned a new type, bc. I did not want to create too much garbage).
  6. The player receives points and extra time for each of the “replaced” pieces.

The gameboard looks like this:

My current problem is with point 5 of the game logic, that is properly counting and clearing the chained pieces. At the moment, when a setpiece is dropped on the board, I call a function like this:

        public void CountChain()
        {
            /// <summary>
            /// Checks how many pieces of the same type are in a chain (situated next to each other)
            /// </summary>

            int currentChain = 0;
            int iterations = 23;

            // Checks the dropped piece for the neigbouring pieces.
            AddNeighbouringPieces(addToChain);

            while (iterations > 0)
            {
                // Checks each of the chained pieces for more neighbouring pieces.
                foreach (SetPiece s in chainedPieces)
                {
                    s.AddNeighbouringPieces(addToChain);
                }

                // Adds pieces from the addToChain list to the chainedPieces list, if it does not already contain these pieces.
                foreach(SetPiece s in addToChain)
                {
                    if(!chainedPieces.Contains(s))
                    {
                        chainedPieces.Add(s);
                    }
                }

                iterations -= 1;
            }

            // If iterations complete, counts the chained pieces.
            if(iterations == 0)
            {
                currentChain = chainedPieces.Count();
                
                // If chain longer than the minimum required, calls ReplacePieces for all the chained pieces.
                if (currentChain >= minChain)
                {
                    Debug.WriteLine("cleared pieces = " + currentChain + " of type:" + type.ToString());
                    ReplacePieces(chainedPieces, currentChain);
                }
                addToChain.Clear();
                chainedPieces.Clear();
            }
        }

        public void AddNeighbouringPieces(List<SetPiece> addToChain)
        {
            // Adds neighbouring pieces to the addToChain list, from which they are later added to the chainedPieces list.

            foreach (SetPiece s in content.board.setPieces)
            {
                if (isNeighboring(currentTile, s.currentTile) && s.type == type && !addToChain.Contains(s))
                {
                    addToChain.Add(s);
                }
            }
        }

As you can see I am using two different lists here - chainedPieces to store all the pieces in the chain, and addToChain, to store the neighbouring pieces of the given piece, which are later added to the chainedPieces list. I did this because obviously I cannot add pieces directly to the chainedPieces list while looping through that list in the foreach loop. However, this seems to me like a very roundabout way to do something simple? Is there a less convoluted way to do something like this?

Also, I think am getting some corner issues, with pieces being replaced when they should not actually be replaced, since they are not part of a 5+ chain. It’s hard for me to pinpoint exactly when the issue occurs, I think I will need to record a couple of playthroughs of the game to detect that, but I suppose if anything, the issue stems from my mistake in the function above. I’m just not sure what it is.

Help?

I’m sure there are several other ways of doing this, but here’s one option. I see where you’re coming from with the extra list, but I think it’s unnecessary. You’re essentially doing a breadth first search (the link shows a simple code implementation, but there are plenty of explanations online), except you want to keep all the nodes you pass along the way. You could do this with a list and an index. Start with the tile that was swapped, which you’re presumably already doing, and i = 0. Then just loop over code that adds neighboring pieces for list[i] and increments i. Now you have a list that’s somewhere between 1 and 5 long, and i is 1. If i ever reaches the end of your list (i >= list.Count) then you can break out and check the length of your list.

Also with checking neighbors, I’m not sure how your grid is set up, but there should be a faster way than iterating through every tile. Consider if you get the x,y coordinates of the one you’re looking at, you can add and subtract 1 to x and to y to get the 4 neighboring tiles.

EDIT: Since you said you just started learning, I thought I’d clarify in case you didn’t know: there’s only a problem with changing a list while iterating over it when you use a foreach loop because it creates the enumerator. If you use a for loop and track the index yourself (which also creates less garbage), then you can arbitrarily access any element you want.

Hmm - I think I understand what you meant. I did something like this, which allowed me to use just one list:

        public void CountChain()
        {
            /// <summary>
            /// Checks how many pieces of the same type are in a chain (situated next to each other)
            /// </summary>
            
            int currentChain = 0;

            AddNeighbouringPieces(chainedPieces);

            currentChain = chainedPieces.Count();

            Debug.WriteLine("current chain = " + currentChain);

            // If chain longer than the minimum required, calls ReplacePieces for all the chained pieces.
            if (currentChain >= minChain)
            {
                Debug.WriteLine("cleared pieces = " + currentChain + " of type:" + type.ToString());
                ReplacePieces(chainedPieces, currentChain);
            }
            chainedPieces.Clear();
        }

        public void AddNeighbouringPieces(List<SetPiece> chainedPieces)
        {
            // Adds neighbouring pieces of the same type to chainedPieces.

            for (var i = 0; i < content.board.setPieces.Count; i++)
            {
                if (isNeighboring(currentTile, content.board.setPieces[i].currentTile) && !chainedPieces.Contains(content.board.setPieces[i]) && content.board.setPieces[i].type == type)
                {
                    chainedPieces.Add(content.board.setPieces[i]);
                    content.board.setPieces[i].AddNeighbouringPieces(chainedPieces);
                }
            }
        }

It seems to be working properly. Let me know if this is more or less what you had in mind, and thanks a lot for your help!

You are probably right about looping through all of the pieces on the board, this seems like an overkill. So in other words, instead of looping through the list of all the pieces every time, I should just check the four neighbouring pieces, e.g. by their coordinates, to make the code faster? I suppose with just 35 pieces on the board the difference will not be noticeable, but I want to improve the code wherever possible.

Yes, that’s close enough to what I meant. And you’re right that with 35 pieces you would probably never notice the difference there.


To be exact, what you’re doing is now a depth-first traversal, because you’re adding calling AddNeighboringPieces on the piece you just added before adding the remaining pieces in your current loop. There’s nothing wrong with this, and it will take about the same amount of time as breadth-first. This is because you’re doing a full “traversal,” so you have to iterate over all of the same pieces anyway. If you were instead doing a “search,” where you stop when you’ve found a certain tile, then one could be faster than the other.

Here’s an even more complex optimization that you’d never notice with 35 tiles, but I’ll mention in case you’re interested. I would guess that in extreme cases with hundreds of tiles, breadth-first would be faster. The reason is that a depth-first traversal calls AddNeighboringPieces again for each piece you find. Those instructions to call and return from the function add extra overhead. In general depth-first searches achieve their iteration through recursion (calling the same function within itself, as you’ve done), and breadth-first searches through a queue (adding new nodes when they’re encountered, and removing them when they’re searched). And since you want to collect the full chain rather than just find the end, you wouldn’t even need to remove nodes from the queue, so you could just use a list. The point is that with a breadth-first traversal, you wouldn’t need to call the same function every time, saving you perhaps nanoseconds each iteration.

1 Like

Ah, ok - I’ll do some reading on depth-first and breadth-first searching and try to have some fun with this, because right now it’s a bit hard for me to comprehend. I’m sure it’ll click if I take a bit more time.

Meanwhile I’ll try to figure out a method to avoid iterating through all of the SetPieces on the board each time.

Again, thanks a lot for the helpful info! :grin:

1 Like