Breitensuche oder doch lieber ein anderer Algo

[dizzy]

Für den allgemeinen Fall dürfte das die beste Möglichkeit sein. Soll heissen: Wenn du keine Randbedingungen sicher hast (z.B. einen maximalen Radius in dem sich, und auch nur DAS nächste Element befinden MUSS), dann wirst du kaum eine andere Chance haben.
Auch so Spielchen wie: Erst jeden 2. testen, bei Misserfolg dann doch mit voller Auflösung scannen sind dann leider nicht mehr drin, da du ja das tatsächlich nächste im 1. Lauf verpassen könntest.

Aber wie wäre es, wenn du im Vorfeld das gesamte Array elementweise durchgehst, und dir eine Art "Karte" baust? Also eine Sammlung aller Koordinaten die nicht nil sind. Dann kannst du via Vektorlängenberechnung von einer Koordinate auf den nächsten Treffer schließen ohne groß zu suchen (zumindest vermeidest zu leere Elemente, ist die Frage wie viel schneller das ist als ein paar sqr(t)s. Hängt davon ab welche Feldart häufiger ist!).
Allerdings ist das für dynamische Systeme wieder nicht so irre gut, da du deine "Karte" ständig up to date halten musst. Wenn du allerdings zum Zeitpunkt der Zuweisung eines Elementes seine Koordinaten kennst, dann lässt sich so eine Karte sehr leicht erstellen! Dann fällt das gesamte Scanning weg.

Und wenn du dann noch massig Speicher "verschwenden" willst, so könntest du gleich zu jedem Element a) seinen nächsten Nachbarn speichern (achtung: die verweisen natürlich immer gegenseitig auf sich!), oder gar b) zu jedem Element alle Entfernungen zu allen anderen Elementen. Dann ließe sich (bei b) auch A* bzw. Bestensuche gut einsetzen.

Gruss,
Fabian