Seite 1 von 2

Verfasst: Dienstag 16. Dezember 2008, 16:19
von Ydope
Genau. Die Felder können auch weitere Zustände/Farben haben. Das ist z.B. hier erklärt: http://en.wikipedia.org/wiki/Langton%27 ... on.27s_ant
Außerdem kann meine Variante nicht nur auf einem Spielfeld mit quadratischen Zellen laufen, sondern auch mit sechseckigen Zellen. Da kennt der Automat dann auch nicht nur "dreh dich 90° nach links bzw. rechts", sondern er kann sich 60° und 120° in beide Richtungen drehen bevor er einen Schritt weiter geht.
Ferner können mehrere Automaten gleichzeitig rumlaufen und noch ein paar weitere Kleinigkeiten.

Wie meinst du das mit dem Merken? Ich habe momentan dieses Array oder verschachtelte Liste oder wie immer man das nennt:

Code: Alles auswählen

feldb = [[False for x in xrange(fsize)] for y in xrange(fsize)] #feld besucht(y/n)
Wenn das Feld x,y besucht wurde, wird es True. In der Hauptschleife:

Code: Alles auswählen

        if feldb[self.x][self.y] == False: 
            visited_count += 1     
            feldb[self.x][self.y] = True 
visited_count zählt global die besuchten Felder.

Wenn ich eine einfache Liste hätte mit den Koordinatenpaaren aller besuchten Felder, wäre zwar das Darstellen aller besuchten Felder schneller, aber dann müsse ich ja jedesmal wenn ein Feld betreten wird, die ganze Liste durchschauen, ob das aktuelle Feld schon drinsteht. Oder?

Verfasst: Dienstag 16. Dezember 2008, 16:49
von numerix
Ydope hat geschrieben:Wenn ich eine einfache Liste hätte mit den Koordinatenpaaren aller besuchten Felder, wäre zwar das Darstellen aller besuchten Felder schneller, aber dann müsse ich ja jedesmal wenn ein Feld betreten wird, die ganze Liste durchschauen, ob das aktuelle Feld schon drinsteht. Oder?
Nicht in dem Sinne, dass du die Liste durchlaufen müsstest - dafür gibt es den "in"-Operator. Ob es damit schneller geht als mit den beiden parallelen Listen könntest du ja ausprobieren.

Verfasst: Dienstag 16. Dezember 2008, 17:18
von Ydope
Da stehe ich etwas auf dem Schlauch und weiß ncht ob wir das gleiche meinen.
Meine eigentliche Schleife ohne die Darstellung soll möglichst schnell sein. Das ist die Hauptpriorität.
Und die ist doch sicher langsamer, wenn ich nach jedem Schritt mittels "in" nachschaue, ob das Feld schon in einer Liste von Koordinatenpaaren ist (und falls es das nicht ist, anhänge), als wenn ich nur schaue, ob das eine Feld in der 2-dimensionalen Liste feldb[x][y] True ist (und falls es False ist, auf True setze). Es können ja durchaus Hunderttausende Felder schon besucht worden sein.
Wenn du wirklich meinst, dass das sein kann, prüfe ich das aber mal.

Gruß

Verfasst: Dienstag 16. Dezember 2008, 17:40
von numerix
Ydope hat geschrieben:Wenn du wirklich meinst, dass das sein kann, prüfe ich das aber mal.
Nein, meine ich nicht. Ich *weiß* es schlicht nicht, aber da sich der Aufwand, es zu probieren, in Grenzen hält, würde ich es einfach mal ausprobieren. Im übrigen dürfte es mit einer Menge (set) statt einer Liste evtl. schneller laufen bei dieser Größenordnung (die mir nicht bewusst war). Aber auch das lässt sich ja einfach ausprobieren und testen ... :wink:

Verfasst: Dienstag 16. Dezember 2008, 19:30
von sea-live
ich glaube es wäre für dich sehr nützlich unter pygame mal das Arcade spiel crush roller zu analysieren wie dieser programmierer das ganze gelöst hat.

Verfasst: Dienstag 16. Dezember 2008, 20:16
von Hyperion
Wieso nimmst Du nicht ein set für die bereits besuchten Felder? Da müßtest Du ja nicht gucken, ob es bereits enthalten ist, oder?

Verfasst: Dienstag 16. Dezember 2008, 20:32
von BlackJack
Ich glaube ich hatte schon einmal vorgeschlagen: Ein Dictionary. Da kann man dann auch gleich den Wert der besuchten Felder speichern.

