Algorithmus für Zufallsverteilung

Hi,
ich suche einen Algorithmus für eine gleichmässige Zufallsverteilung innerhalb eines zweidimensionalen Feldes. Anwendungsgebiet (Beispiel):
Ich habe eine Karte mit 100 x 100 Feldern und möchte auf dieser Karte irgendwelche Dinge verteilen. Diese Verteilung soll rein zufällig sein, aber es darf zu keinen Häufungen kommen.
Fällt jemandem was zu dem Thema ein?

Hi Agmemon...
Ich weis jetzt nicht genau, wie du es machen willst, aber hier sind 2 Lösungsvorschläge:
1. Wenn deine Karte immer gleich groß ist, kannst du direkt per rand($x,$y) 2 Koordinaten und Dinge ausdenken. Die Dinge, die du platzieren möchtest musst du dann auch durchnummerieren.
Danach halt in die DB eintragen.
2. Du kannst dir auch alle freien Felder aus der DB holen und dann folgendes machen:

$anz_rows = mysql_num_rows($qry_result);
$anz_rows--; //Reihenanzahl-- weil in dem Result die Zählung bei Reihe 0 beginnt
$zufallsergebnisreihe = rand(0,$anz_rows);
mysql_data_seek($qry_result);
$zufallsergebnis = mysql_fetch_assoc($qry_result);
?>
Somit hast du ein zufälliges freies Feld aus der DB ausgewählt und musst dir nur noch den Gegenstand ausdenken und ihn Platzieren (siehe oben).
mfg
PS: Ich will ein
SELECT RANDOM feld1, feld2, feld3 FROM table ...
haben!

Original von Agmemon
Diese Verteilung soll rein zufällig sein, aber es darf zu keinen Häufungen kommen.
Fällt jemandem was zu dem Thema ein?

Hm, es könnte auch rein zufällig zu einer Häufung kommen ;-) Ansonsten würde ich hier starten: en.wikipedia.org/wiki/Pseudorandom_number_generator. Pragmatischer Ansatz wäre evtl. den random generator zu verwenden, den Du hast und wenn Du ein neues Ding verteilst, zu gucken ob es eine Häufung geben würde und dann ggf. eine neue Zufallszahl zu ziehen.
Oder vielleicht einen Bereich einer geringsten Häufung ermitteln und dann in diesem Bereich zufällig plazieren.

Wenn keine Häufungen auftreten dürfen brauchst du keinen Zufallsgenerator, dann kannst du auch einen Mechanismus a la "alle X Felder Item A droppen, alle Y Felder Item B usw.". Ansonsten ist eine simple Zufallsverteilung einfach.
1. Jedes Item, welches verteilt werden kann, kriegt einen Wahrscheinlichkeitswert zwischen 0 und 100, die Summe der Wahrscheinlichkeitswerte sollte 100 jedoch nicht übersteigen.
2. Du gehst deine Felder der Reihe nach durch, für jedes Feld generierst du eine Zufallszahl zwischen 0 und 100. Dann gehst du deine Items nach ihrem Wahrscheinlichkeitswert von niedrigster zu höchster Wahrscheinlichkeit durch. Liegt die Zufallszahl im Wertebereich der Wahrscheinlichkeit wird das Item auf dem Feld gedroppt, ansonsten wird weitergemacht bis alle Items durchlaufen wurden, danach machst du mit dem nächsten Feld weiter.
Pseudocode:

