Banner left   Banner center   Banner right

Germanenglish Home · News · Diary · Screenshots · Documentation (Wiki) · Downloads · Guestbook · Forum

Home · Benutzer registrieren · Suchen · Statistik · FAQ · Benutzerliste

Zur Zeit online: keiner ausser dir

 X-Force - Fight For Destiny - Forum —› X-Skript / Developer-Pack —› Hashtable/Hashmap/Dictionary (TDataHolder++)

Autor Mitteilung
verfasst am: 11.05.2010, 20:38
Spielsatz Alliances

Registrierdatum: 14.07.2004, 14:47

 Beiträge: 1185
Vielleicht bin ich auch einfach zu verwöhnt von Python und ähnlich abgehobenen Sprachen, aber meiner Meinung nach braucht X-Skript definitiv etwas im Stile der oben genannten Gerätschaften.
Und damit meine ich kein TDataHolder... das ist zwar ganz brauchbar, aber ich vermisse:
- Iteratoren (die wären sowieso nützlich, aber hierbei besonders)
- ein Check, ob ein Wer existent ist
- etwas a la TIntegerMap, TStringMap, usw... also quasi das gleiche, auf einen Typ beschränkt (wieso? damit ich mir JEDES MAL, wenn ich am DataHolder rumpfusche, gefühlte 20 Zeichen sparen kann)
- Werte automatisch registrieren, wenn sie gesetzt werden und noch nicht bekannt sind (Komfortfunktion)

Eigentlich könnte ich das ja selbst reinhacken... wenn WENN PascalSkript Objekte/Vererbung kennen würde =(

Kennt ihr eigentlich den Murmurhash? Wohl eine der besten Hashfunktionen für nicht-kryptographische Zwecke.
Habe ihn schon vor einiger Zeit in Pascal übersetzt (hab's getestet, landet bei den gleichen Ergebnissen wie die C++ Version (SEED ist eigentlich auch ein Parameter, aber es ist wohl sinnvoller, wenn's konstant ist, statt das die Funktion an drei Stellen mit drei verschiedenen Seeds aufgerufen wird und nix funkioniert... ( vorsicht, das ist ein Haufen schwarzer Magie (so viele schöne Klammern... yay, Lisp!)))):
// MurmurHashNeutral2, by Austin Appleby
function murmur(Key: Array of Char): Cardinal;
const
  M: Cardinal = $5bd1e995;
  R: Integer = 24;
  SEED: Cardinal = 5;
var
  len, h, k, offset: Cardinal;
  fallthrough: Boolean;
begin
  len:= Length(Key);
  h:= SEED xor len;
  offset:= 0;
  while (Length(Key) - offset) >= 4 do
  begin
    k:= Cardinal(Key[offset + 0]);
    k:= k or (Cardinal(Key[offset + 1]) shl 8);
    k:= k or (Cardinal(Key[offset + 2]) shl 16);
    k:= k or (Cardinal(Key[offset + 3]) shl 24);
    k:= k * M;
    k:= k xor (k shr R);
    k:= k * M;
    h:= h * M;
    h:= h xor k;
    offset:= offset + 4;
  end;
  fallthrough:= False;
  if (len = 3) then
  begin
      h:= h xor (Cardinal(Key[offset + 2]) shl 16);
      fallthrough:= True;
  end;
  if (len = 2) or fallthrough then
  begin
    h:= h xor (Cardinal(Key[offset + 1]) shl 8);
    fallthrough:= True;
  end;
  if (len = 1) or fallthrough then
  begin
      h:= h xor Cardinal(Key[offset + 0]);
      h:= h * M;
  end;
  h:= h xor (h shr 13);
  h:= h * m;
  h:= h xor (h shr 15);
  Result:= h;
end;
verfasst am: 11.05.2010, 20:47
Programmierer, allgemeines

Registrierdatum: 06.06.2004, 17:19

 Beiträge: 3186
Was willst du denn machen? Eigene Objekte bzw. Vererbung wirds in X-Script nicht geben, außer PascalScript lernt das irgendwann (bezweifle ich aber). Aber wofür brauchst du Hashtabellen? Und wofür TStringMap und TIntegerMap?
verfasst am: 11.05.2010, 21:08
Spielsatz Alliances

Registrierdatum: 14.07.2004, 14:47

 Beiträge: 1185
