match 3 algorithm

News & General Discussion
1

I’ve been struggling with my remake of sega’s “Columns” match 3 game . I want to use a 2d array to store the grid, and unity 3d objects to store the “visual” of the grid. Including the use of a 3d perspective camera, not a 2d orthographic view.

“Rules”: Its consists of a grid 6 tiles wide and 13 tiles tall. 6 different color gems. The gems drop in a set of three from the top. You have to match 3 or more same color gems in ANY of the 8 directions (horz,vert, diagonals). You can SHIFT the gems vertically in there “3 cell space” before you hit a gem or the bottom of the board below it. When a match of 3 or more either horz, vert, or diagonally is found, the gems destroy and the gems there were above the destroyed ones, slide vertically (only) downward to fill the gaps.

.Im sure you’ve heard of it? Lol

“The Question”: What I would like to discuss is: What is the best way to setup or organize memory arrangement (I’m using a 2d array for the grid and no rigid body for collision), to accomplish match making and grid “resettling” after gems are removed?

“My Thoughts”:

0,0 (x,y) starting at lower left most square of 2d grid.

I was thinking of making my gems each be a different integer for each different color on the grid…red=1,green=2 ,3 = blue, 4 = yellow etc…etc. 0 = an EMPTY tile. I will not be using rigid bodies for the collision detection.When the dropping gem hits the bottom of the board or another gem below. Then it starts the check for say, all 1’s (red) or all 3’s (blue gems) in a row, each match has to be connected by 3 or more of the same numbers (gems), that way you only have to check and see if there is anything in the tile if so, the “color” is based on the Integer. Then check for neighbor tiles of same type and so on. I was going to use Generic LISTS to save all the matches in for final destroying and removal. I was tying to think about how to set this up by kind of starting partially “backwards” with the process. I.E. all the gems have already matched, and have been destroyed, now its time to take the board and “resettle” all gems on it, making a rolling list of the new “base” gems as we will need somewhere to start our new “start match check” from… To update the actual Visual aspect of this, I was thinking of having a “copy grid” of the array, but this one containing the actual GAME OBJECTS instead of just a bunch of integers. This way when it came time to destroy and resettle gems on the screen, we can just “tell” every block where to move as it is setup the same way as our grid we use for matching the integers (which represent the gem gameobjects in memory) (see the pics) So hypothetically if going by my crafty (crappy) picture , and we needed to destroy the gem in the tile at (0,0), and since the “4” on the grid on the left has the same index as the “yellow heart shape” as the grid on the right, we just destroy the object in the “game object array” ,reorganize the gems, indexes, and REPEAT?

I tried writing this a few different ways before I posted this message. I have not written it the way I am speculating of doing above…

“Notes”: I am using the same method to detect “collision” and “move” my blocks around as did the author of the UNITY TUTORIAL of TETRIS.

Looking for some serious thought or experience on this?

Thanks King

1862965--119512--GridnumbersAndVisual3d.jpg
1862965--119512--GridnumbersAndVisual3d.jpg1034×618 87.4 KB

2

I’ve never made a match3 game, so pardon me talking sh*t for a bit.
I also haven’t thought about this too hard, so sorry if my advice sucks.
With that said…

For your grid I would take a strong object orientated approach. So no integers in some dinky array. Rather, objects representing each conceptual item. The reason is that let’s say you use integers. Later you want to extend the game to have ‘power gems’, e.g. when you connect 4, or 5 gems in a row. Then you have ‘3’ for the blue gem, but now you have a blue power gem. Is that ‘8’? What if you later extend the number of base gems? You code will be a complete mess of random numbers. And you still need to manage them. Where does all that managing code go? Into spaghetti functions.

Instead create an object that represents a basic gem. Derive from it for each gem type. Then add properties/methods to represent whether it is ‘normal’, ‘ignited’ etc. You code will be much easier to maintain. If you like you can attach the display gameObject as a reference on the gem object and control it from there. Then give the gem class (or base class) a method like ‘destroy/explode’ which notifies nearby gems to die. To know who is next to who, have a board object. It has a method that when given a gem object returns the gem object next to it. etc. The decision to call explode initially might come from a separate class scanning the board each tick for matches (perhaps the board class itself). The explode method can do whatever it wants based on its gem type, for example it can call explode on nearby gems, all gems in a row, or just itself, etc, based on its own internal state. You gems can also have a method like "Advance()'. When a gem explodes, it calls ‘Advance()’ on the gem above it. If that gem advances successfully (drops down), it calls Advance on the gem above it, and so on. The top row of the board has special tiles that spawns in new gems.

For a board/game this tiny, when in doubt, represent your concept with an object/class, not an integer.

EDIT TL;DR
Represent your concepts with objects. Does your game have a board? you need a board class. Does it have a gem? you need a gem class. Etc.

3

OK, I understood what you have stated for the most part. So of your advice, i agree with the object approach, however im not sure about HOW to “add properties to the gem” or have a “board object”. If i dont use an array for the board, how would i keep track of where every gem is (memory wise)? I will work on a board class 1st, and see if i can get that to work.
I believe that I may have an idea of what you are trying to explain about the “gems” deriving from some generic gem: make a class that creates a “generic” gem and in that same class, “allow” it to do the controlling of the gem, like adding if its red or blue or yeollow. also if it is a “normal” gem, or “powerup gem” etc. after all the setup of the “options” that we are going to include with our new freshly “made to order” gem.then add it to the board etc. I guess the visual image i just got was the Dr Sues episode where he had all those big “star printing machines” and the who’s had to pay to go through each machine to get a star stamped, some machines would put two stars on their bodies, sometimes it would put 1 star on etc. lol I guess we are going to have to go make our own “gem generator” machine(script?) lol

