Σχεδιασμός και υλοποίηση σοβαρού παιγνίου για τον υπολογισμό κύκλων και μονοπατιών Euler
| datacite.contributor.RelatedPerson | Χρήστος Κακλαμάνης | |
| datacite.contributor.RelatedPerson | Δημήτρης Τσώλης | |
| datacite.contributor.Supervisor | Εύη Παπαϊωάννου | |
| dc.contributor.author | Πολυδωρόπουλος, Στέφανος-Ιωάννης | |
| dc.contributor.other | Polydoropoulos, Stefanos-Ioannis | |
| dc.date.accessioned | 2025-09-22T05:46:17Z | |
| dc.date.available | 2025-09-22T05:46:17Z | |
| dc.date.issued | 2025-09-19 | |
| dc.degree | graduateThesis | |
| dc.description.abstract | Από την αρχαιότητα, η κατανόηση και η επίλυση προβλημάτων αποτέλεσαν θεμέλια της εξέλιξης του ανθρώπινου πολιτισμού, επηρεάζοντας κάθε πτυχή της ανθρώπινης δραστηριότητας. Ο άνθρωπος παρατήρησε ότι μπορούσε να μοντελοποιήσει τις σχέσεις και τις αλληλεπιδράσεις μεταξύ τόπων, προσώπων ή εννοιών, χρησιμοποιώντας δομές, που ονομάζονται γραφήματα. Όταν ένα γράφημα αναπαριστά κάποιο δίκτυο, τότε οι κορυφές του λέγονται κόμβοι και οι ακμές του σύνδεσμοι. Έτσι, η δομή πολύπλοκων συστημάτων και δικτύων έγινε πιο σαφής και κατανοητή, οδηγώντας σταδιακά στην ανάπτυξη της θεωρίας γραφημάτων. Το πρώτο καταγεγραμμένο πρόβλημα της θεωρίας γραφημάτων αποδίδεται στο γνωστό πρόβλημα των επτά γεφυρών του Königsberg, το οποίο μελετήθηκε και λύθηκε από τον Ελβετό μαθηματικό Leonhard Euler το 1736. Το πρόβλημα απασχολούσε τους κατοίκους της πόλης και αφορούσε το κατά πόσο είναι δυνατόν να ξεκινήσει κανείς από ένα σημείο, να διασχίσει όλες τις γέφυρες που ένωναν τις τέσσερις περιοχές της πόλης ακριβώς μία φορά, και να επιστρέψει στο αρχικό σημείο. Η αρνητική απάντηση του Euler και η μεθοδολογία του θεμελίωσαν την έναρξη της μελέτης διαδρομών σε γραφήματα, εισάγοντας τους όρους μονοπάτι Euler και κύκλος Euler, δηλαδή ακολουθίες κορυφών και ακμών που διασχίζουν κάθε ακμή του γραφήματος ακριβώς μία φορά. Οι ακολουθίες αυτές παραμένουν μέχρι σήμερα αντικείμενο μελέτης αλλά και εφαρμογής σε πολλούς επιστημονικούς τομείς. Στη σύγχρονη εποχή, προβλήματα όπως η εύρεση διαδρομής που διασχίζει κάθε δρόμο σε ένα αστικό δίκτυο ή η ανακατασκευή αλληλουχιών DNA στη βιοπληροφορική, μπορούν να διατυπωθούν ως προβλήματα εύρεσης μονοπατιών ή κύκλων Euler. Η κατανόηση του προβλήματος, είναι επομένως χρήσιμη όχι μόνο σε θεωρητικό επίπεδο, αλλά και για την επίλυση πραγματικών προβλημάτων. Ένας αποτελεσματικός τρόπος, ώστε όσοι ενδιαφέρονται, να κατανοήσουν το μονοπάτι και τον κύκλο Euler, καθώς και να εξοικειωθούν με τη διαχείριση πρακτικών στιγμιότυπων του προβλήματος, είναι μέσω παιχνιδιών που προσφέρουν διαδραστική και βιωματική μάθηση. Τα σοβαρά παίγνια (serious games) αποτελούν ψηφιακές εφαρμογές, οι οποίες, αξιοποιώντας αρχές και μηχανισμούς παιχνιδιών, έχουν σαν κύριο στόχο την εκπαίδευση και την μάθηση του παίκτη και όχι μόνον την ψυχαγωγία του. Μέσω της αλληλεπίδρασης, της διαδραστικότητας και της αίσθησης επιτεύγματος που προσφέρουν, τα σοβαρά παίγνια λειτουργούν σήμερα ως αποτελεσματικά εργαλεία διδασκαλίας και κατανόησης σύνθετων εννοιών. Στο πλαίσιο της παρούσας διπλωματικής εργασίας παρουσιάζεται το σοβαρό παίγνιο «Τα νησιά του Επίλεκτου» («Islands of the Chosen One») που αποσκοπεί να βοηθήσει φοιτητές ή όσα άτομα ενδιαφέρονται να κατανοήσουν τα προβλήματα εύρεσης μονοπατιών και κύκλων Euler και να πειραματιστούν με σχετικές αλγοριθμικές λύσεις από την βιβλιογραφία. Σύμφωνα με την πλοκή του παιχνιδιού, οι παίκτες είναι εξερευνητές που καλούνται να κατασκευάσουν – εφόσον υπάρχουν – μονοπάτια και κύκλους Euler μέσα από συμπλέγματα νησιών, συνδεδεμένα μεταξύ τους. Οι παίκτες μπορούν να επιλέξουν να παίξουν είτε σε έναν μοναδικό γύρο, είτε σε επίπεδα. Στον μοναδικό γύρο, οι παίκτες καθορίζουν το επιθυμητό επίπεδο δυσκολίας τους, παρέχοντας τις απαραίτητες παραμέτρους για την δημιουργία τυχαίων γραφημάτων, που αντιστοιχούν στα συμπλέγματα νησιών και τις συνδέσεις μεταξύ τους. Τα επίπεδα περιλαμβάνουν τρεις επιλογές διαβαθμισμένης δυσκολίας «Αρχάριος», «Κανονικός», «Προχωρημένος», όπου τα γραφήματα, δηλαδή τα συμπλέγματα των νησιών, δημιουργούνται αυτόματα από το ίδιο το παιχνίδι. Και στην περίπτωση του μοναδικού γύρου και στην περίπτωση των επιπέδων, πριν τους ζητηθεί να σχεδιάσουν έναν κύκλο ή ένα μονοπάτι Euler, οι παίκτες καλούνται πρώτα να προσδιορίσουν αν υπάρχουν τέτοιοι κύκλοι ή μονοπάτια. Η σωστή απάντηση προϋποθέτει κατάλληλο θεωρητικό υπόβαθρο στην θεωρία γραφημάτων, ενώ ο σχεδιασμός κύκλων ή μονοπατιών Euler απαιτεί γνώση των αλγοριθμικών λύσεων που προτείνονται από την βιβλιογραφία. Το σοβαρό παίγνιο που υλοποιήσαμε επιτρέπει στους παίκτες να δοκιμάσουν και να ενισχύσουν τις θεωρητικές τους γνώσεις, εφαρμόζοντάς τις σε πρακτικό επίπεδο. Το παιχνίδι μας είναι προς το παρόν διαθέσιμο στα αγγλικά και στα ελληνικά και είναι ελεύθερα προσβάσιμο μέσω οποιουδήποτε προγράμματος περιήγησης ιστού. Έχει δημιουργηθεί χρησιμοποιώντας την Godot, μια πλατφόρμα για ανάπτυξη παιχνιδιών ανοιχτού κώδικα, που είναι διαδεδομένη λόγω των ενσωματωμένων εργαλείων της, που διευκολύνουν τη δημιουργία σύνθετων διεπαφών χρήστη. | |
| dc.description.translatedabstract | Since ancient times, the understanding and solving of problems have been fundamental to the evolution of human civilization, influencing every aspect of human activity. Humans observed that they could model the relationships and interactions between places, people, or concepts, by using structures called graphs. When a graph represents a network, its vertices are called nodes and its edges are called links. In this way, the structure of complex systems and networks became clearer and more comprehensible, gradually leading to the development of graph theory. The first recorded problem in graph theory is attributed to the famous Seven Bridges of Königsberg problem, which was studied and solved by the Swiss mathematician Leonhard Euler in 1736. The problem concerned the citizens of the city and addressed whether it was possible to start from one point, cross all seven bridges that connected the city's four areas exactly once, and return to the starting point. Euler's negative answer and his methodology established the beginning of the study of routes in graphs, introducing the terms Eulerian path and Eulerian cycle—sequences of vertices and edges that traverse every edge of a graph exactly once. These sequences remain to this day a subject of study and application in many scientific fields. In the modern era, problems such as finding a route that traverses every street in an urban network or reconstructing DNA sequences in bioinformatics, can be formulated as problems of finding Eulerian paths or cycles. The understanding of the problem is therefore useful not only on a theoretical level but also for solving real-world problems. An effective way for those interested to understand the Eulerian path and cycle, as well as to become familiar with managing practical instances of the problem, is through games that offer interactive and experiential learning. Serious games are digital applications that, by utilizing game principles and mechanics, have as their main goal the player's education and learning, rather than just their entertainment. Through the interaction, interactivity, and sense of achievement they offer, serious games now function as effective tools for teaching and understanding complex concepts. In the context of the present diploma thesis, we present the serious game «Islands of the Chosen One», which aims to help students and other interested people understand the problems of finding Eulerian paths and cycles and experiment with relevant algorithmic solutions from the literature. According to the game’s narrative, players are explorers tasked with constructing—if they exist—Eulerian paths and cycles through interconnected island complexes. Players can choose to play either a single round or through layers. In the single round, players set their desired difficulty level by providing the necessary parameters for the creation of random graphs that correspond to the island complexes and their connections. The levels include three graded difficulty options—«Beginner», «Normal» and "Advanced"—where the graphs (i.e., the island complexes) are automatically generated by the game itself. In both the single round and the layers, before being asked to design an Eulerian cycle or path, players are first challenged to determine if such cycles or paths exist. The correct answer requires an appropriate theoretical background in graph theory, while the design of Eulerian cycles or paths requires knowledge of the algorithmic solutions proposed in the literature. The serious game we implemented allows players to test and enhance their theoretical knowledge by applying it at a practical level. Our game is currently available in English and Greek and is freely accessible through any web browser. It was created using Godot, an open-source game development platform that is popular due to its built-in tools, which facilitate the creation of complex user interfaces. | |
| dc.identifier.uri | https://hdl.handle.net/10889/30330 | |
| dc.language.iso | el | |
| dc.rights | Attribution 4.0 International | en |
| dc.rights.uri | http://creativecommons.org/licenses/by/4.0/ | |
| dc.subject | Σοβαρά παιχνίδια | |
| dc.subject | Συμπλέγματα νησιών | |
| dc.subject | Εξερεύνηση | |
| dc.subject | Κύκλοι και μονοπάτια Euler | |
| dc.subject | Αλγόριθμος του Fleury | |
| dc.subject | Μηχανή παιχνιδιών Godot | |
| dc.subject.alternative | Serious game | |
| dc.subject.alternative | Island complexes | |
| dc.subject.alternative | Explorers | |
| dc.subject.alternative | Euler circuit | |
| dc.subject.alternative | Euler path | |
| dc.subject.alternative | Fleury algorithm | |
| dc.subject.alternative | Godot game engine | |
| dc.title | Σχεδιασμός και υλοποίηση σοβαρού παιγνίου για τον υπολογισμό κύκλων και μονοπατιών Euler | |
| dc.title.alternative | Design and development of a serious game for Euler circuits and paths |