מבני נתונים

[Gn0MiCK]

מבני נתונים

אני מקווה שיש פה מישהו גאון... או לפחות יותר חכם ממני שיודע איך כדאי לי לייצג לוח של טטריס הפוך, כמו בתמונה המצורפת. חשבתי על מטריצה אבל אז אני צריך לעבור על 22(!) כיוונים שונים עבור כל קוביה.. ואני חושב שזה לא ממש יעיל... מה דעתכם?

 

[ChipsMan]

אממ..

לא הבנתי מה בדיוק אתה מנסה לעשות.. אתה רוצה שהבדיקה של השכנים של כל קוביה תהיה כמה שיותר מהירה? *-*

 

[Gn0MiCK]

כן

 

[ChipsMan]

סתם רעיון...

ויש לה גם קואורדינאטות שמייצגות את המרכז שלה. קבוצה של קוביות באותו צבע תהיה רשימה של מבנים כאלה. וכל הלוח שלך יהיה רשימה של כל הקבוצות. בנוסף לכל הקוביות יש אורך צלע מסויים. נקרא לו SIZE. בהנתן קוביה A נגדיר: A.x ו- A.y יהיו קואורדינאטות שלה בעולם. בדיקה האם A שכנה של B:

neighbours(A,B) if (|A.x - B.x| <= SIZE) and (|A.y - B.y <= SIZE) then return TRUE else return FALSE​

בדיקה האם A צריכה להבלם על ידי B שנמצאת מעליה:

collides(A,B) if (|A.y - B.y| <= SIZE) the return TRUE else return FALSE​

הקוביה שלך נעה עד שהיא נבלמת על ידי אחת הקוביות. ברגע שהיא נבלמת אתה יוצר קבוצה חדשה שמכילה רק את הקוביה החדשה שהגיעה. אחר-כך אתה בודק מיהם השכנים שלה שבעלי אותו צבע כמוה ומאחד את כל הקבוצות של השכנים שמצאת עם הקבוצה שיצרת בשביל הקוביה שהגעיה. כמובן שאם לא מצאת אף שכן באותו צבע, אז הקוביה נשארת בקבוצה משלה לבד. אפשר לייעל את הרעיון על ידי חלוקה של העולם שלך לרמות אנכיות. אופקית הקוביות יכולות לעמוד איפה שהן רוצות. אנכית המרחק שלהן מהתקרה היא כפולה של אורך הצלע של הקוביה. אז כאשר מגיעה קוביה, אתה בודק האם היא שכנה של הקוביות ברמה שלה, ברמה שמעליה וברמה שמתחתיה, ולא של כל הקוביות בעולם.

 

[ChipsMan]

תתקן את ההתחלה ../images/Emo9.gif

"ויש לה גם קואורדינאטות שמייצגות את המרכז שלה" ==> "לכל קוביה יש קואורדינאטות x,y שמייצגות את המרכז שלה".

 

[ChipsMan]

הנה עוד רעיון לייעול.

מבוסס טיפה על הרעיון של עצי BSP

העולם שלך יהיה מחולק לריבועים בגודל SIZE. אפשר לייצג אותם עם מטריצה. אם לקוביית טטריס מסויימת יש שטח משותף עם אחד הריבועית, היא תהיה משוייכת אליו. שים לב שקוביית טטריס יכולה להיות משוייכת גם ל-4 ריבועים בו זמנית. כאשר הקוביה נעה אתה בודק האם יש לה שטח משותף עם כל הריבועים שהיה לה שטח משותף איתם רגע לפני וגם עם כל השכנים שלהם, ואתה מעדכן את השיוך בהתאם. בדיקה האם הקוביה נבלמת אנכית, והבדיקה מי השכנים שלה לא תעשה מול כל הקוביות בעולם אלא רק מול הקוביות ששייכות לריבועים שאליהם הקוביה משוייכת וגם מול הקוביות ששייכות לשכנים של הריבועים אליהם הקוביה משוייכת. וכמובן, אתה גם צריך בדיקה האם קוביה נבלמת אופקית על ידי קוביה שנמצאת מצידה השמאלי או מצידה הימני. הבדיקה דומה לבדיקה האנכית אבל היא בודקת את קואורדינאטות ה-X במקום את קואורדינאטות ה-Y.

 

[Gn0MiCK]

הרעיון עם הקבוצות נראה לי טוב

ואולי אני באמת אשתמש בו, אבל לא ממש הבנתי את הרעיון עם העצים.. בכל מקרה אם אני אשתמש ברעיון הקבוצות, תיהיה לי בעיה כשאני ארצה לדעת איפה על הלוח לשים את הקוביה, כלומר, איפה על הלוח הקבוצה נמצאת.. לא?

 

[Gn0MiCK]

שמע חשבתי על הרעיון של הקבוצות

ויש כמה בעיות א. אם יש לי קבוצה של 2 ורווח ועוד קבוצה של 2, אני לא אוכל לזהות שכדאי לי להפיל את הקוביה בניהן ובכך לגרום להעלמת 2 הקבוצות... ב. אם הקבוצה נמצאת בתחתית הערימה(או במקרה שלנו הכי למעלה) ויש מעליה קוביות אחרות שחוסמות את הגישה... זה כבר יסבך את כל תהליך החיפוש...

 

[ChipsMan]

פתרונות...

א) לא תהיה שום בעיה. הרי הצעתי שהקוביה החדשה שנחתה הופכת לקבוצה עצמאית. ואליה אתה מאחד את כל הקבוצות של כל השכנים שלה. בסופו של דבר שתי הקבוצות השכנות שלה יתאחדו איתה לקבוצה אחת. ב) שום דבר לא מסבך שום חיפוש. אתה משווה לכל הקוביות שנמצאות בעולם, אם יש מישהי שחוסמת את הקוביה שמתקדמת אתה תגלה אותה.

 

[Gn0MiCK]

טוף... נחשוב על זה עוד קצת... תודה

 

[אלדד28]

לא הבנתי למה 22 כיוונים.

 

[Gn0MiCK]

אם תסתכל על הסרטוט

תראה שאפשר להזיז כל קוביה חצי מהרוחב שלה. ולכן חשבתי לייצג במטריצה שכל חצי רוחב של קוביה על הלוח היא תא במטריצה, ואם זה כך, אז צריך לחפש ב22 כיוונים כי יכול להיות מצב של קוביה ואז רווח של קוביה(2 רווחים במטירצה) ואז עוד קוביה, ואז בעצם אני ארצה להכניס את הקוביה השלישית ברווח שבין 2 הקוביות, בשביל ליצור רצף...