Pikachu matching game - Simple yet algorithmic

A simple Puzzle game that packs quite a bunch in Algorithm & Data structure in Programming.

Pick 2 pokemons with the exact same images, if the path between the 2 isn’t blocked and obey following rule:

path formed shoudn’t have more than 3 edges (in other word: have more than 2 turning points)

Below are the valid path shapes, they have I, L, U, Z shapes…

Algorithms

To represent the board, use a 2D array, each cell is a pokemon (represented by objects with unique ids)

At its core of this game, is the pathfinding algorithm, in order to determine the path from pokemon A -> pokemon B, and to analyze its shape.
To simplify the problem: finding path from A to B with at most 2 turning points. Path should be return as a list of points (used for game path rendering)

brute force: dfs or bfs, then tracing back the path to calculate the number of turning points, invalidate if it’s > 2
to detect a turning point: we must know 3 consecutive points, if none of these 3 points is on the same axis (x == x or y == y) then a turn is made.
A* (AStar): brute force is fine, but let optimize this a bit further, I chose AStar (A*) algorithm.
- I placed a heavy cost on turning point, g cost (cost to distance) has a much lower cost, I don’t calculate f cost since it not needed.
- I do a search first, then trace back the path, make sure it’s <= 2 turning points
- yes and that’s it, it’s more intentional when doing the pathfinding, compared to brute force, which reduce a lot of unecessary checks.

made with godot, source

This algorithm should based on above pathfinding, currently I find no better solution than brute force.
Firstly, group pokemon with same images
For each group, brute force run pathfinding on every pair (so n group => run n! times, O(n!) time complexity)
Return first pair found ASAP.

First, I need to move remaining pieces into a list, then I scramble that list
Then I get all the placeable positions (in case the game has border or blocked cells) into the list, then I also scramble the list
Then run the position list linearly and, keep popping the remaining pieces and place into position

C++, Terminal-based, windows console library