Part 8 - Initial Rules

April 11, 2019

In the previous part we implemented a simple finite state machine that will be used to manage our game rules. As seen near the end, we still need quite a lot of foundation code in order to actually finish the state machine itself. However, if we tackle that first, we risk getting really bored with a lot of code that doesn't give any visual difference in our project. So, why not implement something that will give us new things to see in the game and then go back into more foundation code?

For that, we will implement our first game rule of the project.

The First Rule

Ok, this is not rule number 1 as in "the most important". This is the first to be implemented in the project. As we have delineated in the introduction, the default traditional game mode should spawn some initial blocks in the grid. Because this rule is not meant to be present in all game modes, only the "Default" one, the implementation of this initial block spawning should not be added into the base GameModeInGame class, rather, into a derived class. We do have BP_GMTraditional blueprint class and, if desired, we could implement said rule in there. However, our implementation will be done in a C++ class, AGMInGameTraditional, derived from AGameModeInGame.

In this new class we need a property meant to define how many rows will be filled by the initial blocks. This will be an integer named mInitialFloor. This rule tells that at the beginning of the game, we have to fill in with blocks a few rows in the grid. We did provide means to do that, using the CustomGameInit() function, that will be called by the StateGameInit() function, which we defined in the previous part. With that said, we add into the class the CustomGameInit() override declaration.

#pragma once

#include "GameModeInGame.h"
#include "GMInGameTraditional.generated.h"

UCLASS()
class UCOLUMNSTUTORIAL_API AGMInGameTraditional : public AGameModeInGame
{
   GENERATED_BODY()
public:
   AGMInGameTraditional();

   virtual void CustomGameInit(float Seconds) override;

private:
   UPROPERTY(EditAnywhere, Category = "Gameplay Settings", meta = (DisplayName = "Initial Floor"))
   int32 mInitialFloor;
};

Right after the only include file, we define the constructor which initializes the mInitialFloor property with 3:

#include "GMInGameTraditional.h"

AGMInGameTraditional::AGMInGameTraditional()
   : mInitialFloor(3)
{}

Now for the CustomGameInit() definition. It's relatively simple, at least for the moment. All we have to do is iterate through the rows with index smaller than mInitialFloor. For each of these rows, we iterate through all available columns, spawning random blocks in the relevant cells. And at the end we have to call the super class, so if any derived blueprint class will also get the event, like this:

void AGMInGameTraditional::CustomGameInit(float Seconds)
{
   for (int32 row = 0; row < mInitialFloor; row++)
   {
      for (int32 col = 0; col < GetColumnCount(); col++)
      {
         SpawnBlock(col, row, PickRandomBlock(), true);
      }
   }

   Super::CustomGameInit(Seconds);
}

After building the project we will want to test this. The InGame map level is setup to use the BP_GMTraditional blueprint class as game mode. This class has AGameModeInGame as parent and we have just added a new C++ game mode class. Should we delete the blueprint class and create a new one? Not really. Luckily, we can reparent the blueprint class so its new parent become our new C++ class. In order to do that, edit the BP_GMTraditional blueprint and click the Class Settings button in the toolbar. This will allow us to change the parent of this class.

Blueprint Reparent

Once you select GMInGameTraditional as the new parent, clicking the Class Defaults button in the toolbar should allow editing the mInitialFloor property. If you click the Play button, then the result should be a grid with a few rows filled with blocks, more specifically mInitialFloor rows. With that said, I encourage you to change the mInitialFloor property and test it. Just be careful to not set this value to be bigger than the amount of rows since we didn't add any error checking for this case.

Match Checking

After running (err, testing) the game a few times, you may have noticed something: there is a chance that some of the initial blocks will be forming matching sequences, like this one:

Three triangles and three arcs in diagonals as well as three crosses in horizontal matching sequences. Indeed, we didn't add any kind of spawning restriction into our code. Depending on how you want your game, it may be OK to leave like this, however I will show how to avoid those initial matches. For that, we have to start working on the match checking algorithm.

Although we will not work with match checking caused by the player piece so soon, we will still analyze its case in order to implement the algorithm so we can utilize the same code, or at least part of it, for the initial block spawning, player's pieces and block repositioning.

The first approach one could take is scan the grid counting run lengths and flagging the blocks whenever the count reaches at least 3 (or whatever minimum run length setup in the game play settings). That doesn't sound like an efficient way of checking for matches, although it's not that problematic for a grid this small. Since we can do better, we will do so!

The approach we will take will be "centered" on the blocks that have just landed, either from the player piece reaching the "floor" or block repositioning. The algorithm will begin from each of those blocks and then "walk" in all directions, counting the number of blocks of the same type. The next image is meant to give a visual explanation of the idea. The triangles represent blocks that have just "landed" and the blobs can be anything, not necessary the same block types, maybe even empty grid cells provided there are no blocks above.

Match Checking

The bottom most triangle is the "center" and the algorithm "walks" in 8 directions (the arrows). This "walking" stops if a block of different type is found, an empty cell is found or the "grid border" is found. Notice that the other 2 triangles (in the image) also have to be used as "centers" for further counting. Yes, the vertical counting will result in some blocks being checked multiple times but, really, avoiding this is more trouble than counting a few extra times.

Now, suppose the situation where we start to count matching runs horizontally. We first start "walking" to the left and count just 1 matching block. Then, we go to the right and count 2 matching blocks. The total sum has to include the "center block", meaning that we now have 4 matching blocks. The reason I have brought this case as an example is just to make it clear that when we "walk" to one side and the result is smaller than the minimum run, it doesn't necessarily mean there is not matching run at all. We have to sum the results of both opposing directions as well as the "central block".

With that said, we could create a function CountHorizontalMatch() and then fill in with two loops, one counting to the left and the other counting to the right. Then one could think "well, when walking to the left we also have up-left and down-left" and stuff in these two diagonals into the "left loop". However we will do things a little differently. Instead, there will be a function for each of the 8 directions. One of the reasons for not stuffing everything possible in a single loop is the fact that we would have to track extra variables and then we won't be able to directly stop the loop if we find one of the "stopping conditions". We have to see if the other two directions have also reached stopping conditions in order to actually break the loop. Another reason for this we will find out shortly when applying the algorithm to disallow running matches in the initial play field. Later on we can still create the CountHorizontalMatch() and in it call CountLeftMatch() and CountRightMatch().

The question now, how exactly will this count be done? Remember in part 6 when we added some code to manage the spawned blocks? Just as a reminder, in the AGameModeInGame class we have the mGridData array. From there we have access to the contents of each cell in the grid. In other words, our block counting will just iterate through the objects stored in the array. The algorithm needs a "central cell" to start counting from, so we specify the row and the column through counting functions arguments. We could use that information to check the cell's contents and retrieve the block type in there, however what if the cell is actually empty? Early I have mentioned that blocks spawned to compose the player piece should not be immediately added into the grid data array. For this reason, we specify through an argument the block type to be used in the comparison counting.

Code time. First we have to declare the new functions. In the public section of the AGameModeInGame class:

// Count how many blocks to the left of the specified cell match the requested block type
UFUNCTION(BlueprintPure)
int32 GetLeftMatch(int32 Column, int32 Row, int32 BlockType) const;

// Count how many blocks to the right of the specified cell match the requested block type
UFUNCTION(BlueprintPure)
int32 GetRightMatch(int32 Column, int32 Row, int32 BlockType) const;

// Count how many blocks to the top of the specified cell match the requested block type
UFUNCTION(BlueprintPure)
int32 GetUpMatch(int32 Column, int32 Row, int32 BlockType) const;

// Count how many blocks to the bottom of the specified cell match the requested block type
UFUNCTION(BlueprintPure)
int32 GetDownMatch(int32 Column, int32 Row, int32 BlockType) const;

// Count how many blocks to the top left of the specified cell match the requested block type
UFUNCTION(BlueprintPure)
int32 GetUpLeftMatch(int32 Column, int32 Row, int32 BlockType) const;

// Count how many blocks to the top right of the specified cell match the requested block type
UFUNCTION(BlueprintPure)
int32 GetUpRightMatch(int32 Column, int32 Row, int32 BlockType) const;

// Count how many blocks to the bottom left of the specified cell match the requested block type
UFUNCTION(BlueprintPure)
int32 GetDownLeftMatch(int32 Column, int32 Row, int32 BlockType) const;

// Count how many blocks to the bottom right of the specified cell match the requested block type
UFUNCTION(BlueprintPure)
int32 GetDownRightMatch(int32 Column, int32 Row, int32 BlockType) const;

The actual implementation of each of these functions is relatively simple. The most important aspect to keep in mind is the "walking" through the various cells, more specifically, how the index access changes. In order to "walk one column to the left" it's necessary to subtract 1 from the index. "Walking one column to the right" means adding 1 to the access index. Then, when dealing with vertical movement, "walking one row upwards" means adding ColumnCount to the index. Conversely, "walking one row downwards" means subtracting ColumnCount from the access index. How about the diagonals?! They are simply combinations of horizontal and vertical iteration.