Thanks for the fast reply, its gives me a direction to think about. I would like others in the community to comment if they wish. I do not consider this question or discussion closed or answered as we only have one reply.
Thanks
King

4

Why not use multidimensional arrays?

1 Like
5

Sorry, you can still use an array. I was just directing you away form an array in integers. The board class could use the array internally.

Here is some shell code to show you what I was thinking. Feel free to use it, but it’s just something I quickly wrote as an example. It does show you storing gems and looping through them though.

Board

using System;
using System.Collections.Generic;

namespace Match3
{
    public class Board
    {
        private Gem[,] m_Board;

        public int Width
        {
            get { return m_Board.GetLength(0); }
        }

        public int Height
        {
            get { return m_Board.GetLength(1); }
        }

        public Board(int width = 0, int height = 0)
        {
            InitialiseBoard(width, height);
        }

        public void InitialiseBoard(int width, int height)
        {
            // check width & hight values are legal
            // here I set the min value to 3
            width  = width  < 3 ? 3 : width;
            height = height < 3 ? 3 : height;

            m_Board = new Gem[width, height];
            FillBoardRandom();
        }

        private void FillBoardRandom()
        {
            Array values = Enum.GetValues(typeof(Gem.TYPE));
            Random random = new Random();

            for (int x = 0; x < Width; x++)
            {
                for (int y = 0; y < Height; y++)
                {
                    // Note I choose a random gem that is NOT 0, since zero is
                    // a special placeholder gem for empty cells
                    m_Board[x, y] = new Gem((Gem.TYPE)values.GetValue(random.Next(1, values.Length)));
                }
            }
        }

        public override string ToString()
        {
            string result = "";

            for (int x = 0; x < Width; x++)
            {
                result += "[";
                for (int y = 0; y < Height; y++)
                {
                    result += string.Format("{0} ", m_Board[x, y].ToString());
                    if (y < Height - 1)
                    {
                        result += ", ";
                    }
                }
                result += "]\n";
            }

            return result;
        }

    }
}

Gem

using System;
using System.Collections.Generic;

namespace Match3
{
    public class Gem
    {
        public TYPE Type;

        public enum TYPE
        {
            EMPTY  = 0,
            RED    = 1,
            BLUE   = 2,
            GREEN  = 3,
            YELLOW = 4
        }

        public Gem(TYPE type)
        {
            Type = type;
        }

        public override string ToString()
        {
            return Type.ToString();
        }
    }
}

Usage

Board myBoard = new Board(9, 9);
Console.WriteLine(myBoard);

Output

[BLUE , YELLOW , RED , BLUE , YELLOW , YELLOW , BLUE , GREEN , BLUE ]
[RED , RED , RED , GREEN , GREEN , BLUE , GREEN , BLUE , RED ]
[GREEN , YELLOW , GREEN , GREEN , BLUE , BLUE , BLUE , YELLOW , RED ]
[YELLOW , GREEN , BLUE , BLUE , YELLOW , RED , YELLOW , RED , GREEN ]
[BLUE , GREEN , YELLOW , GREEN , RED , BLUE , YELLOW , RED , YELLOW ]
[YELLOW , RED , YELLOW , GREEN , YELLOW , GREEN , YELLOW , GREEN , RED ]
[RED , YELLOW , GREEN , YELLOW , YELLOW , RED , YELLOW , BLUE , RED ]
[RED , YELLOW , RED , RED , YELLOW , GREEN , YELLOW , BLUE , YELLOW ]
[BLUE , RED , GREEN , RED , GREEN , BLUE , GREEN , BLUE , GREEN ]

Edit* fixed typos in code. Oops.

6

The Super 3match kit can save you a lot of work.

7

A while back I posted some general overview techniques here:

8

I dont want a finished product, i would like to do this without a premade deal. It will “stick” better with me ,even if there is a little reinventing the wheel going onn

2 Likes
9

Hello again. Hope everyone had a good turkey day (if thats your thing).
I have my gem class built not very robustly. Lol I wrote a few lines to generate a random gem,made a few variables for the mad num gems you can have based on my enum count… I also wrote a board filler with whatever color gem i wanted on init to fill the board with. My question is, in using your board shell code r.linsday, once i make a new board from my main game class, how do i INDEX through the board x,y wise? I make a new baord with : GameBoard gridBoard = new GameBoard(width,height);
But im not able to index it… e.g. gridBoard[x,y] = 2;
I get "cannot apply indexing with [ ] to an expression of type GameBoard.
What am i missing?
King

10

Your GridBoard class does not derive from a class that uses indexing, but the private attribute m_board does:

m_board[x,y] = 2;

I suggest to create a getGem() function, to keep m_board private.

public Gem getGem(int x, int y)
{
    return m_board[x,y];
}
// then call it with gridBoard.getGem(x,y)

Other solution would be to extend Gridboard from Gem[,] and adjust all your functions. Then you can call your gems in your grid board with gridBoard[x,y].

public class GridBoard extends Gem[,] { }
1 Like
11

If you want to access the board class like that from any code, one way is to add this to your Board class:

        public Gem this[int x, int y]
        {
            get
            {
                return m_Board[x, y];
            }
            set
            {
                m_Board[x, y] = value;
            }
        }

Here is the documentation.

2 Likes
12

Nanity, I do thank you for the more then one way to skin a cat method, however, I was looking for EXACTLY what r.lindsay posted. I had something so close to that earlier, but I wasnt sure if I was supposed to stay away from “m_board” as it was what appeared to be contained to its class. Again, Ty for the comments,likes, and responses. I’ll go code this up and Let you know how it goes. (still working on the foundation LOL)

Thanks
King