Path finding in 2D grid for objects that can rotate and bigger than one tile (Tetris)

I'm trying to check if there is a path between two locations in a Tetris board. On this question it tells how to account for different shapes: Path finding in grid for objects that occupy more than one tile

But having a shape that can rotate needs a different technique. How should I approach this?

• Looks like we're trying to do the same thing, I just asked it more formally ;)
– Sven
Jul 16, 2015 at 3:37
• @Sven I think I know where there is a sudden interest in our part for writing AI to Blocks :) Good luck and thanks for the link. Jul 16, 2015 at 8:44

Use a standard A-star algorithm, modified to consider all possible orientations as you remove each node from the Openset. There are two possible implementation choices here:

1. Test for suitability of each <neighbour,orientation> tuple before pushing it to the priority queue; or

2. Test for suitability of each <neighbour,orientation> tuple after popping it from the priority queue.

You would need to test both to see if one gives significantly better performance than the other for your particular circumstances.

If there is a cost to rotating remember to account for this as you queue <neighbour,orientation> tuples. As this merely increases the cost of entering a state, your heuristic function does not need to account for it - any existing heuristic will retain its admissibility and consistency under this transformation of the algorithm.

In order to only rotate objects when necessary you may wish to consider a tie-breaker to your cost function - essentially a small cost to rotating even when there is none in reality. One way to do this is to multiply (or bit-shift) your costs by a small integer, then add one for each rotation step in any direction. I have used this in my Hexgrid path-finding implementations to select between equal cost paths to obtain the one that is most visually appealing.

• Alright, thanks I'll try to do what you described. And also no, rotations do not have a cost. I actually thought of this method but I thought this method wouldn't be able to realize if a turn is needed beforehand hitting a wall, because some moves are sometimes illegal when you are next to a wall. I guess I need to give this a proper testing to understand. Jul 16, 2015 at 2:37
• @redneksi: Eric Lippert provides an excellent 4-part introduction to A-star, using C# of course but applicable to any c-type language. Check the bottom of this blog archive: blogs.msdn.com/b/ericlippert/archive/2007/10.aspx Jul 16, 2015 at 2:40
• This is basically what I was getting at with my answer, but this is more clearly explained and deals with some details youll hit further down the road. Jul 16, 2015 at 3:06

I'm curious to hear if there's a more elegant solution, but I feel like brute force may be the best.

Basically try to go down all the paths recursively, under each possible rotation orientation - assuming you only have a few rotation angles.

Something like, if you reach a spot you can't continue to path through, but there is a gap, try rotating to fit through. If you can't and the stack unwinds so to speak, unwind until you are at a place where the piece can be rotated. Rotate the piece and continue to recurse out.

Continue until you get to the destination or until you've tried all available paths at all rotation angles.

If your map is static (doesn't move, or doesn't move often), you could probably do some of this brute force as a preprocessing step so that you'd already have knowledge of how a piece had to be rotated to go down a specific path (or which rotations are valid maybe as a bit mask). That would make it more efficient at runtime.

• That makes sense, thanks. But sometimes the piece should rotate before it reaches the gap to be able to fit through the gap. So I can't do "move down every direction until you can't, rotate if you can't than try to move again" because if I rotated 1 step earlier I could actually fit, but now I can't rotate because I'm touching a wall. Jul 15, 2015 at 23:49
• Or what I should do is "Go everywhere possible with current rotation and store them. On everyone of them, rotate if you can, and go everywhere possible again. Repeat this for 2 more rotations or until you reach the desired location". And than I can trace the route it takes perhaps. But I feel like possible numbers could easily find millions, is this a viable way to solve this problem? Jul 16, 2015 at 0:03
• Yeah there's definitely some details to think through but I think basically you need to test every path for every rotation possible, at leat for the rotations that are possible to reach at that point in the path. As far as this problem exploding into a giant search space, how many distinct rotations can an object have. Is it like Tetris where there are just 4? If so, I don't see that exploding combinatorially. If you have analog rotation capabilities (any floating point angle) then yeah, this solution as described could get pretty hairy if you can't find a way to deal with angle ranges. Jul 16, 2015 at 3:04