• Hey Guest! Ever feel like entering a Game Jam, but the time limit is always too much pressure? We get it... You lead a hectic life and dedicating 3 whole days to make a game just doesn't work for you! So, why not enter the GMC SLOW JAM? Take your time! Kick back and make your game over 4 months! Interested? Then just click here!

Pattern Finding on a grid in a casual, 2D game - more complicated than match 3

Robopoet

Member
I would really appreciate if someone can help me with finding tiles on a grid that complete a pattern. Once a complete pattern is formed I would like the tiles involved to disappear. You can see how the horn pattern in the attached image is complete. I'm not using gravity in this game. The tiles involved in the complete pattern would disappear and be replaced by mostly randomized shapes.

Thank you!
 
Last edited:

Nidoking

Member
That's just Dijkstra's Algorithm, except that instead of distance, you're checking for whether the tiles connect properly in the group. I'd do something like this:

GML:
// Reset to initial state
with (tiles) checked = false;

// Check for complete sets
with (tiles)
{
  // Only check any tile once per iteration
  if (!checked)
  {
    checked = true;
    Create data structure - I use a list, but you could use an array
    Add self.id to the data structure
    loop over the data structure (do or for)
    {
      if tile has a path going up, does the tile above have a path going down?
      if no, destroy the data structure and break - we know none of the visited tiles are in a complete set
      else if the tile above has checked = false, set the tile above.checked = true and add it to the data structure
      repeat for left, down, and right, in any order
      move to the next tile in the structure, if any
    }
    if we made it to the end of the data structure, it contains a complete set.
    else continue - all tiles will be visited exactly once
  }
}
 

rytan451

Member
That's just Dijkstra's Algorithm, except that instead of distance, you're checking for whether the tiles connect properly in the group.
In this case, it's actually more of just being either a depth-first search or breadth-first search. Here's a bit of code implementing the depth-first search that I mentioned:

GML:
function tilesInPattern(x, y, arr) {
  // This indicates it was called without the array, which can only happen from outside of this function. It will return the array instead of true (it's part of a pattern)/false (it's not part of a pattern)
  isReturningArray = false;
  if (is_undefined(arr)) {
    isReturningArray = true;
    arr = [];
  }
  
  if (!doesTileExist(x, y)) {
    if (isReturningArray) {
      return [];
    } else {
      return true;
    }
  }

  var len = array_length(arr);
  for (var i = 0; i < len; i += 2) {
    if (arr[i] == x and arr[i + 1] == y) {
      return true; // Already visited here
    }
  }
  
  // Mark that this location has been visited
  array_push(arr, x, y);

  // Check tile to the left
  if (connectsToLeftTile(x, y)) {
    if (!connectsToRightTile(x - 1, y) {
      array_resize(arr, 0);
      return false; // Pattern is not complete here
    } else if (!tilesInPattern(x - 1, y, arr)) {
      return false; // Pattern is not complete elsewhere
    }
  }
  // Check tile to the right
  if (connectsToRightTile(x, y)) {
    if (!connectsToLeftTile(x + 1, y) {
      array_resize(arr, 0);
      return false; // Pattern is not complete here
    } else if (!tilesInPattern(x + 1, y, arr)) {
      return false; // Pattern is not complete elsewhere
    }
  }
  // Check tile above
  if (connectsToAboveTile(x, y)) {
    if (!connectsToBelowTile(x, y - 1) {
      array_resize(arr, 0);
      return false; // Pattern is not complete here
    } else if (!tilesInPattern(x, y - 1, arr)) {
      return false; // Pattern is not complete elsewhere
    }
  }
  // Check tile below
  if (connectsToBelowTile(x, y)) {
    if (!connectsToAboveTile(x, y + 1) {
      array_resize(arr, 0);
      return false; // Pattern is not complete here
    } else if (!tilesInPattern(x - 1, y, arr)) {
      return false; // Pattern is not complete elsewhere
    }
  }
  if (isReturningArray) {
    return arr;
  } else {
    return true;
  }
}
Note that this isn't completely optimal. This runs in O(N^2) where N is the number of tiles in the pattern. If I wished to reduce the time complexity, I could instead store which tiles were visited in a ds_map, indexing each tile as x + y * TILE_HORIZONTAL_COUNT, then converting this to an array before returning it. Since checking if a value exists in a hash map takes O(1) time, that would reduce the time complexity of this code to O(N).
 

Robopoet

Member
I made this game in a previous version of GameMaker. I did no coding at all.
I enjoyed the gameplay - I got it working up to 5 tile patterns - but it quickly became complicated to find larger completed patterns and replace them.
Is there someone who I could send the game file to who could implement the coding and get the game functional?
I don't know how much time and effort it would take but I'm happy to compensate for time or partner up somehow.
It would be great to work with someone who's experienced with coding.
If you like 2D match games, I think my game is original enough to stand out.

Thanks!
 

rytan451

Member
Every time I say this, people tell me it's Dijkstra's Algorithm. I just gave up. Same difference, ultimately.
Dijkstra's Algorithm specifically uses a priority queue to select the next vertex to visit. In your example, you're using a list data structure like a queue. You could instead use a queue data structure or a stack data structure.

Breadth-First Search is only identical to Dijkstra's Algorithm if all edge weights are the same.
 
Yeah, if you're simply expanding outwards, it's breadth-first, if you're measuring the distance you've travelled (or some other cost metric) and sorting nodes based on that, it's djikstra's and if you're measuring a cost metric and the distance to the goal and sorting nodes based on those two things, it's A*.
 
Top