[RESOLVED] Detecting a Collision "in advance"

Hey,

The attached picture shows a game I'm working on. The Player is the white dot in the centre, and the map, including the brown houses, move around the Player according to where you click.

I have a "HitTest" function that stops the Player when he collides with a wall; it first detects whether the Player is inside or outside the house, and makes calculatations accordingly, allowing for the Player to travel through the grey doors.

My problem is, as you can see in the screenshot, while the Player does stop when he hits a wall, it's a little later than I'd like, resulting in the Player appearing to be half-in and half-out of the house (the Player's co-ordinates are taken to be the centre of the white dot).

I tried to get around this by detecting collision with an invisible "border" around the house - the problem then is that the player can't get OUT of the house, as when he exits through the door, the game stops him because he's still inside the border (I have since removed the border).

Here's the code - if anyone can find a solution to my problem, I'd be very grateful. If you see a way to improve on the code's efficiency also (shouldn't be too hard), please let me know :)

Declarations

Code:

---

Public Type PlayerObj
    ZoneX As Long
    ZoneY As Long
    X As Single
    Y As Single
    XPos As Single
    YPos As Single
    House As Integer
    Width As Long
    Height As Long
    Picture As StdPicture
    Speed As Long
    MoveTime As Long
    MoveSpeedX As Single
    MoveSpeedY As Single
End Type

Public Player As PlayerObj

Public Type HouseObj
    XPos As Single
    YPos As Single
    X As Long
    Y As Long
    Width As Long
    Height As Long
    Colour As String
    'Door (distance from top corner)
        DX As Single
        DY As Single
        DWidth As Long
        DHeight As Long
        DColour As String
End Type

Public Type ZoneObj
    Houses As Long
    House() As HouseObj
End Type

Public Zone() As ZoneObj

---

HitTest Function

Code:

---

Public Function HitTest() As Integer

Dim i As Integer
Dim PX As Single, PY As Single, X2 As Single, Y2 As Single, _
    DX1 As Single, DX2 As Single, DY1 As Single, DY2 As Single

With Player
    PX = .X + .MoveSpeedX
    PY = .Y + .MoveSpeedY
End With

'Returns a value depending on which side of the Player has collided
'    __1__
'    |    |
'  4| [i] |2
'    |_____|
'      3

'Check if the Player hits a house
    For i = 1 To Zone(Player.ZoneX, Player.ZoneY).Houses
        With Zone(Player.ZoneX, Player.ZoneY).House(i)

            X2 = .X + .Width
            Y2 = .Y + .Height
            DY1 = .Y + .DY
            DY2 = .Y + .DY + .DHeight
            DX1 = .X + .DX
            DX2 = .X + .DX + .DWidth
           
            'Is the player outside?
            If Player.House = 0 Then
           
                'Is he entering a house...
                If PX >= .X And PX <= X2 Then
                    If PY >= .Y And PY <= Y2 Then
           
                        '... from the left?
                        If Player.MoveSpeedX > 0 Then
                            If PX >= .X Then
                                'Is he using the door?
                                If PY >= DY1 And PY <= DY2 And DX1 = .X Then
                                    Player.House = i 'Set house
                                    Exit Function
                                Else
                                    HitTest = 2
                                End If
                            End If
                        End If
                       
                        '... from the right?
                        If Player.MoveSpeedX < 0 Then
                            If PX <= X2 Then
                                'Is he using the door?
                                If PY >= DY1 And PY <= DY2 And DX1 = X2 Then
                                    Player.House = i 'Set house
                                    Exit Function
                                Else
                                    HitTest = 4
                                End If
                            End If
                        End If
                       
                        '... from the top?
                        If Player.MoveSpeedY > 0 Then
                            If PY >= .Y Then
                                'Is he using the door?
                                If (PX >= DX1) And (PX <= DX2) Then
                                    If DY1 = .Y Then
                                        Player.House = i 'Set house
                                        Exit Function
                                    End If
                                Else
                                    HitTest = 1
                                End If
                            End If
                        End If
                       
                        '... from the bottom?
                        If Player.MoveSpeedY < 0 Then
                            If PY <= Y2 Then
                                'Is he using the door?
                                If PX >= DX1 And PX <= DX2 And DY1 = Y2 Then
                                    Player.House = i 'Set house
                                    Exit Function
                                Else
                                    HitTest = 3
                                End If
                            End If
                        End If
                       
                    End If
                End If
               
            'Or is he in a house, exiting...
            ElseIf Player.House = i Then
           
                '... from the left?
                If Player.MoveSpeedX > 0 Then
                    If PX >= X2 Then
                        'Is he using the door?
                        If PY >= DY1 And PY <= DY2 And DX1 = X2 Then
                            Player.House = 0 'Set outside
                            Exit Function
                        Else
                            HitTest = 2
                            Player.X = X2
                            Halt
                        End If
                    End If
                   
                '... from the right?
                Else
                    If PX <= .X Then
                        'Is he using the door?
                        If PY >= DY1 And PY <= DY2 And DX1 = .X Then
                            Player.House = 0 'Set outside
                            Exit Function
                        Else
                            HitTest = 4
                            Player.X = .X
                            Halt
                        End If
                    End If
                End If
               
                '... from the top?
                If Player.MoveSpeedY > 0 Then
                    If PY >= Y2 Then
                        'Is he using the door?
                        If PX >= DX1 And PX <= DX2 And DY1 = Y2 Then
                            Player.House = 0 'Set outside
                            Exit Function
                        Else
                            HitTest = 3
                            Player.Y = Y2
                            Halt
                        End If
                    End If
               
                '... from the bottom?
                Else
                    If PY <= .Y Then
                        'Is he using the door?
                        If PX >= DX1 And PX <= DX2 And DY1 = .Y Then
                            Player.House = 0 'Set outside
                            Exit Function
                        Else
                            HitTest = 1
                            Player.Y = .Y
                            Halt
                        End If
                    End If
                End If
            End If
                   
        End With
    Next i

