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





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

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

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

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


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


شنبه 25 فروردين 1386 - 21:56
پاسخ بصورت نقل قول
اگر بازیهایی را که محاسبات 3 بعدی دارند ولی گرافیک آنها دو بعدی است(برخی این بازیها را 2.5 بعدی می نامند.)، کنار بگذاریم و صرفا به بازیهای دو بعدی تک سطحی بنگریم، الگوریتمهای تشخیص برخورد محدودی برایشان یافت می شود. اگر چه ممکن است برخی از این الگوریتم ها قیافه های مختتلفی نیز داشته باشند، اما

گاها این الگوریتم های مختلف الشکل از اصول یکسانی استفاده می نمایند.
همانطور که در مقالات قبلی نیز تا حدودی به این موضوع اشاره شده بود، الگوریتمهای مختلف دقت مختلفی دارند و علاوه براین، این الگوریتمها نیز از قائده "دقت بیشتر در برابر هزینه بالاتر" تبعیت می نمایند. یعنی هر چه الگوریتم شما دقیقتر عمل کند. برای ایجاد این دقت بالا زمان بیشتری را نیز صرف می نمابد.
اگر چه همواره و در همه بازیها دقت بالا مورد نیاز نیست، اما در اکثر مواقع این نیاز وجود دارد و از طرف دیگر نمی توان هزینه بالای برخی از الگوریتمها را نیز نادیده گرفت. در چنین شرایطی اولین راهی که به ذهن شما می رسد این خواهد بود که سعی کنید به نحوی تعادل را بین این دو واقعیت رعایت کنید. یعنی تا جایی که

مقدور باشد و سخت افزار به شما اجازه بدهد از الگوریتمهای کاراتر استفاده کنید.

گویا سخت افزار به شما میگوید هر چه قدر که پول بدهی آش میخوری Mad !!! و گرسنگی شما نیز به حدی است که مجبور می شوید تمام پول خود را به او بدهید، تا خود را بیشتر سیر کنید.!!!!! Crying or Very sad ای کاش می شد به نحوی سر سخت افزار شیره بمالیم. ای کاش می شد ... . یعنی ممکن است؟؟؟؟

از قضیه آش بگذریم. بیایید چند تا از الگوریتمهای موجود را مطالعه کنیم. شاید راهی مناسب برای مشکلمان بیابیم.

یکی از ابتدایی ترین و ساده ترین راههای تست برخورد این است که تمام اشیا را به صورت یک دایره فرض کنیم. بنابراین تنها کاری که برای تشخیص برخورد دو شی در چنین شرایطی باید بکنیم این است که فاصله مرکز دو شی را از یکدیگر بسنجیم.

می دانید که مشخصات دایره با نقطه ای به عنوان مرکز و فاصله ای به عنوان شعاع تعیین می گردد. دو دایره به مرکزهای (x1,y1) , (x2,y2) و به شعاعهای r1 و r2 را فرض کنید قطعه کد نمادین زیر قابلیت تشخیص برخورد یا عدم برخورد آنها را دارد.
كد:

if( square(x1-x2) + square(y1-y2) > square(r1) + square(r2)) then
// there is no collision.
else
//collison happened.


این راه اگر چه خیلی ساده به نظر می رسد اما برای بازیهایی که در آنها اشیا به صورت دایره ای هستند(مثلا همگی توپ هستند.) یا اینکه شمایل آنها بسیار به یک دایره نزدیک است یک راه بسیار دقیق و کارا می باشد. به این تکنیک بعضا دایره محصور کننده یا bounding circle می گویند.
به شکل توجه کنید.



نقاط قرمز رنگ از مرکز اشیا به یک فاصله اند و مرز آنها را نسبتا خوب مشخص می کنند.
اما پر واضح است که استفاده از چنین روشی در بازیهایی که اشیا آنها اشکال نامنظم دارند و به دقت مناسبی نیز نیازمند هستند، یک حماقت بزرگ است.



نوع دیگر از الگوریتمهای تشخیص برخورد از تکنیکی مشابه همین تکنیک استفاده می نماید. گاهی به این تکنیک، تکنیک مستطیل محصور کننده یا bounding rect نیز می گویند. همانطور که از اسم این تکنیک بر می آید در این روش ما اشیا را به صورت مستطیل فرض میکنیم.



در این تصویر یک حشره و مستطیل محصور کننده آن را می بینید.