TStringMap und TIntegerMap: Wie gesagt, eine Komfortfunktion. In vielen Fällen brauche ich etwas, was ich als globales Objekt registrieren kann (quasi-Arrays), aber füge dann doch nur Sachen von einem Typ ein - und tippe dann x-mal z.B. TDataHolder.SetInteger()/.GetInteger() statt einfach nur TIntegerMap.get()/.set().
Wofür ich Hashtabellen brauche? Ja wozu benutzt man denn Hashtabellen, du Witzbold? ^^ Aktueller Anlass: Ich will einer Alien-AI erlauben, sich zu erinnern, vor wie vielen Runden sie welchen Gegner zuletzt gesehen hat. Das geht schlecht mit Arrays ;-) und von Pointern lasse ich wo immer möglich die Finger (mal vorrausgesetzt, PascalSkript kann das überhaupt), der einzig sinnvolle Weg wäre hier ne Hashmap. Ja, das ginge mit TDataHolder - man kann auch OOP in Ansi C machen - aber beides macht keinen Spaß.

Aber wie gesagt, vielleicht bin ich einfach nur zu verwöhnt.
verfasst am: 11.05.2010, 21:55 · Edited by: Natter
Programmierer, allgemeines

Registrierdatum: 06.06.2004, 17:19

 Beiträge: 3186
Wenn du dir Schreibarbeit sparen willst, warum erstellst du dir dann keine extra Unit für den Datenzugriff? Zugegeben, man müsste eventuell für jeden DataHolder eine extra Funktion schreiben (je nachdem, wie du das genau umsetzen willst - denkbar wäre auch der DataHolder als Parameter), aber ich glaube kaum, dass du so viele davon brauchst?

Zitat: sujin
Das geht schlecht mit Arrays ;-) und von Pointern lasse ich wo immer möglich die Finger (mal vorrausgesetzt, PascalSkript kann das überhaupt), der einzig sinnvolle Weg wäre hier ne Hashmap.

Wozu gibts Zweidimensionale Arrays? Zugegeben - es ist in X-Script etwas unhandlich die Länge festzulegen, da der SetLength-Befehl nicht direkt benutzt werden kann. Um Pointer kommst du dabei aber nicht drumrum. Wie willst du denn speichern, um welches Alien es sich handelt? Wenn du dir das Objekt merkst - dann merkst du dir nur einen Pointer, denn eine Objektvariable ist nichts anderes als ein Pointer. Deshalb existieren UFOs ja auch weiter, selbst wenn man der entsprechenden Variable ein neues UFO zuweist. Das wäre übrigens auch ein potentielles Problem in der AI - an Hand der Objektvariablen kannst du nicht ohne weiteres prüfen, ob das Objekt überhaupt noch existiert. Christian hatte dafür zwar mal IsObject eingebaut, ist aber nur eine bedingt brauchbare Methode. Insbesondere könnte es sein, dass an der Speicheradresse zwar nicht mehr das Alien ist, aber dafüür ein anderes Objekt.
verfasst am: 11.05.2010, 22:14
Programmierer, allgemeines

Registrierdatum: 06.06.2004, 17:19

 Beiträge: 3186
Zitat: sujin
Ja wozu benutzt man denn Hashtabellen, du Witzbold?

Das ist leider keine Antwort ;) Mir fällt zwar einiges ein, was man mit Hashmaps machen kann, aber nichts davon scheint mir für X-Skript relevant. Hast du denn eine so große Datenmenge, das sich die Suche mittels Hashtabelle lohnt?
verfasst am: 11.05.2010, 22:21 · Edited by: sujin
Spielsatz Alliances

Registrierdatum: 14.07.2004, 14:47

 Beiträge: 1185
Zitat: Natter
Wenn du dir Schreibarbeit sparen willst, warum erstellst du dir dann keine extra Unit für den Datenzugriff? Zugegeben . man müsste eventuell für jeden DataHolder eine extra Funktion schreiben (je nachdem, wie du dad genau umsetzen willst - denkbar wäre auch der DataHolder als Parameter), aber ich glaube kaum, dass du so viele davon brauchst?

Klar, geht natürlich... aber wenn es möglich ist, würde ich solche Hacks gerne vermeiden ;-)

Zu 2.:
Ich habe mich falsch ausgedrückt. Natürlich kann ich einen Array of TGameFigure erstellen und wenn ich die Daten brauche, den abzuklappern bis ich das Alien finde oder halt nicht. Wie schon gesagt: Man kann auch in C OO machen...
Idealerweise sollte das so aussehen:
for i:=0 to self.TAIGroup.EnemyCount() do
begin
  Figure:= self.TAIGroup.GetEnemy(i);
  LastSeenTable.set(TObject(Figure), -1);
  // ^ mal angenommen, wir überladen set, so dass es 
  // TObjects akzeptiert und deren Adresse hasht
  // sonst halt IntToStr(Int(Figure))

end;

