الشبكة العربية لمطوري الألعاب

خبير  أحمد عزالدين مشاركة 1

السلام عليكم

كيف حالكم جميعا 😄
اتمني تكونوا بخير حال واتمني ان نراكم في المسابقة الحالية بمقالات فريدة 😋

الان لدي مشكلة عاجلة عاجلة جدا
حيث انني اعمل علي برنامج لمشروع تخرج ومبدئيا البرنامج يحاول ان يطبق اسلوب ال path finding علي وحدات موزعة عشوائيا
في بيئة يتم بناؤها من صورة من النوع bmp

حاليا كنت اجرب اختبار بسيط لجزء من الكود لكن يبدوا انه لم يكن بسيطا☺
علي اية حال الان لدي المشكلة الاتية
انا قررت ان استخدام متغيرين ليحملوا بيانات الصورة قبيل استخدام هذه البيانات في بناء ال grid map المستخدمة في البحث
طيب ما الغرض من المتغيرين ( عموما اتمني لو كانت هناك اقتراحات افضل لحل المشكلة)
المتغير الاول يحمل قيم بيكسلات الصورة كاملة وتم تعريفه وتم تحميل كافة بيانات الصورة فيه
وهو متغير من النوع char* لكنه يعمل فعليا كأنه unsigned char* (هذا باستخدام احدي اعدادات ال visual studio)
نذكر ان المتغير قد تم تعريفه هكذا


Raster= new char[BytesPerRow*Height];

الجدير بالذكر انه عند الوصول للبيكسلات ربما قد يستخدم هذا الكود

for (int x = 0; x < 800; x++)
{
   for (int y = 0; y < 600; y++)
   {
      // x * 3 as we have RGB color format so it's 3 byte each
      int index = 3*x + y * BytesPerRow;


      // read from raster image data
      BYTE b = Raster[index];
      BYTE g = Raster[index+1];
      BYTE r = Raster[index+2];
   }
}
 
نلاحظ المتغير index يستخدم للوصول للمصفوفة التي تحتوي بيانات الصورة الفعلية لانها linear array

الان المتغير الثاني والذي قررت استخدامه تم تعريفه بهذه الطريقة


ImageMap = new char[BytesPerRow*Height/3];

هنا تم القسمة علي 3 وذلك لانني اريد حجم هذا المتغير ان تكون ثلث حجم بيانات الصورة
يعني بدلا من استخدام 3 بايت لكل بيكسل كما في المتغير الاول والذي يحمل بيانات الصورة الفعلية
قمت باستخدام المتغير الثاني ليحمل فقط بايت واحد لكل بيكسل وقيمة هذا البايت هي الـ average لقيم ال  3 بايت الكونة لهذا البيكسل من المتغير الاول
الان انا اريد استخدام القيم الموجودة في المتغير الثاني لبناء ال grid map ,والتي سيكون path finding search عليها
حيث انني انوي ان تمثل قيم كل بايت كل بيكسل من المتغير الثاني قيمة التكلفة لكل بيكسل ( لكل node ) في محيط الصورة
حيث انني افترض ان البيئة التي سيتم البحث فيها هي بيئة تمثل تمام بيئة الصورة حيث ان كل بيكسل يمثل node

الان المشكلة هي انه بعد تحميل قيم كلا من المتغيرين بطريقة صحيحة وبكود مثل هذا

for (int x = 0; x < 800; x++)
{
   for (int y = 0; y < 600; y++)
   {
      // x * 3 as we have RGB color format so it's 3 byte each
      int index = 3*x + y * BytesPerRow;


      // read from raster image data
      BYTE b = Raster[index];
      BYTE g = Raster[index+1];
      BYTE r = Raster[index+2];
 
      BYTE avg = (r+g+b)/3;
      if( avg < 0 )
         assert( false );  // if avg happened to be less than 0 then stop	

      //if( x == 25 && y == 372 )
         //assert( false );


      // do some clampping
      if(avg > 254)
         avg = 245;    // assum our max cost = 254
      if(avg < 50)
         avg = 0;      // assume less than 50 cost to be blocked


      // recalculate the index
      index = x + y * BytesPerRow / 3;
      if(index != 0)
         ImageMap[index] = avg;
      else
         ImageMap[0] = avg;
   }
}
الان عندما اقوم باستدعاء دالة هي المسؤلة عن بناء ال  grid map
,هذه الدالة تستقبل متغير يمثل مؤشر لبيانات الصورة المجمعة وهو في الواقع يمثل المتغير الثاني المذكور بالاعلي
وعند قراءة بيانات التكلفة من المتغير المرسل لهذه الدالة اجد ان التكلفة تظهر قيما سالبة وتسبب مشكلة بالبرنامج
كود الدالة المسؤلة عن البناء كالاتي