$map = array
(
array(1, 2, 3, 4, 5),
array(6, 7, 8, 9, 10),
array(11, 12, 13, 14)
);
$items = array(
array("name" => "item1", "propability" => ,
array("name" => "item2", "propability" => 15),
array("name" => "item3", "propability" => 32)
);
for($x = 0; $x < count($map); $x++)
{
for($y = 0; $y < count($map[$x]); $y++)
{
$item = chooseItem();
if($item) {
// Item in der Map verewigen.
}
}
}
function chooseItem()
{
$rand = rand(0, 100);
foreach($items as $item)
{
if($item["propability"] <= $rand) {
return $item;
}
}
}
Wenn du bereits eine bestehende Map hast, gibt es eventuell auch einfachere Möglichkeiten. Wie z.b. einfach eine bestimmte Anzahl zufälliger Felder aus der Datenbank zu holen und diesen ein Item geben.
Ich verwende meinen Lösungsansatz für das Füllen einer neuen Spielkarte in meinem Spiel (ich muss da sowieso alle Felder generieren), vielleicht ists ja auch was für dich.

Original von Kaiser Nero
PS: Ich will ein
SELECT RANDOM feld1, feld2, feld3 FROM table ...
haben!

SELECT * FROM table ORDER BY RAND() LIMIT 10

Original von Agmemon
Ich habe eine Karte mit 100 x 100 Feldern und möchte auf dieser Karte irgendwelche Dinge verteilen. Diese Verteilung soll rein zufällig sein, aber es darf zu keinen Häufungen kommen.

genau zu dem prob hab ich nen uralt-script in asp geschrieben . sollte aber einfach zu php zu migrieren sein ..
war eins meiner ersten scripte, also nicht hauen
rafb.net/paste/results/c9CfEM30.html
hatte nen paar geländetypen, die nebeneinander vorkommen dürfen, sollen etc.
hab vorher nen paar linien wasser gezogen (grob nen paar striche) und dann das script drauf losgelassen .. ruft sich immer selbst auf, bis es fertig ist ..
prinzip: nimm feld oben, nimm feld links, schau, was zu beiden passt, loop (1 zeile + 1. spalte mit wasser definiert)
wie gesagt uralt.. anfang/mitte '03 meint mein windows ..
am besten schreibst du es ganz neu, aber ist ne idee, wie man auch "realistisches", "stimmiges" und "passendes" gelände generieren kann.
berge kommen etwas weiter weg vom wasser vor .. das ne wüste am wasser liegt ist auch unwahrscheinlich, wenn kein sumpf dazwischen ist etc.

Also die Sache mit dem Zufallszahlengenerator ist klar
Ich dachte da eher an einen Mechanismus, der die Nachbarfelder mit ein bezieht. Also es wird ein Feld per Zufall bestimmt, geprüft ob auf einem der Nachbarfelder schon ein Spezial ist und, sollte dies der Fall sein, das Feld verwirft. Auch das stellt von der Programmierung her kein Problem da.
Es würde mich halt interessieren, ob es da im Bereich der theoretischen Informatik vielleicht irgendein Standardverfahren gibt, dass am besten stochastisch abgesichert ist. Nach der hochinteressanten A*-Algorithmus Diskussion, hatte ich die Hoffnung, dass euch was dazu einfällt.

Ach, da fällt mir gerade noch etwas ein: Wie wäre, wenn Du Deine Dinger streng regelmäßig verteilst und sie danach "zufällig" verschiebst. Beim Veschieben könntest Du z.B. ein Fläche ermitteln, in der das Ding steht aber immer noch genug Abstand zu anderen Dingern besteht, so das das Kriterium "Häufung" noch nicht gegeben ist. Innerhalb dieser Fläche verschiebst Du das Ding dann. Wenn Du das dann evtl. mehr als einmal über alle Dinger machst, sollte evtl. das dabei heraus kommen, was Du möchtest.
Im Gegensatz zu dem "Wenn nicht so toll, dann noch mal" Ansatz hättest Du dann auch eine deterministische Laufzeit.

Würde folgendes Verfahren nutzen.
Du erzeugst einen Punkt wirklich zufällig.
Dann lädst du alle Punkte elektrisch positiv auf und dadurch stoßen sie sich ab. Die Kraft ist umgekehrt quadratisch positiv zum Radius. Nur der neue Punkt kann sich bewegen.
Nun simulierst du diese Bewegung ein paar 100 Iterationsschritte, bis der Punkt zum Stillstand oder nahezu zum Stillstand gekommen ist (lokales Minimum).
Damit erreichst du, dass dein System ein möglichst niedriges Energieniveau annimmt (du hast hohe Energie durch obige Definition durch Nähe von Punkten definiert).
Ich denke, dass du so eine einigermaßen zufällige, aber mit großen Abständen versehene Verteilung hinbekommst.

sehr interesanter gedanke TheUndeadable.. gefällt mir irgendwie...
legt man am anfang ein raster sagen mit der größe a yxy felder und verteilt in jedem zufällig x punkte und lässt dann deine idee drauf los sollte die karte sehr gleichmäßig werden ohne große leerstellen/häufungen.. vllt schon zu gleichmäßig

Zufällig und keine Häufung wiedersprechen sich. Du wirst immer Häufungen haben, sonst ist es nicht zufällig, sondern nur "gut verteilt".
Kannst auch einfach guggn:
Is was neben dran? Wenn ja: Wirf den Punkt weg, generier nen neuen.
Undeads lösung dürfte für deinen bedarf etwas overdressed sein, nehme ich an

ich hätts evtl mit rauschen gemacht.
tv karte an und etwas weißes rauschen aufnehmen ;p

Oder einfach in einem Grafikprogramm mit einem Störungsfilter ein Rauschbild erstellen. Wenn du mehr als schwarz und weiß als Zustand brauchst kannst du ja auch farbiges rauschen nehmen. Dann die Grafik pixelweise einlesen und dementsprechend die Felder setzen.
Die Idee find ich gar nicht so blöd

Vielen Dank für die ganzen Anregungen. Habe mich jetzt erstmal für eine Variante der Zufallszahlen mit Nachbarprüfung entscheiden. In der kleineren Testumgebung funktioniert das auch gut und performant. Wie es im echten großen System läuft, wird sich zeigen. Aber dann hätte ich noch eine Variation auf Basis eines genetischen Algorithmus in der Hinterhand.