Im Vergleich zu anderen Punkten den weitesten Punkt in einem Raster finden

Dies ist der einfachste Algorithmus, den ich mir vorstellen kann, der immer noch gute Ergebnisse liefert. Es prüft nur 9 mögliche Positionen: die Ecken, die Mitte der Seiten und der Mittelpunkt. Die meiste Zeit landet der Spieler in einer Ecke, aber Sie brauchen offensichtlich mehr Positionen als Feinde.

Der Algorithmus läuft auf meinem i5-Desktop in 0,013ms. Wenn Sie Mathe.pow () durch Mathe.abs () ersetzen, kommt das auf 0,0088 Millisekunden herunter, allerdings mit weniger zuverlässigen Ergebnissen. (Seltsamerweise ist das langsamer als meine andere Antwort, die Trigonometrie-Funktionen verwendet.)

Wenn Sie das Code-Snippet (wiederholt) ausführen, wird das Ergebnis mit zufällig positionierten Feinden in einem Canvas-Element angezeigt.

Das ist ähnlich wie das, was Sie bereits tun, aber mit zwei Durchgängen, bei denen der erste Durchgang ziemlich grob sein kann. Reduziere zuerst die Auflösung. Teilen Sie das 500x500-Gitter in 10x10-Gitter, von denen jedes 50x50 ist. Bestimmen Sie für jedes der resultierenden 100 Subgrids, welche mindestens einen Gegner haben und lokalisieren Sie das Subgitter, das am weitesten von einem Subgitter entfernt ist, das einen Feind enthält. In diesem Stadium gibt es nur 100 Subgrids, über die man sich Sorgen machen muss. Sobald Sie das Subgitter gefunden haben, das am weitesten von einem Feind entfernt ist, erhöhen Sie die Auflösung. Dieses Subgitter hat 50x50 = 2500 Quadrate. Machen Sie Ihren ursprünglichen Ansatz mit diesen Quadraten. Das Ergebnis ist 50x50 + 100 = 2600 Quadrate zum Verarbeiten statt 500x500 = 250.000. (Passen Sie die Zahlen für den Fall an, in dem es nicht 500x500 gibt, aber mit der gleichen Grundstrategie).

Hier ist eine Python3-Implementierung. Es verwendet zwei Funktionen:

1) fullResSearch(a,b,n,enemies) Diese Funktion nimmt eine Reihe von Feinden, eine Eckenposition (a,b) und eine int, n , und findet den Punkt im nxn-Quadrat der Positionen, deren obere linke Ecke (a, b) und findet den Punkt in dem Quadrat, dessen maximale Entfernung zu einem Feind maximal ist. Es wird nicht angenommen, dass die Gegner in diesem nxn-Raster sind (obwohl sie das sicher sein können).

2) findSafePoint(n, enemies, mesh = 20) Diese Funktion nimmt eine Gruppe von Feinden auf, von denen angenommen wird, dass sie sich im nxn-Gitter befinden, beginnend bei (0,0). mesh bestimmt die Größe der Subgrids, standardmäßig 20. Das gesamte Grid wird in mesh x mesh subgrids aufgeteilt (oder etwas kleiner entlang der Grenzen, wenn mesh nicht n teilt), was ich denke von als Territorien. Ich nenne ein Territorium ein feindliches Territorium, wenn es einen Feind darin hat. Ich erstelle die Menge der feindlichen Gebiete und gebe sie an fullResSearch mit dem Parameter n dividiert durch mesh anstelle von n weiter. Der Rückgabewert gibt mir das Gebiet, das am weitesten von einem gegnerischen Gebiet entfernt ist. Ein solches Gebiet kann als ziemlich sicher angesehen werden. Ich füttere dieses Gebiet wieder in fullResSearch , um den sichersten Punkt in diesem Gebiet als Gesamtrückgabefunktion zu finden. Der resultierende Punkt ist entweder optimal oder nahezu optimal und wird sehr schnell berechnet. Hier ist der Code (zusammen mit einer test -Funktion):

