וייי long time no see. באתי עם בעיה

[MegaMango]

וייי long time no see. באתי עם בעיה

משלי הפעם. 1. בקרוב יש לי מועד ב' באלגוריתמים 2 ואני חייב להצליח !!! למישהו יש רעיון איך להשיג שאלות טובות? תרגול של הצפנה, רדוקציות, שאלות על גרפים..אלגוריתמים הסתברותיים וחמדנים.. כל דבר יתקבל בברכה :] 2.אררררר התנגשות מלבן במפה >< הגעתי במשחק שאני מתכנת למצב שבו אני צריך לבדוק התנגשויות בין אוביקטים לבין המפה. החלטתי שאין צורך בהתנגשות פוליגונים (מערכת הקרב לא זקוקה לזה ולכן זה ממש overkill) אז אני מסתפק בהתנגשות של מלבן עם המפה. השחקן מיוצג בעזרת מלבן והמפה מיוצגת בעזרת קווים. הבעיה היא שרציתי לעשות גם שתהיה אפשרות להרוס את משטח המפה...כלומר, הקווים של המפה יכולים להסתדר בכל צורה אפשרית. זה יכול להיות עיגול מאוד קטן וזה יכול להיות זיגזג נוראי. איך אני מצליח לעשות התנגשות של מלבן עם המפה? חשבתי למתוח קו מהקצוות של המלבן אל הנקודות שבהן הקצוות צריכות להיות בסוף התנועה (ולסגור אותם)ואז לבדוק אם יש קו שנחתך בקווים האלה או מוכל בהם..אבל זה מיליון עבודה >< יש משהו יודע ופשוט יותר? חשבתי להוסיף גם אפשרויות של טיפוס והליכה על קירות ונראה לי שזה רק מסתבך ככה...

 

[vinney]

המם....

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

 

[MegaMango]

המטרה היא למצוא את הנקודה הראשונה

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

 

[vinney]

המם...

אם השחקן שלך זז מנקודה X לנקודה Y, הוא לא זז בקו בודד, הוא תופס איזשהו שטח בתנועה. תגדיר פוליגון שיכיל את כל השטח הזה, ואז תבדוק אם יש קוים מוכלים או חותכים. זה אכן נעשה בO של N, פר קו, ז"א זה N*M, כשN זה נקודות התוחמות את השטח המדובר, וM זה מספר הקוים הנבדקים. שוב, כל הדברים האלה לא מסובכים, אתה בטח מכיר אותם, הבעיה היא למצוא את אותן M הקוים שאתה צריך לבדוק מול השטח שלך, ז"א - אתה צריך לבדוק על אילו ריבועים יעבור השחקן שלך, כדי לבדוק את הקוים מתוך הריבועים האלה. אסימפטוטית זה יכול להיות קצת יקר, אבל תכל'ס זה נראה לי אפשרי (אלא אם כן יש לך הרבה קוים ישרים שעוברים דרך כמה ריבועים, מהתיאור שלך, נשמע כאילו בכל ריבוע יש הרבה קוים, לא בכל קו יש הרבה ריבועים, כך שבמקרה שלך מהר מאוד תמצא פגיעה). יכול להיות שאני לגמרי לא בכיוון? לא יודע, לא ממש עסקתי בזה ברצינות אי פעם

 

[MegaMango]

מה שאתה אומר באמת היה

הכיוון שלי , אבל יש הרבה ריבועים לקו בעיקר... הביע ההיא שאני צריך למצוא את כל הקווים שמוכלים\חותכים את השטח של התנועה ומביניהן לבדוק את הראשון שיתנגש בצלע התחתונה או הצדדית של המלבן. אין לי כחחחחחחחחח למה הייתי חייב לעשות מפה עם קווים? למה החלטתי שאפשר להרוס אותה? למה אני עושה את זה לעצמי?!?! למה אני בכלל מתכנת את המשחק הזזה? >_____< אוף אוףא וףא ו אףוא ואףאוף

 

[vinney]

מה היה השיקול שלך לבחירת מבנה

נתונים?

 

[MegaMango]

החלטתי שזה יוצא הכי יעיל

