C# Bejeweled 3 bot - part 2 - moving tiles

Summing up the last post: we can now identify the gems on the board and produce an array containing color indices.

The move class

I love writing ‘simple’ code that speaks for itself. Does it make the code slower? Maybe, but until I don’t experience any sluggishness on my 3 years old low end laptop then I don’t care! Clarity comes first, then comes optimization if it’s needed.

Here is the whole move class (and an extra enum):

using System.Drawing;

namespace BejeweledBot
{
  public enum Direction
  {
    UP,
    RIGHT,
    DOWN,
    LEFT
  }

  public class Move
  {
    public Point Pt { get; set; }
    public Direction Direction { get; set; }

    public Move(Point pt, Direction dir)
    {
      Pt = pt;
      Direction = dir;
    }
  }
}

Moving the tiles

{ 1,  2,  3,  0,  3,  1}
{ 1,  1,  2,  0,  0,  1}
{ 0,  0,  3,  0,  0,  0}
{ 0,  5,  3,  3,  1,  3}

Let’s say that the above is the array we consider (and ignore elements with 0 value). If this was our game board we would have two valid moves:

  • Move element (0,2)[row,column] down
  • Move element (3,5) left

I look for matches separately in two directions; horizontally and vertically. Here is roughly what the algorithm I created does:

  • Select row and column

  • Checks 8 neighbours (2 elements up, down, left, right) of a selected row and column to see if there are any elements with matching value

Bejeweled algorithm, finding neighbours
Red is the selected value, blue are the neighbours I check for the target value (3)
  • If there are elements with matching values in the neighbourhood then algorithm proceeds further by iterating through them

  • If the matching neighbour is far from the selected row and column then I look for matches either horizontally or vertically

Searching for valid neighbour move
If any of values marked in blue were 3 then moving them appropriately would be a valid move
  • If the two matching elements are one close to the other then things get a bit more complicated:
Searching for valid neighbour move
  • We then check all close neighbours of the element marked in pink to see if any of them have the value we are interested in. We are doing the same operation on the neighbour to the bottom of the group (in this case not shown on the picture).

Enough talking, let’s see some code!

Here is the function for matching neighbours in one direction:

private static List<Point> getHorizontalMatch(int[,] arr, int row, int col, int distance, int targetValue)
{
  int height = arr.GetLength(0);
  int width = arr.GetLength(1);
  if (width != height)
    throw new ArgumentException("Provided array was not square");

  List<Point> pointList = new List<Point>();

  for (int j = col - distance; j <= col + distance; j++)
  {
    if (j >= 0 && j < width && j != col)
    {
      if (arr.TryGetValue(row,j) == targetValue)
      {
        pointList.Add(new Point(row, j));
      }
    }
  }
  return pointList;
}

The distance allows me to specify what is the range of tiles I’m interested in. In case of point 2 the distance will be 2. In case of point 5 the distance will be 1.

TryGetValue is an extension method that ensures that I never try to check the array for a value out of bonds. Here is the code:

namespace BejeweledBot
{
  public static class ArrExtension
  {
    public static int TryGetValue(this int[,] arr, int row, int col)
    {
      bool widthOK = false;
      bool heightOK = false;
      if (row >= 0 && row < arr.GetLength(0))
        widthOK = true;
      if (col >= 0 && col < arr.GetLength(1))
        heightOK = true;

      if (widthOK && heightOK)
        return arr[row, col];
      else
        return -1; //we won't have values less than zero in the board array
    }
  }
}

More codeeeeeee

OK, there is some more code. I promise this is the last snippet and then I will shut up! Since we have some code for matching neighbours now we can put together the last final function(s). The code to follow returns the list of Moves, so we know which tiles to move where to score some shiny points!

private static List<Move> getMoves(List<Point> matches, Point source)
{
  List<Move> moves = new List<Move>();
  foreach (Point pt in matches)
  {
    if (pt.X < source.X)
    {
      moves.Add(new Move(pt, Direction.DOWN));
    }
    else if (pt.X > source.X)
    {
      moves.Add(new Move(pt, Direction.UP));
    }
    else if (pt.Y < source.Y)
    {
      moves.Add(new Move(pt, Direction.RIGHT));
    }
    else if (pt.Y > source.Y)
    {
      moves.Add(new Move(pt, Direction.LEFT));
    }
  }
  return moves;
}

private static List<Move> getValidMoves(Point target, List<Point> validNeighbours, int[,] board)
{
  //x - row
  //y - col
  List<Move> moves = new List<Move>();
  int value = board[target.X, target.Y];
  foreach (Point neighbour in validNeighbours)
  {
    //one index of neighbour is always the same as the index of target
    //horizontal check
    if (neighbour.X == target.X)
    {
      int minY = Math.Min(neighbour.Y, target.Y);
      int maxY = Math.Max(neighbour.Y, target.Y);
      if (maxY - minY == 1) //points are next to one another
      {
        Point leftPoint = new Point(target.X, minY - 1);
        Point rightPoint = new Point(target.X, maxY + 1);

        List<Point> leftMatches = getAllMatches(board, leftPoint.X, leftPoint.Y, 1, value);
        moves.AddRange(getMoves(leftMatches, leftPoint));

        List<Point> rightMatches = getAllMatches(board, rightPoint.X, rightPoint.Y, 1, value);
        moves.AddRange(getMoves(rightMatches, rightPoint));

        moves.RemoveAll(mv => (mv.Pt == neighbour || mv.Pt == target));
      }
      else //points have an empty tile between them
      {
        Point midPoint = new Point(target.X, minY + 1);
        List<Point> midMatches = getVerticalMatch(board, midPoint.X, midPoint.Y, 1, value);
        moves.AddRange(getMoves(midMatches, midPoint));
      }
    }
    else //vertical check TODO: refactor
    {
      int minX = Math.Min(neighbour.X, target.X);
      int maxX = Math.Max(neighbour.X, target.X);
      if (maxX - minX == 1)//points are next to one another
      {
        Point topPoint = new Point(minX - 1, target.Y);
        Point bottomPoint = new Point(maxX + 1, target.Y);

        List<Point> topMatches = getAllMatches(board, topPoint.X, topPoint.Y, 1, value);
        moves.AddRange(getMoves(topMatches, topPoint));

        List<Point> bottomMatches = getAllMatches(board, bottomPoint.X, bottomPoint.Y, 1, value);
        moves.AddRange(getMoves(bottomMatches, bottomPoint));

        moves.RemoveAll(mv => (mv.Pt == neighbour || mv.Pt == target));
      }
      else //points have an empty tile between them
      {
        Point midPoint = new Point(minX + 1, target.Y);
        List<Point> midMatches = getHorizontalMatch(board, midPoint.X, midPoint.Y, 1, value);
        moves.AddRange(getMoves(midMatches, midPoint));
      }
    }
  }
  return moves;
}

Summing up

So here it is! Now you can get the valid moves for the bejeweled game. In the last post I will show you how I handle keyboard events and simulate mouse clicks. Stay tuned!

Or if you can’t wait then just grab the source code.

Mateusz Sadowski

Mateusz Sadowski
Mat is a Robotics consultant and the author of Build Mobile Robots with ROS 2 LiveProject series.

Remote Robotics Consulting - A Five-Year Retrospective

In this blog post, I will highlight some of the updates since my last blog and offer some advice that I hope will be useful for anyone looking to get into technical consulting. Continue reading

I Created a Project-based ROS2 Course

Published on July 05, 2022

IMUs and LiDARs - Not Uncommon Pitfalls

Published on February 24, 2022