Wie läßt die Server-Spiel-Clients über andere in der Nähe sichtbar Spieler auf effiziente Art und Weise informieren?

Question

Ich arbeite an einem Multiplayer-Flash-Spiel. Der Server informiert jeden Client, was andere Spieler in der Nähe der Spieler sind. diese den Server zu tun hat, zu überprüfen, welche Kunden nahe beieinander sind kontinuierlich. Im Folgenden ist das, was ich in diesem Moment verwenden, als eine temporäre Lösung:

private function checkVisibilities()
{
    foreach ($this->socketClients as $socketClient1)
    { //loop every socket client
        if (($socketClient1->loggedIn()) && ($socketClient1->inWorld()))
        { //if this client is logged in and in the world
            foreach ($this->socketClients as $cid2 => $socketClient2)
            { //loop every client for this client to see if they are near
                if ($socketClient1 != $socketClient2)
                { //if it is not the same client
                    if (($socketClient2->loggedIn()) && ($socketClient2->inWorld())
                    { //if this client is also logged in and also in the world
                        if ((abs($socketClient1->getCharX() - $socketClient2->getCharX()) + abs($socketClient1->getCharY() - $socketClient2->getCharY())) < Settings::$visibilities_range)
                        { //the clients are near each other
                            if (!$socketClient1->isVisible($cid2))
             { //not yet visible -> add
                                 $socketClient1->addVisible($cid2);
                            }
                        }
                        else
                        { //the clients are not near each other
                            if ($socketClient1->isVisible($cid2))
                            { //still visible -> remove
                                $socketClient1->removeVisible($cid2);
                            }
                        }
                    }
                    else
                    { //the client is not logged in
                        if ($socketClient1->isVisible($cid2))
                        { //still visible -> remove
                            $socketClient1->removeVisible($cid2);
                        }
                    }       
               }
         }
     }
}

Es funktioniert gut. Aber bisher habe ich nur mit zwei Spielern in einer Zeit gespielt. Diese Funktion wird Looping jeden Kunden für jeden Kunden. Also, mit 100 Spielern würde die 100 * 100 = 10.000 Schleifen werden jedes Mal, wenn die Funktion ausgeführt wird. Dies scheint nicht den besten oder effizienteste Weg, es zu tun.

Jetzt frage ich mich, was Sie Leute denken über meine aktuelle Setup, und wenn Sie irgendwelche Vorschläge auf einem besseren Weg, um diese Sichtbarkeiten der Handhabung.

Update: Ich habe vergessen zu erwähnen, dass die Welt unendlich ist. Es ist eigentlich „das Universum“. Es gibt keine Karten. Außerdem ist es ein zweidimensionales (2D) Spiel.

Vielen Dank im Voraus.

Answer 1

Die einfachste Lösung ist, die Welt in ein einheitliches Raster zu partitionieren, etwa so:

_|____|____|____|_
 |    |    |    |
_|____|____|____|_
 |    |    |    |
_|____|____|____|_
 |    |    |    |
_|____|____|____|_
 |    |    |    |

Dann Ihre Objekte in jedes Raster Kachel einfügen, die sie sich überschneiden:

_|____|____|____|_
 | @  |    |    |
_|____|____|____|_
 |    |d d |    |
_|____|____|____|_
 |    | d  |  d |
_|____|____|____|_
 |    |    |    |

Jetzt eine Abfrage für Objekte in der Nähe zu tun, müssen Sie nur auf Zellen in der Nähe suchen. Zum Beispiel, um zu sehen, die innerhalb einer Kachel aus dem Player (@), können Sie nur in 9 Fliesen überprüfen müssen, nicht die ganze Karte:

/|////|////|____|_
/|/@//|////|    |
/|////|////|____|_
/|////|d/d/|    |
/|////|////|____|_
 |    | d  |  d |
_|____|____|____|_
 |    |    |    |

Abhängig von Ihrer Welt, jedoch kann diese Technik ziemlich verschwenderisch sein: es könnte eine Menge von leeren Zellen sein. Wenn dies ein Problem wird, können Sie eine komplexere räumlichen Index implementieren.

Answer 2

Das erste, was ich sagen kann, ist, dass der Code von innen nach außen aussieht. Warum haben Sie eine hohe Spiellogik-Funktion, die das Grunzen-Arbeit der Kontrolle zu tun hat, die Kunden in und in der Welt angemeldet sind? Alle, die Vernetzung Sachen sollten aus der Spiellogik entfernt werden, so dass sie auf einer höheren Ebene getan und die In-Game-Logik hat nur die Spieler zu behandeln, die gerade spielen und in der Welt. Dies lässt Sie mit einer einfachen Frage: sind diese zwei Spieler nahe genug zueinander? Eine einfache Abstandsprüfung genügt hier, wie Sie bereits haben.

Das nächste, was ist die Menge der Looping Sie tun zu reduzieren. Die Entfernung ist in der Regel ein Kommutativgesetz, so dass Sie nicht brauchen, um den Abstand zwischen A und B als auch zu überprüfen, wie zwischen B und A. Um dies zu tun, während Ihre ersten Schleife durchläuft alle Kunden, die zweite Schleife muss nur über iterieren alle Clients, die nach dem ersten kommen. Dies halbiert die Anzahl der Iterationen was Sie tun müssen.

Sie müssen auch diese kontinuierlich nicht tun, wie Sie angeben. Sie müssen es nur oft genug, um sicherzustellen, tun, dass das Spiel reibungslos läuft. Wenn die Bewegungsgeschwindigkeit nicht alles ist, dass hohe dann könnten Sie nur diese alle paar Sekunden zu tun haben, denn er ist gut genug zu sein.

Wenn dies immer noch nicht gut genug ist für Sie dann eine Art räumlichen Hashing-Systems, wie durch IANH beschrieben eine gute Möglichkeit zur Verringerung der Anzahl der Abfragen, die Sie tun. Ein Gitter ist am einfachsten, aber eine Art Baumstruktur (im Idealfall selbst Balancing) ist eine weitere Option.

Answer 3

Versuchen Sie, eine Quad-Baum mit Orten der Spieler zu vertreten.
Der Wiki-Artikel hierfür ist hier .
Was sie tut, ist es, die Objekte halten Sie es im Raum geben (Benutzer) in einem Baum, die den Raum aufteilt (Ebene) so viel wie nötig. Wie für die Unendlichkeit Problem - nichts in der Programmierung wirklich unendlich ist, so eine Grenze definieren, die von den Benutzern nicht übergeben werden können (gehen auch für eine sehr große Zahl für eine Koordinate, etwas, das einen Benutzer 100 Jahre oder so dauern wird zu bekommen) .