אם הייתי משתמש במבנה ממויין לכל האוביקטים(אפילו עם איזשהו hash) זה עדיין היה יוצא פחות מהיר. זה אמור להיות משחק פלטפורמה כבד מאוד מאוד. מפות ששוקלות כמה עשרות מגה ואורכן הוא 30X4 מסכים (הרזולוציה היא 800 על 600), מלאא אוביקטים.. למשל, בחלק מהמפה, יש עצים. עץ אחד , לדוגמא, יכיל בו מלאא פרפרים ורודים ונחמדים. כשאחד השחקנים מתקרב לעץ, כל הפרפרים בו-זמנית מתחילים להתעופף בכל רחבי המסך(לא, אנימציה לא תספיק כאן) ולכן כל פרפר הוא אוביקט. נכון, אני יכול לעשות שהפרפים יהיו אוביקט נפרד ושלא תהיה אפשרות לפגוע בהם ואין אפילו צורך לשלב אותם במבנה הנתונים..אבל מה יותר מהנה מאשר לירות קרן לייזר ולראות פרפרים מתמוססים? אם כל ריבוע במשחק צריך להצביע על האובייקטים שמוכלים בו(או חלקית מוכלים בו) אז מתי שאובייקט זז, הוא צריך להחליף את הריבועים שלו -אז כל אוביקט מכיל גם מצביעים לכל הריבועים שבהם הוא נמצא. יש לי עדיין בעיות עקרוניות כמו מה למשל צריך לקרות אם שחקן עף ממש ממש מהר והוא נתקע פתאום בפיסת אדמה מעופפת (ממש קטנה, שנוצרה מתוך הרס של כל האדמה סביבה). הגיוני שפיסת האדמה המעופפת תעצור אותו?(!!) לתת לו פשוט לעבור דרכה? בלע! ומה קורה אם החלטת להרוס חלק ממשטח שעומדים עליו אוביקטים? אם היית הורס את המשטח, היית מצפה שהאוביקטים יתחילו ליפול.. אבל איך נדע מה הם האוביקטים בשטח שהרסת? כדי לייעל את זה, צריך שגם כל קו יכיל פוינטרים לאוביקטים ש"דבוקים" אליו! אוף. זה פשוט סיוט.

 

[vinney]

יש לך שכבות?

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

 

[MegaMango]

ירדתי מכל העניין.

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

 

[vinney]

לגבי המבחן לא יכול לעזור לך../images/Emo10.gif

אבל בקישורים יש הרבה בנושא, בעיקר מבני נתונים, אבל גם תורת הגרפים, תחטט

 

[MegaMango]

חיטטתי ..לא עוזר \=

 

[gil levi]

בקשר לשאלה הראשונה

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

 

[MegaMango]

ווו נראה מעניין! תודה. אני אתחיל

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

 

[vinney]

נוסף לקישורים, ../images/Emo51.gif../images/Emo70.gif

 

[MegaMango]

עוד שאלה.

במבחן הקודם באלגו' 2, במועד א', הייתה שאלה שעד עכשיו אין לי מושג מה הפיתרון שלה. שאלה אמריקאית שאומרת , בהתייחסות לאלגוריתם הלא משופר למציאת מספרים ראשוניים (זה שמשתמש במשפט פרמה בלי המשפט הקטן של המוד כדי לפסול תוך כדי) , מה יכולה להיות ההסתברות להצלחה? 1. אחד 2. בין חצי לאחד 3. ייתכן שמתחת לחצי אך לבטח גדול מאפס 4. יכול להיות גם אפס השאלה הזו מנוסחת מוזר! מה זה "יכולה להיות" ? אם ידוע שהמספר שקיבלנו ובדקנו באלגוריתם הוא מספר קרמייקל והמספר שאנחנו בודקים זר לו (אך פריק) , אז אנחנו יודעים שההסתברות היא אפס. אבל זו הסתברות מותנית! מה הטעם בלשאול מה יכולה להיות ההסתברות , אם יש רק הסתברות אחת כללית כשלא יודעים שום דבר על הנתונים? אוף ><