وبلاگ تخصصي برنامه نويسي با VB

الگوريتم Collision Detection

نکته : اگر مباحث آشنايي با تابع BitBlt و آشنايي با تکنيک Masking را مطالعه نکرده ايد ، پيشنهاد مي کنم ابتدا آنها را مطالعه کنيد .

تکنيک collision detection ، تکنيک تشخيص برخورد دو sprite متحرک در صفحه مي باشد . اين تکنيک براي ساخت بازيهاي کامپيوتري بسيار استفاده مي شود و الگوريتمهاي زيادي براي تشخيص برخورد دو بعدي و سه بعدي وجود دارد . در اين بخش من شما را با چند تکنيک تشخيص برخورد دوبعدي آشنا خواهم کرد :
يکي از ساده ترين الگوريمتهاي تشخيص برخورد ، الگوريتم bounding box مي باشد . در اين الگوريتم مرزهاي دو sprite یا bounding rectangles چک مي شوند تا برخورد تشخيص داده شود .
يکي ديگر از الگوريتمهاي تشخيص برخورد ، الگوريتم bounding sphere است . در اين الگوريتم دايره هاي محيطي دو sprite با هم مقايسه مي شوند .
اما يکي از بهترين الگوريتم هاي تشخيص برخورد دو بعدي الگوريتمي است که ابتدا مستطيل محيطي دو sprite را با هم مقايسه مي کند و در صورت وجود تداخل دو مستطيل ، به سراغ چک کردن تداخل در سطح پيکسلهاي دو sprite مي رود . براي بررسي تداخل در سطح پيکسل از mask هاي دو sprite استفاده مي شود .
قبل از معرفي اين الگوريتم ابتدا چند تابع را که در اين الگوريتم استفاده مي شوند معرفي خواهم کرد :
1 – تابع CreateCompatibleDC موجود در کتابخانه gdi32 : اين تابع يک حافظه DC ( device context ) مطابق با مقصد مشخص شده مي سازد .
2 – تابع CreateCompatibleBitmap موجود در کتابخانه gdi32 : اين تابع يک bitmap مطابق با مقصدي که توسط DC مشخص شده ، مي سازد .
3 – تابع DeleteDC موجود در کتابخانه gdi32 : يک DC را از حافظه پاک مي کند .
4 – تابع GetPixel موجود در کتابخانه gdi32 : مقدار rgb رنگ يک پيکسل را برمي گرداند .
5 – تابع SelectObject موجود در کتابخانه gdi32 : يک شي را از درون يک DC انتخاب مي کند .
6 – تابع DeleteObject موجود در کتابخانه gdi32 : يک شي را حذف کرده و کليه منابع اختصاص يافته به آنرا آزاد مي کند .
7 – تابع IntersectRect موجود در کتابخانه user32 : تداخل دو مستطيل را محاسبه مي کند و مختصات مستطيل تداخلي را در يک مستطيل مقصد قرار مي دهد .

حال که با اين توابع آشنا شديد به سراغ معرفي الگوريتم مي روم . در اين الگوريتم ابتدا بايد يک type از نوع مستطيل تعرف کنيم :

Type RECT
Left As Long
Top As Long
Right As Long
Bottom As Long
End Type


همچنين نياز به تعريف متغيرهاي زير داريم :

Dim MaskRect1 As RECT
Dim MaskRect2 As RECT
Dim DestRect As RECT
Dim i As Long
Dim j As Long
Dim Collision As Boolean
Dim MR1SrcX As Long
Dim MR1SrcY As Long
Dim MR2SrcX As Long
Dim MR2SrcY As Long
Dim hNewBMP As Long
Dim hPrevBMP As Long
Dim tmpObj As Long
Dim hMemDC As Long


سپس بايد کليه توابع فوق را بهمراه تابع BitBlt در پروژه خود declare کنيد . با استفاده از API viewer مي توانيد فرمت اين توابع را پيدا کنيد .
شکل کلي تابع تشخيص برخورد بصورت زير است :