void CPathfinder::SetupWorld( int xgridSize, int ygridsize, char** gridMapData, int bytesPerRow )
{
   // setup the world for use
   m_grid = new MapGrid( xgridSize, ygridsize );

   //m_walkers.push_back(new BestFirstSearchMapGridWalker(m_grid));
   //m_walkers.push_back(new BreadthFirstSearchMapGridWalker(m_grid));
   //m_walkers.push_back(new DijkstrasMapGridWalker(m_grid));
   m_walkers.push_back(new AStarMapGridWalker(m_grid));

   setCurrentWalker(0);

   //setHeuristicMethod(BestFirstSearchMapGridWalker::EUCLIDEANDIST);
   setHeuristicMethod(AStarMapGridWalker::EUCLIDEANDIST);
   setHeuristicWeight(1.0f);

   // fill the m_grid with the costs from the passed grid map image data
   for(int xx=0 ; xx   {
      for(int yy=0 ; yy      {
         int i = xx + yy * bytesPerRow / 3;
         int cost = (*gridMapData)[i];
         if( cost < 0 )
            assert( false ); // if cost was -1 then stop			
         m_grid->setCost( xx, yy, cost );		
      }
   }


   m_currentWalker->BuildGridNode( m_grid );
}

اتمني اي اقتراحات لحل المشكلة
ويتم استدعاء هذه الدالة كالاتي

bmp.LoadBMP ("map.bmp");

// create the path finding world here and initialize it
pathFinder.SetupWorld( 800, 600, &(bmp.ImageMap), bmp.BytesPerRow );

اعتذر عن الاطالة ولكم جزيل الشكر
والسلام عليكم

أحمد عزالدين
طالب دراسات عليا
جامعة كالجري

خبير مدير وسام البهنسي مشاركة 2

وفي 22/صفر/1430 05:37 م، أعرب ahmed ezz عن رأيه بالموقف كالآتي:

المتغير الثاني والذي قررت استخدامه تم تعريفه بهذه الطريقة


ImageMap = new char[BytesPerRow*Height/3];

هنا تم القسمة علي 3 وذلك لانني اريد حجم هذا المتغير ان تكون ثلث حجم بيانات الصورة
يعني بدلا من استخدام 3 بايت لكل بيكسل كما في المتغير الاول والذي يحمل بيانات الصورة الفعلية

لست مضطراً لاتباع هذه الطريقة. فـ BytesPerRow قد يكون أكثر من عرض الصورة مضروباً بحجم البكسل (لاعتبارات خاصة بالرسم لا يسعني ذكرها الآن). بينما أنت تريد نسخ القيم إلى مصفوفة خاصة بك، لذلك يكفي أن تعلن عن مصفوفتك بالطريقة الطبيعية:
 

ImageMap = new BYTE[Width*Height];
 
ومن ثم تستطيع الوصول لأي بكسل بسهولة ووضوح:


BYTE Value = ImageMap[x+y*Width];
 
أما بالنسبة لمشكلة الرقم السالب الذي تحصل عليه، فإنه من غير الممكن أن ينتج إلا في حال كون مصفوفتك من نوع signed char. لذلك فقد تكون قد ارتكبت خطأ ما أثناء إعداد المشروع ليفترض أن char هو دائماً عدد بلا إشارة.
من منظوري الشخصي أنا أبتعد عن مثل هذه الطريقة لأنها ستحير كل من يقرأ الكود غيرك، كما أنها ستجعلك عرضة لكثير من الأخطاء عند التعامل مع مكتبات أخرى.
الحل الأمثل هو استخدام متغيرات من نوع BYTE (أيضاً 4 أحرف، لذلك لن تبذل جهداً إضافياً في الكتابة على الكيبورد مقارنة بـ char 😄 )
 
 
النقطة الأخرى التي أود أن أعقب عليها هي طريقة تمرير المؤشر. لماذا **char ؟
يمكنك ببساطة تمرير *char والتعامل معه بشكل عادي، فيصبح الكود هكذا:


//int cost = (*gridMapData)[i]; // لا حاجة لهذا
int cost = gridMapData[i]; // هكذا أفضل

أخيراً، لاحظت أنك تعالج بكسلات الصورة بالمرور عليها بالطريقة الآتية:


for (int x = 0; x < 800; x++)
{
   for (int y = 0; y < 600; y++)
   {
      BYTE pix = map[x+y*width];
      ...
   }
}
 
بينما سيكون الأداء أفضل لو مررت عليها هكذا:


for (int y = 0; y < 600; y++)
{
   for (int x = 0; x < 800; x++)
   {
      BYTE pix = map[x+y*width];
      ...

   }
}
 
سؤال المليون هو:  برأيكم، لماذا سيكون الأداء في الحالة الثانية أفضل؟ ☺

وسام البهنسي
مبرمج في إنفيديا وإنفريمز

خبير  أحمد عزالدين مشاركة 3

السلام عليكم

شكرا اخي وسام لي سرعة الرد

في 18 فبراير 2009 02:15 ص، قال وسام البهنسي بهدوء وتؤدة:

النقطة الأخرى التي أود أن أعقب عليها هي طريقة تمرير المؤشر. لماذا **char ؟يمكنك ببساطة تمرير *char والتعامل معه بشكل عادي
بخصوص هذا التمرير - بصراحة لقد كنت استخدم الطريقة البسيطة وعدلتها من كثرة شكي في وجود الخطأ المذكور
لكن بالفعل يبدوا ان الخطأ لا يتعلق بهذا الامر
وسأخذ بنصيحة حضرتك واجعل الكود يعتمد علي  BYTE
وسأوافيكم بالنتيجة قريبا

في 18 فبراير 2009 02:15 ص، عقد وسام البهنسي حاجبيه بتفكير وقال:

لست مضطراً لاتباع هذه الطريقة. فـ BytesPerRow قد يكون أكثر من عرض الصورة مضروباً بحجم البكسل (لاعتبارات خاصة بالرسم لا يسعني ذكرها الآن)
بصراحة ان ال BytesPerRow في هذه الحالة تمثل كامل عرض الصورة باخذ ال padding pixels  الموجودة ربما في نهاية بعض الاسطر
يعني من الاخر قيمة BytesPerRow هي ال image pitch

ايضا سأحاول ان ابسط الكود مرة اخري حسب نصائح حضرتك
وشكرا لك

بخصوص الامتحان السريع حول السؤال عن افضلية الاداء في الحالة الثانية
فاعتقد انه للسبب الاتي

في الحالة الاولي
تم استخدام المتغير x وسيتم الوصول اليه 800 مرة
وسيتم الوصول للمتغير y في الحلقة الداخلي 800 * 600 مرة

في الحالة الثانية
تم استخدام المتغير x وسيكون ال access time له 600 مرة فقط
وسيتم الوصول للمتغير y في الحلقة الداخلي 800 * 600 مرة

فيظهر من ذلك ان الاداء في الحالة الثانية افضل لانه يقلل ال  access time لمتغيرات العدادات الخصة بالحلقة
اتمني ان يكون هذا الحل صحيحا 😄 فبعد بحث سريع عن كفاءة الحلقات التكرارية المتداخلة وصلت لهذا الحل

شكرا لك😄
والسلام عليكم

أحمد عزالدين
طالب دراسات عليا
جامعة كالجري

محترف  انس مشاركة 4

السلام عليكم


مشاركتي ستكون كلاتي :

الطريقة الثاتية عبارة عن قرائة خطية للمصفوفة ... توافق الكتابة التالية :

*(pixel++)


مثال : ليكن y=0 .
سيتم قراءة البكسالات التالية

(1,0),(2,0),(3,0) ...

اي قراءة السطر الاول من الصورة .

اما بالطريقة الاولى فان قراءة المصفوفة يكون بطرية القفز☺ .(الان القراءة عمودية)
فالمتغير

int index ;
pixel [index]

سيكون كلتالي 

x= 0
index (0),(3),(6),(9)
x=1
index (1),(4),(7),(10)
....

هدا سيؤدي الى تغير عنوان المؤشر بطريقة اقل فعالية من الطريق السابقة .



01 :          | 02 :
200240        | 200240
200243        | 200241
200246        | 200242
...           | ...
200241        | 200247
200244        | 200248
200247        | 200249


..............................
هدا مجرد اقتراح اتمنى ان يكون في محله☺

.............................

اخي الكريم احمد عز لست بالستوى المطلوب لمجادلتك و لكن لي تعليق على

وفي 18 فبراير 2009 09:10 ص، قال ahmed ezz متحمساً:

في الحالة الاوليتم استخدام المتغير x وسيتم الوصول اليه 800 مرةوسيتم الوصول للمتغير y في الحلقة الداخلي 800 * 600 مرةفي الحالة الثانيةتم استخدام المتغير x وسيكون ال access time له 600 مرة فقط وسيتم الوصول للمتغير y في الحلقة الداخلي 800 * 600 مرة
لو تم الوصول الى x  مرة فقط فستكون الطريقة المروضة خاطئة لان الصورة لن تكون كاملة ... ينقصها 200 بكسل من كل عمود

كلاتا الطريقتين  تسمحات بالوصول الى x 800 مرة في كل سطر و الوصول الy  600 مرة في عمود  والا فلن تكون الصورة كاملة 



ملاحظة اخرى :

ف الطريقة 2 يتم الوصول ال y  600 مرة فقط و x 600*800  اما الطريقة الاولى فالعكس y 600*800 و x 800

سلام

خبير  سلوان الهلالي مشاركة 5

وفي 18 شباط 2009 02:15 ص، ظهر شبح ابتسامة على وجه وسام البهنسي وهو يقول:

أخيراً، لاحظت أنك تعالج بكسلات الصورة بالمرور عليها بالطريقة الآتية:


for (int x = 0; x < 800; x++)
{
   for (int y = 0; y < 600; y++)
   {
      BYTE pix = map[x+y*width];
      ...
   }
}
 
بينما سيكون الأداء أفضل لو مررت عليها هكذا:


for (int y = 0; y < 600; y++)
{
   for (int x = 0; x < 800; x++)
   {
      BYTE pix = map[x+y*width];
      ...

   }
}
 
سؤال المليون هو:  برأيكم، لماذا سيكون الأداء في الحالة الثانية أفضل؟ ☺

السلام عليكم, 
جوابي هو: للمسألة علاقة بالتعامل مع الكاش الموجودة على وحدة المعالجة المركزية بطريقة سيئة, حيث بسبب حجم الذاكرة الكبير نسبياً قد يسبب الدخول إليها بطريقة غير متعاقبة المشكلة المسماة cache thrashing, التي تقلل من فائدة خطوط الكاش لتسريع التنفيذ.

في الطريقة الأولى يتم الدخول بهذا التسلسل (حسب مؤشر المصفوفة):
العنصر 1: 0
العنصر 2: 0 + 1 * w
العنصر 3: 0 + 2 * w
...
كما نلاحظ فإن العناصر ليست متعاقبة, وتصل المسافة بين عنصر والعنصر الذي يليه في اسوأ حالة إلى: 599 * w
 
أما في الطريقة الثانية:
العنصر 1: 0
العنصر 2: 1
العنصر 3: 2
وهكذا...
منما يعني إننا حصلنا على التعاقب الذي يستثمر الكاش بالطريقة المثلى.
ولذلك فإن الطريقة الثانية هي الأفضل.
 
أتمنى ان يكون جوابي صحيحاً 😄

خبير مدير وسام البهنسي مشاركة 6

رائع! فعلاً الجواب الصحيح يتعلق بفعالية الكاش، وهو ما ذكره tombston بشكل غير صريح عندما قال:
 

أما في 23/صفر/1430 05:30 ص، فقد تنهد tombston بارتياح وهو يرد:

هدا سيؤدي الى تغير عنوان المؤشر بطريقة اقل فعالية من الطريق السابقة .

وذكره سلوان بشكل صريح: 

في 23/صفر/1430 06:23 ص، غمغم سلوان الهلالي باستغراب قائلاً:

للمسألة علاقة بالتعامل مع الكاش الموجودة على وحدة المعالجة المركزية بطريقة سيئة, حيث بسبب حجم الذاكرة الكبير نسبياً قد يسبب الدخول إليها بطريقة غير متعاقبة المشكلة المسماة cache thrashing, التي تقلل من فائدة خطوط الكاش لتسريع التنفيذ.

عندما تحصل على القيم من عناوين غير متتالية فإنك معرض أكثر لاستنفاذ كامل الطرق في خط الكاش الواحد (cache ways in a cache line)، وبالتالي ستدفع كلفة زمنية أعلى لجلب القيم من الذاكرة الرئيسية كل مرة إلى ذاكرة الكاش. 
 
أنا سعيد جداً بهذه الإجابات، وسعيد أكثر بأن أصحابها من أعضاء الشبكة! انظروا كم أنا سعيد: 😄 😄   (واحدة للإجابات وواحدة للأعضاء)!
 
شكراً

وسام البهنسي
مبرمج في إنفيديا وإنفريمز