למי שלא מכיר את המשחק Bejeweled, המשחק הוא לוח מגודל 8X8 של יהלומים מצבעים שונים, המשתמש צריך למצוא רצף של יהלומים ע"י החלפת שני יהלומים אם יש רצף שיותר גדול מ3 הם נעלמים הלבנים שמלמעלה יורדות ונכנסות חדשות וכך הלאה(עבור כל רצף המשתמש מקבל ניקוד)

אני כותב את המשחק בC++

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

תודה

דרך אחת פשוטה (אך לא בכרח טובה) היא לבדוק כל האפשרויות להחלפת היהלומים: אם ההחלפה מייצרת רצף - מוסיפים אותו לרשימת המהלכים האפשריים. לבסוף בודקים את הרשימה ומוצאים את המהלך הכי טוב (לדוגמא רצף הכי גדול).

בלי קשר לאלגוריתם שמוצא את הבחירה הנכונה ביותר,

מה המטרה שלך, משחק, או אלגוריתם לפתרון המשחק ?

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

לפעמים עושים הנחות. "המשתמש תקוע והוא רק מחפש צעד אחד שיוכל להזיז אותו הלאה" - אתה יכול לעצור אחרי שמצאת אופציה אחת.

הכל תלוי כמובן במה רוצים להשיג. הרבה פעמים האלגוריתם המדוייק הוא לאו דווקא זה שמשתמשים בו.

אני רוצה לכתוב את הHINT של המשחק, כלומר ברגע שהמשתמש לחץ על הכפתור, התוכנית תמצא בעצמה רצף ותקיף במסגרת את היהלום שבאמצעותו ניתן יהיה לקבל רצף

ההצעה של Zelig נראית הכי טובה. עבור כל יהלום תנסה להחליף אותו עם כל אחד מהשכנים ותבדוק אם יוצא רצף. אם כן, תשמור את האינדקסים

של שני היהלומים.

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

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

נראה לי שאני מתחיל להבין..., אבל עדיין יש לי בעיה של גילוי הרצף למשל יש מקרים:

1)
   X
   X
X X Z X X
   X 


2)
  T Q W
  B X F
  I J X
  T Q X 
....   

יש המון אפשרויות, אני רוצה למציאת רצף תיהיה כללית עד כמה שאפשר עכשיו יש גרסה הבעיה שיש שם המון תנאים, יש אפשרות לייעל את זה טיפה

חשבתי אולי לחפש רצף בכל הלוח (כל פעם שמחליפים שני יהלומים שכנים) הבעיה שלא כל פעם שמחליפים יש רצף, חשבתי אולי לרוץ על השכנים של

יהלום ספיציפי כל פעם אבל זה לא מספיק כמו שרואים בדוגמא 2.

לא הבנתי.

מה הבעיה שלך ? לגלות רצף ?

רוץ על המטריצה עם i,j ולכל תא תבדוק רצף כלפי מטה/ימינה בלבד.

לכל החלפה של תא A עם תא B מספיק לבדוק רק רצפים שכוללים את A או את B, ולא את כל הלוח.

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

אולי אני לא מבין מה בדיוק אתה שואל?

הצלחתי לבסוף לעשות את הHINT הבעיה שעכשיו יש לי פשוט הרבה מאוד תנאים, יש אולי דרך לאחד ביניהם למשהו קצת יותר "נקי"

זמן הריצה לא כזה עקרוני אחרי הכל זה מטריצה מגודל קבוע 8X8

אילו תנאים יש ב-HINT?