how to improve my 2D collision detection system? [modified]

O G I

Hi everyone, I started writing programs on VB .NET in the year of 2006, reading Jim Buyens book "Faster Smarter Beginning Programming" and that's only skill I got in programming, so I could say that I'm new in writing programs. My dream was to make my own game, I searched the net to find a simple collision detect system, but all I found was "detecting collisions between 2 or three, or maximum 10 objects" which is pretty simple because there is very small count of objects and we know exactly how much they are. There was nothing like "collision detect between various number of objects", so I've made myself one using the following logic: I've created a string array which size is equal to the count of the pixels that the playground is made of - if my playground is 9000 x 9000 then the array is something like this: strWorldArr(81000000) - each element in the array represents a single pixel of the playground and all objects that move on the playground fill their name in the elements of the array using their coordinates to locate the elements of the array which represents the pixels beneath them. Here is the code of the main part of my collision detect system:

REM: checking the pixels before moving the object if the values of the array elements which they present are clean then its good to go:
Function CleanChecker(ByVal panHero As HeroBody, ByVal szeSize As Size, _
ByVal intStartPos As Integer, ByVal intEndPos As Integer, _
ByVal intCycle As Integer)
Dim intCount As Integer = 0
For i = 0 To intCycle
For e = intStartPos To intEndPos
If strWorldArr(e) <> panHero.Name And strWorldArr(e) <> "†" Then
intCount += 1
End If
Next
intStartPos += szeSize.Width
intEndPos += szeSize.Width
Next
Return intCount
End Function

REM: this subroutine cleans behind the object, or fills it's new positions:
Sub CleanOrFill(ByVal panHero As HeroBody, ByVal strChar As String, \_
                ByVal szeSize As Size, ByVal intStartPos As Integer, \_
                ByVal intEndPos As Integer, ByVal intCycle As Integer)
    For i = 0 To intCycle
        For e = intStartPos To intEndPos
            strWorldArr(e) = strChar
        Next
        intStartPos += szeSize.Width
        intEndPos += szeSize.Width
    Next
End Sub

REM: this subroutine is one of 4 which call the CleanCh

Dave Kreskowiak

Member 3734843 wrote:

I think that this code is pretty simple, why it takes so much power to run?

Well, since String's under the .NET CLR are immutable (cannot change them), every time you make a change to a string you're creating a new 81 MEGABYTE string! :wtf: Each old string is dropped, by not before the new one is created. Multiply that by the number of times you're making a change to the string and you've quite possibly created the worst collision detection algorithm ever.

Member 3734843 wrote:

Is this slow calculation have anything to do with the programming language - Visual Basic 2008 - .NET Framework 3.5?

Nope. I can assure you, the performance problem is entirely in the design of your algorithm.

Member 3734843 wrote:

Is there anyway to improve the collision detect performance of this system or this project is doomed?

Until you completely rewrite the detection algo to use the processor more efficiently, you're project is doomed. Using an array of integers should improve performance dramatically. Completely scraping the array and comparing the bounds of object to object would be far better since you don't have to compare against 81000000 pixels every time you more something by 1 pixel. It comes down to representing your objects more effificently and in a manner that lends itself to better collision detection. Really, pickup a book or two on game programming. I really can't explain how to do something better in a forum post.

A guide to posting questions on CodeProject[^]
Dave Kreskowiak Microsoft MVP Visual Developer - Visual Basic
2006, 2007, 2008

riced

I think Dave K has hit the nail on the head. :) You need to do something different to what you are doing. This link might get you started: www.gamedev.net/reference/articles/article754.asp[^]

Regards David R

Luc Pattyn

Wouldn't it be a lot more efficient to actually test each pair of objects for a possible overlap (based on their shapes and coordinates), rather than dealing with 81 million pixels? You can further optimize by: - sorting the objects to some criterium, say the leftmost x-coordinate - have a rectangular outline for initial tests; and only when those overlap do a more elaborate test taking actual shape into account. - not testing pairs of non-moving objects. It may take a slightly more complex piece of code, but it will be worth it. :)

Luc Pattyn [Forum Guidelines] [My Articles]

- before you ask a question here, search CodeProject, then Google - the quality and detail of your question reflects on the effectiveness of the help you are likely to get - use the code block button (PRE tags) to preserve formatting when showing multi-line code snippets

O G I

Thank you for the advices, the moving objects I use are actually windows forms, and I'm not comparing all those 81000000 elements with each other - the logic is different but very long to explain in the forum. Now I've just turned off the collision detect system and for my big surprisse I've noticed that nothing is changed - again If I put more than 100 objects(windows forms) to move arund my desktop - the performance is the same as if the collision detect statements are turned on. I suspect that using windows forms as units in the playground field is a bad idea, I think that windows ust can't redraw smoothly the new positions of that much forms. You can try this by yourself to see I move 100 System.Windows.Forms.Form objects around my desktop using the following code: Public Class frmMain Private Sub frmMain_KeyDown(ByVal sender As Object, ByVal e As System.Windows.Forms.KeyEventArgs) Handles Me.KeyDown Select Case e.KeyCode Case Keys.W For Each frmHero As System.Windows.Forms.Form In Me.OwnedForms frmHero.Left += 5 frmHero.Top += 5 Next Case Keys.C Dim frmHer As New System.Windows.Forms.Form frmHer.Show(Me) frmHer.FormBorderStyle = Windows.Forms.FormBorderStyle.None frmHer.BackColor = Color.Red frmHer.Size = New Size(5, 5) Me.Focus() Me.Text = Me.OwnedForms.Count End Select End Sub If you try this code on any machine You'll see that you can move smoothly about 100 objects(windows forms) or little more depending on the PC. Is it possible that the bad performance of my collision detect system is hidden somewhere in this characteristic of Windows OS(I use windows Vista Ultimate SP1 and Windows XP professional SP2)? I thought to try C++ with DirectX, but I still don't have money to buy these products. I heard that DirectX is optimized for game programming.

Dave Kreskowiak

O.G.I. wrote:

the moving objects I use are actually windows forms

Yikes! I think that's the heaviest control you could have used. Truthfully, I wouldn't have used anything in the ToolBox, but instead went with either drawing everything myself, or gone with the XNA framework.

O.G.I. wrote:

I suspect that using windows forms as units in the playground field is a bad idea

Yep - it is!

O.G.I. wrote:

You can try this by yourself

I don't have to. I KNOW it's a really bad idea. Since you just created a small form, removing the borders and titlebar, along with just about everything else, you've essentially made a very heavy-weight Panel control.

O.G.I. wrote:

I thought to try C++ with DirectX, but I still don't have money to buy these products. I heard that DirectX is optimized for game programming.

You don't need C++ and DirectX. And, BTW, the DirectX SDK is free and you can pickup the Visual C++ Express Edition for free, here[^]. If I were you, with little experience, I'd start with the XNA Game Studio[^]. It uses C#, but is not that hard to learn if you know VB.NET already.

A guide to posting questions on CodeProject[^]
Dave Kreskowiak Microsoft MVP Visual Developer - Visual Basic
2006, 2007, 2008