Making Algorithm to Find Most Move Efficient Solution in a Complicated 2d Puzzle Game

Question

I'm trying to make an algorithm of any sort that can find the solution with the lowest move count. I'm coding in GML using GMS2 and it's for a game that I'm making myself.

This is a picture of the most simple level

The reason I call it a complicated 2d puzzle game is because of how many types of blocks there are. The goal is to connect the two blocks and the player gets a trophy for solving it in a low move count, but I don't want to have to find the most efficient solutions by hand for every level, especially some of the super complicated levels.

This is an example of a level with all block types in it

The black boxes with an X on them are immovable and act as obstacles

The two blocks you're supposed to connect and the small blue blocks are simple movable blocks and can be moved in any of the four cardinal directions as long as the space is open

The long blue blocks act the same way but require an open space their same size to move into a spot

The red blocks act as a normal movable block, but cannot be placed next to each other. They can still be diagonal from each other though

And the green blocks can only be moved in the directions indicated on the block, meaning only left and right or only up and down

My first thought was to make a depth first search algorithm to just brute force all possible game states until it finds the quickest solution but I'm unsure of how to pull that off.

If anyone has any ideas for methods I could use or information that could help at all then I'm open to all feedback since I don't really know much about algorithms or machine learning at all, thanks in advance!

Answer 1

The standard approach is a breadth-first search. Looking at this hashmap and native queues I believe you can code it in GML, though that wouldn't be my first choice. (Python would be because you can have complex objects as dictionary keys. Dictionary being what Python calls a hashmap. Without that you'll need to serialize/deserialize objects to use them as keys. Serialize being a complicated word meaning, "write out a text representation". Ideally a compact text representation.)

The idea looks like this:

Create hashmap of position and last move
initialize it with start position and last move is none
put start position into a queue of positions to analyze
while stuff in queue and not yet solved:
    pop position from queue
    for each valid move from position:
        if resulting position is solved:
            it is solved and we have final position
        if resulting position is NOT in hashmap:
            add position + move to hashmap
            add position to queue
if no final position:
    there is no answer
else:
    path = []
    prev_move = hashmap of final position
    while prev_move is not none:
        add prev_move to start of path
        unto prev_move from final position to get new final position

And if it is solvable, then path will wind up being the shortest path from the starting position to any position where it is solved.

Note that the number of possible positions explodes, so you can only solve fairly small puzzles. With ideas like A* search you can make this slightly more efficient, but given how much backtracking tends to be involved, not much.