Verfasst: Dienstag 16. Dezember 2008, 20:49
von Ydope
Ok ich werde einen Benchmark machen mit der momentanen Variante, mit Set und mit Dictionary.

@ sea-live: ich finde dort das Spiel "crush roller" leider nicht.

Verfasst: Dienstag 16. Dezember 2008, 21:30
von Ydope
Dumme Frage:
Wie mache ich das denn überhaupt mit einem Set?
Ich will doch immer Punktepaare speichern und die sind nicht sequenzierbar.
Ein Set für x-Werte und eines für y-Werte geht auch nicht, denn ich brauche ja die Paare.

Verfasst: Dienstag 16. Dezember 2008, 21:54
von BlackJack
@Ydope: Was meinst Du mit "nicht sequenzierbar"? Man kann Tupel mit Zahlen drin in einem `set()` speichern bzw. als Schlüssel in Dictionaries verwenden.

Verfasst: Dienstag 16. Dezember 2008, 22:40
von Ydope
Vergleich bisherige Variante <-> dictionary
Bei der dictionary-Variante wird die .has_key-Methode benutzt um zu prüfen, ob das Feld schon besucht wurde. Wenn nicht, wird der key gesetzt.

20 Mio. Schritte

1500x1500 Felder, mit Automat, der am Ende eine knappe Mio. Felder besucht hat:
bisherig: ~31s
dictionary: ~114s

90x90 Felder, mit Automat, der ca. 1500 Felder besucht:
bisherig: ~28,5s
dictionary: ~80s

@ BlackJack
hier in Kurzform mein Problem:
>>> set ([(1,2),(2,1)])
set([(1, 2), (2, 1)])

>>> set.add([(0, 1)])
TypeError: descriptor 'add' requires a 'set' object but received a 'list'

>>> set.add((0, 1))
TypeError: descriptor 'add' requires a 'set' object but received a 'tuple'

>>> set.add([0, 1])
TypeError: descriptor 'add' requires a 'set' object but received a 'list'

>>> set.add(0,1)
TypeError: descriptor 'add' requires a 'set' object but received a 'int'

Mit set.update passiert das gleiche. Wo ist der Fehler?

Verfasst: Dienstag 16. Dezember 2008, 22:42
von DasIch
Ydope hat geschrieben:Bei der dictionary-Variante wird die .has_key-Methode benutzt um zu prüfen, ob das Feld schon besucht wurde. Wenn nicht, wird der key gesetzt.
dicts _sind_ Container...

Verfasst: Dienstag 16. Dezember 2008, 22:51
von Ydope
DasIch hat geschrieben:
Ydope hat geschrieben:Bei der dictionary-Variante wird die .has_key-Methode benutzt um zu prüfen, ob das Feld schon besucht wurde. Wenn nicht, wird der key gesetzt.
dicts _sind_ Container...
Was willst du mir damit sagen?
Ich wollte BlackJacks Vorschlag umsetzen und im Dictionary gleich den Wert der Zelle speichern. Der key ist das Koordinaten-Paar der Zelle. Wenn die Zelle noch nicht besucht wurde, gibt es den Key noch nicht.
Wenn ein Schritt gemacht wurde, muss daher doch geprüft werden, ob es den key gibt.

Verfasst: Dienstag 16. Dezember 2008, 22:52
von numerix

Code: Alles auswählen

In [8]: punkte = set([(1,2),(3,4),(5,6)])

In [9]: punkte.update([(7,8)])

In [10]: punkte
Out[10]: set([(1, 2), (5, 6), (3, 4), (7, 8)])

Verfasst: Dienstag 16. Dezember 2008, 23:02
von str1442
Ydope:

Du schmeißt das neue set() weg, und versucht die Add methode der *Klasse* set ohne Instanz aufzurufen.

Verfasst: Dienstag 16. Dezember 2008, 23:09
von BlackJack
@Ydope: ``in`` ist schneller als `has_key()` aufzurufen, aber letztendlich brauchst Du das wahrscheinlich gar nicht, sondern eher die `get()`- oder die `setdefault()`-Methode. Eventuell auch ein `collections.defaultdict`.

Verfasst: Dienstag 16. Dezember 2008, 23:14
von Ydope
Danke euch. Hab das mit dem Set endlich geschnallt.
Hier also der vollständige Benchmark:

20 Mio. Schritte ohne Bildschirmdarstellung

1500x1500 Felder, mit Automat, der am Ende eine knappe Mio. Felder besucht hat:
bisherig: ~31s
dictionary: ~114s
set: ~78s