Ok, so let's begin by implementing the easier functions, dealing with horizontal movement. You may notice the usage of an extra variable, current_column that is used as the loop stop condition. We could go away from this variable if we compute how many columns must be iterated through, however this extra variable way makes things a little simpler, specially when dealing with the diagonals counting.

int32 AGameModeInGame::GetLeftMatch(int32 Column, int32 Row, int32 BlockType) const
{
   // Walk to the left
   int32 current_column = Column - 1;
   int32 data_index = GetCellIndex(current_column, Row);
   if (data_index < 0)
      return 0;

   int32 counted = 0;
   while (current_column >= 0)
   {
      ABlock* block = mGridData[data_index].BlockActor;

      // If cell is empty or if the block is of different type, stop the counting
      if (!block || !block->IsSameTypeID(BlockType))
         return counted;

      counted++;
      data_index--;
      current_column--;
   }
   return counted;
}

int32 AGameModeInGame::GetRightMatch(int32 Column, int32 Row, int32 BlockType) const
{
   // Walk to the right
   int32 current_column = Column + 1;
   int32 data_index = GetCellIndex(current_column, Row);
   if (data_index < 0)
      return 0;
   
   int32 counted = 0;
   while (current_column < GetColumnCount())
   {
      ABlock* block = mGridData[data_index].BlockActor;

      // If cell is empty or if the block is of different type, stop the counting
      if (!block || !block->IsSameTypeID(BlockType))
         return counted;

      counted++;
      data_index++;
      current_column++;
   }
   return counted;
}

Let's deal with the vertical block match counting. Remember, in order to iterate through the rows while staying in the same column all we have to do is add/subtract column count to/from the access index. Similarly to the extra variable we have used in the horizontal counting functions, we use current_row for the vertical functions:

int32 AGameModeInGame::GetUpMatch(int32 Column, int32 Row, int32 BlockType) const
{
   // Walk upwards (add to the index)
   int32 current_row = Row + 1;
   int32 data_index = GetCellIndex(Column, current_row);
   if (data_index < 0)
      return 0;

   int32 counted = 0;
   while (current_row < GetRowCount())
   {
      ABlock* block = mGridData[data_index].BlockActor;

      // If cell is empty or if the block is of different type, stop the counting
      if (!block || !block->IsSameTypeID(BlockType))
         return counted;

      counted++;
      data_index += GetColumnCount();
      current_row++;
   }
   return counted;
}

int32 AGameModeInGame::GetDownMatch(int32 Column, int32 Row, int32 BlockType) const
{
   // Walk downwards (subtract from the index)
   int32 current_row = Row - 1;
   int32 data_index = GetCellIndex(Column, current_row);
   if (data_index < 0)
      return 0;

   int32 counted = 0;
   while (current_row >= 0)
   {
      ABlock* block = mGridData[data_index].BlockActor;

      // If cell is empty or if the block is of different type, stop the counting
      if (!block || !block->IsSameTypeID(BlockType))
         return counted;

      counted++;
      data_index -= GetColumnCount();
      current_row--;
   }
   return counted;
}

For the diagonals, as mentioned, we have to combine the two "movement operations in one". Let's first implement the two cases where we "walk upwards". On both cases we have to add column count into the index so we iterated the "rows above". After that, just subtract or add one to the index so we move to the left or to the right column.

int32 AGameModeInGame::GetUpLeftMatch(int32 Column, int32 Row, int32 BlockType) const
{
   // Walk to the left and upwards
   int32 current_column = Column - 1;
   int32 current_row = Row + 1;
   int32 data_index = GetCellIndex(current_column, current_row);
   if (data_index < 0)
      return 0;

   int32 counted = 0;
   while (current_row < GetRowCount() && current_column >= 0)
   {
      ABlock* block = mGridData[data_index].BlockActor;

      // if cell is empty or if the block is of different type, stop the counting
      if (!block || !block->IsSameTypeID(BlockType))
         return counted;

      counted++;
      data_index += GetColumnCount() - 1;
      current_column--;
      current_row++;
   }
   return counted;
}

int32 AGameModeInGame::GetUpRightMatch(int32 Column, int32 Row, int32 BlockType) const
{
   // Walk to the right and upwards
   int32 current_column = Column + 1;
   int32 current_row = Row + 1;
   int32 data_index = GetCellIndex(current_column, current_row);
   if (data_index < 0)
      return 0;

   int32 counted = 0;
   while (current_row < GetRowCount() && current_column < GetColumnCount())
   {
      ABlock* block = mGridData[data_index].BlockActor;

      // if cell is empty or if the block is of different type, stop the counting
      if (!block || !block->IsSameTypeID(BlockType))
         return counted;

      counted++;
      data_index += GetColumnCount() + 1;
      current_column++;
      current_row++;
   }
   return counted;
}