Ein typischer Lauf:

(Ich habe mit fullResSearch auf dem gesamten Gitter verifiziert, dass (271,499) tatsächlich optimal für diese Feinde ist)

Diese Methode betrachtet alle Feinde vom Mittelpunkt aus, prüft die Richtung, in der sie sich befinden, findet den leersten Sektor und gibt dann einen Punkt auf einer Linie durch die Mitte dieses Sektors zurück, 250 von der Mitte entfernt. < br> Das Ergebnis ist nicht immer perfekt, und der sichere Platz ist nie in der Mitte (obwohl das hinzugefügt werden könnte), aber vielleicht ist es gut genug.

Der Algorithmus läuft mehr als eine Million Mal pro Sekunde auf meinem i5-Desktop, aber ein Telefon ist vielleicht nicht so gut mit Trigonometrie. Der Algorithmus verwendet 3 Trigonometriefunktionen pro Feind: atan2 (), cos () und sin (). Diese werden wahrscheinlich den größten Einfluss auf die Ausführungsgeschwindigkeit haben. Vielleicht könnten Sie das cos () und sin () durch eine Nachschlagetabelle ersetzen.

Führen Sie das Code-Snippet aus, um ein Beispiel mit zufällig positionierten Feinden zu sehen.

Hier ist eine interessante Lösung, aber ich kann die Effizienz nicht testen. Bilden Sie für jeden Feind eine Reihe von Zahlen aus jeder Zahl, beginnend mit eins und erhöht sich für jede Entfernung um eins. Vier Anfangslinien werden von den vier Kanten kommen und jedes Mal, wenn Sie weiter hinausgehen, erstellen Sie eine weitere Linie, die in einem Winkel von 90 Grad herauskommt, und erhöhen auch die Anzahl jeder Abstandsänderung. Wenn die Nummernzeile auf eine bereits erstellte Nummer trifft, die kleiner ist als diese, wird sie nicht überschrieben und erreicht nicht weiter. Das bedeutet im Wesentlichen, dass wenn die Linien eine Nummer kleiner als diese finden, keine weiteren Gittermarkierungen überprüft werden, wodurch das gesamte Gitter für alle Feinde überprüft werden muss.

}

Hier ist der Code, den ich verwendet habe, um das gesamte Grid abzubilden. Das Schöne daran ist, dass die Häufigkeit, mit der die Zahl überprüft / geschrieben wird, nicht so sehr von der Anzahl der Gegner auf dem Bildschirm abhängt. Mit einem Counter und zufällig generierten Feinden konnte ich folgendes bekommen: 124 Gegner und 1528537 Checks, 68 Gegner und 1246769 Checks, 15 Gegner und 795695 500 Gegner und 1747452 Checks. Dies ist ein großer Unterschied im Vergleich zu deinem früheren Code, der die Anzahl der Gegner * Anzahl der Felder. Für 124 Gegner hätten Sie 31000000 Checks gemacht, während dies 1528537 getan hätte, was weniger als 5% der Anzahl der normalerweise durchgeführten Checks ist.

Triangulieren die Feinde (es gibt weniger als 5?); und trianguliere jede Ecke des Gitters mit dem nächsten Gegnerpaar. Der Umkreis von einem dieser Dreiecke sollte ein anständiger Ort sein, um wieder zu spawnen.

Nachfolgend finden Sie ein Beispiel in JavaScript. Ich habe die Canvas-Methode aus der Antwort von m69 zur Demonstration benutzt. Die grünen Punkte sind die Kandidaten, die getestet wurden, um zu dem blau gefärbten Vorschlag zu gelangen. Da wir die Ecken triangulieren, werden sie hier nicht als Lösung angeboten (vielleicht können die zufällig näher liegenden Lösungen für einen Spieler aufregend sein? Alternativ können Sie auch die Ecken testen ...).