eta مدیر سایت
تاريخ عضويت: 2 شنبه 27 تير 1384 تعداد ارسالها: 2153 محل سكونت: شاهين شهر
شنبه 25 فروردين 1386 - 21:56 |
|
|
اگر بازیهایی را که محاسبات 3 بعدی دارند ولی گرافیک آنها دو بعدی است(برخی این بازیها را 2.5 بعدی می نامند.)، کنار بگذاریم و صرفا به بازیهای دو بعدی تک سطحی بنگریم، الگوریتمهای تشخیص برخورد محدودی برایشان یافت می شود. اگر چه ممکن است برخی از این الگوریتم ها قیافه های مختتلفی نیز داشته باشند، اما
گاها این الگوریتم های مختلف الشکل از اصول یکسانی استفاده می نمایند.
همانطور که در مقالات قبلی نیز تا حدودی به این موضوع اشاره شده بود، الگوریتمهای مختلف دقت مختلفی دارند و علاوه براین، این الگوریتمها نیز از قائده "دقت بیشتر در برابر هزینه بالاتر" تبعیت می نمایند. یعنی هر چه الگوریتم شما دقیقتر عمل کند. برای ایجاد این دقت بالا زمان بیشتری را نیز صرف می نمابد.
اگر چه همواره و در همه بازیها دقت بالا مورد نیاز نیست، اما در اکثر مواقع این نیاز وجود دارد و از طرف دیگر نمی توان هزینه بالای برخی از الگوریتمها را نیز نادیده گرفت. در چنین شرایطی اولین راهی که به ذهن شما می رسد این خواهد بود که سعی کنید به نحوی تعادل را بین این دو واقعیت رعایت کنید. یعنی تا جایی که
مقدور باشد و سخت افزار به شما اجازه بدهد از الگوریتمهای کاراتر استفاده کنید.
گویا سخت افزار به شما میگوید هر چه قدر که پول بدهی آش میخوری !!! و گرسنگی شما نیز به حدی است که مجبور می شوید تمام پول خود را به او بدهید، تا خود را بیشتر سیر کنید.!!!!! ای کاش می شد به نحوی سر سخت افزار شیره بمالیم. ای کاش می شد ... . یعنی ممکن است؟؟؟؟
از قضیه آش بگذریم. بیایید چند تا از الگوریتمهای موجود را مطالعه کنیم. شاید راهی مناسب برای مشکلمان بیابیم.
یکی از ابتدایی ترین و ساده ترین راههای تست برخورد این است که تمام اشیا را به صورت یک دایره فرض کنیم. بنابراین تنها کاری که برای تشخیص برخورد دو شی در چنین شرایطی باید بکنیم این است که فاصله مرکز دو شی را از یکدیگر بسنجیم.
می دانید که مشخصات دایره با نقطه ای به عنوان مرکز و فاصله ای به عنوان شعاع تعیین می گردد. دو دایره به مرکزهای (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 بوده است. |
|