Public Function CollisionDetect(ByVal x1 As Long, ByVal y1 As Long, ByVal X1Width As Long, ByVal Y1Height As Long,ByVal Mask1LocX As Long, ByVal Mask1LocY As Long, ByVal Mask1Hdc As Long, ByVal x2 As Long, ByVal y2 As Long,ByVal X2Width As Long, ByVal Y2Height As Long, ByVal Mask2LocX As Long, ByVal Mask2LocY As Long,ByVal Mask2Hdc As Long) As Boolean


که x1 و y1 و x2 و y2 بترتيب مختصات نقطه بالايي سمت چپ sprite اول و دوم هستند .
x1width و y1height و x2width و y2height بترتيب ابعاد مستطيا محيطي دو sprite هستند .
Mask1Hdc و Mask2Hdc ، DC هاي ماسکهاي دو sprite هستند .


Mask1LocX و Mask1LocY مختصات افست ماسک اول و Mask2LocX و Mask2LocY مختصات افست ماسک دوم مي باشند .
ابتدا ابعاد مستطيلهاي محيطي دو sprite را تنظيم مي کنيم :

MaskRect1.Left = x1
MaskRect1.Top = y1
MaskRect1.Right = x1 + X1Width
MaskRect1.Bottom = y1 + Y1Height
MaskRect2.Left = x2
MaskRect2.Top = y2
MaskRect2.Right = x2 + X2Width
MaskRect2.Bottom = y2 + Y2Height


سپس توسط تابع IntersectRect تداخل مستطيلهاي محيطي بررسي مي شود و در صورت تداخل ، مستطيل تداخل استخراج مي شود :

i = IntersectRect(DestRect, MaskRect1, MaskRect2)x
If i = 0 Then
CollisionDetect = False


حال به سراغ بررسي پيکسل به پيکسل مي رويم . براي اينکار بايستي مقادير sourceX و sourceY را براي HDC هاي دو ماسک بدست آوريم :

Else
If x1 > x2 Then
MR1SrcX = 0
MR2SrcX = x1 - x2
Else
MR2SrcX = 0
MR1SrcX = x2 - x1
End If
If y1 > y2 Then
MR2SrcY = y1 - y2
MR1SrcY = 0
Else
MR2SrcY = 0 ' here
MR1SrcY = y2 - y1 - 1
End If


سپس حافظه هاي DC و Bitmap را براي انجام مقايسه تخصيص مي دهيم :

hMemDC = CreateCompatibleDC(Screen.ActiveForm.hdc)x
hNewBMP = CreateCompatibleBitmap(Screen.ActiveForm.hdc, DestRect.Right- DestRect.Left, DestRect.Bottom - DestRect.Top)x
hPrevBMP = SelectObject(hMemDC, hNewBMP)x


اولين sprite را در حافظه hMemDc قرار مي دهيم :

i = BitBlt(hMemDC, 0, 0, DestRect.Right - DestRect.Left,DestRect.Bottom- DestRect.Top,Mask1Hdc, MR1SrcX + Mask1LocX, MR1SrcY + Mask1LocY,vbSrcCopy) x


sprite دوم را با sprite اول OR مي کنيم :

i = BitBlt(hMemDC, 0, 0, DestRect.Right - DestRect.Left,DestRect.Bottom- DestRect.Top,Mask2Hdc, MR2SrcX + Mask2LocX, MR2SrcY + Mask2LocY, vbSrcPaint)x


حال تمام پيکسل هاي hMemDC را بررسي مي کنيم . اگر رنگ يکي از اين پيکسلها سياه باشد يعني تداخل وجود دارد :

Collision = False
For i = 0 To DestRect.Bottom - DestRect.Top - 1
For j = 0 To DestRect.Right - DestRect.Left - 1
If GetPixel(hMemDC, j, i) = 0 Then
Collision = True
Exit For
End If
Next
If Collision = True Then
Exit For
End If
Next
CollisionDetect = Collision


در پايان تمام object ها و DC ها را از بين مي بريم :

tmpObj = SelectObject(hMemDC, hPrevBMP)x
tmpObj = DeleteObject(tmpObj)x
tmpObj = DeleteDC(hMemDC)x


نکته : براي دريافت برنامه نمونه با من تماس بگيريد .


+ حامد شیدائیان ; ۱:٠٥ ‎ب.ظ ; شنبه ٦ مهر ،۱۳۸۱
comment نظرات ()