Mal wieder Performance Probleme..

[Purebasium]

Hi Leute,
es tut mir leid, dass ich jetzt schon wieder ein kleines Problem hab:
Ihr kennt doch sicher alle Spiele wie z.B Die Siedler. Viele Kleine Menschen wuseln durch die Gegend, wobei jeder eine andere Aufgabe hat und seinen Weg durch ganze Städte immer schnell findet.
Wie man eine Wegfindung programmiert ist mir klar und auch wie ich es hinkrieg, dass EIN Mensch das gut befolgt. Jetzt will ich dass ganze mit etwas mehr Menschen machen (z.B mit ca. 1000+).
Allerdings hab ich das Problem, dass ich kaum so viele Menschen berechnen kann und das mindestens 60 mal in der Sekunde.

Code: Alles auswählen

 
id=0
 For x = 1 To 50
  For y= 1 To 50
id+1
M.Object(id)\menschx+3
Next y
 Next x

Allein so eine einfache Änderung dauert schon ca.2 ms für 2500 Menschen.


Und auch meine Wegfindung brauch so ca.20 ms pro Berechnung
Hat jemand vielleicht ein paar Tipps, wie man sowas gut umsetzt?
Und muss ich vielleicht irgendwas besonderes beachten?

Ist

Code: Alles auswählen

 M.Object(id)\menschx 

geeignet für einen schnelle verwendung oder kann man das irgendwie besser/schneller machen?



(Es tut mir leid, wenn ich hier mein Problem vielleicht etwas zu schlecht beschrieben hab)

P.s.:
Kennt jemand noch die siedler IV von 2003?
Selbst Damals, vor 12 Jahren, lief so etwas mit vielen Menschen schon reibungslos.

[NicTheQuick]

Die Wegfindungsroutine musst du ja im Grunde immer nur einmal machen. Nämlich immer dann, wenn sich das Ziel für einen Menschen ändert. Die Wegfindungsroutine kann man je nach Wegenetz auf verschiedene Arten programmieren. Bei den Siedlern gibt es ja vordefinierte Wege, die alle zusammen einen Graphen bilden. Den kürzesten Weg kann man dann mit dem Dijkstra-Algorithmus finden. Das sollte bei Graphen, die gerade mal so groß sind wie eine Kleinstadt, eigentlich schnell machbar sein. Ändert sich der Graph ständig, kann, macht das dem Dijkstra-Algorithmus auch nicht so viel aus. Wichtig ist nur, dass die Datenstruktur passend gewählt ist. Packt man alles in einen Graphen, bei dem jedes Node ein einzelner Speicherbereich ist, passt der Graph selten komplett in den Cache und ist somit langsamer. Speichert man alle Nodes in einem Array, kann die CPU alle Nodes meistens schon in einem Rutsch in den Cache schieben, womit es wesentlich schneller geht.

Wenn ich jetzt mehr über deine Datenstrukturen wüsste, könnte ich dir vielleicht sogar noch mehr Tipps geben.

[Purebasium]

Code: Alles auswählen

Structure Object
  x.i
  y.i
  Type.i
  id.i
  aussehen.i
EndStructure
Global Dim M.Object(10000)

Code: Alles auswählen

Global Dim MapDaten(200, 200)
;für jeden x/y wert eine Hausid

Jeder Mensch und jedes Haus ist ein M.Object().
Jedes Haus ist nochmal in einer map gespeichert, in der sie halt nach x und y sortiert sind.
Beim rendern wird halt geschaut z.b. auf x=3 und y=5 ist ein haus mit der id=273
Dann:

Code: Alles auswählen

Displaysprite(M.Object(273)\aussehen,3,5)

Allerdings optimierte ich das noch.