פיתוח אלגוריתם יעיל וכללי של עננים


(Itzik Arzoni) #1

ממשיך את הדיון מ יצירת עננים בקוד:

הרעש של פרלין

טוב, אני אקצר את הסיפור: רעש סטטי אינו מתאים לייצירת טקסטורות טבעיות, הוא נראה… סאטטי מידי.

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

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

לכתוב את הגלגל מחדש?

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

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

בסופו של דבר, מישהו יישם את האלגוריתם הזה עבור 1 - 4 מימדים ב C#. האם אפשר להמיר את זה להקס?

####אני מוכן לנסות!


(מיכאל שלמה) #4

אני מקווה שתשאר בחיים ולא תשתגע… :smiley:
בכל מקרה, זה מטורף מה שאפשר להשיג בעזרת מתמטיקה, מה שלא הצלחתי להבין זה איך רעש הזה קשור לעננים. כמו כן, הוא זה לא “כבד” מדי בשביל לשתמש בו ליצירת עננים?


(Itzik Arzoni) #5

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

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

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

####וזה עובד אותו הדבר בדיוק עם שני מימדים:.

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

פרלין תלת מימדי אמיתי נראה כך:

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

#####מבולבל?

לגבי השאלה השניה, האם הוא כבד ליצירת עננים…

אהם…

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

בוא נראה ביישום.


(Itzik Arzoni) #6

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

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

רגע, רגע, זה לא אומר שאני מפסיק פה. אני אנסה ליישם את האלגוריתם החכם יותר, שעל פי ויקיפדיה הוא בסיבוכיות של N^2 ולא 2^N . ההבדל הוא קריטי בביטמפים גדולים. או לפחות ככה נראה…


(מיכאל שלמה) #7

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

התכוונת n^n? ולך על זה! זה נשמע מגניב ומועיל!


(Itzik Arzoni) #8

ניסיון ראשון…

טוב, נתחיל עם השורה התחתונה: נכשלתי. זה מה שיצא:

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

העברת הקוד מC#

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

Int64 ?

בתרגום של הסינטקס עצמו לא היה מסובך במיוחד. זו אמנם הרבה עבודה ידנית של להעביר מילים מתחילת השורה לסופה, אבל סך הכל, הדברים די דומים. לפלאש ActionScript, דרך אגב, יש ממירים אוטומטים. לתרגם את מבני הנתונים של מערך זו לא בעיה. []int בשפת #C הופך מיד ל <Array<Int.
הבעיה התחילה כשהייתי צריך להמיר את טיפוס הנתונים של Long, שזה בעיקרון מספר שלם המורכב מ8 בייטים, 64 סיביות. אז הסתבכתי.
מכיוון שהקס מיועדת להרבה שפות, ולחלק מהשפות אין תמיכה בטיפוס הנתונים הזה, לה בעצמה אין טיפוס בסיסי של מספרים בגודל הזה. עבור כל שפה בנפרד, כמו ג’אווה וC יש לה את מבני הנתונים המיוחדים של אותה שפה, אבל יש לה גם מבנה נתונים אחד שעושה הדמייה של 64 סיביות, על מערכות בהם אין את הטיפוס הזה. כמו JavaScript, השפה אליה כיוונתי.

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

###טוב, טוב התפזרתי.
לא התייאשתי מהאלגוריתם הזה, אבל שמתי אותו בצד לעת עתה.

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

אמשיך לעדכן! :sunglasses:


(Itzik Arzoni) #9

הת’רד הזה נשכח לעת עתה. אבל אני ארכז פה כל מיני אלגוריתמים שנכתבו בהקס, בדיוק לשם כך:
מספר אלגוריתמים שנכתבו על ידי GamePopper:

אלגוריתם של ניקולס (היוצר של הקס) בעצמו: