Die zu Grunde liegende Aufgabe ist es ja, etwas zu schreiben, was Gebrauch von Graphen macht. JustJim hat zwar etwas vorgeschlagen, was "Graphen" als Thema verwendet, allerdings würde das nicht notwendigerweise auch Graphen für Berechnungen verwenden und es dürfte schwierig werden, das einigermaßen interessant (Darstellung, Spielspaß, ...) umzusetzen.
Wegfindungen werden häufig mit Graphen umgesetzt, wie bereits erwähnt. Willst du ein Spiel entwickeln, wäre das Einfachste also etwas, was intern für bspw. die KI eine solche Wegfindung verwendet. Je nachdem, was von euch genau erwartet wird, ist evtl. die Wegfindung an sich bereits genug, um die Aufgabe zu erledigen.
Damit die Wegfindung etwas interessanter wird, könnte es gewisse "Abkürzungen" geben, wie bspw. die in Portal verwendeten Portale o. ä. Eine Mechanik könnte bspw. sein, dass man über das Anpassen der Wege die verwendeten Wege anpasst. So könnten entweder Feinde von einem abgelenkt werden, der Spieler an statisch positionierten Hindernissen vorbei navigiert werden oder etwas ganz anderes gemacht werden. Wichtig wäre nur, was den Weg suchen soll, wohin dieser führen soll, was die Konsequenzen der Ankunft sind und welche Hindernisse es zwischenzeitlich geben kann, genauso wie deren Umgehung oder Beseitigung.
Da es aber "nur" eine Schulaufgabe, solltest du dich da nicht zu sehr übernehmen und etwas kleines, aber ausreichendes machen. Bei Pac Man versuchen die Geister bei jeder Abbiegung einen möglichst passenden (/kurzen) Weg zum Spieler zu finden, der nicht von einem anderen Geist verwendet wird. Das alleine könnte schon ausreichend sein und es ist ein Spiel.