partikelsystem: interaktion ist linkslastig

pixartist

jo titel klingt komisch ist aber so!
das ganze könnt ihr euch anschauen auf
http://pastebin.com/d5a63f9cc
der code ist relativ kurz (die sdl funktionen könnt ihr getrost überspringen...)
in frame() spielt die musik.

kurz für den überblick: ich habe 4 verschiedene partikelsorten, fallen partikel bestimmter typen auf einen punkt, "reagieren" sie miteinander und erzeugen die nächste sorte an partikeln...bis sie sich gegenseitig auslöschen. partikel sind in ner selbstgebauten verketteten liste gespeichert.

nun habe ich folgendes problem: von rechts nach links verlaufen die reaktionen sehr schnell, von links nach rechts aber ganz langsam...ich kenne das problem von einfacher iteration über einen array mit partikeln, aber ich dachte das ganze müsste durch die verwendung einer verketteten liste über eine größere fläche ausgeglichen werden (die partikel werden anfangs per rand() verteilt)

am besten compiliert ihr euch den code fix falls ihr grad sdl zur hand habt, dann wisst ihr was ich meine.

Hat jmd ne idee woran es liegt und vielleicht eine Lösung?

edit: oh man, dass free() in killParticle könnte ihr gerne entkommentieren

rapso

pixartist schrieb:

ich kenne das problem von einfacher iteration über einen array mit partikeln, aber ich dachte das ganze müsste durch die verwendung einer verketteten liste über eine größere fläche ausgeglichen werden

kannst du bitte erlaeutern was das problem beim array genau war und wieso du denkst dass das mit deiner listenimplementierung besser ist? das koennte uns helfen dir zu helfen

pixartist

rapso schrieb:

pixartist schrieb:

ich kenne das problem von einfacher iteration über einen array mit partikeln, aber ich dachte das ganze müsste durch die verwendung einer verketteten liste über eine größere fläche ausgeglichen werden

kannst du bitte erlaeutern was das problem beim array genau war und wieso du denkst dass das mit deiner listenimplementierung besser ist? das koennte uns helfen dir zu helfen

nunja wenn ich die partikel über nen 2 dimensionalen array implementiere, und den von links oben nach rechts unten durchiteriere, dann berechne ich bei zwei nebeneinanderliegenden partikeln erst den linken, dann den rechten usw. dadurch verlaufen dinge wie z.b. kollisionserkennung und ähnliches immer asynchron von den richtungen her...

einen von der position unabhängigen, eindimensionalen array als packung für die partikel habe ich wegen der ekelhaften begrenzung der partikelanzahl vermieden..
aber das ist ja ziemlich egal ob die partikel nun über ne verkettete liste oder nen eindimesionalen array iteriert werden

edit: ich verstehe sowieso nicht, wie spiele wie z.B. "falling sand game" eine symmetrische kollisionsabfrage bei partikeln hinkriegen, ich sehe da nähmlich nur 2 möglichkeiten
1. parallelität - nicht möglich
2. gigantische rekursionen - praktisch nicht möglich

wie schaffen diese spiele das?

rapso

verstehe, wenn du den linken berechnest ist der schon bei t+1 waehrend der rechte noch bei t ist, wenn du dann den rechten mit dem linken aus der zukunft berechnest, geht natuerlich alles schief.

da helfen die lists auch nicht, da du die liste bestimmt genau so durchgehst.

mach es halt so wie die anderen spiel auch und verwende doublebuffering.

pixartist

rapso schrieb:

verstehe, wenn du den linken berechnest ist der schon bei t+1 waehrend der rechte noch bei t ist, wenn du dann den rechten mit dem linken aus der zukunft berechnest, geht natuerlich alles schief.

da helfen die lists auch nicht, da du die liste bestimmt genau so durchgehst.

mach es halt so wie die anderen spiel auch und verwende doublebuffering.

sprich ich rechne die bewegung in einen puffer für das nächste frame und flippe den dann sozusagen wenn ich fertig bin ? hmm ist ne idee ^^

edit: dann weis ich aber doch bei der berechnung nicht ob ich nicht vielleicht mehrere partikel auf den selben punkt schiebe..das ist doch grade bei kollisionserkennung recht ärgerlich

pixartist schrieb:

[...]
wie schaffen diese spiele das?
[...]

2. gigantische rekursionen [...]

ja, das sind einfach gigantische rekursionen mit paar vorfiltersachen wie das "zoning" [keine ahnung wie der offizielle begriff dafür lautet], also einteilen der "welt" in virtuelle zonen, oder ganz einfach irgendwelche simplen logischen tricks um paar rechendurchgänge zu sparen. irgendwie muss ja berechnet werden, gibt leider keinen magischen "iterations-killer-algo".

natürlich haste am ende trotzdem ne riesige anzahl iterationen, aber unsere pcs von heute... sind ja nicht von gestern. spiele wie "burning sand" machen ja nich soo viel mehr als diese kleinen partikel+ ihre eigenschaften zu berechnen und dann zu zeichnen. wenn du nebenher nichts mehr machst schafft das jeder pc locker in flüssiger rate.

rapso

@pixelartist

schau dir mal [url=http://en.wikipedia.org/wiki/Conway's_Game_of_Life]game of life[/url] an. die sandspiele sind eher so gemacht wie ein komplexeres game of life