Claim
You claim to be using a 'backtracking' algorithm. I would disagree. You are using repeated random walks, starting at random positions from previous walks; I see no evidence of "backtracking".
Dictionaries
Dictionaries are fast; their look up operations are \$O(1)\$.
But they are not FAST. The input key must be converted to a hash value, then the hash value is converted to a bin number, then the bin is searched for a key that exactly matches the given key, and if found the corresponding value is returned.
Overusing dictionaries will result in slower code, and you are doing that here.
Double Indirection
You have a dictionary mapping direction names to direction values, and then you randomly select a direction name from a list of available directions, and look up the corresponding direction value.
You are not using the direction name for anything other than the lookup. It is a middle-value.
Consider instead a list of direction values. Let's remove the direction_to_coords dictionary and instead define the four directions as constants, and initialize directions to those instead:
UP = {'y': -2, 'half': 1}
DOWN = {'y': 2, 'half': -1},
LEFT = {'x': -2, 'half': 1},
RIGHT = {'x': 2, 'half': -1}
directions = [UP, DOWN, LEFT, RIGHT]
Now, instead of choosing a random direction name and looking up the "action", we can just pick a random "action".
direction_action = random.choice(directions)
If the way is blocked, you remove the direction_action from the possibilities:
directions.remove(direction_action)
Heterogeneous dictionaries
Your direction actions are different animals. While they all have a 'half' key, only some have an 'x' key, while the others have a 'y' key. This means after selecting a random action, you have to check if 'y' in direction_action to determine which kind of animal you have.
Instead, you want to store the same kind of thing. For example:
UP = {'full': (0, -2), 'half': (0, 1)}
DOWN = {'full': (0, 2), 'half': (0, -1)}
LEFT = {'full': (-2, 0), 'half': (1, 0)}
RIGHT = {'full': (2, 0), 'half': (-1, 0)}
The 'full' and 'half' attributes contain the change in both row and col for that direction, even if the change is zero for that dimension. There is no longer a need to check if 'y' in direction_action because the same code will execute for the horizontal and vertical directions.
direction = random.choice(directions)
dc, dr = direction['full']
if 0 < row + dr < height and 0 < col + dc < width and pixels[row + dr, col + dc] != 255:
row += dr
col += dc
dig(row, col)
dc, dr = direction['half']
dig(row + dr, col + dc)
directions = [UP, DOWN, LEFT, RIGHT]
visited += 1
paths.append([row, col, 0])
else:
directions.remove(direction)
22 lines has been reduced to 13, an if/if/else/else/if/else has become just an if/else, and a dictionary indirection lookup has been removed.
Note: The variable names like dc and dr come from calculus, where a change in a variable x is often written as \$\Delta x\$, pronounced "delta-x", and later \$\delta x\$, or simply \$dx\$. Choose more descriptive names if you are not comfortable with these.
Two Steps Forward, One Step Back
Those 'full' and 'half' dictionary keys are yet another unnecessary dictionary lookup. We simply need a pairs of direction vectors; a tuple of tuples:
UP = (0, -2), (0, 1)
DOWN = (0, 2), (0, -1)
LEFT = (-2, 0), (1, 0)
RIGHT = (2, 0), (-1, 0)
...
direction = random.choice(directions)
(dc, dr), (hc, hr) = direction
if 0 < row + dr < height and 0 < col + dc < width and pixels[row + dr, col + dc] != 255:
row += dr
col += dc
dig(row, col)
dig(row + hr, col + hc)
directions = [UP, DOWN, LEFT, RIGHT]
visited += 1
paths.append([row, col, 0])
else:
directions.remove(direction)
Two steps forward
You really don't need the "half" vectors at all; they are a -0.5 scale version of the forward vector. Let's get rid of them.
UP = (0, -2)
DOWN = (0, 2)
LEFT = (-2, 0)
RIGHT = (2, 0)
...
direction = random.choice(directions)
dc, dr = direction
if 0 < row + dr < height and 0 < col + dc < width and pixels[row + dr, col + dc] != 255:
row += dr
col += dc
dig(row, col)
dig(row - dr // 2, col - d // 2)
directions = [UP, DOWN, LEFT, RIGHT]
visited += 1
paths.append([row, col, 0])
else:
directions.remove(direction)
Flotsam and Jetsam
You tried to track "dead ends" in your paths, but decided it was too expensive. However, you are still paying a cost for the attempt, by extracting a deadend variable that is never used from a paths entry, and constructing an array with a useless 0 at the end:
row, col, deadend = random.choice(paths)
...
paths.append([row, col, 0])
Remove the , deadend and the , 0.
Possible Algorithmic Improvement
As the maze fills up, your paths list will fill with many, many positions where it is impossible to move from. It is easy to imagine a case where due to an unfortunate turn in the random walk, one spot is left unvisited. Your code will execute row, col = random.choice(paths) to select a random point to start walking from, try walking in the 4 directions, and then repeat with a new random choice.
Consider the 600x600 maze, with a total of 360,000 positions. With one unvisited location, paths will contain 359,999 visited locations, but at most 4 of those will be beside the unvisited spot. The odds of selecting one of those 4 spots is low: 0.001%! On average, it will take about 45,000 iterations, with 1,800,000 walk direction attempts, to randomly select one of those 4 spots necessary to finish the generation. Unfortunately, it can take many, many more. It is not even guaranteed to every finish.
Before you execute random.choice(paths), you are sitting at a row, col which you are unable to move from. You randomly selected this location, you would know it is impossible to move from it. There is no point in keeping this location in paths to be selected. You could remove it, so it can never be selected again:
paths.remove([row, col])
row, col = random.choice(paths)
With this change, the paths list will grow as the maze is initially built, and then start to shrink as the maze approaches completion, ensuring the maze generation will complete.
Unfortunately, paths.remove([row, col]) is an \$O(n)\$ operation. It will search for the value from the start of the list, and once it finds it, it would have to move all values in the list after it forward by one position.
Removing items from a set is an \$O(1)\$ operation. Since you are not concerned with the order of elements in paths, turning it into a set of (row, col) tuples (because [row, col] lists are not hashable) may provide a speedup.
paths = set()
...
paths.add((row, col))
...
if len(directions) == 0:
in_deadend += 1
paths.discard((row, col))
row, col = random.choice(list(paths))
...
Because sets are not indexable, we need to convert it into a list to use random.choice(). Due to this back-and-forth, you'll need to profile to determine if this change is actually an improvement.
Backtracking
Profiling shows the set / tuple / paths.discard() change made things slower. Let's try actual backtracking. This will change the appearance of the generated maze, since the new segments will start further along the previous path.
Instead of the "Possible Algorithmic Improvement", make the following change.
Replace:
row, col = random.choice(paths)
with:
row, col = paths.pop()
My generation time for a 500x500 maze dropped in half, but note these are once again incomparable as the maze is being generated in a different fashion and produces a substantially different maze.