Hopefully my explanation was good enough for you to understand the logic behind this and the last two functions are not necessary to be shown here. Nevertheless, for sake of completeness, I'm adding the code here:

int32 AGameModeInGame::GetDownLeftMatch(int32 Column, int32 Row, int32 BlockType) const
{
   // Walk to the left and downwards
   int32 current_column = Column - 1;
   int32 current_row = Row - 1;
   int32 data_index = GetCellIndex(current_column, current_row);
   if (data_index < 0)
      return 0;

   int32 counted = 0;
   while (current_row >= 0 && current_column >= 0)
   {
      ABlock* block = mGridData[data_index].BlockActor;

      // if cell is empty or if the block is of different type, stop the counting
      if (!block || !block->IsSameTypeID(BlockType))
         return counted;

      counted++;
      data_index -= (GetColumnCount() + 1);
      current_column--;
      current_row--;
   }
   return counted;
}

int32 AGameModeInGame::GetDownRightMatch(int32 Column, int32 Row, int32 BlockType) const
{
   // Walk to the right and downwards
   int32 current_column = Column + 1;
   int32 current_row = Row - 1;
   int32 data_index = GetCellIndex(current_column, current_row);
   if (data_index < 0)
      return 0;

   int32 counted = 0;
   while (current_row >= 0 && current_column < GetColumnCount())
   {
      ABlock* block = mGridData[data_index].BlockActor;

      // if cell is empty or if the block is of different type, stop the counting
      if (!block || !block->IsSameTypeID(BlockType))
         return counted;

      counted++;
      data_index += 1 - GetColumnCount();
      current_column++;
      current_row--;
   }
   return counted;
}

No Initial Matches

We can now use those functions to create the algorithm that will avoid matching sequences in the initial spawned blocks. The way we will do this follows:

1. Use the random block picker to obtain a random block type ID. Let's call this NewBlockType.
2. Call the various match counting using NewBlockType as the last argument and the cell where the block should be spawned at as the "center". Let's call the result MatchCount.
3. If any MatchCount+1 (+1 because we have to take the spawn candidate into account) results in a matching run, go back to 1. Otherwise, continue.
4. Spawn the block.

Those steps are run for each of the cells in which we have to spawn a new block. Hopefully this brief explanation is enough to make it clear why we have added the BlockType argument in each of the match counting functions.

Before jumping into the code, there is one more important thing to talk. We don't have to call all 8 of the match counting functions! Our block spawning code fills each row, from left to right and beginning from the bottom row. What this means is that we will never have blocks to the right of the desired cell in the same row. Likewise, we will never have blocks upwards of the desired cell, including the two up diagonals. As a consequence in this section of the code we can ignore GetTopleftMatch(), GetTopMatch(), GetToprightMatch() and GetRightMatch() function calls. This showcases one of the benefits of having the block counting functions separated like we have done.

By looking into the "4 steps" necessary to spawn new blocks without causing matching runs, it's clear that we have a potential loop where we have to obtain a random block type ID until this new block type does not cause a matching run. The actual condition requires calling four functions and checking the results of each one of them. In order to make things a bit simpler, we will create a new function, SpawnAllowed() meant to return true if the new block can be spawned in the requested cell. Because this is a helper function, let's declare it in the private section of the AGMInGameTraditional class:

bool SpawnAllowed(int32 Column, int32 Row, int32 TypeID) const;

As you can see, those are pretty much the same arguments we have to use with each one of the match counting functions. We have to call 4 block counting functions and if only one of them return the count necessary to form a matching run, then SpawnAllowed has to return false. In other words, all four functions have to return a value small enough to not form matching sequences in order to actually returning true. The code should make this clearer:

bool AGMInGameTraditional::SpawnAllowed(int32 Column, int32 Row, int32 TypeID) const
{
   // The minimum match run size
   // TODO: obtain this value from game settings
   const int32 match_run = 3;

   if (GetLeftMatch(Column, Row, TypeID) + 1 >= match_run)
      return false;
   if (GetDownRightMatch(Column, Row, TypeID) + 1 >= match_run)
      return false;
   if (GetDownMatch(Column, Row, TypeID) + 1 >= match_run)
      return false;
   if (GetDownLeftMatch(Column, Row, TypeID) + 1 >= match_run)
      return false;
   return true;
}

You may have noticed a TODO comment in the code. We will deal with that shortly. Let's now update our block spawning code to implement that "four step algorithm".

