Betretbaren Bereich einfärben? (Algorithmus gesucht)



  • Hi,
    Ich arbeite gerade an einem rundenbasierenden Spiel, welches nicht tilebasiert ist. Der Spieler ist umgeben von Hindernissen(wenn nötig können diese als Oval angenommen werden) und hat eine bestimmte Reichweite, die er gehen kann. Nun möchte ich den betretbaren Bereich einfärben.
    Als Skizze(Das Kreuz ist der Spieler, der Rest Hindernisse)
    http://imagesload.net/img/passable.png
    Wie fange ich das am besten an?



  • Ich würds so machen: du berechnest approximiert den Bereich, den du ohne Hindernisse erreichen kannst. Also nur wirklich grob. Dann legst du einen Gitternetzgraphen* über diesen Bereich, wirfst die Knoten raus auf denen Hindernisse liegen, und berechnest dann einen auf das Problem optimierten Dijkstra.** Dann färbste halt die Umgebung um jeden erreichbaren Knoten ein.

    *oder den Graphen, der deinen Wegfindungsalgorithmus am Besten beschreibt.
    **Sollte hier auf ne Breitensuche mit maximaler Tiefe hinauslaufen, sofern du nur Hindernisse und nicht zusätzlich noch unterschiedlich schwere Terrains hast.


Log in to reply