Und um gestorbene Figures zu handhaben/Segfaults zu vermeiden, gibt es EVENT_FIGURE_ONDIE, oder?

Und: Referenzen sind keine Pointer ;-)

Edit: Die Aliens, die diese AI kriegen, treten in Massen (mind. 40-50) auf - werden vom Spieler also vermutlich mit voller Mannstärke angegangen - und sollen regen Gebrauch davon machen. Wie stark das der Performance tatsächlich wehtun wird, kann ich nicht beurteilen - aber die Sache schreit nach irgendeiner Art von lookup table, und du würdest mir mein Hobbyprogrammiererherz brechen, wenn du micht zwingst, dass mit einem O(n)-Algorithmus anzugehen ^^
verfasst am: 11.05.2010, 22:36
Programmierer, allgemeines

Registrierdatum: 06.06.2004, 17:19

 Beiträge: 3186
Zitat: sujin

Und: Referenzen sind keine Pointer ;-)

Jein. Natürlich enthalten sie auch noch die Info, welche Daten an dem Speicherort liegen. Aber alles was man mit Pointern falsch machen kann, kann man auch mit Referenzen falsch machen.

Ansonsten sehe ich immernoch nicht so recht, welchen Grund es haben sollte, sowas per Hashtabelle zu lösen. Mit was würdest du denn dann nach einer Einheit suchen, doch wieder mit der Referenz. Dann tut es doch ein beliebies Listenobjekt (z.B. TList) - wozu sollte ich mir da die Mühe machen, den Umweg über eine Hashliste selbst zu gehen (dachte erst, du wolltest die direkt in PascalScript umsetzen).
verfasst am: 11.05.2010, 22:46
Spielsatz Alliances

Registrierdatum: 14.07.2004, 14:47

 Beiträge: 1185
TList habe ich in X-Skript nicht. Wenn sich das ändern würde, würde das diesen Fall tatsächlich lösen.
Aber TList ist auch nur n Array mit Methoden -> O(n) -> pfui ^^

Zu Referenz vs. Pointer: Versuch mal Inc(Ptr); und Inc(Obj); ... aber egal, geht am Thema vorbei.
verfasst am: 11.05.2010, 23:01 · Edited by: Natter
Programmierer, allgemeines

Registrierdatum: 06.06.2004, 17:19

 Beiträge: 3186
Naja, Hashtabelle geht ja nur mit O(1), wenn sie richtig gewählt wurde. Hinzu kommt der Zeitaufwand fürs berechnen des Hashwertes - man braucht also schonmal eine gewisse Menge an Daten, damit man wirklich schneller ist. Ich hab mich allerdings nicht genug mit dem Thema beschäftigt, um sagen zu können, ab wievielen Daten man effizienter ist.
TList wird man auch nicht direkt in X-Script ermöglichen können, weil man Objekte für X-Skript immer um Speicher- und Ladefunktionen erweitern muss. Aber das kann man ja durch ein abgeleitetes Objekt umgehen.


Ansonsten, mir ist schon klar, das Pointer und Referenzen nicht exakt das gleiche sind, hab mich da wohl ungeschickt ausgedrückt (das Inc nicht klappt, liegt allerdings eher an Inc, und weniger an der Referenz - durch einen Integer-Cast ist das auch mit Referenzen möglich), mir gings mehr darum, dass ich keinen Grund sehe, sich vor dem Einsatz von Pointern zu sträuben, aber gleichzeitig problemlos Referenzen zu benutzen.
verfasst am: 11.05.2010, 23:22
Spielsatz Alliances

Registrierdatum: 14.07.2004, 14:47

 Beiträge: 1185
Ja, Hashtabellen sind nicht per se schneller - aber wenn diese AI je so kompliziert wird, wie es mir vorschwebt (ausgeklüngeltes Schwarmbewusstsein, koordiniertes Vorgehen, langzeit-Planung), dann beschleicht mich das Gefühl, dass ich mit ner lookup table deutlich besser dran bin.
Kleine Erbsenzählerei: Ne Hash-Funktion kann nicht O(1) sein (in dem Sinne, dass "ganzlangerstring" und "_" gleich viele Arbeitsschritte erfordern), aber sie ist definitiv billiger als ne lineare Suche in nem Array. Nur lookup ist bei beiden O(1). Wobei murmurhash2 auf nem (big endian, also z.B. x86, also auch jeder 32 Bit Windows PC) 2 x 2,4 Ghz CPU locker 2000 mb/s schafft - das sollte also nicht das Problem sein ;-)