void AGMInGameTraditional::CustomGameInit(float Seconds)
{
   for (int32 row = 0; row < mInitialFloor; row++)
   {
      for (int32 col = 0; col < GetColumnCount(); col++)
      {
         int32 block_type = PickRandomBlock();
         while (!SpawnAllowed(col, row, block_type))
         {
            block_type = PickRandomBlock();
         }

         SpawnBlock(col, row, block_type, true);
      }
   }

   Super::CustomGameInit(Seconds);
}

Build the project and test it. If you really want to make sure the algorithm is working, you may temporarily increase number of columns and rows, as well as the "initial floor". This code should be enough to completely "deny" any matching runs to occur in the initial play field.

Matching Run Setting

In the SpawnAllowed() function we have hard coded the minimum match run size to 3. But what if you want a game mode or difficulty setting that requires the player to match 5 blocks of the same type instead of 3? In order to obtain this kind of flexibility we have to provide yet another game play setting. In this case it will be named mMatchRunSize. This setting will be used by every "in game" game mode which, in turn, makes AGameModeInGame class a very good candidate to hold this property. However, if there is any desire to add a menu where the player can directly specify this value, the ideal place becomes our Game Instance class (UColGameInstance), so the setting "persists" between the maps.

In this tutorial we will not work with a menu allowing the player to setup the match run size, however we will keep the setting in the game instance so the flexibility to expand is there. With that in mind, in the private section of the UColGameInstance class, we add this new property:

// Defines the minimum matching sequence size
UPROPERTY(EditAnywhere, meta = (DisplayName = "Match Run Size"))
int32 mMatchRunSize;

And then, we need means to access this property from elsewhere. In the public section we add a function to get the value of the new property and another to set it:

UFUNCTION(BlueprintPure)
int32 GetMinimumMatchRunSize() const { return mMatchRunSize; }

UFUNCTION(BlueprintCallable)
void SetMinimumMatchRunSize(int32 RunSize) { mMatchRunSize = RunSize; }

Finally, in the constructor of the game instance class we initialize the property with a default value. In this case, 3:

UColGameInstance::UColGameInstance()
{
   ...
   mMatchRunSize = 3;
}

Our game modes will become the "consumers" of this property. To obtain the value we need to get the game instance pointer and then call GetMinimumMatchRunSize(). Previously we have create a blueprint function library providing means to obtain the game instance pointer, as well as access to a property stored in the instance class. Let's follow the same pattern and include two functions in the library, one meant to edit and the other to read this property:

// Set the minimum run size inside the game instance
UFUNCTION(BlueprintCallable, meta = (WorldContext = "WorldContextObject"))
static void SetMinimumMatchRunSize(const UObject* WorldContextObject, int32 NewSize);

// Obtain the minimum match run size from the game instance
UFUNCTION(BlueprintPure, meta = (WorldContext = "WorldContextObject"))
static int32 GetMinimumMatchRunSize(const UObject* WorldContextObject);

Implementing them is straightforward, since we just use the already created function, GetColGameInstance() and then directly access the game instance's functions:

void UColBPLibrary::SetMinimumMatchRunSize(const UObject* WorldContextObject, int32 NewSize)
{
   if (UColGameInstance* gi = GetColGameInstance(WorldContextObject))
   {
      gi->SetMinimumMatchRunSize(NewSize);
   }
}

int32 UColBPLibrary::GetMinimumMatchRunSize(const UObject* WorldContextObject)
{
   if (UColGameInstance* gi = GetColGameInstance(WorldContextObject))
   {
      return gi->GetMinimumMatchRunSize();
   }
   return 3;
}

Let's go back to the SpawnAllowed() function. Remember those specific lines?

// The minimum match run size
// TODO: obtain this value from game settings
const int32 match_run = 3;

We can now change into this:

// The minimum match run size
const int32 match_run = UColBPLibrary::GetMinimumMatchRunSize(this);

And for this to work we have to add the correct library in the includes of the .cpp file:

#include "GMInGameTraditional.h"
#include "ColBPLibrary.h"

Build the project and test again! As part of the tests, experiment increasing the match run size property to 4 or 5. With this you should see how frequent 3 blocks of the same type appear together and that our match counting algorithm is indeed working!

In this part we have dealt with one very important part of the code in the project, the match checking algorithm. This is what will allow the game to have the main objective working, that is, the match 3 part! Although we didn't add any interactivity yet, we at least can see something different each time the game is tested. Namely, the initial spawned blocks within the grid in the traditional game mode.

In the next part we begin working in the player piece, which is the thing that will provide the interactivity to the player!