مختصات یک مستطیل با یک نقطه(x,y) و دو عدد به عنوان طول(w) و عرض(h) قابل شناسایی است.

دو مستطیل با مشخصات (x1,y1) ، (x2,y2) و طول و عرضهای w1,w1,h1,h2 را در نظر بگیرید.
قطعه کد نمادین زیر قابلیت تشخیص برخورد بین چنین دو مربعی را دارد:
كد:

if(  x2 > x1+w1 OR x2+h2 < x1 OR y2 > y1+h1 OR y2+h2<y1) then
// there is no collision.
else
//collision happened.

به تصاویر زیر نگاه کنید.



در این تصویر برخورد وجود دارد و مستطیلها نیز این قضیه را تایید می کنند.



در این تصویر در واقع برخوردی وجود ندارد. اما مستطیل ها با هم تداخل دارند.

همانطور که می بینید این تکنیک برای این حشره، جواب دقیقی نخواهد داد.

روش دیگری از روشهای کم هزینه و غیر دقیق وجود دارد که به look up table معروف است. در این روش برای تشخیص اینکه در یک نقطه از بازی( مثلا نقطه ای به بزرگی یک مربع 10*10 !!!!!) تداخل وجود دارد، از یک جدول استفاده می شود. این جدول می تواند از یک آرایه دو بعدی که هر عنصر آن یک متغیر بولی(متغیر بولی یا متغیر منطقی متغیری است که تنها دو عدد یا حالت را می پذیرد مثل 0 یا 1 ، درست یا غلط. می توان این دو حالت را برای منظورهای مختلفی به کار برد. در اینجا آنها را به عنوان پر یا خالی بودن یک خانه جدول به کار برده ایم.) است، تشکیل شده باشد. هر زمان که بخواهیم بفهمیم که آیا یک شی با اشیاء دیگر تداخل دارد، تنها کافیست ببینیم این شی در کدام خانه جدول قرار دارد سپس اگر مقدار آن خانه جدول «پر» بود یعنی تداخل رخ داده و در غیر این صورت هیچ تداخلی وجود ندارد.(نکته مهم در اینجا این است که برای به روز نگه داشتن جدول لازم است پس از خروج هر شی از یک خانه جدول آن خانه را به عنوان خالی اعلام کنیم.(به شرطی که شی دیگری در آن خانه نباشد.) و پس از ورود یک شی به یک خانه جدول آن را به عنوان یک خانه پر در جدول ثبت کنیم.)
مزیتی که این روش نسبت به دو روش قبل دارد، این است که در این روش نیاز به هیچ گونه جستجو یا پیمایشی وجود ندارد. در حالی که اگر به نحوه عمل روشهای پیشین توجه کرده باشید، آنها در هر مرحله تنها دو شی را برای تست برخورد چک می کنند. اما ممکن است در یک بازی بیش از دو شی وجود داشته باشد. چیزی که در آنجا ضروری به نظر می رسد این است که برای اطمینان ازعدم برخورد یک شی با سایر اشیاء باید تست برخورد آن شی با تمام اشیاء بازی را انجام داد.
اما در مقابل این مزیت روش look up table (جدول مراقبت) ایراداتی نیز دارد. از آن جمله می توان به فضای اضافی لازم برای جدول و هزینه زمانی به روز نگاه داشتن جدول اشاره کرد.

این روش برای بازیهای ساده که در آنها حرکت اشیاء، گسسته و به میزان معین است، بسیار مناسب خواهد بود. اگر چه این به این معنا نیست که این روش برای سایر بازی ها بلا استفاده است.

توجه داشته باشید که روش جدول مراقبت به طرق بسیاری قابلیت گسترش و بهبود و همچنین مطابقت با محیطهای متفاوت را دارا می باشد. که مطالعه آنها به شما توصیه می گردد.

این تکنیکها، نمونه هایی از تکنیکهایی بودند که هر کدام به نوعی سادگی و کم هزینگی را انتخاب کرده اند.

منتظر قسمت دوم باشید.

منابع :

http://forums.indiegamer.com/archive/index.php/t-307.html
http://www.gamedev.net/reference/articles/article735.asp

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

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

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

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

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



0 بار اين نامه ويرايش شده است كه آخرين بار توسط 5 شنبه 30 فروردين 1386 - 13:20 در 3 بوده است.
ارسال  بازگشت به بالا
ديدن مشخصات كاربر ارسال پيغام خصوصي ارسال ايميل
 

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


