I'm trying to implement "sliding" movement on a simple grid, where the movement vector is continuous (floating point direction) but the grid is discrete (boolean blocked or open on integer axes).
The "destination" tile is found by adding the rounded movement vector to the current tile. That part is naive and works well enough.
For example, here:
- blue is the current (source) tile
- the yellow arrow is the movement vector
- green is the destination tile
But this movement ends up being restrictive and I'd like to enable "sliding" to approximate player intent. My goal is that if the destination tile is blocked, the "next best" tile is used instead, provided it is available. I don't know how to calculate that.
As you can see, the naive destination tile (where the yellow arrow lands) is blocked. As a result, I'd like to pick the green tile above as the destination tile.
However, crossing a diagonal should be allowed either, so the following case should result in the movement being blocked:
Finally, I'd like this algorithm to be as permissive as possible, so even the smallest component of the movement vector could win if no better alternative is found. For example, the movement should carry upwards in that case:
This sounds like a fairly simple problem and there may be existing algorithms for it, but I don't know what it's called, so I'm having trouble finding resources on it.