End Function

---

Code that moves the Player

Code:

---

Private Sub MapUpdate_Timer()

Dim Hit As Integer

'Updates the map every frame
Game.Cls

    'Draw Houses
    UpdateMap

    'Draw Player
    With Player
   
        If (.MoveTime > 0) Then
       
            'Move Player
            Hit = HitTest
            If Hit = 0 Then
                .X = .X + .MoveSpeedX
                .Y = .Y + .MoveSpeedY
                .MoveTime = .MoveTime - 1
            End If
           
                'Move zones
                If (.X >= 500) Then
                    .X = 500 - .X
                    .ZoneX = .ZoneX + 1
                ElseIf (.X <= 0) Then
                    .X = 500 + .X
                    .ZoneX = .ZoneX - 1
                End If
                If (.Y >= 500) Then
                    .Y = 500 - .Y
                    .ZoneY = .ZoneY + 1
                ElseIf (.Y <= 0) Then
                    .Y = 500 + .Y
                    .ZoneY = .ZoneY - 1
                End If
               
        Else 'Stop
            .MoveSpeedX = 0
            .MoveSpeedY = 0
        End If
       
        'Draw Player
        Call DrawPlayer(Player, .XPos, .YPos, .Width, .Height)
       
    End With

Game.Refresh

End Sub

---

Moved from the Visual Basic 6 and Earlier forum.

What you ultimately want is what's called a Quaternion. It's a math construction that makes dealing with rotation, heading and collision prediction easy. There's plenty of examples of using quaternions for 2D rotation and collision detection on the net. Google around and ye shall find.

One of the reasons they're used in rotation is they don't suffer from gimbal lock which is a major plus.

Could you upload your project? It's too much code to find the problem just by looking at it.

Quote:

---

Originally Posted by Jenner

What you ultimately want is what's called a Quaternion.
One of the reasons they're used in rotation is they don't suffer from gimbal lock which is a major plus.

---

You don't need quaternions for 2D, there's no such thing as gimbal lock there.

For the OP, I think your program's going to get really complicated really fast. I'd want do define walls in a more general way, like with a separate data structure containing all the line segments or something. Then there's just no wall where the door is, and players can't get too close to any wall.

Quote:

---

Originally Posted by Kallog

For the OP, I think your program's going to get really complicated really fast. I'd want do define walls in a more general way, like with a separate data structure containing all the line segments or something. Then there's just no wall where the door is, and players can't get too close to any wall.

---

I know what you mean, and that would be ideal, but I'm not sure I'd know where to start, exactly... I'm not even sure I know what a data structure is. But I have a feeling it's exactly what I want.

If someone's willing to help me, I'd be prepared to revamp my wall collision code. However, I don't think the project as a whole is going to get too complicated, as it's all contained in one function, so as soon as I've got that sorted, I don't have to worry about the walls any more.

EDIT: In fact, I've already come up with a small workaround by detecting which side of the player has collided and moving him backwards slightly.

Quote:

---

Originally Posted by jcis

Could you upload your project? It's too much code to find the problem just by looking at it.

---

For anyone who wants to take a look, I'll upload it.

Excuse the terrible name, it's only temporary - also I'm currently in the process of revamping the Combat menu, so you can ignore all that (it'll probably crash anyway).

If anyone knows how I can improve any part of it, don't hesitate to let me know, as I'm sure you're all much more knowledgeable than me :)

Just off the top of my head.

Have an array full of line segments, like x1,y1,x2,y2 for each piece of wall. That's what I mean by data structure, haha, real simple type of data structure :P

Whenever the player tries to move, check his initial and final position against every line segment to see if he's changed from one side of it to the other. If so, don't let him move.


If all your walls are going to stay horizontal and vertical the line-crossing test would be really easy. Perhaps split it into two arrays and two tests - one for horizontal walls (y,x1,x2), and one for vertical walls (x,y1,y2).

Ah, that doesn't sound too bad.

Could I do that without changing my "House" code though? (i.e. make the "line" arrays from the following data):

Code:

---

        With Zone(0, 0).House(1)
                .X = 150: .Width = 50
                .Y = 350: .Height = 40
                .DX = 20: .DWidth = 15
                .DY = 0: .DHeight = 0
                .Colour = &H46188: .DColour = &HC0C0C0
        End With

---

.DX and .DY are the X and Y distances from the top-left corner of the house to the top-left of the door.

I like your game, i wouldn't worry too much about optimizations now, this is how you did it, the most important thing is to make it work. Now, about your problem, i've got to the point where i can see the player movement is ok when going left and up, it's not going trought the walls, the problem appears when the player goes right or down, and if you see, X speed is postive when going right, Y speed is positive when going down, these 2 cases with positive speeds is where the problem should be solved, do you have any idea why this could be happening when speed is positive? I think this is the key to make it work.

Thanks! I think what you described is because the player's co-ordinates are taken to be at the top-left corner of the player.

I've now revised the HitTest function by splitting it into 2 (X and Y) and by taking into account every side of the player, rather than treating him as a single point. I also took your advice, Kallog, and detected the exact moment where the player actually crosses the line, rather than detecting whether or not he's actually inside the house, and then moving him back out.

I'll upload the new project - works like a charm :)