90x90 Felder, mit Automat, der nur ca. verschiedene 1500 Felder besucht:
bisherig: ~28,5s
dictionary: ~80s
set: ~52s

Diese Varianten sind also deutlich langsamer.
Auch wenn damit evtl. eine leicht schnellere Bildschirmdarstellung möglich wäre, lohnt sich das nicht.

Verfasst: Dienstag 16. Dezember 2008, 23:19
von Ydope
BlackJack hat geschrieben:@Ydope: ``in`` ist schneller als `has_key()` aufzurufen, aber letztendlich brauchst Du das wahrscheinlich gar nicht, sondern eher die `get()`- oder die `setdefault()`-Methode. Eventuell auch ein `collections.defaultdict`.
OK dann werde ich das probieren und mich über diese Methoden informieren. Aber erst morgen. Will das jetzt nicht schon wieder umbauen und muss erstmal genau kapieren, was du meinst und ob das möglich ist.
Letztendlich wirds trotzdem langsamer als der bisherige Weg sein :roll:

Gruß :wink:

Verfasst: Dienstag 16. Dezember 2008, 23:27
von Hyperion
Ydope hat geschrieben: OK dann werde ich das probieren und mich über diese Methoden informieren. Aber erst morgen. Will das jetzt nicht schon wieder umbauen und muss erstmal genau kapieren, was du meinst und ob das möglich ist.
Letztendlich wirds trotzdem langsamer als der bisherige Weg sein :roll:
Also ich kann das nicht glauben! Die besuchten Felder müssen doch um ein vielfaches weniger sein, als das gesamte statische Spielfeld! Also muss doch eine Variante, in der man sich gezielt nur die benötigten Felder abarbeitet schneller sein (zumindest mal von den Algorithmus-Schritten).

Kannst Du Deinen Code mal irgend wo pasten?

Desweiteren ist mir noch nicht klar, wieso man sich so viele Felder merken muss. Werden denn nicht nur die geändert, auf denen sich die Ameise gerade befindet? Das wäre ja eigentlich nur eines ... aber vermutlich kenne ich den Algo zu wenig. Zumindest beim Vorgehen des Wikipedia Artikels sollte das aber so sein.

Verfasst: Mittwoch 17. Dezember 2008, 00:04
von Ydope
Hyperion hat geschrieben:
Ydope hat geschrieben: OK dann werde ich das probieren und mich über diese Methoden informieren. Aber erst morgen. Will das jetzt nicht schon wieder umbauen und muss erstmal genau kapieren, was du meinst und ob das möglich ist.
Letztendlich wirds trotzdem langsamer als der bisherige Weg sein :roll:
Also ich kann das nicht glauben! Die besuchten Felder müssen doch um ein vielfaches weniger sein, als das gesamte statische Spielfeld! Also muss doch eine Variante, in der man sich gezielt nur die benötigten Felder abarbeitet schneller sein (zumindest mal von den Algorithmus-Schritten).

Kannst Du Deinen Code mal irgend wo pasten?

Desweiteren ist mir noch nicht klar, wieso man sich so viele Felder merken muss. Werden denn nicht nur die geändert, auf denen sich die Ameise gerade befindet? Das wäre ja eigentlich nur eines ... aber vermutlich kenne ich den Algo zu wenig. Zumindest beim Vorgehen des Wikipedia Artikels sollte das aber so sein.
OK hier der ganze Code auf eigene Gefahr:
http://pastebin.com/m331663db
Die Hauptschleife ist in aufgehts()
Die ersten sechs Funktionen von def truchet bis def draw_bigant kannst du erstmal ignorieren.

Jeder Schritt läuft so ab, dass alle Ant-Instanzen nacheinander aufgerufen werden (default-mäßig bleibt das nur eine).
Dort dreht sich dann die Ameise, ändert den Zustand der Zelle, malt ggf. (siehe unten) die Zelle auf den Bildschirm, und geht eine Zelle weiter.
Dann kommt der nächste Schritt, usw.

Bei langsamer Geschwindigkeit (änderbar mit den links und rechts Tasten) wird jeder Schritt einzeln gemalt, innerhalb der "Ant"-Klasse.
Bei höheren wird alle 100.000 oder mehr Schritte screenupdatefull() ausgeführt und damit das komplette Fenster neu gezeichnet. Daher steht viel draw-Code letztendlich zweimal drin.

PS: Dinge, die diese dictionary-Sache betreffen, findest du in den Zeilen 163, 216 und 392. Ist jetzt aber erstmal alles wieder rausgeflogen und back-to-normal.

Gruß