Zu Pointern: Da musst du dich wohl bei grässlichen Sprachen ohne Referenzen (I'm looking at you, C) und ihren zivilisierteren Erzrivalen, bei denen es nur Referenzen plus Garbage Collection gibt, bedanken.
verfasst am: 12.05.2010, 17:24
Registrierdatum: 22.08.2008, 15:51

 Beiträge: 403
Zitat: sujin
Die Aliens, die diese AI kriegen, treten in Massen (mind. 40-50) auf

Jetzt bin ich aber auch neugierig, was genau willst du machen mit dem Schwarm verhalten und so, denn so ein Hashtable klingt fast etwas umständlich für nur 50 Aliens. Ein Hashtable wird erst merkbar schneller mit einem Array mit mehr als 1000 Einheiten(gilt zumidest für C++/C#, Quelle: meine Studien und Schulunterlagen).
Vieleicht lässt sich deine Idee auch anders umsetzen, zb mit einem Binärbaum.
verfasst am: 12.05.2010, 18:23 · Edited by: sujin
Spielsatz Alliances

Registrierdatum: 14.07.2004, 14:47

 Beiträge: 1185
Binärbaum... pfft. Der ist gut, um Schülern/Studenten zu ärgern, und wenn er ausbalanciert ist (aber das muss man auch erstmal sicherstellen -> einsetzen teurer), kann man effizient darin suchen. Ansonsten selten brauchbar. Aber bitte, ein Beispiel:
Zitat: ich, paar Posts weiter oben
[...] einer Alien-AI erlauben, sich zu erinnern, vor wie vielen Runden sie welchen Gegner zuletzt gesehen hat.

Wenn du dafür ne bessere Lösung kennst als ne lookup table, immer her damit.
Darüber hinaus (und das wäre auch für andere konzipierte AIs ne Überlegung wert imho) spiele ich mit dem Gedanken, noch weitergehende Beobachtungen mit einzelnen TGameFigures zu assoziieren (assoziieren wie in "Assoziatives Array" ;-) ), die sich wohl kaum (oder nur mit sehr viel Umständen und De-/Enkoderei) in einem Usertag speichern ließen, selbst wenn es einen gäbe. Das könnte leicht die Dimensionen eines mittelgroßen Records annehmen. Für Gegner etwa: Abschüsse in dieser Mission, wie lange im Sichtfeld gewesen, letzte bekannte Position (ergänzend zu dem bereits erwähnten "vor x Runden gesehen"), vermutete verbleibende HP/geschätzte Gefahr/usw (die AI verkrüppeln, indem ich sie raten lasse statt einfach TGameFigure.HP o.Ä. auszulesen), etc pp. Ähnlich für die eigene Seite: Wie gefährdet wer ist, wer wie viel wovon abgekriegt hat (beides zum Beispiel für Moral... Alien wird von dutzend Mörsern beschossen -> Aliens rennt und kauert sich hinters UFO ^^), etc pp.
Natürlich alles für taktische Entscheidungen und Gameplay, und nicht um euch zu ärgern ^^


Zu deinen Quellen: Das überrascht mich doch ziemlich - ich rede hier von ner linearen Suche im Array vs. Hash-Lookup! Murmurhash plus lookup sind ca. 60 Opcodes, rechnen wir noch die Tabellenverwaltung drauf und gehen großzügig auf 100 rauf. Array-Lookup sind (schätze ich mal, bin kein Assembly-Guru) 3 Opcodes, plus Vergleich sind (wenn wir von nem Array of Int aus) 4 oder 5 (wenn die Register knapp sind und der zweite Operand erst ausm Speicher geholt werden muss), deutlich mehr, wenn wir Strings oder sonstige nicht-numerische Daten vergleichen.
Noch dazu kann ist's sehr teuer, aus einem Array etwas zu entfernen (letztes Item ausgenommen), weil wirklich alles bewegt werden muss... 50x mov statt 1x bis 4x in ner Hashtabelle (je nach genauer Implementierung (hier sind String schon wieder deutlich teurer, das gilt aber für die Arrays aber noch mehr, da die ja alle Strings kopieren müssen)).
Da ich oft und gerne items einsetzen oder entfernen werde und oft nach (mehr oder weniger zufällig verteilten) Werten suchen, sehe ich nicht wirklich, wozu es 1000 items brauchen soll, um von der Performance her lohnend zu sein. Und selbst wenn es teurer sein sollte... "use the right tool for the job", und n assoziatives Array ist hier definitiv das beste Werkzeug ;-)


Edith möchte anmerken, dass ich mich grade mit Haskell beschäftige und sowieso viel mit Python mache - man möge mir also vergeben, wenn ich von Zeit zu Zeit kein Verständnis für die Sachzwänge von Pascal & Co. habe ;-)
verfasst am: 12.05.2010, 20:49
Grafiker

