Karte optimal ausnutzen

Wenn sich ein neuer Spieler in meinem Browsergame anmeldet, dann kriegt er auf einer Karte von 200x200 Felder per Random ein Startfeld zugeteilt. Er hat ein Sichtradius von 4 Feldern. Dort kann er dann seine Stadt aufbauen oder die Umgebung auskundschaften.

Leider kommt es oft vor, dass Spieler, die sich neu anmelden, auf einem Feld landen, wo es schon anderen Städte in der Nähe hat.

Nun zu der eigentlichen Frage:
Gibt es einen einfachen Algorithmus, der mir das Feld liefert, dass am weitesten von allen umliegenden Siedlungen entfernt ist?

Einen Algorythmus wirds da nicht geben. Wenn dann muss hierzu alle Städte, Objekte und Co abfragen und dann schauen wo noch Platz ist.

Problem was du hier hast, ist eindeutig deine Random-Verteilung.
Eine Karte von 200x200 Feldern klingt vielleicht auf den Ersten Blick recht gross (40000 Felder). Doch wenn du die Spieler wild in der Gegend umherpflanzt dann verschwendest du enormen Spielraum.
Wenn ein Starterland von 9x9 Feldern für neue Spieler da sein sollen (Stadt mit 4 Feldern pro Richtung) dann sind immerhin noch Platz für rund 4400 Spieler. Wenn du aber jetzt schon wild Städte gepflanzt hast, dann sind einige Städte mit unter 15 Felder voneinander entfernt. Doch eine Stadt kannst du dazwischen dann nicht mehr setzen, weil der Mindestraum geschnitten wird.

Solch eine Karte kannst du nur einrichten wenn du ein Schachbrettmuster verwendest was der Reihe nach mit Spielern füllst. Sieht vielleicht langweilig aus, aber auf die Weise werden sich neue und alte Spieler kaum begegnen, was gleich ein Noobschutz darstellt.

Für dein Random-System da müsste die Karte deutlich grösser sein! Wenn du 4000 Spieler auf 1000x1000 Feldern platzierst so hätte jeder Spieler noch 250 Landfelder die er besiedeln und bebauen kann. Da fällt es dann auch nicht so auf, dass der Nachbar vielleicht nur 15 Felder entfernt ist - solange man zur anderen Seite expandieren kann. Bloss wenn sich die Spieler so schon auf die Füsse treten und per Zufall ein Neuling zwischen 2 alte Spieler gesetzt wird - welche evtl. auch grade noch im Krieg sind - dann kannst du dir ausmalen wie lange sich der Neuling in deinem Spiel aufhalten wird.

Ich denke das ist am leichtesten direkt in MySQL zu lösen, du gibst die Bedingungen an und wählst als Sortierung RAND(), dann kannst du einfach den ersten Datensatz verwenden.

Aus den Manual-Kommentaren dev.mysql.com/doc/refman/5.1/en/select.html:
> SELECT * FROM foo ORDER BY RAND(NOW()) LIMIT 1;

(Das Problem das Mudder erwähnt musst du natürlich vorher lösen.)

Du kannst auch das Schachfeldsystem von Mudder und Zufall gleichzeitig nutzen. Leg einfach die einzelnen Schachfelder fest, rechne dir aus auf welchen Koordinaten neue Städte entstehen können und such dir davon eine zufällige aus.

Danke für die Tipps. Ich werde es aber warscheinlich so lösen:

Die Karte wird aufgeteilt in 16 Blöcke a 50x50 Felder. Von jedem der Blöcke ermittle ich die Anzahl Siedlungen und weise dann dem Spieler via RAND() ein Feld zu, dass sich in dem Block mit den wenigsten Siedlungen befindet.

Das löst nicht gerade alle Probleme, ist aber einfach :wink:

Naja du musst es letztenendes wissen..

Nur die Variante verhindert nicht, dass neue Städte auf alte gesetzt werden. Ich kenne zwar auch dein Spiel nicht, doch ein neuer Nachbar, der plötzlich mitten im Reich auftaucht, wird nur von wenigen Spielern freundlich aufgenommen!

Warum machst du es nicht so wie (glaub ich) alle? Jeden Spieler (in deinem Fall in einem bestimmten Abstand zueinander) nebeneinander platzieren?

nebeneinander... hört sich arg langweilig an.... dann eher über das mögliche areal ein kästchensystem legen. die kästchen halt X mal X Felder groß (je nach wunsch) und dann per zufall ein noch freies kästchen aussuchen
und vielleicht als zusatz dann wiederum darin eines der felder zufällig auswählen..

finde ich viel schöner...

Es sieht vielleicht schöner und "wilder" aus, doch sobald es ein Spiel ist wo die Wegstrecke berechnet wird und Zeit kostet wäre sie recht zweifelhaft.

Ein neuer Spieler der zwischen 2 alte gesetzt wird hat keine Chance sich ins Spiel zu integrieren, sondern der wird nur eine nahgelegene Raidfarm. Wenn man die Spieler Reihe an Reihe legt, so sieht das vielleicht langweilig aus.. aber das Spieleralter (im Spiel) und der jeweilige Fortschritt sind mit dem des Nachbarn recht gleich.

Ansonsten sollte aber auch bei fortschreitendem Spiel und gelöschten, inaktiven Spielern die immer größer werdenden Lücken betrachtet werden. Wenn man sich als Spieler allein gelassen fühlt ohne Nachbarn wäre das auch doof. Dann ist mir ein neuer Nachbar lieber, nur darf dann das Spielprinzip nicht aus Raiden und nix weiter bestehen. Gibt ja solche Raidspiele wo die Altgebiete immer dünner besiedelt sind.

Also ich sehe das Problem eher darin, dass man mit zufälliger Verteilung sehr viel Platz "verschwendet".

Der "alte gegen neue"-Konfikt kann man leicht mit einer gestaffelten Zufallsverteilung lösen.
z.B. könnte man abhängig von der Spieleranzahl einen Kreisbereich festlegen in dem neue Spieler zufällig verteilt werden, so dass neue Spieler immer weiter vom Zentrum entfernt sind.
Allerdings muss man abwägen können, wieviele Spieler in die jeweiligen Bereiche passen und sollen (damit es nicht zu leer bleibt). Perfektionisten könnten auch noch ausgedünnte Bereiche wieder auffüllen.
Performenz Probleme sehe ich da keine, weil die Berechnung nur einmal pro neuem Spieler durchgeführt werden muss und bei einfachen Formen auch leicht umzusetzen ist.

Bei The West hab ich weniger das Problem, dass die alten Spieler die neuen angreifen. Das Ziel des Spieles ist: gemeinsam gehen die KI zu kämpfen. Ein neuer Spieler braucht aber einige dutzend freie Felder um seine Siedlungen aufzubauen. Die können ganz gut etwas wild verteilt sein.