משחקי כאוס – חלק שני

משולשים (Triangles)

מבוא

1.    משולש סירפינסקי

2.    רקורסיה

3.    משחק כאוס

משולש סירפינסקי

בשנת 1916 הציג מתימטקאי פולני Vaclav Sierpinski את פרקטל המשולש שלו, המתקבל באופן הבא:

1.    קח משולש מלא,  ושווה שוקיים.

2.    חלק את המשולש ל- 4 משולשים קטנים ושווי-שוקיים.

3.    הסר את המשולש האמצעי, כך שנוצר חור.

4.    חלק את שלוש המשולשים שווי-השוקיים הנותרים בדיוק כפי שמתואר בשלב 2.

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

איור מס' 1: השלבים הראשונים של משולש סירפינסקי

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

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

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

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

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

§   כאשר פונקציה/שגרה קוראת לפונקציה/שגרה אחרת התהליך מכונה קינון (Nesting).

§   כאשר פונקציה/שגרה קוראת לעצמה מתקבל תהליך רקורסיבי.

בשני המקרים הנ"ל, המחשב מבצע פעולות רבות שהן שקופות למשתמש, כגון פתיחת מחסנית (Stack) הכנסת משתנים בסדר קבוע מראש, ושליפתם בעת הצורך בסדר קבוע מראש, כגון - נתון ראשון שנכנס הוא גם הראשון שיוצא (FIFO – First In First Out). אין כוונה לעמוד על ההסבר המלא, או לעסוק במבנה זיכרון, או מחסנית המחשב ולכן נשאיר קצת Imagination, Magic & Mystery באופן הפעולה של תהליכים רקורסיביים.

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

תאור כללי של "סכמת החזרה" מובא באיור מס' 2 (זהו בעצם השלב הראשון). נקבע שלושה כיווני התקדמות, ונסמנם ב- 1, 2 ו- 3. נסמן את נקודת האמצע בכל אחת משוקי המשולש ונגדירן כ-
(Xn1, Yn1) וכ"ו. נשים לב למיקום המיוחד של ראשית הצירים – פינה שמאלית עליונה. זוהי ברירת המחדל של המחשב, ולא נשנה אותה. כעת נכתוב את הפקודה המציירת את המשולש המרכזי (זה שאותו מוציאים החוצה, והוא גם מחלק את המשולש הגדול ל- 4 משולשים):

LINE (Xn1, Yn1)-(Xn2, Yn2)

LINE (Xn3, Yn3)-(Xn2, Yn2)

LINE (Xn1, Yn1)-(Xn3, Yn3)

ואת שלוש הקריאות (קריאות תלויות בכיוון, קריאה עבור כל כיוון) שבאמצעותם מציירים את המשולש(ים) הנ"ל:

CALL MakeTriangle(X1, Y1, Xn1, Yn1, Xn3, Yn3, I + 1)

CALL MakeTriangle(X2, Y2, Xn1, Yn1, Xn2, Yn2, I + 1)

CALL MakeTriangle(X3, Y3, Xn3, Yn3, Xn2, Yn2, I + 1)

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

SUB MakeTriangle (X1, Y1, X2, Y2, X3, Y3, I)

         IF I=5 THEN EXIT SUB

         Xn1 = (X1 + X2) / 2: Yn1 = (Y1 + Y2) / 2

         Xn2 = (X2 + X3) / 2: Yn2 = (Y2 + Y3) / 2

         Xn3 = (X1 + X3) / 2: Yn3 = (Y1 + Y3) / 2

         LINE (Xn1, Yn1)-(Xn2, Yn2)

         LINE (Xn3, Yn3)-(Xn2, Yn2)

         LINE (Xn1, Yn1)-(Xn3, Yn3)

         CALL MakeTriangle(X1, Y1, Xn1, Yn1, Xn3, Yn3, I + 1)

         CALL MakeTriangle(X2, Y2, Xn1, Yn1, Xn2, Yn2, I + 1)

         CALL MakeTriangle(X3, Y3, Xn3, Yn3, Xn2, Yn2, I + 1)

END SUB

עם הפעלת התוכנית, מתבצעת הקריאה הראשונה. היא מסתיימת כאשר I=5 (מסתיימת רק באופן חלקי, ראה להלן). כעת נכנסת לפעולה המחסנית ושולפת נתונים, ומאפשרת לשלב 2 ושלב 3 "לעבוד" עבור שלב 1. באופן כזה מצויירים משולשי 2 ו- 3 כאשר אנו עדיין בשלב 1. כאשר זה מסתיים עוברים לשלב 2 וכ"ו, ולאחר מכן לשלב  3 וכ"ו, כפי שמתואר באיור מס' 2.

חמשת השלבים הראשונים של משולש סירפינסקי מתוארים באיור מס' 3.

איור מס' 2: "סכמת החזרה" והקריאות הרקורסיביות (The Motif)

איור מס' 3: חמישה שלבים ראשונים של משולש סירפינסקי

קוד מקור למשולש סירפינסקי

