שלום וברכה.

אני בונה כרגע ב C (ב SDL) משחק "מבוך" ואיתו גם אפשרות לעריכת שלבים.

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

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

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

את המשחק אני בונה ב C בעזרת ספריית ה SDL.

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

תודה מראש,

יוסף אור

...

http://en.wikipedia.org/wiki/Maze_generation_algorithm

http://he.wikipedia.org/wiki/%D7%90%D7%9C%D7%92%D7%95%D7%A8%D7%99%D7%AA%D7%9E%D7%99%D7%9D_%D7%9C%D7%99%D7%99%D7%A6%D7%95%D7%A8_%D7%9E%D7%91%D7%95%D7%9B%D7%99%D7%9D

תודה על התשובה המהירה :-)

קראתי כבר את הערך בויקיפדיה העברית, אבל לא באנגלית - עוד מגבלה שיש לי בנוסף ל"אינטרנט רימון" - אני לא יודע אנגלית.

לא הצלחתי להבין את האלגוריתם שמוסבר בויקיפדיה. משום מה אני לא מחבב במיוחד אלגוריתמים ;-)

אין אלגוריתמים יותר פשוטים ?

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

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

כבר יצא לי להיפגש במושג הזה - תורת הגרפים:

http://www.interlect.co.il/le/Default.aspx *

לא חשבתי שזה יועיל לי, לכן לא למדתי את זה.

יהיה לי שימושי ללמוד את "תורת הגרפים" ?

אשמח לתשובה :-)

ותודה על התשובות הקודמות...

* האתר עובד רק ב IE

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

מומלץ לך להתמקד בצד האלגוריתמי יותר של תורת הגרפים (אלגוריתמי חיפוש למיניהם) ופחות בצד המתמטי (קומבינטוריקה, תורת רמזי וכו').

ממליץ לך גם לקרוא על עקומת פאנו \ הילברט

http://en.wikipedia.org/wiki/Space-filling_curve

מה הקשר בין זה לבניית מבוכים?

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

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