Komplizierte Mysql abfrage

[rox²³]

Moin ich war lange nicht mehr hier

Ich stehe gerade vor einem Problem besser gesagt vor einem Schönheitsfehler.
Ich habe eine Map 10 x 10 Km groß auf der befinden sich Gegner + mein Spielecharakter.
Die Gegener befinden sich in einer Mysql Datenbank und haben eindeutige Coordinaten auf denen diese sich befinden.
Jetzt möchte ich beim erstellen der Weltkarte nur den jeweiligen Teil von 512 x 512 pixel anzeigen und um die Datenbank zu schonen nur alle Gegner auslesen und anzeigen die sich im Umkreis von 1Km befinden.
Das mache ich ganz einfach in dem ich mit meinen Char Position +- 1Km ermittle und via BETWEEN ermittle.
Das problem ist das dass Ergebniss ja nicht die perfekte Distanz von Char ist sondern nur eine Quadrat um den Char herum der an den ecken zum beispiel viel höher als 1 km liegt.
Ohne lang darüber nachzudenken ist mir bewusst das so eine DB Abfrage evt. sehr lang und komplex werden könnte wenn ich zu gemüte ziehe wie ich schon die Distanznzeige berechne:

Code: Alles auswählen

distance = Math.floor(Math.sqrt(Math.pow(mapx - playerx, 2) + Math.pow(mapy - playery, 2)));

Jetzt meine Frage an die MySql Spezialisten: Gibt es eine Möglichkeit eine DB abfrage so zu erstellen das ich einen Kreisrunden Sichtradius um meinen Char herum bekomme ohne eine eigens entwickeltes Framework für MySQL zu entwickeln was für diese Aufgabe ausgelegt ist oder soll ich lieber die einfache Variante nehmen?

EDIT: es ist verhext aber immer wenn ich hier was poste komme ich nach abschicken selbst auf die Lösung
Ich denke ich lese das ganze mit Between aus und bessere anhand der javascript Lösung der Distanz dann einfach in php das ganze aus so sollte ich nen Kreisrunden radius bekommen.
Wer dennoch ne bessere möglichkeit findet kann das gern posten

[Pyramide]

Ich denke ich lese das ganze mit Between aus und bessere anhand der javascript Lösung der Distanz dann einfach in php das ganze aus so sollte ich nen Kreisrunden radius bekommen.

So würde ich es auch machen. Da MySQL auch Rechenfunktionen hat, könntest du zwar theoretisch auch den komplexen Filter in die WHERE-Bedingung packen, allerdings kann die Datenbank dann bei der Abfrage keinen Index verwenden, sondern müsste immer die komplette Tabelle durchsuchen.

[rox²³]

Da bin ich beruhigt das ich nicht der einzige bin der die Lösung in betracht zieht.
Es sollte ja auch schon etwas DB sparsam sein.
Da der Sichtradius zum einem ja auch die DB entlasten soll wäre ich mit der Rechenfunktionen der MySQL wohl eher nicht auf der optimalen Schiene.

[Miriam]

Also ich habe das mal mit dem Pythagoras in der HAVING Klausel getested.
Konnte dort keine gravierenden zeitlichen Unterschiede herausfinden im Vergleich zur Abfrage mit nur dem BETWEEN in der WHERE Klausel (DB war mit 394,285 Datensätzen bestückt).

Das sah dann in etwa so aus:

Code: Alles auswählen

$distance = 1; // in Deiner Läöngeneinheit
$player_x = 0; // variabel
$player_y = 0; // variabel

$neg_x_diff = $player_x - $distance; 
$pos_x_diff = $player_x + $distance; 
$neg_y_diff = $player_y - $distance; 
$pos_y_diff = $player_y + $distance;

$sql = 'SELECT name, x_pos, y_pos FROM players
        WHERE x_pos BETWEEN ' .  $neg_x_diff . ' AND ' . $pos_x_diff . '
        AND y_pos between ' . $neg_y_diff . ' AND ' . $pos_y_diff . '
        HAVING POW(x_pos, 2) + POW(y_pos, 2) <= ' . pow($distance, 2); 

Annahme: Die Erdkrümmung soll nicht mit berücksichtig werden.

[rox²³]

oh nice

Nein Erdkrümmung gibt es keine.
Werde das gleich mal antesten sieht aber vielversprechend aus

thx

[gn#36]

Die Abfrage berücksichtigt bei dem Kreis allerdings nicht den Abstand zum Spieler. Hierfür müssten die Koordinaten noch mit in die Berechnungen eingehen. So wird die Schnittmenge aus Kreis um 0 und einem Rechteck bestimmt. Having ist ausserdem für aggregierte Abfragen gedacht soviel ich weiß, in diesem Fall würde ich behaupten, dass du kaum einen Unterschied sehen dürftest wenn du den Inhalt der Having Klausel mit in das Where einfügst. So oder so findet eine Vorselektierung mit dem Rechteck statt, anschließend wirfst du noch Leute raus die nicht im Kreis liegen. Da das Rechteck mit einem Index erledigt werden kann wird es so oder so zuerst bestimmt.

[Miriam]

Da habe ich mich durch die Spieler-Koordinaten (0, 0) etwas ins Bockshorn jagen lassen. In einem Spieler zentrierten Koordinatensystem ist das also kein Problem

Die Abfrage muß also lauten:

Code: Alles auswählen

$sql = 'SELECT name, x_pos, y_pos FROM players
        WHERE x_pos BETWEEN ' .  $neg_x_diff . ' AND ' . $pos_x_diff . '
        AND y_pos between ' . $neg_y_diff . ' AND ' . $pos_y_diff . '
        AND POW(' . $player_x . ' - x_pos, 2) + POW(' . $player_y . ' - y_pos, 2) <= ' . pow($distance, 2); 

Zum Thema HAVING Klausel:

Der SQL-Standard sieht vor, dass HAVING nur Spalten in der GROUP BY-Klausel oder solche Spalten referenzieren darf, die in Zusammenfassungsfunktionen verwendet werden. Allerdings unterstützt MySQL eine Erweiterung dieses Verhaltens und gestattet HAVING ferner die Referenzierung von Spalten in der SELECT-Liste und Spalten in äußeren Unterabfragen.

Es gibt doch immer irgendeine Ausnahme. Hab's nun in AND geändert.

[gn#36]

Interessant in dem Zuge könnte auch ein speziell für geodaten gedachter Datentyp sein. Ich vermute mal, dass dann Distanzbestimmungen optimiert werden: http://dev.mysql.com/doc/refman/5.0/en/ ... sions.html

Gibt es für andere Datenbanken ebenfalls.

[Miriam]

Ja, diese Geometrie-Funktionen bringen schon was: http://dev.mysql.com/doc/refman/5.1/de/ ... tions.html
In diesem Zusammenhang sind diese Geometriemodelle auch hilfreich: http://dev.mysql.com/doc/refman/5.1/de/ ... model.html

[rox²³]

Funtioniert wunderbar
Hab mal zum testen übertrieben viel auf die Map gepackt

[ externes Bild ]

vielen Dank nochmal für die schnelle Hilfe.