DECLARE SUB MakeTriangle (X1!, Y1!, X2!, Y2!, X3!, Y3!, I)

SCREEN 12

X1 = 320: Y1 = 0

X2 = 0: Y2 = 479

X3 = 639: Y3 = 479

LINE (X1, Y1)-(X2, Y2), 12

LINE (X1, Y1)-(X3, Y3), 12

LINE (X2, Y2)-(X3, Y3), 12

CALL MakeTriangle(X1, Y1, X2, Y2, X3, Y3, 0)

LOCATE 1, 1: INPUT ; idle

SUB MakeTriangle (X1, Y1, X2, Y2, X3, Y3, I)

         IF I = 6 THEN EXIT SUB

         Xn1 = (X1 + X2) / 2: Yn1 = (Y1 + Y2) / 2

         Xn2 = (X2 + X3) / 2: Yn2 = (Y2 + Y3) / 2

         Xn3 = (X1 + X3) / 2: Yn3 = (Y1 + Y3) / 2

         LINE (Xn1, Yn1)-(Xn2, Yn2), 12

         LINE (Xn3, Yn3)-(Xn2, Yn2), 12

         LINE (Xn1, Yn1)-(Xn3, Yn3), 12

         CALL MakeTriangle(X1, Y1, Xn1, Yn1, Xn3, Yn3, I + 1)

         CALL MakeTriangle(X2, Y2, Xn1, Yn1, Xn2, Yn2, I + 1)

         CALL MakeTriangle(X3, Y3, Xn3, Yn3, Xn2, Yn2, I + 1)

END SUB

שטיח סירפינסקי

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

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

איור מס' 4: שטיח סירפינסקי – סכמת החזרה והתוצאה הגראפית

ריבועים

עוד דוגמא לרקורסיה באיור הבא:

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

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

איור מס' 5: ריבועים

משחק כאוטי

חוקי המשחק הם הבאים:

1.    צייר משולש כלשהו, וסמן את קדקודיו ב- A, B ו- C.

2.    סמן נקודה כלשהי בתוך המשולש וקבע אותה כנקודת מוצא.

3.    הטל קוביה.

4.    אם יצא 1 או 2 - מתח קו דמיוני מנקודת המוצא לקודקוד A, וסמן את נקודת האמצע של הקו. הנקודה החדשה היא נקודת מוצא חדשה

       אם יצא 3 או 4 - מתח קו דמיוני מנקודת המוצא לקודקוד B, וסמן את נקודת האמצע של הקו. הנקודה החדשה היא נקודת מוצא חדשה.

       אם יצא 5 או 6 - מתח קו דמיוני מנקודת הייחוס לקודקוד C, וסמן את נקודת האמצע של הקו. הנקודה החדשה היא נקודת מוצא חדשה.

5.    בצע שלבים 3 ו- 4 ללא גבול.

על מנת לראות את המובן מאיליו, אבל תוך הדגשתו, נשתמש בצבעים בהתאם לקודקוד שבו עושים שימוש – A – צבע צהוב, B – צבע סגול, C – צבע אדום. ראה האיור בעמוד הבא.

איור מס' 6: משולש סירפינסקי לאחר 500000 הטלות קוביה

קוד המקור של משחק כאוטי

SCREEN 12: CLS

LINE (0, 0)-(639, 479), 9, BF

PSET (320, 10): PSET (70, 350): PSET (570, 350)

x0 = 320: y0 = 200

WHILE n < 500000

 RANDOMIZE TIMER

   n = n + 1

   LOCATE 1, 1: PRINT n

   j = INT(RND * 6) + 1

   IF j = 1 OR j = 2 THEN

       x = (x0 + 320) / 2: y = (y0 + 10) / 2

       PSET (x, y), 14

       x0 = x: y0 = y

   END IF

   IF j = 3 OR j = 4 THEN

       x = (x0 + 70) / 2: y = (y0 + 350) / 2

       PSET (x, y), 13

       x0 = x: y0 = y

   END IF

   IF j = 5 OR j = 6 THEN

       x = (x0 + 570) / 2: y = (y0 + 350) / 2

       PSET (x, y), 12

       x0 = x: y0 = y

   END IF

WEND

END

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

משולש סירפינסקי בתלת ממד

לא בדיוק תלת ממד. נבנה פירמידה חלולה, ונחרר את דופנותיה, האחוריים והקדמיים. נשתמש בשתי השיטות – משחק כאוטי, ורקורסיה. התוצאה להלן:

איור מס' 7: ציורים תלת ממדיים באמצעות הטלות קוביה ושיגרה רקורסיבית

כמה מילים על רקורסיה

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

כמובן שקיימת גם רקורסיה רגילה, לא של מבנים גיאומטריים. דוגמאות קלאסיות שתמצאו בכל ספר תכנות הן: פונקצית העצרת n!, שיטת מיון QuickSort, סדרת פיבונאצ'י.

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

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

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

שיטת IFS שמשה את  בארנסלי מייקל כאשר חיבר את פרקטל עלה השרך (Fern), המובא להלן:

איור מס' 8: עלה השרך של בארנסלי