Wegfindung Tiles, direkter Weg?

[Kenji]

Hi flasher

Ich bins wieder einmal mit einem Problem. Und zwar geht es um eine Wegfindung mit Tiles. Ich habe viele einzelne Punkte auf meinem Koordinatensystem. Ich will zuerst abfragen, ob überhaupt ein direkter Weg möglich ist (also von a zu b, respektive von rot zu gelb).
Zuerst dachte ich: Ja locker, und hab den direkten Weg abgefragt. Das Problem. Wenn man eine Linie darüberlegt, stimmt es plötzlich nicht mehr überein...

So sollte es aussehen:



- Was ich nicht will: Jedes einzelne Pixel der Linie abfragen, in welchem Tile es ist
- Das ganze sollte möglichst performant sein, da es ziemlich häufig ausgeführt wird.

Hat da jemand grad ne lösung auf lager?

Besten Dank im Voraus.

Gruss
Kenji

[Gullyking]

Vielleicht helfen dir diese Links weiter.

http://de.wikipedia.org/wiki/A*-Algorithmus
http://www.geosimulation.de/methoden...lgorithmus.htm

[Kenji]

Nein, trotzdem danke.

Mit der Wegfindung habe ich absolut kein Problem, es geht um den direkten Weg, und zwar unter der direkten Linie. Ich will herausfinden, welche Felder von der direkten Linie berührt werden. So wie auf dem Bild oben, die blauen Felder. Es muss doch eine Formel geben oder sowas um das auszurechnen...


EDIT: OK, ich habe mich vielleicht falsch ausgedrückt. Ich meine die Luftlinie. Ich will alle Felder wissen, die auf der Luftlinie liegen.

[Dharokan]

Such doch einfach mal nach 'nem Algorithmus zum Zeichnen einer Linie. Der muss dann ja auch alle Pixel kennen, die von der Linie "berührt" werden.

Vielleicht hilft's ja...