0
\$\begingroup\$

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

enter image description here

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.

enter image description here

However, crossing a diagonal should be allowed either, so the following case should result in the movement being blocked:

enter image description here

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:

enter image description here

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.

\$\endgroup\$
1
\$\begingroup\$
  1. Check if the cell in the direction of the largest component (in absolute value) is free.

    • If so, move there. Done.
  2. Check if the cell in the direction of the smallest component (in absolute value) is free.

    • If so, check if the diagonal cell that's the sum of the two previous offsets checked is also free.

      • If so, move there. Done.
    • If not, move to the tile in step 2. Done.

  3. If we get here, we're blocked on both sides and cannot honour movement in this direction.

You'll likely want to set a minimum threshold on the check in step 2. If the smallest component is very close to zero, you might want to stop rather than slide, to avoid it feeling too slippery.

\$\endgroup\$
  • \$\begingroup\$ Thanks! Your algorithm worked for this case. In the end, I realized I needed to cover more cases so I used a different approach. I first have a method to determine whether one cell can move to a neighboring one without crossing a "wall", then the algorithm checks this for a list of possible destinations, in decreasing order of priority. \$\endgroup\$ – Lazlo Nov 12 '20 at 3:38
  • 1
    \$\begingroup\$ @Lazlo I bet other users would appreciate seeing that algorithm written up as an answer. \$\endgroup\$ – DMGregory Nov 12 '20 at 4:33
0
\$\begingroup\$

I realized I needed to cover more cases than my question initially asked for, so this is the approach I used instead of the accepted answer (which did cover the initial cases).

  1. Create a check function to tell whether a cell can move to a neighbouring cell

    a) If the cell is a direct neighbour in a cross on either the X or Y axis, return whether that cell is open

    b) If the cell is in a diagonal, also check that the neighbouring cell of either of its components is open

  2. Test the following cases, in order of priority. As soon as one move is allowed, take it and abort.

    1. Move in the exact direction
    2. Move in direction of the largest component
    3. Move in direction of the smallest component
    4. Move in direction of the largest component with the reverse of the smallest component
    5. Move in direction of the smallest component with the reverse the largest component
    6. Move in direction of the reverse of the smallest component
    7. Move in direction of the reverse of the largest component
    8. Move in the reverse direction
  3. If no case allowed a movement, fail to move

Steps 2.4 to 2.8 are optional -- it depends how permissive you want the algorithm to be. I personally only kept 2.4 and 2.5, in the end.

My specific implementation looks like this:

        private bool CanMove(Vector2 p, Vector2 q)
        {
            //var distance = Vector2.Distance(p, q);
            //
            //if (distance > 1.01)
            //{
            //  throw new ArgumentException($"Points must be up to 1 unit apart ({distance})");
            //}

            var pi = GetPixel(p);
            var qi = GetPixel(q);

            // If the destination isn't open, then we can't move to it.
            if (!IsOpen(qi))
            {
                return false;
            }

            var delta = qi - pi;

            // If we're moving in a cross (no diagonal),
            // then we only need to check if the destination
            // is open, no need for further checks.
            if (delta.x == 0 || delta.y == 0)
            {
                return true;
            }

            // If we're moving in diagonal, we also need to check if
            // either side path leading to it is open.
            var dx = pi + new Vector2Int(delta.x, 0);
            var dy = pi + new Vector2Int(0, delta.y);

            return IsOpen(dx) || IsOpen(dy);
        }

        private bool TryMove2(Vector2 source, Vector2 target, ref float remainingDistance, out Vector2 destination, out bool succeeded)
        {
            var difference = target - source;
            var distance = difference.magnitude;

            if (distance == 0)
            {
                //Debug.Log("No movement");
                destination = source;
                succeeded = true;
                return false;
            }
            
            var direction = difference.normalized;

            var continueOnSuccess = remainingDistance > 1;

            if (distance > 1)
            {
                distance = 1;
            }
            else if (distance > remainingDistance)
            {
                distance = remainingDistance;
            }

            // Try possibilities in this order:
            // 1. Move in exact direction
            // 2. Move in direction of largest component
            // 3. Move in direction of smallest component
            // 4. Move in direction of largest component with reverse smallest component
            // 5. Move in direction of smallest component with reverse largest component
            // 6. Move in direction of reverse smallest component
            // 7. Move in direction of reverse largest component
            // 8. Move in reverse direction

            var xComponent = new Vector2(Mathf.Sign(direction.x), 0);
            var yComponent = new Vector2(0, Mathf.Sign(direction.y));

            Vector2 largestComponentDirection;
            Vector2 smallestComponentDirection;
            Vector2 largestReverseSmallestDirection;
            Vector2 smallestReverseLargestDirection;
            Vector2 reverseSmallestDirection;
            Vector2 reverseLargestDirection;

            if (Mathf.Abs(direction.x) > Mathf.Abs(direction.y))
            {
                largestComponentDirection = xComponent;
                smallestComponentDirection = yComponent;
                largestReverseSmallestDirection = xComponent - yComponent;
                smallestReverseLargestDirection = yComponent - xComponent;
                reverseSmallestDirection = -yComponent;
                reverseLargestDirection = -xComponent;
            }
            else
            {
                largestComponentDirection = yComponent;
                smallestComponentDirection = xComponent;
                largestReverseSmallestDirection = yComponent - xComponent;
                smallestReverseLargestDirection = xComponent - yComponent;
                reverseSmallestDirection = -xComponent;
                reverseLargestDirection = -yComponent;
            }
            
            var exactAttempt = source + direction * distance;
            var largestComponentAttempt = source + largestComponentDirection * distance;
            var smallestComponentAttempt = source + smallestComponentDirection * distance;
            var largestReverseSmallestAttempt = source + largestReverseSmallestDirection * distance;
            var smallestReverseLargestAttempt = source + smallestReverseLargestDirection * distance;
            var reverseSmallestAttempt = source + reverseSmallestDirection * distance;
            var reverseLargestAttempt = source + reverseLargestDirection * distance;
            var reverseAttempt = source - direction * distance;

            if (CanMove(source, exactAttempt))
            {
                destination = exactAttempt;
            }
            else if (CanMove(source, largestComponentAttempt))
            {
                destination = largestComponentAttempt;
            }
            else if (CanMove(source, smallestComponentAttempt))
            {
                destination = smallestComponentAttempt;
            }
            else if (CanMove(source, largestReverseSmallestAttempt))
            {
                destination = largestReverseSmallestAttempt;
            }
            else if (CanMove(source, smallestReverseLargestAttempt))
            {
                destination = smallestReverseLargestAttempt;
            }
            //else if (CanMove(source, reverseSmallestAttempt))
            //{
            //  destination = reverseSmallestAttempt;
            //}
            //else if (CanMove(source, reverseLargestAttempt))
            //{
            //  destination = reverseLargestAttempt;
            //}
            //else if (CanMove(source, reverseAttempt))
            //{
            //  destination = reverseAttempt;
            //}
            else
            {
                succeeded = false;
                remainingDistance = 0;
                destination = source;
                return false;
            }

            succeeded = true;
            remainingDistance -= distance;
            return continueOnSuccess;
        }
```
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.