| // Daemon zum automatisierten Erstellen von Karten. |
| // Soll spaeter mal wichtige Wege berechnen koennen fuer Anfaenger. |
| // |
| // |
| // Wer mir ohne triftigen Grund daran herumpfuscht, der wird standesrechtlich |
| // mit faulen Eiern beworfen. ]:-> |
| // |
| // Tiamak |
| |
| #pragma strong_types,save_types,rtt_checks |
| #pragma no_clone,no_inherit,no_shadow |
| #pragma pedantic,range_check,warn_deprecated |
| #pragma warn_empty_casts,warn_missing_return,warn_function_inconsistent |
| |
| #include <strings.h> |
| #include <wizlevels.h> |
| #include <player.h> |
| #include <properties.h> |
| #include <rooms.h> |
| #include <moving.h> |
| |
| #define LOGNAME "PATHD" |
| #define SAVEFILE "/p/daemon/save/pathd" |
| #define DUMPFILE "/p/daemon/save/pathd-dump" |
| //#define DEBUG |
| |
| // 10 verschiedene Leute werden gebraucht, um eine Verbindung zu verifizieren |
| #define NEEDED 10 |
| #define TIMEOUT_NEW 1209600 // 14 Tage |
| #define TIMEOUT_OLD 7776000 // 90 Tage |
| |
| // Art des Ausgangs |
| #define NORMAL 0 |
| #define SPECIAL 1 |
| #define COMMAND 2 |
| |
| // Kosten fuer unterschiedliche Wege |
| #define COST_EXITS ({ 1, 10, 100 }) |
| #define COST_MANY 3 |
| #define COST_FEW 5 |
| #define COST_ONE 10 |
| // Kosten fuer Weltenwechsel (Para -> Normal) |
| #define COST_WORLDCHANGE 100 |
| |
| #ifdef DEBUG |
| #define DBG(x) if ( find_player("zesstra") ) \ |
| tell_object( find_player("zesstra"), (x)+"\n" ); |
| #define TELL_USER(x) if ( this_player() ) \ |
| tell_object( this_player(), (x)+"\n" ); |
| #else |
| #define DBG(x) |
| #define TELL_USER(x) |
| #endif |
| |
| #define LOG(x) log_file( "PATHD", (x), 100000 ); |
| |
| // Variablen |
| nosave int time_to_clean_up; // Zeit fuer naechstes Cleanup der Daten |
| |
| mapping pathmap; |
| /* Prefix : ([ <submap> ]), |
| <submap> ist ein Mapping von Raeumen mit einem Array von Verbindungen: |
| ([<room>: ({ conn1, conn2, conn3, ...}), ...]) |
| Jede Verbindung ist ein Array mit folgenden Indizes: |
| */ |
| #define CONN_DEST 0 // Zielraum |
| #define CONN_CMD 1 // Kommando |
| #define CONN_USERS 2 // Benutzer: ({spieler, seher}) |
| #define CONN_EXITTYPE 3 // Ausgangsart (s.o.) |
| #define CONN_TIMES 4 // Zeit letzter Benutzung: ({spieler,seher}) |
| #define CONN_PARA 5 // Parawelt |
| #define CONN_FLAGS 6 // Flags fuer die Verbindung (z.B. permanent) |
| // Indizes in CONN_USERS. Beide Eintraege sind entweder gehashte UIDs ODER -1, |
| // wenn die Verbindung von mehr als NEEDED unterschiedlichen gegangen wurde. |
| #define CONN_U_PLAYERS 0 // Spieler-UIDs |
| #define CONN_U_SEERS 1 // Seher-UIDS |
| // Indizes von CONN_TIMES. Zeitstempel der letzten Benutzung... |
| #define CONN_T_PLAYERS CONN_U_PLAYERS // ... durch Spieler |
| #define CONN_T_SEERS CONN_U_SEERS // ... durch Seher |
| |
| // Konstanten fuer CONN_FLAGS |
| #define CFLAG_PERMANENT 0x1 // Verbindung nicht expiren |
| #define CFLAG_DONTUSE 0x2 // Verbindung nicht im Routing nutzen |
| #define CFLAG_DUPLICATE 0x4 // Kommando hat mehrere Verbindungen |
| |
| // laufende Pfadsuchen |
| nosave mapping searchlist = ([]); |
| /* |
| ([ <uuid> : SL_VISITED; SL_DESTINATION;... ... ]) |
| */ |
| // Indizes in <data>: |
| #define SL_START 0 |
| #define SL_DESTINATION 1 // Zielraum |
| #define SL_VISITED 2 // abgelaufene/gepruefte Raeume |
| #define SL_CANDIDATES 3 // moegliche Ziele |
| #define SL_WIZLEVEL 4 // Wizlevel |
| #define SL_PARA 5 // Parawelt |
| #define SL_TODO 6 // noch zu pruefende Raume (SL_CANDIDATES-SL_VISITED) |
| #define SL_CALLBACK 7 // Closure fuer Callback nach Routenberechnung |
| // SL_CANDIDATES: ([<raum>: ({verbindungsdaten}), ...]) |
| // Indizes im Array <verbindungsdaten>: |
| #define SLT_COSTS 0 // Kosten fuer Verbindung bis hier |
| #define SLT_WAY 1 // bisheriger Weg von Start bis hier |
| #define SLT_COMMANDS 2 // Kommandos fuer Weg von Start bis hier |
| |
| // cache fuer berechnete Wege |
| nosave mapping pathcache = ([]); |
| // Aufbau: ([ "startraum": <dests>, ...]) |
| // <dests>: (["zielraum": <wege>, ...]) |
| // <wege>: ([parawelt: (<struct path_s>) ]) |
| |
| struct path_s { |
| int costs; // Kosten des kompletten Pfades |
| string *rooms; // Liste von durchlaufenen Raeumen |
| string *cmds; // Liste von Kommandos, um Raeume zu durchlaufen |
| int ttl; // time-to-live, Ablaufzeit des Pfads im Cache |
| int para; // Parawelt |
| int flags; // Flags zu dem Pfad |
| }; |
| // Flags fuer Pfade im Pfadcache |
| #define PFLAG_PERMANENT CFLAG_PERMANENT |
| #define PFLAG_DONTUSE CFLAG_DONTUSE |
| |
| |
| // Prototypes |
| public void create(); |
| public void add_paths( mixed connections ); |
| public varargs void show_pathmap( string path ); |
| public varargs int show_statistic( int verbose, int silent ); |
| public int change_pathmap( string pfad, mixed *verbindungen ); |
| public mapping get_pathmap(); |
| public void reset(); |
| public varargs int remove( int silent ); |
| public varargs int query_prevent_shadow( object ob ); |
| static int insert_paths( mixed *path ); |
| static mixed *format_paths( mixed buf ); |
| static void _search( string fname, string start ); |
| private string _get_prefix( string path ); |
| protected void cleanup_data( string *names, int idx ); |
| protected void expire_path_cache(string *startrooms); |
| |
| |
| public void create() |
| { |
| // wir muessen das Savefile schreiben duerfen |
| seteuid(getuid()); |
| |
| if ( !restore_object(SAVEFILE) ) { |
| pathmap = ([]); |
| } |
| } |
| |
| |
| // Wird von Spielern aufgerufen mit den Wegen, die sie gelaufen sind |
| public void add_paths( mixed connections ) |
| { |
| mixed paths; |
| |
| // keinen Aufruf per Hand bitte |
| if ( !previous_object() || !this_player() |
| || this_interactive() && getuid(this_interactive()) != "zesstra" |
| || file_size( "/std/shells" + |
| explode( object_name(previous_object()), ":" )[0] |
| + ".c" ) < 1 ) |
| return; |
| |
| #if __BOOT_TIME__ < 1357042092 |
| // alte Spielerobjekte liefern noch ein Array von Strings statt eines |
| // Arrays von Arrays. |
| connections = map(connections, function mixed (string path) |
| { |
| // Alle Daten kommen als ein String mit '#' als Trenner an. |
| // Muster: Startraum#Zielraum#Verb#Methode der Bewegung#Parawelt |
| mixed buf = explode( path, "#" ); |
| // Falls im Verb auch # vorkam (unwahrscheinlich, aber moeglich): |
| buf[2..<3] = ({ implode( buf[2..<3], "#" ) }); |
| return buf; |
| } |
| ); |
| #endif |
| |
| // Daten aufbereiten |
| paths = map( connections, #'format_paths/*'*/ ) - ({0}); |
| // Neue Raeume eintragen |
| filter( paths, #'insert_paths/*'*/ ); |
| } |
| |
| public mixed get_path_from_cache(string from, string to, int para) { |
| // wenn im Cache, aus dem Cache liefern. |
| mapping targets = pathcache[from]; |
| if (targets) { |
| mapping paths = targets[to]; |
| if (paths) { |
| if (member(paths, para)) { |
| struct path_s p = paths[para]; |
| if (p->ttl > time()) |
| return ({ from, to, para, p->costs, |
| copy(p->rooms), copy(p->cmds) }); |
| else { |
| m_delete(paths, para); |
| } |
| } |
| } |
| } |
| return 0; |
| } |
| |
| // Suchfunktion, um die kuerzeste Verbindung zwischen zwei Raeumen zu finden |
| public int SearchPath( string from, string to, int para, |
| closure callback) |
| { |
| // Pro UID darf es nur einen Suchauftrag geben. |
| string uid=getuid(previous_object()); |
| if ( member(searchlist,uid) ) |
| return -1; |
| // und mehr als 5 gleichzeitig erstmal auch nicht. |
| if (sizeof(searchlist)>4) |
| return -2; |
| |
| // Anfrage loggen |
| LOG(sprintf("%s: Suche %s -> %s (%d) von %s (%s, %s, %s)\n", |
| strftime("%y%m%d-%H%M%S"), from, to, para, uid, |
| object_name(previous_object()), |
| object_name(this_player()) || "NO-PL", |
| object_name(this_interactive()) || "NO-TI") ); |
| |
| // wenn Start- oder Zielraum nicht bekannt sind, kann es auch keine Route |
| // geben. |
| if (!member(pathmap[_get_prefix(to)],to) |
| || !member(pathmap[_get_prefix(from)],from) ) |
| return -3; |
| |
| mixed path = get_path_from_cache(from, to, para); |
| if (path) { |
| if (callback) |
| apply(callback,path); |
| return 2; |
| } |
| |
| // Datenstrukturerklaerung: s.o. |
| mapping targets = m_allocate(1200,3); |
| m_add(targets,from,0,({}),({}) ); |
| searchlist+= ([ uid: from; to; ({}); |
| targets; |
| (query_wiz_level(this_interactive())?1:0); |
| para; ({}); callback]); |
| |
| // Die eigentliche Suche starten |
| _search( uid, from ); |
| |
| return 1; |
| } |
| |
| // Gespeicherte Informationen zu einem Raum oder einem kompletten Gebiet |
| // abfragen. Gebiete lassen sich aber nur als "Organisationseinheiten" abfragen. |
| // Dabei werden Gebiete unterhalb von /d/* als /d/region/magiername |
| // abgespeichert und der Rest unter den ersten beiden Teilpfaden. |
| public varargs void show_pathmap( string path ) |
| { |
| string pre; |
| |
| if ( path ) |
| { |
| pre = _get_prefix(path); |
| |
| if ( pre == path ) |
| // Ganzen Teilbaum ausgeben |
| printf( "Pathmap[%O]: %O\n", path, pathmap[path] ); |
| else |
| // Nur Infos ueber einen Raum ausgeben |
| printf( "Pathmap[%O]: %O\n", path, |
| pathmap[pre] ? pathmap[pre][path] : 0 ); |
| } |
| else |
| // Ohne Argument wird die gesamte Map ausgegeben. |
| // Klappt aber eher nicht (mehr) wegen Buffer overflow. ;^) |
| printf( "Pathmap: %O\n", pathmap ); |
| } |
| |
| |
| // Statistic zu den gespeicherten Daten anzeigen. |
| // Mit 'verbose' wird jede Organisationseinheit einzeln aufgelistet, ohne |
| // wird grob nach Regionen zusammengefasst. |
| public varargs int show_statistic( int verbose, int silent ) |
| { |
| int i, ges; |
| string *ind, name; |
| mapping m; |
| |
| if ( verbose ){ // Stur jeden Eintrag auflisten |
| ind = sort_array( m_indices(pathmap), #'</*'*/ ); |
| for ( i = sizeof(ind); i--; ){ |
| if ( !silent ) |
| printf( "%-30s: %4d\n", ind[i], sizeof(pathmap[ind[i]]) ); |
| ges += sizeof(pathmap[ind[i]]); |
| } |
| } |
| else { // Regionen zusammenfassen |
| ind = m_indices(pathmap); |
| m = ([]); |
| |
| for ( i = sizeof(ind); i--; ){ |
| if (strstr(ind[i],"/d/") == 0) |
| // /d... jeweils nach zwei Teilpfaden |
| name = implode( explode( ind[i], "/" )[0..2], "/" ); |
| else if ( strstr(ind[i],"/players") == 0) |
| // Alle Playerverzeichnisse zusammenfassen ... |
| name = "/players"; |
| else |
| // ... den Rest nach einem Teilpfad |
| name = implode( explode( ind[i], "/" )[0..1], "/" ); |
| |
| if ( !m[name] ) |
| m[name] = sizeof( pathmap[ind[i]] ); |
| else |
| m[name] += sizeof( pathmap[ind[i]] ); |
| } |
| |
| ind = sort_array( m_indices(m), #'</*'*/ ); |
| for ( i = sizeof(ind); i--; ){ |
| if ( !silent ) |
| printf( "%-30s: %4d\n", ind[i], m[ind[i]] ); |
| ges += m[ind[i]]; |
| } |
| } |
| |
| if ( !silent ) |
| printf( "\nGesamt: %d Raeume.\n", ges ); |
| |
| return ges; |
| } |
| |
| |
| // Manipulieren der internen Pathmap. Nur zum Debuggen und somit |
| // nur fuer Zesstra erlaubt. Sonst verhunzt mir noch wer meine Daten. ;^) |
| public int change_pathmap( string pfad, mixed *verbindungen ) |
| { |
| if ( !this_interactive() || getuid(this_interactive()) != "zesstra" |
| || !previous_object() || getuid(previous_object()) != "zesstra" ) |
| return -1; |
| |
| if ( mappingp(verbindungen) ){ |
| if ( !pathmap[_get_prefix(pfad)] ) |
| return 0; |
| |
| pathmap[_get_prefix(pfad)] = verbindungen; |
| } |
| else { |
| if ( !pathmap[_get_prefix(pfad)][pfad] ) |
| return 0; |
| |
| pathmap[_get_prefix(pfad)][pfad] = verbindungen; |
| } |
| |
| return 1; |
| } |
| |
| // Die Funktion gibt alle dem pathd bekannten Raeume als Mapping von Arrays |
| // zurueck. Schlüssel des Mappings sind dabei Gebiete. |
| public mapping get_rooms() |
| { |
| string *submaps; |
| mapping roommap; |
| int i; |
| |
| roommap=([]); |
| |
| submaps=m_indices(pathmap); |
| |
| i=sizeof(submaps); |
| |
| while (i--) |
| if (sizeof(m_indices(pathmap[submaps[i]]))) |
| roommap[submaps[i]]=m_indices(pathmap[submaps[i]]); |
| |
| return roommap; |
| } |
| |
| // Daten zu einer Verbindung sammeln und aufbereiten |
| static mixed *format_paths( mixed buf ) |
| { |
| string cmd, uid; |
| object ob; |
| mapping exits; |
| int art; |
| |
| // Magier und Testspieler koennen auch in nicht angeschlossene Gebiete |
| // und werden deshalb nicht beachtet. |
| if ( IS_LEARNER(previous_object(1)) || |
| IS_LEARNER(lower_case( previous_object(1)->Query(P_TESTPLAYER)||"" )) ) |
| return 0; |
| |
| cmd = trim(buf[2],TRIM_BOTH); |
| #if __BOOT_TIME__ < 1357042092 |
| // " 0" am Ende des Befehls abschneiden. *grummel* |
| if (cmd[<2..]==" 0") |
| cmd = cmd[..<3]; |
| #endif |
| |
| // Wenn der Zielraum als String angegeben wurde, kann der fuehrende |
| // Slash fehlen! |
| if ( buf[1][0] != '/' ) |
| buf[1] = "/" + buf[1]; |
| |
| // Zum Abfragen der zusaetzlichen Daten brauchen wir das Objekt selber |
| catch(ob = load_object(buf[0]);publish); |
| if (!objectp(ob)) |
| return 0; |
| |
| // Kleiner Hack - bei Transportern etc. ist 'ob' die nicht initialisierte |
| // Blueprint. Jede Abfrage von P_EXITS wuerde nett auf -Debug scrollen. |
| // Da P_IDS im create() auf jeden Fall auf ein Array gesetzt wird, |
| // missbrauche ich das hier als "Ist initialisiert"-Flag. |
| if ( !ob->QueryProp(P_IDS) ) |
| return 0; |
| |
| // Art des Ausgangs feststellen. |
| if ( mappingp(exits = ob->QueryProp(P_EXITS)) && exits[cmd] ) |
| art = NORMAL; // "normaler" Ausgang |
| else if ( mappingp(exits = ob->QueryProp(P_SPECIAL_EXITS)) && exits[cmd] ) |
| art = SPECIAL; // SpecialExit |
| else { |
| // Kommandos, die einen in einen anderen Raum bringen |
| art = to_int(buf[3]); // Move-Methode |
| |
| // Es zaehlen aber nur Bewegungen, die halbwegs "normal" aussehen, |
| // d.h. kein M_TPORT, M_NOCHECK und M_GO muss gesetzt sein. |
| if ( art & (M_TPORT | M_NOCHECK) || !(art & M_GO) ) |
| return 0; |
| else |
| art = COMMAND; |
| } |
| |
| // Die UID der Spieler/Seher wird verschluesselt. |
| // Schliesslich brauchen wir sie nur fuer statistische Zwecke und nicht, |
| // um Bewegungsprofile zu erstellen. crypt() reicht fuer diese Zwecke |
| // wohl erstmal. |
| uid = getuid(previous_object(1)); |
| uid = crypt( uid, "w3" ); |
| |
| // Start, Ziel, Verb, Wizlevel(TP), UID(TP), Art des Ausgangs, Parawelt |
| return ({ buf[0], buf[1], cmd, query_wiz_level(previous_object(1)) ? 1 : 0, |
| uid, art, to_int(buf[4]) }); |
| } |
| |
| // Prueft alle Verbindungen im Array <conns>, welche das gleiche Kommando wie |
| // <conn> haben, ob sie in unterschiedliche Raeume fuehren. Wenn ja, sind sie |
| // fuer das Routing nicht nutzbar. Ausnahme: Verbindungen, die in |
| // unterschiedliche Parawelten fuehren. |
| // Aendert <conns> direkt. |
| private void check_and_mark_duplicate_conns_by_conn(mixed conns, mixed conn) { |
| foreach(mixed c: conns) { |
| if ( c[CONN_CMD] == conn[CONN_CMD] |
| && c[CONN_DEST] != conn[CONN_DEST] |
| && c[CONN_PARA] == conn[CONN_PARA] ) |
| { |
| c[CONN_FLAGS] |= CFLAG_DUPLICATE; |
| conn[CONN_FLAGS] |= CFLAG_DUPLICATE; |
| } |
| } |
| } |
| |
| private void check_and_mark_duplicate_conns(mixed conns) { |
| foreach(mixed c: conns) |
| check_and_mark_duplicate_conns_by_conn(conns, c); |
| } |
| |
| |
| // Neue Verbindung in der Datenbank eintragen |
| static int insert_paths( mixed *path ) |
| { |
| string pre = _get_prefix(path[0]); |
| |
| // Falls noch gar kein Eintrag existiert, neu initialisieren |
| if ( !mappingp(pathmap[pre]) ) |
| pathmap[pre] = ([]); |
| |
| if ( !pointerp(pathmap[pre][path[0]]) ) |
| pathmap[pre][path[0]] = ({}); |
| |
| // Aufbau von 'path': |
| // ({ Start, Ziel, Verb, Wizlevel(TP), UID(TP), Art des Ausgangs, Para }) |
| // Aufbau von 'conn' (s. auch ganz oben) |
| // ({ Ziel, Verb, ({ Spieler-UIDs, Seher-UIDs }), Art des Ausgangs, |
| // ({ Letztes Betreten durch Spieler, durch Seher }), Parawelt }) |
| |
| // Alle Verbindungen des Raumes durchgehen |
| mixed conns = pathmap[pre][path[0]]; |
| // Kommandos der Verbindungen sammeln. Wenn es zwei Verbindungen mit dem |
| // gleichen Kommando gibt, sind beide unbenutzbar. |
| mixed cmds = m_allocate(10); |
| int i; |
| for ( i = sizeof(conns); i--; ) |
| { |
| mixed conn = conns[i]; |
| m_add(cmds,conn[CONN_CMD]); // Kommandos aller Conns merken |
| // Wenn Zielraum, Verb und Parawelt passen ... |
| if ( conn[CONN_DEST] == path[1] && conn[CONN_CMD] == path[2] |
| && conn[CONN_PARA] == path[6] ) |
| { |
| // Wenn schon genug Leute diese Verbindung genutzt haben, einfach |
| // nur die Zeit der letzten Benutzung aktualisieren. |
| int index = path[3] ? CONN_U_SEERS : CONN_U_PLAYERS; // Seher? |
| if ( conn[CONN_USERS][index] == -1 ) |
| { |
| conn[CONN_TIMES][index] = time(); |
| break; |
| } |
| // Ansonsten die (neue?) UID hinzufuegen und die Zeit aktualisieren. |
| else |
| { |
| conn[CONN_USERS][index] = |
| conn[CONN_USERS][index] - ({ path[4] }) + ({ path[4] }); |
| if ( sizeof(conn[CONN_USERS][index]) >= NEEDED ) |
| conn[CONN_USERS][index] = -1; |
| |
| conn[CONN_TIMES][index] = time(); |
| break; |
| } |
| } |
| } |
| |
| // Falls keine Verbindung gepasst hat, eine neue erzeugen. |
| if ( i < 0 ) { |
| int index = path[3] ? CONN_U_SEERS : CONN_U_PLAYERS; // Seher? |
| mixed uids = ({ ({}), ({}) }); |
| uids[index] = ({ path[4] }); |
| mixed times = ({ 0, 0 }); |
| times[index] = time(); |
| |
| // Aufbau siehe oben |
| mixed conn = ({ path[1], path[2], uids, path[5], times, path[6], 0 }); |
| conns += ({ conn }); |
| // wenn die neue Verbindung nen Kommando benutzt, welches schon fuer |
| // eine andere Verbindung aus diesem Raum benutzt wird, sind beide |
| // nicht nutzbar, da das Ziel nicht eindeutig ist. In diesem Fall |
| // muessen alle diese als unbenutzbar fuer das Routing markiert |
| // werden. |
| if (member(cmds, conn[CONN_CMD])) { |
| check_and_mark_duplicate_conns_by_conn(conns,conn); |
| } |
| } |
| |
| pathmap[pre][path[0]] = conns; |
| |
| // Ob 0 oder 1 ist eigentlich total egal, da das Ergebnis-Array sowieso |
| // verworfen wird. |
| return 0; |
| } |
| |
| private void add_to_cache(string from, string to, int para, int costs, |
| string *rooms, string *cmds) { |
| struct path_s p = (<path_s> costs : costs, rooms: rooms, cmds : cmds, |
| para: para, flags: 0, ttl: time()+86400); |
| if (!member(pathcache, from)) { |
| pathcache[from] = m_allocate(1); |
| pathcache[from][to] = m_allocate(1); |
| } |
| else if (!member(pathcache[from], to)) { |
| pathcache[from][to] = m_allocate(1); |
| } |
| pathcache[from][to][para] = p; |
| } |
| |
| // Diese Funktion berechnet die Kosten einer Verbindung. |
| // Ein Seherstatus schliesst die Moeglichkeiten von Spielern ein (seher |
| // kann Spielerpfade problemlos nutzen). |
| // Wenn eine Verbindung in eine andere Parawelt fuehrt, als in <para> |
| // angefragt, wird sie erheblich teurer. |
| protected int _calc_cost(mixed* path, int seer, int para) |
| { |
| mixed* interest=path[CONN_USERS]; |
| |
| // Basiskosten nach Ausgangsart |
| int costs = COST_EXITS[path[CONN_EXITTYPE]]; |
| |
| // Verbindungen in andere als die gewuenschte Parawelt werden bei der |
| // suche nicht beruecksichtigt, aber Verbindung von Para nach Normal und |
| // umgekehrt sind erlaubt. Para->Normal soll aber etwas teurer sein, damit |
| // es bevorzugt wird, in der angefragten Welt zu bleiben. |
| // (Hintergrund: wenn man in Para ist, laeuft man meistens trotzdem durch |
| // Normalweltraeume, weil es keine passenden Pararaeume gibt). |
| if (para != path[CONN_PARA]) |
| costs += COST_WORLDCHANGE; |
| |
| // wenn schon genug unterschiedliche Leute die Verbindung gelaufen sind, |
| // kostet es die Basiskosten. Fuer Seher auch die Spieler einschliessen. |
| if (interest[CONN_U_PLAYERS]==-1 |
| || (seer && interest[CONN_U_SEERS]==-1)) |
| return costs; |
| else |
| { |
| // Sonst wird die Verbindung teurer. |
| // Anzahl Spielernutzer kann nicht -1 sein (s.o.). |
| int usercount = sizeof(interest[CONN_U_PLAYERS]); |
| // wenn <seer>, wird ggf. die Anzahl an Sehernutzern drauf addiert. |
| // Wert fuer Seher kann nicht -1 sein (s.o.) |
| if (seer) |
| usercount += sizeof(interest[CONN_U_SEERS]); |
| switch (usercount) |
| { |
| case 0: |
| costs=1000000; |
| break; |
| case 1..2: |
| costs*=COST_ONE; |
| case 3..4: |
| costs*=COST_FEW; |
| default: |
| costs*=COST_MANY; |
| } |
| return costs; |
| } |
| DBG(sprintf("Huch, keine Ahnung, Kosten unbestimmbar: %O",path)); |
| return 1000; |
| } |
| |
| // Neuimplementation von Humni, benutzt einfach simpel einen |
| // Dijkstra-Algorithmus. "Simpel" schreibe ich, bevor ich die |
| // Funktion schreibe, fluchen werde ich gleich. |
| static void _search(string fname, string from) |
| { |
| // <from> ist jetzt anzuguckende/zu bearbeitende Raum. |
| |
| // Die aktuelle Liste an abgesuchten Raeumen, Raeume, in denen |
| // alle Wege bereits eingetragen sind. |
| string* rooms_searched=searchlist[fname,SL_VISITED]; |
| |
| // Zielort |
| string to = searchlist[fname,SL_DESTINATION]; |
| |
| // moegliche Ziele |
| mapping targets=searchlist[fname,SL_CANDIDATES]; |
| |
| // wizlevel |
| int seer = searchlist[fname,SL_WIZLEVEL]; |
| |
| // para |
| int para=searchlist[fname,SL_PARA]; |
| |
| // Noch zu bearbeitende Raeume |
| string* to_do=searchlist[fname,SL_TODO]; |
| |
| DBG("_search() start."); |
| |
| while ((get_eval_cost()>900000) && from && (from != to)) |
| { |
| // Fuege den aktuellen Raum (from) als Weg hinzu |
| DBG(sprintf("Fuege hinzu: %s",from)); |
| rooms_searched+=({from}); |
| // Aus den Raeumen drumrum werden die Ausgaenge gesucht |
| // und zur Wegliste hinzugefuegt. |
| |
| // Pfade von <from> weg aus der Liste holen |
| mixed* paths=pathmap[_get_prefix(from)][from]; |
| |
| // Liste der Verbindungen von <from> durchgehen |
| foreach (mixed conn:paths) |
| { |
| int newcost; |
| // wenn der Raum schonmal gesehen wurde, ist hier nix mehr noetig. |
| if (member(rooms_searched,conn[CONN_DEST])>-1) |
| { |
| DBG(sprintf("Raum %s hab ich schon!",conn[CONN_DEST])); |
| } |
| else |
| { |
| // Verbindung je nach Flag nicht nutzen. Ausserdem: |
| // wenn die Verbindung in eine Parawelt fuehrt, aber kein |
| // Seherstatus gegeben ist, existiert die Verbindung nicht. |
| // Weiterhin kommt eine Verbindung nicht in Frage, wenn sie in |
| // eine andere Parawelt fuehrt, weil der Weltuebergang nur an |
| // bestimmten Orten moeglich ist. Ausnahme davon sind Wechsel |
| // zwischen Normalwelt und Parawelt. |
| if ( |
| (conn[CONN_FLAGS] & CFLAG_DONTUSE) |
| || (conn[CONN_FLAGS] & CFLAG_DUPLICATE) |
| || (!seer && conn[CONN_PARA]) |
| || (conn[CONN_PARA] && conn[CONN_PARA] != para) |
| ) |
| continue; |
| newcost = targets[from,SLT_COSTS]; // kosten bis hierher |
| // + Kosten in naechsten Raum. |
| newcost += _calc_cost(conn,seer,para); |
| // es koennte sein, dass es Verbindungen mit gleichem |
| // Start/Ziel gibt, aber unterschiedlichen Kosten. In diesem |
| // Fall wuerde das Ziel der aktuellen Verbindung mehrfach |
| // hinzugefuegt und das letzte gewinnt. Daher sollte diese |
| // Verbindung nur hinzugefuegt werden, wenn noch keine |
| // Verbindung in den Zielraum existiert, die billiger ist. |
| if (member(targets,conn[CONN_DEST]) |
| && newcost >= targets[conn[CONN_DEST],SLT_COSTS]) |
| continue; |
| // Weg bis hierher plus naechsten Raum |
| string* new_way = targets[from,SLT_WAY]; |
| new_way += ({conn[CONN_DEST]}); |
| // Kommandos bis hierher plus naechstes Kommando |
| string* new_commands = targets[from,SLT_COMMANDS]; |
| new_commands += ({conn[CONN_CMD]}); |
| // naechsten Raum in Todo fuer die Pruefung unten vermerken |
| to_do += ({conn[CONN_DEST]}); |
| // Und Kosten/Weg/Kommandos bis zum naechsten Raum unter |
| // targets/Kandidaten ablegen. |
| targets += ([conn[CONN_DEST]:newcost;new_way;new_commands]); |
| } |
| } |
| // Nachdem die Raeume alle zu den Kandidaten an moeglichen Wegen |
| // hinzugefuegt wurden, wird nun der neueste kuerzeste Weg gesucht. |
| // Natuerlich nur aus denen, die schon da sind. |
| if (sizeof(to_do)>0) |
| { |
| // Kosten des ersten todo als Startwert nehmen |
| string minraum; |
| int mincosts=__INT_MAX__; |
| // und ueber alle todos laufen um das Minimum zu finden. |
| foreach(string raum: to_do) |
| { |
| if (mincosts>targets[raum,SLT_COSTS]) |
| { |
| minraum = raum; |
| mincosts=targets[raum,SLT_COSTS]; |
| } |
| } |
| DBG(sprintf("Neuer kuerzester Raum: %s",minraum)); |
| |
| // der billigst zu erreichende Raum wird das neue <from> fuer den |
| // naechsten Durchlauf |
| from=minraum; |
| // und natuerlich aus dem to_do werfen. |
| to_do-=({minraum}); |
| DBG(sprintf("Anzahl untersuchter Raeume: %d, Todo: %d, " |
| "Kandidaten: %d", |
| sizeof(rooms_searched),sizeof(to_do),sizeof(targets))); |
| } |
| else |
| { |
| from=0; |
| } |
| } // while ende |
| |
| if (!from) |
| { |
| // Hmpf... |
| TELL_USER("Kein Weg gefunden!"); |
| if (searchlist[fname, SL_CALLBACK]) |
| funcall(searchlist[fname,SL_CALLBACK], |
| searchlist[fname,SL_START], to, para, |
| 0,0,0); |
| m_delete( searchlist, fname ); // suchauftrag entsorgen |
| return; |
| } |
| else if (from==to) |
| { |
| // JUCHU! |
| TELL_USER(sprintf("Weg gefunden! %O,%O,%O", |
| targets[to,SLT_COSTS],targets[to,SLT_WAY], |
| targets[to,SLT_COMMANDS])); |
| add_to_cache(searchlist[fname,SL_START], to, para, |
| targets[to,SLT_COSTS],targets[to,SLT_WAY], |
| targets[to,SLT_COMMANDS]); |
| if (searchlist[fname, SL_CALLBACK]) |
| funcall(searchlist[fname,SL_CALLBACK], |
| searchlist[fname,SL_START], to, para, |
| targets[to,SLT_COSTS],targets[to,SLT_WAY], |
| targets[to,SLT_COMMANDS]); |
| m_delete( searchlist, fname ); // suchauftrag entsorgen |
| return; |
| } |
| |
| // Wenn das alles nicht war, waren es die Eval-Ticks. Mist. Spaeter |
| // weitersuchen... |
| searchlist[fname,SL_VISITED]=rooms_searched; |
| searchlist[fname,SL_CANDIDATES]=targets; |
| searchlist[fname,SL_TODO]=to_do; |
| call_out("_search",2,fname,from); |
| } |
| |
| |
| // Die Daten ueber Raeume werden quasi gehasht abgespeichert, damit wir nicht |
| // so schnell an die Begrenzung bei Arrays und Mappings stossen. |
| // Dabei ist der 'Hash' der Anfang des Pfades. |
| private string _get_prefix( string path ) |
| { |
| string *tmp; |
| |
| tmp = explode( path, "/" ); |
| |
| // Bei Raeumen unterhalb von /d/* wird /d/region/magiername benutzt |
| if ( strstr(path, "/d/") == 0) |
| return implode( tmp[0..3], "/" ); |
| // Ansonsten die ersten beiden Teilpfade, falls soviele vorhanden sind |
| else if ( sizeof(tmp) < 4 ) |
| return implode( tmp[0..1], "/" ); |
| else |
| return implode( tmp[0..2], "/" ); |
| } |
| |
| // Reset und Datenhaltung |
| // reset wird alle 3h gerufen, um das Savefile immer mal wieder zu speichern. |
| // Datenaufraeumen aber nur einmal pro Tag. |
| public void reset() |
| { |
| if ( time_to_clean_up <= time() ) |
| { |
| // Einmal pro Tag Reset zum Aufraeumen der Datenbank |
| rm(DUMPFILE".raeume"); |
| rm(DUMPFILE".conns"); |
| time_to_clean_up = time() + 86400; |
| expire_path_cache(m_indices(pathcache)); |
| call_out(#'cleanup_data, 30, |
| sort_array(m_indices(pathmap), #'</*'*/), 0 ); |
| |
| } |
| save_object(SAVEFILE); |
| set_next_reset(10800); |
| } |
| |
| protected void expire_path_cache(string *startrooms) { |
| foreach(string start : startrooms) { |
| mapping targets = pathcache[start]; |
| foreach (string target, mapping paths: targets) { |
| foreach(int para, struct path_s p: paths) { |
| if (p->ttl < time() |
| || !(p->flags & PFLAG_PERMANENT) ) |
| m_delete(paths,para); |
| } |
| if (!sizeof(paths)) |
| m_delete(targets, target); |
| } |
| startrooms-=({start}); |
| if (!sizeof(targets)) |
| m_delete(pathcache, start); |
| // recht grosser Wert, weil immer komplette Startraeume in einem |
| // erledigt werden. |
| if (get_eval_cost() < 1000000) |
| break; |
| } |
| if (sizeof(startrooms)) |
| call_out(#'expire_path_cache, 4, startrooms); |
| } |
| |
| // Datenbank aufraeumen |
| protected void cleanup_data( string *names, int idx ) |
| { |
| int size, i, j, k; |
| string *rooms; |
| mixed *paths; |
| |
| size = sizeof(names); |
| |
| // Ein bisserl mitloggen, damit wir Schwachstellen im System auch finden. |
| if ( !idx ){ |
| LOG( sprintf("=== %s: Starte cleanup_data(): %O Gebiete, %O Raeume " |
| + "...\n", strftime("%y%m%d-%H%M%S"), size, |
| show_statistic(1, 1) ) ); |
| } |
| else { |
| LOG( sprintf("%s: Setze cleanup_data() fort.\n", |
| strftime("%y%m%d-%H%M%S") ) ); |
| } |
| |
| // Brav gesplittet, damit es kein Lag gibt. |
| // Die Grenze ist recht hoch angesetzt, da immer gleich komplette |
| // Teilbaeume aufgeraeumt werden. |
| while ( get_eval_cost() > 1100000 && idx < size ){ |
| rooms = sort_array( m_indices(pathmap[names[idx]]), #'</*'*/ ); |
| |
| for ( i = sizeof(rooms); i--; ){ |
| paths = pathmap[names[idx]][rooms[i]]; |
| int conn_count = sizeof(paths); |
| mapping cmds=m_allocate(sizeof(paths)); |
| |
| for ( j = conn_count; j--; ) { |
| mixed conn = paths[j]; |
| for ( k = 0; k < 2; k++ ) { // Spieler/Sehereintraege |
| // Diese Verbindung hat noch keiner genutzt bisher |
| if ( !conn[CONN_TIMES][k] ) |
| continue; |
| // Wenn Verbindung permanent, ueberspringen |
| if (conn[CONN_FLAGS] & CFLAG_PERMANENT) |
| continue; |
| |
| if ( conn[CONN_USERS][k] == -1 // 'bekanntes' Gebiet |
| && time() - conn[CONN_TIMES][k] > TIMEOUT_OLD ){ |
| // LOG( sprintf("*** Loesche alte " |
| // + (k ? "Seher" : "Spieler") |
| // + "-Verbindung %O.\n", paths[j]) ); |
| conn[CONN_USERS][k] = ({}); |
| conn[CONN_TIMES][k] = 0; |
| } |
| else if ( conn[CONN_USERS][k] != -1 // 'neues' Gebiet |
| && time() - conn[CONN_TIMES][k] > TIMEOUT_NEW ){ |
| conn[CONN_USERS][k] = ({}); |
| conn[CONN_TIMES][k] = 0; |
| } |
| } |
| |
| // Wenn eine Verbindung weder von Spielern noch von Sehern |
| // benutzt wurde in letzter Zeit und sie keine permanented |
| // ist, Verbindung ganz loeschen. |
| if (!(conn[CONN_FLAGS] & CFLAG_PERMANENT) |
| && !conn[CONN_TIMES][CONN_T_PLAYERS] |
| && !conn[CONN_TIMES][CONN_T_SEERS] ) { |
| paths[j..j] = ({}); // conn rauswerfen |
| conn_count--; |
| } |
| else { |
| // Connections nach Kommandos speichern. |
| if (member(cmds, conn[CONN_CMD])) |
| cmds[conn[CONN_CMD]] += ({conn}); |
| else |
| cmds[conn[CONN_CMD]] = ({conn}); |
| // und das duplicate flag loeschen, das wird spaeter neu |
| // gesetzt, wenn noetig. |
| // (There is no chance that a concurrent search will check |
| // these connections until they are marked again.) |
| conn[CONN_FLAGS] &= ~CFLAG_DUPLICATE; |
| // Connections dumpen |
| if (!(conn[CONN_FLAGS] & CFLAG_DUPLICATE)) |
| { |
| mixed u=({conn[CONN_USERS][CONN_U_PLAYERS], |
| conn[CONN_USERS][CONN_U_SEERS] }); |
| write_file(DUMPFILE".conns",sprintf( |
| "%s|%s|%s|%d|%d|%d|%d\n", |
| rooms[i],conn[CONN_DEST],conn[CONN_CMD], |
| conn[CONN_EXITTYPE],conn[CONN_PARA], |
| (u[0]==-1 ? 0 : NEEDED-sizeof(u[0])), |
| (u[0]==-1 ? 0 : NEEDED-sizeof(u[0])) |
| )); |
| } |
| } |
| } |
| |
| // Ein Raum ohne Verbindungen frisst nur Platz in der Datenbank |
| if ( !conn_count ){ |
| // LOG( sprintf("*** Loesche kompletten Raum %O\n", rooms[i]) ); |
| m_delete( pathmap[names[idx]], rooms[i] ); |
| } |
| else { |
| // wenn Kommandos nicht eindeutig sind, dann werden die |
| // entsprechenden Verbindungen gekennzeichnet. Alle in Frage |
| // kommenden Verbindungen sind jeweils schon zusammensortiert. |
| foreach(string cmd, mixed conns : cmds) { |
| if (sizeof(conns)>1) |
| check_and_mark_duplicate_conns(conns); |
| } |
| // ggf. geaendertes Verbindungsarray wieder ins Mapping |
| // schreiben. |
| pathmap[names[idx]][rooms[i]] = paths; |
| // Raum/Node ins Dump schreiben |
| write_file(DUMPFILE".raeume",sprintf( |
| "%s\n",rooms[i])); |
| } |
| } |
| idx++; |
| } |
| if ( idx >= size ) { |
| LOG( sprintf("=== %s: Beende cleanup_data()! Uebrig: %O Raeume.\n", |
| strftime("%y%m%d-%H%M%S"), show_statistic(1, 1) ) ); |
| } |
| else { |
| call_out( #'cleanup_data, 2, names, idx ); |
| LOG( sprintf("%s: WARTE 20s bei Evalcost %O\n", |
| strftime("%y%m%d-%H%M%S"), get_eval_cost()) ); |
| } |
| } |
| |
| // Beim Entladen speichern |
| public varargs int remove( int silent ) |
| { |
| // Vor dem Entfernen noch schnell die Daten sichern |
| save_object(SAVEFILE); |
| destruct(this_object()); |
| |
| return 1; |
| } |
| |
| |
| // Zum Debuggen. Nur für Tiamak. Bzw. nun fuer Zook, Vanion, Rumata |
| #define ALLOWED ({"zook","vanion","rumata","zesstra","humni"}) |
| #define MATCH(x,y) (sizeof(regexp(x,y))) |
| public mapping get_pathmap() |
| { |
| if ( !this_interactive() || !MATCH(ALLOWED,getuid(this_interactive())) |
| || !previous_object() || !MATCH(ALLOWED,getuid(previous_object()))) |
| return ([]); |
| |
| return pathmap; |
| } |
| public mapping get_pathcache() |
| { |
| if ( !this_interactive() || !MATCH(ALLOWED,getuid(this_interactive())) |
| || !previous_object() || !MATCH(ALLOWED,getuid(previous_object()))) |
| return ([]); |
| |
| return pathcache; |
| } |
| |
| #undef ALLOWED |
| #undef MATCH |