تاريخ عضويت: 5 شنبه 30 شهريور 1385
تعداد ارسالها: 1347
محل سكونت: ايران-->سرزمين سركوب!


شنبه 25 فروردين 1386 - 22:05
پاسخ بصورت نقل قول
دستت درد نكنه استفاده كردم !
با آرزوي موفقيت براي شما! Laughing

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

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


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


شنبه 25 فروردين 1386 - 22:45
پاسخ بصورت نقل قول
خواهش میکنم. خیلی خوشحال شدم. Question
به هر حال منم نیاز به روحیه دارم.
اگه کس دیگه ای هم هست که از اینا بدش نمیاد. بگه ما هم بدونیم. Rolling Eyes

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

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

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


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


1 شنبه 26 فروردين 1386 - 12:18
پاسخ بصورت نقل قول
خسته نباشي . الان دانشگاه هستم نمي تونم مطالعه كنم بعدا نظرم رو مي گم ...

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

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


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


1 شنبه 26 فروردين 1386 - 13:12
پاسخ بصورت نقل قول
منتظرم Arrow

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

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

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


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


1 شنبه 26 فروردين 1386 - 13:27
پاسخ بصورت نقل قول
خيلي جالبه Very Happy
از قبليا جامع تر بود Laughing

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

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


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


1 شنبه 26 فروردين 1386 - 13:44
پاسخ بصورت نقل قول
ممنون
نظر دادن که یادتون نمیره Surprised

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

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

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


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


1 شنبه 26 فروردين 1386 - 14:45
پاسخ بصورت نقل قول
خوب احسان جان خوندم ( البته در همون دانشگاه ) خسته نباشي .
در مورد حالت هاي اول درسته توي TGB اين حالت ها در نظر گرفته شده يعني دايره و كل عكس كه همون مستطيله در اين صورت محاسبات كاهش پيدا مي كنه ولي توي GM اين حالت ها در نظر گرفته نشده البته شايد روش تشخيص برخورد در اين دو موتور متفاوت باشه چون توي GM حتي از يك شكل كمكي ساده استفاده نشده و به نظر من اين باعث مي شه كه حافظه زيادي رو استفاده كنه ولي در TGB از يه پليگان استفاده مي شه كه البته بايد از نوع كانوكس باشه ( 2d convex : چند ضلعي بسته اي كه زاويه خارجي كوچكتر از 180 درجه نداشته باشه يا هر خطي كه از پليگان عبور مي دهيم فقط يك بار پليگان رو قطع كنه ...) البته با توضيحات شما نمي شه فهميد كه چرا در موتور TGB پليگان هر آبجكت بايد كانوكس باشه . به نظر من اين موتور از روش برخورد در محيط TGE استفاده مي كنه يعني از الگريتم هاي 3 بعدي چون در TGE هم شي 3 بعدي كمكي بايد كانوكس باشه ...

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

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


تاريخ عضويت: جمعه 16 مرداد 1383
تعداد ارسالها: 3279
محل سكونت: Germany


1 شنبه 26 فروردين 1386 - 15:23
پاسخ بصورت نقل قول
خيلي خوب بود.
آفرين.

_________________




استدیوی نرم افزاری بلوبالک
www.Bluebulk.info
ارسال  بازگشت به بالا
ديدن مشخصات كاربر ارسال پيغام خصوصي ديدن وب سايت كاربر
 

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


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


1 شنبه 26 فروردين 1386 - 15:53
پاسخ بصورت نقل قول
ممنون از توجه همه.
برای مجتبی :
روشی که از پلی گون برای تشخیص برخورد میکنه یکی از روشهای خوب و کاراست. و مفهوم اینو که نه سیخ می سوزه و نه کباب میشه تو اونجا دید.
البته الگوریتمش کمی پیچیده تر از این الگوریتمهاست و بنده هم تا حالا ازش استفاده نکردم.
حالا شاید برای قسمت بعدی ریز اون روش رو عم در آوردم و خدمتتون ارائه کردم. Idea
ولی خوب کلیاتش شبیه همین الگوریتمهای محصور کننده است.
اونجا به جای دایره و مستطیل از پنج ضلعی استفاده میشه.
البته شایدم سطحش یه ذره از مبتدی بالاتر باشه.
بگذریم بازم ممنون.

برای شهروز:
مرسی شهروز جان
امبدوارم توجهت به اینجا ادامه دار باشه.

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

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

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


 
پرش به:  


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


unity3d

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