Registrierdatum: 06.03.2005, 16:04

 Beiträge: 460
So gut ich die Idee mit 50 oder 100 oder 200 Aliens als Gegner finde, steigert es doch nicht unwesentlich die Spieldauer der Bodenmission, und du benötigst die entsprechenden Bodenkarten(wohl das geringere Problem) dazu.

Ich hoffe du hast das mal mit der jetzigen Spielengine ausprobiert nur um ein Zeitgefühl zu bekommen :)
verfasst am: 12.05.2010, 21:48 · Edited by: Natter
Programmierer, allgemeines

Registrierdatum: 06.06.2004, 17:19

 Beiträge: 3186
Zitat: sujin


Edith möchte anmerken, dass ich mich grade mit Haskell beschäftige und sowieso viel mit Python mache - man möge mir also vergeben, wenn ich von Zeit zu Zeit kein Verständnis für die Sachzwänge von Pascal & Co. habe ;-)

Ich hab nix gegen Verbesserungsvorschläge. Aber bevor ich Hashfunktionen bereitstelle (was eine ganze Menge Arbeit macht, obwohl man das alles ohne Mehraufwand für den Skripter anders lösen kann), will ich erstmal die Skripte sehen, die zu spürbaren Leistungseinbrüchen führen.

PS: Bei echtem Schwarmverhalten bräuchtest du übrigens keinerlei austausch zwischen den Skripten - das ergibt sich nämlich automatisch dadurch, dass jedes Individuum für sich allein nach bestimmten Regeln agiert.
verfasst am: 13.05.2010, 00:17 · Edited by: sujin
Spielsatz Alliances

Registrierdatum: 14.07.2004, 14:47

 Beiträge: 1185
Zitat: JohnS
Ich hoffe du hast das mal mit der jetzigen Spielengine ausprobiert nur um ein Zeitgefühl zu bekommen :)

Ja, habe ich. Auch, wenn ich nicht lange ausgehalten habe (Rundenwechsel gefühlte 15 Sekunden mit meinem nicht-Gamer-PC, 10 Runden kein Konntakt, danach gut und gerne ein Dutzend Tombari Wissenschaftler als Tontauben ^^)
Soll definitiv nicht zur Norm werden... und die Kerle sollen auch nicht öfter als ein, allerhöchstens zwei mal auftreten (wenigstens in Mengen > ca. 20).

Zitat: Natter
PS: Bei echtem Schwarmverhalten bräuchtest du übrigens keinerlei austausch zwischen den Skripten - das ergibt sich nämlich automatisch dadurch, dass jedes Individuum für sich allein nach bestimmten Regeln agiert.

Der größte Teil des Konzept funktioniert genau so, allerdings will ich eben doch Informationsaustausch - "Hey du, hier um die Ecke ist Beute". Sag du mir, was von der Performance her billiger ist: x Callbacks, die alle erstmal über ne globale Variable den Sinn und Zweck ihres Aufrufs erfragen müseen, oder alles in einem Meta-Skript verwalten.

Zitat: Natter
Ich hab nix gegen Verbesserungsvorschläge. Aber bevor ich Hashfunktionen bereitstelle (was eine ganze Menge Arbeit macht, obwohl man das alles ohne Mehraufwand für den Skripter anders lösen kann), will ich erstmal die Skripte sehen, die zu spürbaren Leistungseinbrüchen führen.

Ich baue ne lineare Suche dort ein, wo ich bisher nen Platzhalter für zukünftige Hashtables hatte, teste und poste das Ergebnis hier... vielleicht noch heute, eher morgen.
verfasst am: 13.05.2010, 16:28
Registrierdatum: 22.08.2008, 15:51

 Beiträge: 403
Zitat: sujin
Zu deinen Quellen: Das überrascht mich doch ziemlich

Wundert mich nicht, deine Rechung klingt (über den Daumen gepeilt) auch richtig. Ich sprach von einem MENSCHLICH merkbaren unterschied.

Und bevor du binär Bäume (oder oder andere Bäume) für unnütz erklärst: Sie können bei einer vielzahl von stark menschlichen entscheidungslastigen Prozessen schon viel arbeit erledigen und somit die gefühlte Rechenzeit verkürzen (zB Nokias SMS Wörterbuch). Ist für dein Schwarmdeken zugegebener maßen unnötig.



Du musst dich registrieren um auf dieses Thema zu antworten.
Login :: » Name » Passwort

Ladezeit (sec.): 0.012 · Powered by miniBB 1.6 with parts of 1.7 © 2001-2003