Finden von nicht abgeschlossenen Plättchen in einem kachelbasierten Spiel

Ich arbeite an einem 2D-Kachel-basierten Spiel und versuche gerade, ein 2D-Äquivalent von Schattenvolumen zum Laufen zu bringen. Ich habe Probleme, die Oberflächen zu finden, die Schatten werfen sollen. Von jedem Punkt im Spiel muss ich entweder die nicht abgeschlossenen Gesichter oder das gesamte Plättchen finden.

Meine Frage ist, wie kann ich diese Kacheln / Kanten bei einem bestimmten Punkt so schnell wie möglich finden?

In der schurkenhaften Community wird viel an diesem Problem gearbeitet.

Auf dieser Seite finden Sie einige Algorithmen und Bibliotheken, die Ihnen möglicherweise helfen. http://roguebasin.roguelikedevelopment.org/index.php?title=Field_of_Vision

Dies ist keine vollständige Antwort, aber hoffentlich hilft es.

Ist Ihre Karte / Kachel statisch oder dynamisch eingestellt? Wenn es statisch, würde ich dringend empfehlen Ihnen , die Offline - Bearbeitung und Precompute so viel wie Sie diese Weise können zu tun. Sie können es auf jede gewünschte Weise tun (Raycasting oder etwas Klügeres), aber es ist Ihnen nicht wirklich wichtig, sehr schnell zu arbeiten, da alles offline geschieht, während Sie Ihre Level "backen". Sie können entweder genau vorberechnen, welche Kacheln von jedem Punkt aus sichtbar sind, oder größere Regionen und alle Kacheln erstellen, die möglicherweise von jeder Region aus sichtbar sind.

Zur Laufzeit sollte die Abfrage nach den sichtbaren Kacheln sehr einfach und sehr schnell sein.

Wenn Sie dynamisch erstellte Levels haben, gilt dies natürlich überhaupt nicht :-)

Hier können Sie sehen, wie ich dies für ein C # -Roguelike implementiert habe . Der Code ist nicht stark optimiert, aber er scheint für mich schnell genug zu sein und (was noch wichtiger ist) sollte ziemlich einfach zu lesen sein. Es handelt sich im Grunde genommen um einen einfachen Schattenwurfalgorithmus, der jeweils einen Oktanten arbeitet.

Ich bin mir nicht sicher, auf welcher Plattform Sie sich befinden, aber ich kann mir keine Plattform vorstellen, die nicht schnell genug wäre, um nur einen Kreis um Ihre Lightcasting-Entitäten zu bilden (es sei denn, es gibt viele von ihnen) und festzustellen, ob die Die Kachel, die in Ihrem Kreisalgorithmus "gezeichnet" werden soll, ist eine feste Kachel und somit lichtblockierend. Von da an wäre es etwas schwieriger, da Sie Kreissegmente verfolgen müssten, die verdeckt sind oder nicht, aber es wäre das, was ich tun würde. Eine andere Möglichkeit wäre, Strahlen in einem Kreis (wieder ziemlich schnell) in den Kachelauflösungsraum zu werfen und jeden Strahl anzuhalten, wenn er auf eine feste Kachel trifft.