xonix אלגוריתם לסגירת שטחים

[sharpi]

זוכרים את המשחק סוגר שטחים?

אני צריך עזרה במציאת אלגוריתם על מנת לממש את המשחק

כיצד אני יכול להגדיר את מבנה הנתונים וכיצד האלגוריתם יפעל? למשל כשסוגרים שטח איך אני מזהה את השטח שנסגר? על כל האופציות השונות.

תודה

[שניצל]

ערוך בבקשה את הכותרת כך שתכיל את תמצית השאלה.

נ.ב. המשחק נקרא Xonix.

[Ghosthunter]

בכלליות, זה האלגוריתם:http://en.wikipedia.org/wiki/Connected_component_labeling

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

[sharpi]

לא כל כך הבנתי את האלגוריתם.

תוכל לתת לי כיוון מחשבה לאלגוריתם סגירת השטחים? איך אני מזהה שסגרתי שטח? .9ובאיזה שטח מדובר)

[Ghosthunter]

יש 2 פעולות שאתה צריך לעשות -

1. לזהות שסגרת שטח.

2. לסמן את השטח שנסגר.

1. כדי לזהות שסגרת שטח אתה פשוט בודק האם אתה נמצא על קו שכבר צוייר.

2. כדי לסמן את השטח שנסגר, אתה מפעיל את האלגוריתם הזה.

[sharpi]

2. כדי לסמן את השטח שנסגר, אתה מפעיל את האלגוריתם הזה.

תוכל להסביר בבקשה את העיקרון של האלגוריתם שמזהה את השטח הנסגר ומסמן אותו.?

[-LosNir-]

http://www.sunlightd.com/Archive/Windows/DirectX/Xonix1.aspx

[Ghosthunter]

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

[sharpi]

http://www.sunlightd.com/Archive/Windows/DirectX/Xonix1.aspx

היכן האלגוריתם עצמו של הסוגר שטחים? לא הצלחתי להבין משם.

בו נאמר שיש לי מערך דו ממדי שמציין 0 פנוי 1 תפוס.

כשאני סוגר שטח יש הרבה 1 ובתוכו 0. איך אני מסמן את כל השטח ב 1 ים, איך אני מזהה את השטח הספציפי שנסגר?

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

אם אני מסתכל על מערך דו ממדי שצייני למעלה, איך בדיוק זה מסמן לי את השטח שנסגר? איך ה 0ים בתוך השטח הסוגר הופכים ל1 ים?

[Ghosthunter]

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

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

[sharpi]

בא נאמר שיש לי מערך דו ממדי שיש לו מסגרת של 1 ים.

ועכשיו מישהו סגר שטח בפנים. אז יש בפנים שטח נוסף שמוקף ב 1 ובתוכו 0 ים. (מסביב ל1 ים יש 0 ים) איך האלגוריתם מתמודד עם זה?

[sharpi]

אוקיי, תודה הסתדרתי

[Ghosthunter]

נוצרו לך שני תתי שטחים - שבמקום שיהיה בהם 0 יהיה בהם ערכים אחרים (בכל תת שטח יהיה ערך אחר).

אתה צריך לבדוק באיזה תתי שטחים אין "יריבים", ולהפוך את הערך שלהם ל- 1 (כלומר, לסמן את השטח כמלא).

איך הסתדרת בסוף?

[sharpi]

בדיוק כמו שאמרת, הבנתי את זה (תודה)