Help with moving sprite through playfield with obstacles

[+DZ-Jay]

I'm working on a routine that moves a sprite across a play-field filled with obstacles.  The sprite moves in 16 directions, using a table of pre-computed velocity vectors for each direction; and will move on an axis unless an obstacle (i.e., a background card which is not one of the "walkable path" set) is encountered.

 

The problem is that I believe my algorithm is very inefficient and would like some help in improving it, if possible.  Below I describe the algorithm.

 

I test the displacement on each axis independently, so that the sprite can continue moving on any axis which is not directly blocked.  This allows the sprite to slide across the edge of obstacles when its direction is not strictly perpendicular to it -- that is to say, when encountering the obstacle at an angle.  This is illustrated in the diagram below.

In the above illustration, the sprite is moving in a 45˚ angle to the right (direction #2 of 16).  We test the displacement on the X axis (right) and discover an obstacle there.  We also test the displacement on the Y axis (up) and notice that the path is open.  Consequently, the sprite slides across the edge of the obstacle upwards.

 

Below is some pseudo-code describing the tests.  Notice that we adjust the positions by 4 pixels on each axis, to check the card directly under the center of the sprite (origin + 4).

' (PosX, PosY) are the current position
' (TempPosX, TempPosY) are the target positions after displacement
TempPosX = PosX + VelX
TempPosY = PosY + VelY

' Test displacement in X:
'   Check if the card directly underneath the
'   new position is open or blocked.
If PathIsOpen(TempPosX + 4, PosY + 4) Then
    PosX = TempPosX
End If

' Test displacement in Y:
'   Check if the card directly underneath the
'   new position is open or blocked.
If PathIsOpen(PosX, TempPosY + 4) Then
    PosY = TempPosY
End If

 

 

This works rather well, but it makes the play-field feel a little blocky, since the sliding movement is constrained to right-angles.  So, I allocated a few cards in GRAM for special "corner" blocks.  The idea is that when the sprite is over one of these special cards, it can slide across a diagonal edge on the card.  There are four of these special cards, one for each of the four corners:

 0 .......#    #.......
 1 ......##    ##......
 2 .....###    ###.....
 3 ....####    ####....
 4 ...#####    #####...
 5 ..######    ######..
 6 .#######    #######.
 7 ########    ########
   01234567    01234567

 0 ######## 0  ########
 1 .####### 1  #######.
 2 ..###### 2  ######..
 3 ...##### 3  #####...
 4 ....#### 4  ####....
 5 .....### 5  ###.....
 6 ......## 6  ##......
 7 .......# 7  #.......
   01234567    01234567

 

Because the slope of the edges are purely diagonal, dissecting the cards down the middle, the maximum offset in one axis can be derived directly from the current offset in the other.

 

For example, consider the first case, the top-left corner:

    ; Threshold   ------,
    ; Axis Offset --,   |
    ;               |   |
    ; 0             Y   X <         X   Y <
    .......# 0      0   7           0   7
    ......## 1      1   6           1   6
    .....### 2      2   5           2   5
    ....#### 3      3   4           3   4
    ...##### 4      4   3           4   3
    ..###### 5      5   2           5   2
    .####### 6      6   1           6   1
    ######## 7      7   0           7   0

 

When moving in the X direction, we compare the vertical offset within the card to know how much the sprite is allowed to move in the current axis.  When the Y offset is 1, the maximum X offset is 6, and so on.  In this particular case, the maximum X offset is the complement of the current Y offset; i.e., MaxOffsetX = (8 - OffsetY).

 

Below is some pseudo code describing the algorithm.

    ' (PosX, PosY) are the current position
    ' (TempPosX, TempPosY) are the target positions after displacement
    TempPosX = PosX + VelX
    TempPosY = PosY + VelY

    OffsetX = TempPosX % 8
    OffsetY = TempPosY % 8

    ' The sprite can move in X up to an offset
    ' that is the complement of the Y offset.
    '
    ' In other words, when the Y offset is 1,
    ' the sprite can move up to offset 7.
    If (OffsetX <= (8 - OffsetY)) Then
      ' Sprite can move ...
      PosX = TempPosX
    Else
      ' Sprite is blocked, cap it to the threshold ...
      PosX = (8 - OffsetY)
    End If

 

The offsets and comparisons change depending on the axis and the card -- there are four cases for each of the two axis, so eight comparisons in total.

 

This all works rather well, as illustrated in the video below:

 

I'm quite happy with the way it works -- it's just that I'm afraid the code is horrendously inefficient. 😬

 

I admit that my algorithm is not the best.  It is probably quite naïve, and I'm sure there are better ways to do the same thing.  First off, I operate on each axis individually, which leads to the same sort of computations being done twice.

 

Below is the full algorithm, taken straight from my code and modified slightly to generalize the variables, remove any irrelevant parts, and make it easier to follow.

Spoiler

'' ======================================================================== ''
''  Input:
''      Sprite velocity and position are in Q8.8 fractional values.
''
''      #VelocityX      Velocity X component (Q8.8 fraction)
''      #VelocityY      Velocity Y component (Q8.8 fraction)
''      #PositionX      Current sprite position in X (Q8.8 fraction)
''      #PositionY      Current sprite position in Y (Q8.8 fraction)
''
''  Temp:
''      TempX           Temporary X position, (Q8 integer)
''      TempY           Temporary Y position, (Q8 integer)
''      TempCard        Index in GRAM of card directly under sprite
''      TempMaxOffset   Maximum offset within 8x8 background card
''
''      OffsetX         X Offset of sprite within current 8x8 background card
''      OffsetY         Y Offset of sprite within current 8x8 background card
''      #TempDist
''
'' ======================================================================== ''
MoveObjectInPath: Procedure
    ' ----------------------------------------------------------------
    ' Compute new X position
    ' ----------------------------------------------------------------
    If (#VelocityX <> 0) Then
        #TempPosX = (#VelocityX + #PositionX)
        TempX     = (#TempPosX / 256)

        ' Constrain the X position within the screen horizontal boundaries
        If (TempX <= PLAYFIELD_MIN_X) Then
            #PositionX = (PLAYFIELD_MIN_X * 256)
        ElseIf (TempX >= PLAYFIELD_MAX_X) Then
            #PositionX = (PLAYFIELD_MAX_X * 256)
        Else
            ' Constraint the X position to the open path.
            ' --------------------------------------------------------

            ' We'll use the current Y position to isolate changes in X.
            ' In other words, we are testing the card directly underneath
            ' the sprite after displacing it only in X direction.
            TempY    = (#PositionY / 256)
            TempCard = GetBackgroundCardIndex(TempX, TempY)

            ' Check if path is open ...
            If CheckPathIsOpen(TempCard) Then
                ' Path is open, so adjust the position
                #PositionX = #TempPosX

            ' Check if it is a sloped-path ...
            ElseIf CheckPathIsSloped(TempCard) Then
                ' Compute X and Y offsets within 8x8 background card.
                ' The offset is computed from the center of the sprite,
                ' which is 4 pixels from origin, e.g., (TempX + 4).
                OffsetX = ((TempX + 4) % 8)
                OffsetY = ((TempY + 4) % 8)

                ' Determine the X offset and compute the distance to
                ' maximum threshold.  The sign of the distance tells us
                ' whether it is before (positive) or beyond (negative)
                ' the threshold.
                On (TempCard And 3) Fast Goto \
                                    .SlopeX0, \
                                    .SlopeX1, \
                                    .SlopeX2, \
                                    .SlopeX3

                     ' Top-Left
                     '      .......# 0
                     '      ......## 1
                     '      .....### 2
                     '      ....#### 3
                     '      ...##### 4
                     '      ..###### 5
                     '      .####### 6
                     '      ######## 7  Threshold = (8 - #OffsetY)
                     '      01234567
                    .SlopeX0:
                        #TempDist     = ((8 - OffsetY) - OffsetX)
                        TempMaxOffset = #TempDist
                        Goto .EndCaseX

                    ' Bottom-Left
                    '       ######## 0
                    '       .####### 1
                    '       ..###### 2
                    '       ...##### 3
                    '       ....#### 4
                    '       .....### 5
                    '       ......## 6
                    '       .......# 7  Threshold = OffsetY
                    '       01234567
                    .SlopeX1:
                        #TempDist     = (OffsetY - OffsetX)
                        TempMaxOffset = #TempDist
                        Goto .EndCaseX

                    ' Top-Right
                    '       #....... 0
                    '       ##...... 1
                    '       ###..... 2
                    '       ####.... 3
                    '       #####... 4
                    '       ######.. 5
                    '       #######. 6
                    '       ######## 7  Threshold = OffsetY
                    '       01234567
                    .SlopeX2:
                        #TempDist     = (OffsetX - OffsetY)
                        TempMaxOffset = -(#TempDist)
                        Goto .EndCaseX

                    ' Bottom-Right
                    '       ######## 0
                    '       #######. 1
                    '       ######.. 2
                    '       #####... 3
                    '       ####.... 4
                    '       ###..... 5
                    '       ##...... 6
                    '       #....... 7  Threshold = (8 - OffsetY)
                    '       01234567
                    .SlopeX3:
                        #TempDist     = (OffsetX - (8 - OffsetY))
                        TempMaxOffset = -(#TempDist)
                        ' Goto .EndCaseX

                .EndCaseX:

                ' When the distance is negative, it means the sprite
                ' has gone beyond the sloped boundary; so we adjust
                ' the position accordingly.
                If (#TempDist < 0) Then
                    TempX = (TempX + TempMaxOffset)
                    #TempPosX   = (TempX * 256)
                End If

                ' Update the X position
                #PositionX = #TempPosX

            ' Otherwise, path is blocked ...
            Else
                ' The offset is computed from the center of the sprite
                ' which is 4 pixesl from its origin.
                OffsetX = ((TempX + 4) % 8)

                ' When the path is blocked, we need to adjust the
                ' position in the opposite direction to that in which
                ' the sprite is moving.
                '
                ' In other words, if the sprite is moving left when
                ' encountering an obstacle, we assume that the obstacle
                ' is on the left side, so we adjust the position to the
                ' right.
                
                ' The sign of the velocity indicates the direction in X
                ' (negative = left, positive = right).
                If (#VelocityX < 0) Then
                    TempX = (TempX + (8 - OffsetX))
                Else
                    TempX = (TempX - (OffsetX + 1))
                End If

                ' Update the X position
                #PositionX = (TempX * 256)

            End If

        End If
    End If

    ' ----------------------------------------------------------------
    ' Compute new Y position
    ' ----------------------------------------------------------------
    If (#VelocityY <> 0) Then
        #TempPosY = (#VelocityY + #PositionY)
        TempY     = (#TempPosY / 256)

        ' Constrain the Y position within the screen vertical boundaries
        If (TempY <= PLAYFIELD_MIN_Y) Then
            #PositionY = (PLAYFIELD_MIN_Y * 256)
        ElseIf (TempY >= PLAYFIELD_MAX_Y) Then
            #PositionY = (PLAYFIELD_MAX_Y * 256)
        Else
            ' Constraint the Y position to the open path
            ' --------------------------------------------------------

            ' We'll use the current X position to isolate changes in Y.
            ' In other words, we are testing the card directly underneath
            ' the sprite after displacing it only in Y direction.
            TempX   = (#PositionX / 256)
            TempCard = GetBackgroundCardIndex(TempX, TempY)

            ' Check if the path is blocked ...
            If CheckPathIsOpen(TempCard) Then
                #PositionY = #TempPosY

            ' Check if it is a sloped-path ...
            ElseIf CheckPathIsSloped(TempCard) Then
                ' Compute X and Y offsets within 8x8 background card
                ' The offset is computed from the center of the sprite,
                ' which is 4 pixels from origin, e.g., (TempY + 4).
                OffsetX = ((TempX + 4) % 8)
                OffsetY = ((TempY + 4) % 8)

                ' Determine the Y offset and compute the distance to
                ' maximum threshold.  The sign of the distance tells us
                ' whether it is before (positive) or beyond (negative)
                ' the threshold.
                On (TempCard And 3) Fast Goto \
                                    .SlopeY0, \
                                    .SlopeY1, \
                                    .SlopeY2, \
                                    .SlopeY3

                     ' Top-Left
                     '      .......# 0
                     '      ......## 1
                     '      .....### 2
                     '      ....#### 3
                     '      ...##### 4
                     '      ..###### 5
                     '      .####### 6
                     '      ######## 7  Threshold = (8 - OffsetY)
                     '      01234567
                    .SlopeY0:
                        #TempDist     = ((8 - OffsetX) - OffsetY)
                        TempMaxOffset = #TempDist
                        Goto .EndCaseY

                    ' Bottom-Left
                    '       ######## 0
                    '       .####### 1
                    '       ..###### 2
                    '       ...##### 3
                    '       ....#### 4
                    '       .....### 5
                    '       ......## 6
                    '       .......# 7  Threshold = OffsetX
                    '       01234567
                    .SlopeY1:
                        #TempDist     = (OffsetY - OffsetX)
                        TempMaxOffset = -(#TempDist)
                        Goto .EndCaseY

                    ' Top-Right
                    '       #....... 0
                    '       ##...... 1
                    '       ###..... 2
                    '       ####.... 3
                    '       #####... 4
                    '       ######.. 5
                    '       #######. 6
                    '       ######## 7  Threshold = OffsetX
                    '       01234567
                    .SlopeY2:
                        #TempDist     = (OffsetX - OffsetY)
                        TempMaxOffset = #TempDist
                        Goto .EndCaseY

                    ' Bottom-Right
                    '       ######## 0
                    '       #######. 1
                    '       ######.. 2
                    '       #####... 3
                    '       ####.... 4
                    '       ###..... 5
                    '       ##...... 6
                    '       #....... 7  Threshold = (8 - OffsetX)
                    '       01234567
                    .SlopeY3:
                        #TempDist     = (OffsetY - (8 - OffsetX))
                        TempMaxOffset = -(#TempDist)
                        ' Goto .EndCaseY

                .EndCaseY:

                ' When the distance is negative, it means the sprite
                ' has gone beyond the sloped boundary; so we adjust
                ' the position accordingly.
                If (#TempDist < 0) Then
                    TempY = (TempY + TempMaxOffset)
                    #TempPosY   = (TempY * 256)
                End If

                ' Updated the Y position
                #PositionY = #TempPosY

            ' Otherwise, path is blocked ...
            Else
                ' The offset is computed from the center of the sprite
                ' which is 4 pixesl from its origin.
                OffsetY = (TempY % 8)

                ' When the path is blocked, we need to adjust the
                ' position in the opposite direction to that in which
                ' the sprite is moving.
                '
                ' In other words, if the sprite is moving downwards when
                ' encountering an obstacle, we assume that the obstacle
                ' is below, so we adjust the position upwards.

                ' The sign of the velocity indicates the direction in Y
                ' (negative = up, positive = down).
                If (#VelocityY < 0) Then
                    TempY = (TempY + (8 - OffsetY))
                Else
                    TempY = (TempY - (OffsetY + 1))
                End If

                ' Updated the Y position
                #PositionY = (TempY * 256)
            End If

        End If
    End If

    Return
End

 

As you can see, each axis is processed separately, and includes three main checks:

• Is the sprite new position outside bounds?  Adjust position accordingly to keep it within bounds.
• Is the sprite new position on an open path card?  Accept new position
• Is the sprite new position on a sloped path card?  Adjust the position depending on which card it is, and its offset within it.
• Is the sprite new position on a blocked card?  Adjust the position depending on whether the velocity is positive or negative.

 

I would imagine that this is a solved problem and that there are easier and simpler ways to attack it.  I'm sure to all you veterans out there, the above is shockingly, incredibly, and stupidly more complicated than it needs to be.  But that's as best as my little brain can figure out. 

 

Any help will be greatly appreciated!

 

     -dZ.

[Kiwi]

With my Towering Inferno game. This was my first time using top down 16 directional movement. So my solution was to restore the previous player position if they collide with the wall(impassable object), which doesn't allow them to slide against the wall, thus making it sticky. 

[+DZ-Jay]

1 hour ago, Kiwi said:

With my Towering Inferno game. This was my first time using top down 16 directional movement. So my solution was to restore the previous player position if they collide with the wall(impassable object), which doesn't allow them to slide against the wall, thus making it sticky. 

Thanks.  I quite like the sliding -- it's a feature I built by design, not a side-effect.  That's the reason I test each axis independently, so that I can isolate displacement on on axis and adjust it if blocked, or allow it if not.

 

    dZ.

[+DZ-Jay]

By the way, the "On (TempIdx And 3) Fast Goto ..." structure above is my IntyBASIC hacky way of implementing a switch statement.

 

If @nanochess is paying attention, I wished IntyBASIC had a switch statement.

 

It could follow the Visual Basic "Select Case" statement, but work as a dispatch table like in my example above.  I do not mind using this pattern at all, but it feels silly to have to include the Goto table and the "Goto <end label>," and having to come up with unique custom labels for each case that do not collide with any others in the same scope. *sigh*

 

So, this:

On (TempIdx And 3) Fast Goto \
                    .SlopeX0, \
                    .SlopeX1, \
                    .SlopeX2, \
                    .SlopeX3

    .SlopeX0:
        #TempDist  = ((MOB_AXIS_LENGTH - #DeltaY) - #DeltaX)
        TempOffset = #TempDist
        Goto .EndCaseX

    .SlopeX1:
        #TempDist  = (#DeltaY - #DeltaX)
        TempOffset = #TempDist
        Goto .EndCaseX

    .SlopeX2:
        #TempDist  = (#DeltaX - #DeltaY)
        TempOffset = -(#TempDist)
        Goto .EndCaseX

    .SlopeX3:
        #TempDist  = (#DeltaX - (MOB_AXIS_LENGTH - #DeltaY))
        TempOffset = -(#TempDist)
        ' Goto .EndCaseX

.EndCaseX:

 

Could be done similar to something like this:

Select Case (TempIdx And 3)
    Case 0
        #TempDist  = ((MOB_AXIS_LENGTH - #DeltaY) - #DeltaX)
        TempOffset = #TempDist

    Case 1
        #TempDist  = (#DeltaY - #DeltaX)
        TempOffset = #TempDist

    Case 2
        #TempDist  = (#DeltaX - #DeltaY)
        TempOffset = -(#TempDist)

    Case 3
        #TempDist  = (#DeltaX - (MOB_AXIS_LENGTH - #DeltaY))
        TempOffset = -(#TempDist)

End Select

 

And the compiler would create the labels, the jump table, and the breakout GOTOs, automatically.

 

     -dZ.

[+nanochess]

I don't see your code as inefficient.

 

In fact my programmer mind sees it as the minimum code possible, as each direction must be computed independently otherwise you cannot get the slide feature.

 

[+DZ-Jay]

11 minutes ago, nanochess said:

I don't see your code as inefficient.

 

In fact my programmer mind sees it as the minimum code possible, as each direction must be computed independently otherwise you cannot get the slide feature.

 

 

Hi, @nanochess, thanks for responding.  I appreciate you taking the time to look at the code.  I sort of thought that doing each axis separately was the only way to get the slide feature, but I wasn't really sure.  (Actually, I tried adjusting the position on both axes at once, and re-arranging the tests, but I couldn't get it to work correctly, so I thought I could be doing it wrong.)

 

Still, you or anybody can provide some feedback on how to improve it, it would be greatly appreciated.  Maybe the computations or the tests conditions could be improved?

 

    -dZ.

[+nanochess]

I gave another look and I don't see nothing blatantly unoptimized. So I figure you are good.

 

[+DZ-Jay]

Thank you, @nanochess.  I appreciate the help.

 

For anybody interested, feel free to use the algorithm above for any purpose if you find it useful.  Let me know if you have any questions or need help adapting it to your own program.

 

     -dZ.