Contacts
صفحه اصلی پورتال | صفحه اصلی تالار | ثبت نام | اعضاء | گروه ها | جستجو | پرسش و پاسخ | فروشگاه الکترونیکی | خرید پستی بازی های کامپیوتری





صفحه اول انجمنها -> اصول اولیه در طراحی بازیهای کامپیوتری -> مقاله : تشخیص برخورد دو بعدی(قسمت سوم)
 

ارسال يك موضوع جديد   پاسخ به يك موضوع ديدن موضوع قبلي :: ديدن موضوع بعدي
برو به صفحه 1, 2  بعدي

نظر خود را در مورد مفید بودن این مقاله بیان کنید
چیز جدیدی یاد نگرفتم
0%
 0%  [ 0 ]
بد نبود
50%
 50%  [ 1 ]
خیلی به دردم خورد
50%
 50%  [ 1 ]
مجموع آراء : 2

مقاله : تشخیص برخورد دو بعدی(قسمت
نويسنده
پيغام
eta
مدیر سایت
مدیر سایت


تاريخ عضويت: 2 شنبه 27 تير 1384
تعداد ارسالها: 2153
محل سكونت: شاهين شهر


شنبه 12 خرداد 1386 - 19:41
پاسخ بصورت نقل قول
اگر مقاله اول و دوم تشخيص برخورد دو بعدي رو مطالعه نکرديد، پيشنهاد مي کنم اول به مطالعه اونها بپردازيد.


توي مقالات اول و دوم تشخيص برخورد دو بعدي به مسائلي همچون انواع الگوريتمهاي تشخيص برخورد دو بعدي، مزايا و معايب هر کدوم و در نهايت روشي براي ترکيب الگوريتمهاي مختلف در راستاي بهره وري بيشتر پرداختيم. در اين مقاله قصد دارم تا روش ديگري از ترکيب الگوريتمها رو که توي پروژه شخصي خودم هم امتحانش کردم براتون توضيح بدم.
توي مقاله دوم ما معيار مقايسه الگوريتمها براي جايگرفتن در زنجيره الگوريتمها رو دقت و هزينه در نظر گرفتيم يعني الگوريتمي که در اولين مرحله استفاده مي شد از کمترين هزينه و اجبارا از کمترين دقت نيز برخوردار بود. الگوريتمهاي بعدي هر کدوم هزينه بيشتري داشتند ولي در مقابل از دقت بالاتري هم در تشخيص برخوردار بودند.
اما توي اين مقاله به اين نکته اشاره خواهم کرد که الگوريتمهاي مختلف از جوانب ديگري هم با هم قابل مقايسه هستند.

در مقاله دوم به روش جدول مراقبت(lookup table) اشاره کرديم و خصوصياتش رو تا حدودي براي شما تشريح کرديم.
روش جدول مراقبت در يک نگاه نزديک يک روش بسيار انعطاف پذيره. چرا که شما مي تونيد نسبت خانه هاي جدول به نقشه بازي رو به هر ميزان دلخواه در نظر بگيريد. شما اگر در يک بازي دو بعدي نسبت تعداد خانه هاي جدولتون رو به سايز نقشه يک به يک در نظر بگيريد. ميتونيد تشخیص برخورد رو با بالاترين دقت مورد نيازتون انجام بديد و از طرف ديگه اگه هر چه اين نسبت کوچکتر بشه شما هزينه کمتري براي استفاده از جدول مراقبت خواهيد پرداخت.
يکي از مناسبترين روشها براي پياده سازي روش جدول مراقبت استفاده از يک عکسه. چرا که امکانات کار کردن با یک عکس جزو ابتدایی ترین امکاناتیه که شما به عنوان بازی ساز بهش نیاز دارید.(متاسفانه در بسیاری از موتور ها این امکان به دلیل سطح پایین بودن از کاربران گرفته میشه. چرا که اونا ترجیح میدن که محیطشون رو با اینگونه امکانات شلوغ نکنند. و اصولا لازم نمی دونند که کاربر با امکانات سطح پایینی مثل این سر و کله بزنه!! که البته میبینید که با این کار خلاقیتش رو هم تا سطح زیادی از او می گیرند.)
بگذریم. شما ميتونيد وضع اشغال بودن يا نبودن يک نقطه از محيط بازي رو در يک عکس سياه و سفيد اعمال کنيد و بعد هر زمان که به اون عکس مراجعه کنيد خيلي سريع ميتونيد از پر يا خالي بودنش مطلع بشيد.(در واقع با دسترسي order يک يا قابل شمارش) علاوه بر اين شما در اين راستا مي تونيد از فرمتهاي مخصوص عکسهاي سياه و سفيد استفاده کنيد که در اونها براي هر پيکسل تنها يک بيت کافي خواهد بود.
خوب بذارید یه ذره دقیقتر به روش جدول مراقبت نگاه کنیم.
همونطور که قبلا گفتیم در روش جدول مراقبت دستیابی به اطلاعات یک پیکسل با زمان دستیابی یک قابل انجامه و از طرف دیگر بر خلاف اکثر روشهای دیگه نیازی به جستجو بین کلیه آبجکتها برای بررسی امکان تداخل هم نداره. ما فقط یک جدول داریم و آبجکتمون رو تو اون جدول چک می کنیم. اما حرکت کردن یک آبجکت موجب تغییر وضعیت جدول میشه بنابراین ما مجبور خواهیم شد تا برای هر حرکت اطلاعات محل قبلی آبجکت در جدول رو پاک کنیم و اطلاعات محل جدید رو وارد کنیم که هزینه واقعا بالایی رو به همراه داره.
همونطور که در مقالات قبلی دیدید ما تونستیم با نوعی ترکیب الگوریتمها که تشکیل زنجیره ای از الگوریتمها بود، مزایای چند الگوریتم رو کنار همدیگه جمع کنیم و به یک روش واقعا کارا برسیم. به نظر شما اینجا چه طوری میتونیم از اینهمه نکات مثبتی که روش جدول مراقبت داره استفاده کنیم و زیر بار هزینه بالای اون هم نریم؟؟؟؟؟
ممکنه اول این گفته عجیب به نظر برسه. چرا که پرداخت هزینه بالا لازمه استفاده از روش جدول مراقبته!! اما اگه مقاله قبلی رو به دقت خونده باشید، اونجا این حقیقت رو مشاهده کردید که ما در جاهایی که می دیدیم کار از دست یک الگوریتم ساده و سریع برمیاد از اون استفاده کردیم و دیگه به خودمون زحمت استفاده از یک الگوریتم پیچیده رو ندادیم. در واقع یه جور تقسیم وظایف یا تنظیم قوا انجام دادیم.
خوب اینجا هم می تونیم کار مشابه رو انجام بدیم. به یاد بیارید که ما تو چند خط بالاتر گفتیم که هزینه روش جدول مراقبت به دلیل نیاز به به روز رسانی پس از حرکت هر آبجکته. خوب اگه آبجکتهامون حرکت نکنند چی؟!!! بهتر بگم اگه آبجکتهایی که برای تشخیص برخورد با اونا از جدول مراقبت استفاده میکنیم ثابت باشند چی؟!! بذارید باز هم واضح تر بگم.
راه حل اینه :
ما تو بازی برحسب دسته بندی مبنی بر حرکت، دو نوع آبجکت داریم. یکی آبجکت ثابته و دیگری آبجکت متحرک اگه ما برای آبجکتهای ثابتمون از روش جدول مراقبت استفاده کنیم هیچ هزینه ای برای به روز رسانی جدول نخواهیم پرداخت. ممکنه بپرسید با بقیه آبجکتهمون چی کار کنیم. جواب اینه : خوب دنیا رو که الگوریتم قحطی نگرفته! می تونید از همون زنجیره ای که تو مقاله قبل گفتیم استفاده کنید.
در حقیقت اون تقسیم بندی ای که تو مقاله قبلی کردیم یه تقسیم بندی طولی بود. یعنی هر وقت الگوریتمی نتونست تشخیص قطعی بده، از قوی ترش استفاده کردیم. و در این جا یه تقسیم بندی عرضی انجام میدیم. یعنی از همون ابتدا می تونیم الگوریتم مناسب رو تشخیص بدیم و تشخیص برخورد رو بهش بسپاریم.

اینم یه شبه کد برای این کار :
كد:

boolean detectCollision(Object o1) {
   if(o1.checkMaskInPicture(staticObjectsImage) == COLLISION)
      return true;
   for(int i=0 ; i<dynamicObjects.length ; i++)
      if(o1.checkBoundingRectCollision(dynamicObjects[i]) == COLLISION)
         return true;
      else if(o1.checkPixelByPixelCollision(dynamicObjects[i]) == COLLISION)
         return true;
   return false;
}


با این روش هزینه تشخیص برخورد از «تعداد آبجکتهای متحرک + تعداد آبجکتهای ثابت» به «تعداد آبجکتهای متحرک + 1» کاهش پیدا میکنه.

منابع :
تجربیات شخصی

نوع استفاده از منابع :
استفاده عملی در پروژه شخصی

سطح مقاله : متوسط

نویسنده : احسان طاهری
پست الکترونیک : eh_taheri@yahoo.com

*** کلیه حقوق مطالب این پست برای نویستده و سایت طراحان ایرانی محفوظ است و استفاده از آن با ذکر منبع بلا مانع است.***

_________________
تالار اصول ->صفحه ها، مقالات و تاپیکهای مفید



اين نامه توسط eta در 1 شنبه 13 خرداد 1386 - 09:04 ويرايش شده است.
ارسال  بازگشت به بالا
ديدن مشخصات كاربر ارسال پيغام خصوصي ارسال ايميل
 

نويسنده
پيغام
iran_adventure
مدیر انجمن
مدیر انجمن


تاريخ عضويت: شنبه 4 آذر 1385
تعداد ارسالها: 2069
محل سكونت: تهران


شنبه 12 خرداد 1386 - 20:50
پاسخ بصورت نقل قول
جالب بود احسان جان مخصوصا جدا كردن آبجكت هاي ثابت و متحرك . در مورد انجين ها هم قبول دارم خوب بود كه اين گزينه ها رو در اختيار كاربر قرار مي دادند ولي يه سوال آيا انجين ها از همين روش استفاده مي كنند ؟ متاسفانه تعداد انجين هاي 2 بعدي خيلي كمه ولي از معروف ها مي شه GM رو نام برد كه در موردش اطلاعاتي ندارم . در مورد TGB هم اطلاعاتي ندارم !! ولي مي دونم كه براي تشخيص برخورد فقط از پليگان هايي استفاده مي كنه كه زواياي داخلي اون بايد كمتر از 180 درجه باشه كه همين نشون مي ده كه از روش PixelByPixel استفاده نمي كنه چون اگه استفاده مي كرد كانوس يا كانوكس بودن پليگان مهم نبود . اگه يادت باشه اين مطلب رو در مقاله هاي قبلي هم گفتم كه فكر كنم گفتي اين روش از نوع ديگه ايه ...

_________________
Make something happen
ارسال  بازگشت به بالا
ديدن مشخصات كاربر ارسال پيغام خصوصي ارسال ايميل نام كاربري در پيغامگير Yahoo
 

نويسنده
پيغام
مصطفي سپهريان
پیر بازی سازی
پیر بازی سازی


تاريخ عضويت: جمعه 24 آذر 1385
تعداد ارسالها: 1147
محل سكونت: تو يه فلش مموري دو گيگ


شنبه 12 خرداد 1386 - 23:24
پاسخ بصورت نقل قول
نقل قول:

جالب بود احسان جان مخصوصا جدا كردن آبجكت هاي ثابت و متحرك .

كاملا موافقم... نسبت به قبلي ها خيلي پيشرفته تر بود Laughing
موفق باشي

_________________
«پشتکار»«پشتکار»«پشتکار»
ارسال  بازگشت به بالا
ديدن مشخصات كاربر ارسال پيغام خصوصي ارسال ايميل ديدن وب سايت كاربر نام كاربري در پيغامگير Yahoo
 

نويسنده
پيغام
eta
مدیر سایت
مدیر سایت


تاريخ عضويت: 2 شنبه 27 تير 1384
تعداد ارسالها: 2153
محل سكونت: شاهين شهر


1 شنبه 13 خرداد 1386 - 09:04
پاسخ بصورت نقل قول
ممنونم از دو تا دوست قدیمی تالار اصول!!!!

برای مجتبی و مصطفی :
خوب اصل مطلب هم همین جدا کردن تشخیص خطا برای بالا رفتن سرعت بود.

برای مجتبی :
خوب نمی دونم که موتورهای این کار رو می کنند یا نه ولی به احتمال 90 درصد میشه از یه چیز این رو متوجه شد. اگه موتور از شما بپرسه که آبجکتت متحرک یا ثابته به احتمال زیاد برای همین می خواد Idea

_________________
تالار اصول ->صفحه ها، مقالات و تاپیکهای مفید

ارسال  بازگشت به بالا
ديدن مشخصات كاربر ارسال پيغام خصوصي ارسال ايميل
 

نويسنده
پيغام
iran_adventure
مدیر انجمن
مدیر انجمن


تاريخ عضويت: شنبه 4 آذر 1385
تعداد ارسالها: 2069
محل سكونت: تهران


1 شنبه 13 خرداد 1386 - 12:02
پاسخ بصورت نقل قول
نقل قول:

اگه موتور از شما بپرسه که آبجکتت متحرک یا ثابته به احتمال زیاد برای همین می خواد


آره . ولي من كه نديدم Wink البته شايد از روش هاي قبلي استفاده كنه ولي اين يه تيكه رو حذف كرده باشه . ولي در كل جدا از روش ها فكر مي كنم ترتيب استفاده كه گفتي از كم هزينه ترين به پر هزينه ترين استفاده بشه مگر در 2 حالت كه يكيش اينه كه موتور اوپتيمايز نباشه ! يكيش هم اينه كه از الگوريتم برخوردي استفاده كنه كه هزينه اش براي دوري و نزديكي اشيا فرق نمي كنه . حالا نمي دونم همچين الگريتمي وجود داره يا نه ولي اگه باشه انجين از همون يه الگريتم بهينه استفاده مي كنه ...

_________________
Make something happen
ارسال  بازگشت به بالا
ديدن مشخصات كاربر ارسال پيغام خصوصي ارسال ايميل نام كاربري در پيغامگير Yahoo
 

نويسنده
پيغام
eta
مدیر سایت
مدیر سایت


تاريخ عضويت: 2 شنبه 27 تير 1384
تعداد ارسالها: 2153
محل سكونت: شاهين شهر


1 شنبه 13 خرداد 1386 - 14:39
پاسخ بصورت نقل قول
هزینه الگوریتمهایی که من میشناسم به دوری و نزدیکی وابسته نیستند. اما زنجیره ای که تو مقاله دوم تشکیل دادیم این قابلیت رو داره که به مقدار لازم هزینه کنه!!

نمی دونم که نرم افزار ها این کارها رو می کنند یانه اما تصور میکنم که این امر از نرم افزارها بعیده.

بگذریم این روش جدول مراقبت روش بسیار خفنیه من که باهاش خیلی حال میکنم.
از مزیتهای دیگرش اینه که میشه از run length encoding (اگه اشتباه نکنم) توش استفاده کرد. نمی دونم تا حالا عکسهای با فرمت rle رو دیدی یا نه.
اینا رو می خواستم تو یه مقاله جدا بگم اما پیش خودم گفتم زیاد کش دار نشه بهتره.

خوب بذار اول فرمت bmp رو براتون بگم bmp یه آرایه ساده است. به صورتی که اطلاعات مربوط به پیکسلهای عکس رو به سطر به سطر از بالا و اگه اشتباه نکرده باشم از طرف چپ توی فایل میریزه و والسلام.

یه عکس دورنگ بیتمپ رو در نظر بگیر. تشکیل شده از تکرار های بسیار بلند( همون run ها) چند بیت شکل هم.

مثل :

سیاه سفید سفید سفید سفید سفید سیاه
سیاه سیاه سفید سفید سفید سیاه سیاه
سیاه سیاه سیاه سفید سیاه سیاه سیاه

ما می تونیم این تصاویر رو به فرم زیر زخیره کنیم :

سیاه 1 سفید 6 سیاه 9 سفید 12 سیاه 17 سفید 18 سیاه 21

یعنی تا خانه 1 سیاه کن. از یک تا 6 سفید. 6 تا 9 سیاه و ...(البته تو این مثال طول بزرگترین run ها مون 7 و 8 بود، که در واقعیت این طولها به چند هزار هم میرسه.)

و به این ترتیب به مقدار زیادی در حافظه مورد نیاز برای ذخیره این عکس صرفه جویی کنیم. و به راحتی با یه باینری سرچ به اطلاعات مورد نظرمون دسترسی داشته باشیم.
از این گذشته تصور میکنم سخت افزارهای گرافیکی هم از تصاویر به این فرمت پشتیبانی میکنند. یعنی شما مجبور نخواهید بود این کارها رو به cpu محول کنید.

اینم یکی دیگه از مزیتهای جدول مراقبت و یکی دیگه از جذابیتهای دنیای اصوله که موتورها کاربرانشون رو از اون محروم می کنند.

یکی دیگه هم هست که به زودی می گمش.

_________________
تالار اصول ->صفحه ها، مقالات و تاپیکهای مفید

ارسال  بازگشت به بالا
ديدن مشخصات كاربر ارسال پيغام خصوصي ارسال ايميل
 

نويسنده
پيغام
iran_adventure
مدیر انجمن
مدیر انجمن


تاريخ عضويت: شنبه 4 آذر 1385
تعداد ارسالها: 2069
محل سكونت: تهران


1 شنبه 13 خرداد 1386 - 16:03
پاسخ بصورت نقل قول
در مورد عكس دورنگي منظورت رو گرفته بودم . ولي اين قضيه شمردن پيكسل هاي سفيد و سياه جالب بود ...
حالا ببين اين كه من مي گم عمليه يا نه ؟
يه دايره فرضي دور هر آبجكت بكشيم هر وقت اين دايره ها با هم برخورد كرد ( يعني فاصل شون از يه حدي كمتر شد ) جدول مراقبت تشكيل بشه و محدوده كوچكي بشه تا سرعتش بيشتر بشه . مثلا از مركز دو تا دايره . اين طوري يه مستطيل تشكيل مي شه كه نقطه برخورد حتما توي اون مستطيله ...

_________________
Make something happen
ارسال  بازگشت به بالا
ديدن مشخصات كاربر ارسال پيغام خصوصي ارسال ايميل نام كاربري در پيغامگير Yahoo
 

نويسنده
پيغام
eta
مدیر سایت
مدیر سایت


تاريخ عضويت: 2 شنبه 27 تير 1384
تعداد ارسالها: 2153
محل سكونت: شاهين شهر


1 شنبه 13 خرداد 1386 - 16:58
پاسخ بصورت نقل قول
خوب مجتبی
1. برای دایره فرضی که نیاز به یه سرچ روی کل آبجکتها داریم. بعدش هم جدول مراقبت از روشهایی مثل چک کردن پیکسل به پیکسل استفاده میکنه.

2. مقاله دوم رو هم که خوندی!!

نتیجه : این روشی که گفتی همون روش مقاله دومه.

_________________
تالار اصول ->صفحه ها، مقالات و تاپیکهای مفید

ارسال  بازگشت به بالا
ديدن مشخصات كاربر ارسال پيغام خصوصي ارسال ايميل
 

نويسنده
پيغام
iran_adventure
مدیر انجمن
مدیر انجمن


تاريخ عضويت: شنبه 4 آذر 1385
تعداد ارسالها: 2069
محل سكونت: تهران


1 شنبه 13 خرداد 1386 - 17:28
پاسخ بصورت نقل قول
E راست مي گي ! فكر كنم حقيقتش اين باشه كه من اون موقع خوب حاليم نشده بود . الان دوباره خوندم موضوع تازه اومد دستم ...
راستي در مورد دوري و نزديكي كه تو پست قبليت گفتي فرق نمي كنه ... : خوب آبجكت هايي كه از هم دورند احتمال برخورد كمتره ديگه .

_________________
Make something happen
ارسال  بازگشت به بالا
ديدن مشخصات كاربر ارسال پيغام خصوصي ارسال ايميل نام كاربري در پيغامگير Yahoo
 

نويسنده
پيغام
eta
مدیر سایت
مدیر سایت


تاريخ عضويت: 2 شنبه 27 تير 1384
تعداد ارسالها: 2153
محل سكونت: شاهين شهر


1 شنبه 13 خرداد 1386 - 17:52
پاسخ بصورت نقل قول
دوری و نزدیکی تو کجا رو میگی. نفهمیدم؟؟

_________________
تالار اصول ->صفحه ها، مقالات و تاپیکهای مفید

ارسال  بازگشت به بالا
ديدن مشخصات كاربر ارسال پيغام خصوصي ارسال ايميل
 

نمايش نامه هاي ارسال شده قبلي:   
ارسال يك موضوع جديد   پاسخ به يك موضوع    صفحه 1 از 2 تمام ساعات و تاريخها بر حسب 3.5+ ساعت گرينويچ مي باشد
برو به صفحه 1, 2  بعدي


 
پرش به:  


شما نمي توانيد در اين انجمن نامه ارسال كنيد.
شما نمي توانيد به موضوعات اين انجمن پاسخ دهيد
شما نمي توانيد نامه هاي ارسالي خود را در اين انجمن ويرايش كنيد
شما نمي توانيد نامه هاي ارسالي خود را در اين انجمن حذف كنيد
شما نمي توانيد در نظر سنجي هاي اين انجمن شركت كنيد


unity3d

بازگردانی به فارسی : علی کسایی @ توسعه مجازی کادوس 2004-2011
Powered by phpBB © 2001, 2011 phpBB Group
| Home | عضويت | ليست اعضا | گروه هاي كاربران | جستجو | راهنماي اين انجمن | Log In |