blob: 17d34ad0b5ea1525506f1aeac15077cf55bda6af [file] [log] [blame]
MG Mud User88f12472016-06-24 23:31:02 +02001// Daemon zum automatisierten Erstellen von Karten.
2// Soll spaeter mal wichtige Wege berechnen koennen fuer Anfaenger.
3//
4//
5// Wer mir ohne triftigen Grund daran herumpfuscht, der wird standesrechtlich
6// mit faulen Eiern beworfen. ]:->
7//
8// Tiamak
9
10#pragma strong_types,save_types,rtt_checks
11#pragma no_clone,no_inherit,no_shadow
12#pragma pedantic,range_check,warn_deprecated
13#pragma warn_empty_casts,warn_missing_return,warn_function_inconsistent
14
15#include <strings.h>
16#include <wizlevels.h>
17#include <player.h>
18#include <properties.h>
19#include <rooms.h>
20#include <moving.h>
21
22#define LOGNAME "PATHD"
23#define SAVEFILE "/p/daemon/save/pathd"
24#define DUMPFILE "/p/daemon/save/pathd-dump"
25//#define DEBUG
26
27// 10 verschiedene Leute werden gebraucht, um eine Verbindung zu verifizieren
28#define NEEDED 10
29#define TIMEOUT_NEW 1209600 // 14 Tage
30#define TIMEOUT_OLD 7776000 // 90 Tage
31
32// Art des Ausgangs
33#define NORMAL 0
34#define SPECIAL 1
35#define COMMAND 2
36
37// Kosten fuer unterschiedliche Wege
38#define COST_EXITS ({ 1, 10, 100 })
39#define COST_MANY 3
40#define COST_FEW 5
41#define COST_ONE 10
42// Kosten fuer Weltenwechsel (Para -> Normal)
43#define COST_WORLDCHANGE 100
44
45#ifdef DEBUG
46#define DBG(x) if ( find_player("zesstra") ) \
47 tell_object( find_player("zesstra"), (x)+"\n" );
48#define TELL_USER(x) if ( this_player() ) \
49 tell_object( this_player(), (x)+"\n" );
50#else
51#define DBG(x)
52#define TELL_USER(x)
53#endif
54
55#define LOG(x) log_file( "PATHD", (x), 100000 );
56
57// Variablen
58nosave int time_to_clean_up; // Zeit fuer naechstes Cleanup der Daten
59
60mapping pathmap;
61/* Prefix : ([ <submap> ]),
62 <submap> ist ein Mapping von Raeumen mit einem Array von Verbindungen:
63 ([<room>: ({ conn1, conn2, conn3, ...}), ...])
64 Jede Verbindung ist ein Array mit folgenden Indizes:
65 */
66#define CONN_DEST 0 // Zielraum
67#define CONN_CMD 1 // Kommando
68#define CONN_USERS 2 // Benutzer: ({spieler, seher})
69#define CONN_EXITTYPE 3 // Ausgangsart (s.o.)
70#define CONN_TIMES 4 // Zeit letzter Benutzung: ({spieler,seher})
71#define CONN_PARA 5 // Parawelt
72#define CONN_FLAGS 6 // Flags fuer die Verbindung (z.B. permanent)
73// Indizes in CONN_USERS. Beide Eintraege sind entweder gehashte UIDs ODER -1,
74// wenn die Verbindung von mehr als NEEDED unterschiedlichen gegangen wurde.
75#define CONN_U_PLAYERS 0 // Spieler-UIDs
76#define CONN_U_SEERS 1 // Seher-UIDS
77// Indizes von CONN_TIMES. Zeitstempel der letzten Benutzung...
78#define CONN_T_PLAYERS CONN_U_PLAYERS // ... durch Spieler
79#define CONN_T_SEERS CONN_U_SEERS // ... durch Seher
80
81// Konstanten fuer CONN_FLAGS
82#define CFLAG_PERMANENT 0x1 // Verbindung nicht expiren
83#define CFLAG_DONTUSE 0x2 // Verbindung nicht im Routing nutzen
84#define CFLAG_DUPLICATE 0x4 // Kommando hat mehrere Verbindungen
85
86// laufende Pfadsuchen
87nosave mapping searchlist = ([]);
88/*
89 ([ <uuid> : SL_VISITED; SL_DESTINATION;... ... ])
90 */
91// Indizes in <data>:
92#define SL_START 0
93#define SL_DESTINATION 1 // Zielraum
94#define SL_VISITED 2 // abgelaufene/gepruefte Raeume
95#define SL_CANDIDATES 3 // moegliche Ziele
96#define SL_WIZLEVEL 4 // Wizlevel
97#define SL_PARA 5 // Parawelt
98#define SL_TODO 6 // noch zu pruefende Raume (SL_CANDIDATES-SL_VISITED)
99#define SL_CALLBACK 7 // Closure fuer Callback nach Routenberechnung
100// SL_CANDIDATES: ([<raum>: ({verbindungsdaten}), ...])
101// Indizes im Array <verbindungsdaten>:
102#define SLT_COSTS 0 // Kosten fuer Verbindung bis hier
103#define SLT_WAY 1 // bisheriger Weg von Start bis hier
104#define SLT_COMMANDS 2 // Kommandos fuer Weg von Start bis hier
105
106// cache fuer berechnete Wege
107nosave mapping pathcache = ([]);
108// Aufbau: ([ "startraum": <dests>, ...])
109// <dests>: (["zielraum": <wege>, ...])
110// <wege>: ([parawelt: (<struct path_s>) ])
111
112struct path_s {
113 int costs; // Kosten des kompletten Pfades
114 string *rooms; // Liste von durchlaufenen Raeumen
115 string *cmds; // Liste von Kommandos, um Raeume zu durchlaufen
116 int ttl; // time-to-live, Ablaufzeit des Pfads im Cache
117 int para; // Parawelt
118 int flags; // Flags zu dem Pfad
119};
120// Flags fuer Pfade im Pfadcache
121#define PFLAG_PERMANENT CFLAG_PERMANENT
122#define PFLAG_DONTUSE CFLAG_DONTUSE
123
124
125// Prototypes
126public void create();
127public void add_paths( mixed connections );
128public varargs void show_pathmap( string path );
129public varargs int show_statistic( int verbose, int silent );
130public int change_pathmap( string pfad, mixed *verbindungen );
131public mapping get_pathmap();
132public void reset();
133public varargs int remove( int silent );
134public varargs int query_prevent_shadow( object ob );
135static int insert_paths( mixed *path );
136static mixed *format_paths( mixed buf );
137static void _search( string fname, string start );
138private string _get_prefix( string path );
139protected void cleanup_data( string *names, int idx );
140protected void expire_path_cache(string *startrooms);
141
142
143public void create()
144{
145 // wir muessen das Savefile schreiben duerfen
146 seteuid(getuid());
147
148 if ( !restore_object(SAVEFILE) ) {
149 pathmap = ([]);
150 }
151}
152
153
154// Wird von Spielern aufgerufen mit den Wegen, die sie gelaufen sind
155public void add_paths( mixed connections )
156{
157 mixed paths;
158
159 // keinen Aufruf per Hand bitte
160 if ( !previous_object() || !this_player()
161 || this_interactive() && getuid(this_interactive()) != "zesstra"
162 || file_size( "/std/shells" +
163 explode( object_name(previous_object()), ":" )[0]
164 + ".c" ) < 1 )
165 return;
166
167#if __BOOT_TIME__ < 1357042092
168 // alte Spielerobjekte liefern noch ein Array von Strings statt eines
169 // Arrays von Arrays.
170 connections = map(connections, function mixed (string path)
171 {
172 // Alle Daten kommen als ein String mit '#' als Trenner an.
173 // Muster: Startraum#Zielraum#Verb#Methode der Bewegung#Parawelt
174 mixed buf = explode( path, "#" );
175 // Falls im Verb auch # vorkam (unwahrscheinlich, aber moeglich):
176 buf[2..<3] = ({ implode( buf[2..<3], "#" ) });
177 return buf;
178 }
179 );
180#endif
181
182 // Daten aufbereiten
183 paths = map( connections, #'format_paths/*'*/ ) - ({0});
184 // Neue Raeume eintragen
185 filter( paths, #'insert_paths/*'*/ );
186}
187
188public mixed get_path_from_cache(string from, string to, int para) {
189 // wenn im Cache, aus dem Cache liefern.
190 mapping targets = pathcache[from];
191 if (targets) {
192 mapping paths = targets[to];
193 if (paths) {
194 if (member(paths, para)) {
195 struct path_s p = paths[para];
196 if (p->ttl > time())
197 return ({ from, to, para, p->costs,
198 copy(p->rooms), copy(p->cmds) });
199 else {
200 m_delete(paths, para);
201 }
202 }
203 }
204 }
205 return 0;
206}
207
208// Suchfunktion, um die kuerzeste Verbindung zwischen zwei Raeumen zu finden
209public int SearchPath( string from, string to, int para,
210 closure callback)
211{
212 // Pro UID darf es nur einen Suchauftrag geben.
213 string uid=getuid(previous_object());
214 if ( member(searchlist,uid) )
215 return -1;
216 // und mehr als 5 gleichzeitig erstmal auch nicht.
217 if (sizeof(searchlist)>4)
218 return -2;
219
220 // Anfrage loggen
221 LOG(sprintf("%s: Suche %s -> %s (%d) von %s (%s, %s, %s)\n",
222 strftime("%y%m%d-%H%M%S"), from, to, para, uid,
223 object_name(previous_object()),
224 object_name(this_player()) || "NO-PL",
225 object_name(this_interactive()) || "NO-TI") );
226
227 // wenn Start- oder Zielraum nicht bekannt sind, kann es auch keine Route
228 // geben.
229 if (!member(pathmap[_get_prefix(to)],to)
230 || !member(pathmap[_get_prefix(from)],from) )
231 return -3;
232
233 mixed path = get_path_from_cache(from, to, para);
234 if (path) {
235 if (callback)
236 apply(callback,path);
237 return 2;
238 }
239
240 // Datenstrukturerklaerung: s.o.
241 mapping targets = m_allocate(1200,3);
242 m_add(targets,from,0,({}),({}) );
243 searchlist+= ([ uid: from; to; ({});
244 targets;
245 (query_wiz_level(this_interactive())?1:0);
246 para; ({}); callback]);
247
248 // Die eigentliche Suche starten
249 _search( uid, from );
250
251 return 1;
252}
253
254// Gespeicherte Informationen zu einem Raum oder einem kompletten Gebiet
255// abfragen. Gebiete lassen sich aber nur als "Organisationseinheiten" abfragen.
256// Dabei werden Gebiete unterhalb von /d/* als /d/region/magiername
257// abgespeichert und der Rest unter den ersten beiden Teilpfaden.
258public varargs void show_pathmap( string path )
259{
260 string pre;
261
262 if ( path )
263 {
264 pre = _get_prefix(path);
265
266 if ( pre == path )
267 // Ganzen Teilbaum ausgeben
268 printf( "Pathmap[%O]: %O\n", path, pathmap[path] );
269 else
270 // Nur Infos ueber einen Raum ausgeben
271 printf( "Pathmap[%O]: %O\n", path,
272 pathmap[pre] ? pathmap[pre][path] : 0 );
273 }
274 else
275 // Ohne Argument wird die gesamte Map ausgegeben.
276 // Klappt aber eher nicht (mehr) wegen Buffer overflow. ;^)
277 printf( "Pathmap: %O\n", pathmap );
278}
279
280
281// Statistic zu den gespeicherten Daten anzeigen.
282// Mit 'verbose' wird jede Organisationseinheit einzeln aufgelistet, ohne
283// wird grob nach Regionen zusammengefasst.
284public varargs int show_statistic( int verbose, int silent )
285{
286 int i, ges;
287 string *ind, name;
288 mapping m;
289
290 if ( verbose ){ // Stur jeden Eintrag auflisten
291 ind = sort_array( m_indices(pathmap), #'</*'*/ );
292 for ( i = sizeof(ind); i--; ){
293 if ( !silent )
294 printf( "%-30s: %4d\n", ind[i], sizeof(pathmap[ind[i]]) );
295 ges += sizeof(pathmap[ind[i]]);
296 }
297 }
298 else { // Regionen zusammenfassen
299 ind = m_indices(pathmap);
300 m = ([]);
301
302 for ( i = sizeof(ind); i--; ){
303 if (strstr(ind[i],"/d/") == 0)
304 // /d... jeweils nach zwei Teilpfaden
305 name = implode( explode( ind[i], "/" )[0..2], "/" );
306 else if ( strstr(ind[i],"/players") == 0)
307 // Alle Playerverzeichnisse zusammenfassen ...
308 name = "/players";
309 else
310 // ... den Rest nach einem Teilpfad
311 name = implode( explode( ind[i], "/" )[0..1], "/" );
312
313 if ( !m[name] )
314 m[name] = sizeof( pathmap[ind[i]] );
315 else
316 m[name] += sizeof( pathmap[ind[i]] );
317 }
318
319 ind = sort_array( m_indices(m), #'</*'*/ );
320 for ( i = sizeof(ind); i--; ){
321 if ( !silent )
322 printf( "%-30s: %4d\n", ind[i], m[ind[i]] );
323 ges += m[ind[i]];
324 }
325 }
326
327 if ( !silent )
328 printf( "\nGesamt: %d Raeume.\n", ges );
329
330 return ges;
331}
332
333
334// Manipulieren der internen Pathmap. Nur zum Debuggen und somit
335// nur fuer Zesstra erlaubt. Sonst verhunzt mir noch wer meine Daten. ;^)
336public int change_pathmap( string pfad, mixed *verbindungen )
337{
338 if ( !this_interactive() || getuid(this_interactive()) != "zesstra"
339 || !previous_object() || getuid(previous_object()) != "zesstra" )
340 return -1;
341
342 if ( mappingp(verbindungen) ){
343 if ( !pathmap[_get_prefix(pfad)] )
344 return 0;
345
346 pathmap[_get_prefix(pfad)] = verbindungen;
347 }
348 else {
349 if ( !pathmap[_get_prefix(pfad)][pfad] )
350 return 0;
351
352 pathmap[_get_prefix(pfad)][pfad] = verbindungen;
353 }
354
355 return 1;
356}
357
358// Die Funktion gibt alle dem pathd bekannten Raeume als Mapping von Arrays
359// zurueck. Schlüssel des Mappings sind dabei Gebiete.
360public mapping get_rooms()
361{
362 string *submaps;
363 mapping roommap;
364 int i;
365
366 roommap=([]);
367
368 submaps=m_indices(pathmap);
369
370 i=sizeof(submaps);
371
372 while (i--)
373 if (sizeof(m_indices(pathmap[submaps[i]])))
374 roommap[submaps[i]]=m_indices(pathmap[submaps[i]]);
375
376 return roommap;
377}
378
379// Daten zu einer Verbindung sammeln und aufbereiten
380static mixed *format_paths( mixed buf )
381{
382 string cmd, uid;
383 object ob;
384 mapping exits;
385 int art;
386
387 // Magier und Testspieler koennen auch in nicht angeschlossene Gebiete
388 // und werden deshalb nicht beachtet.
389 if ( IS_LEARNER(previous_object(1)) ||
390 IS_LEARNER(lower_case( previous_object(1)->Query(P_TESTPLAYER)||"" )) )
391 return 0;
392
393 cmd = trim(buf[2],TRIM_BOTH);
394#if __BOOT_TIME__ < 1357042092
395 // " 0" am Ende des Befehls abschneiden. *grummel*
396 if (cmd[<2..]==" 0")
397 cmd = cmd[..<3];
398#endif
399
400 // Wenn der Zielraum als String angegeben wurde, kann der fuehrende
401 // Slash fehlen!
402 if ( buf[1][0] != '/' )
403 buf[1] = "/" + buf[1];
404
405 // Zum Abfragen der zusaetzlichen Daten brauchen wir das Objekt selber
406 catch(ob = load_object(buf[0]);publish);
407 if (!objectp(ob))
408 return 0;
409
410 // Kleiner Hack - bei Transportern etc. ist 'ob' die nicht initialisierte
411 // Blueprint. Jede Abfrage von P_EXITS wuerde nett auf -Debug scrollen.
412 // Da P_IDS im create() auf jeden Fall auf ein Array gesetzt wird,
413 // missbrauche ich das hier als "Ist initialisiert"-Flag.
414 if ( !ob->QueryProp(P_IDS) )
415 return 0;
416
417 // Art des Ausgangs feststellen.
418 if ( mappingp(exits = ob->QueryProp(P_EXITS)) && exits[cmd] )
419 art = NORMAL; // "normaler" Ausgang
420 else if ( mappingp(exits = ob->QueryProp(P_SPECIAL_EXITS)) && exits[cmd] )
421 art = SPECIAL; // SpecialExit
422 else {
423 // Kommandos, die einen in einen anderen Raum bringen
424 art = to_int(buf[3]); // Move-Methode
425
426 // Es zaehlen aber nur Bewegungen, die halbwegs "normal" aussehen,
427 // d.h. kein M_TPORT, M_NOCHECK und M_GO muss gesetzt sein.
428 if ( art & (M_TPORT | M_NOCHECK) || !(art & M_GO) )
429 return 0;
430 else
431 art = COMMAND;
432 }
433
434 // Die UID der Spieler/Seher wird verschluesselt.
435 // Schliesslich brauchen wir sie nur fuer statistische Zwecke und nicht,
436 // um Bewegungsprofile zu erstellen. crypt() reicht fuer diese Zwecke
437 // wohl erstmal.
438 uid = getuid(previous_object(1));
439 uid = crypt( uid, "w3" );
440
441 // Start, Ziel, Verb, Wizlevel(TP), UID(TP), Art des Ausgangs, Parawelt
442 return ({ buf[0], buf[1], cmd, query_wiz_level(previous_object(1)) ? 1 : 0,
443 uid, art, to_int(buf[4]) });
444}
445
446// Prueft alle Verbindungen im Array <conns>, welche das gleiche Kommando wie
447// <conn> haben, ob sie in unterschiedliche Raeume fuehren. Wenn ja, sind sie
448// fuer das Routing nicht nutzbar. Ausnahme: Verbindungen, die in
449// unterschiedliche Parawelten fuehren.
450// Aendert <conns> direkt.
451private void check_and_mark_duplicate_conns_by_conn(mixed conns, mixed conn) {
452 foreach(mixed c: conns) {
453 if ( c[CONN_CMD] == conn[CONN_CMD]
454 && c[CONN_DEST] != conn[CONN_DEST]
455 && c[CONN_PARA] == conn[CONN_PARA] )
456 {
457 c[CONN_FLAGS] |= CFLAG_DUPLICATE;
458 conn[CONN_FLAGS] |= CFLAG_DUPLICATE;
459 }
460 }
461}
462
463private void check_and_mark_duplicate_conns(mixed conns) {
464 foreach(mixed c: conns)
465 check_and_mark_duplicate_conns_by_conn(conns, c);
466}
467
468
469// Neue Verbindung in der Datenbank eintragen
470static int insert_paths( mixed *path )
471{
472 string pre = _get_prefix(path[0]);
473
474 // Falls noch gar kein Eintrag existiert, neu initialisieren
475 if ( !mappingp(pathmap[pre]) )
476 pathmap[pre] = ([]);
477
478 if ( !pointerp(pathmap[pre][path[0]]) )
479 pathmap[pre][path[0]] = ({});
480
481 // Aufbau von 'path':
482 // ({ Start, Ziel, Verb, Wizlevel(TP), UID(TP), Art des Ausgangs, Para })
483 // Aufbau von 'conn' (s. auch ganz oben)
484 // ({ Ziel, Verb, ({ Spieler-UIDs, Seher-UIDs }), Art des Ausgangs,
485 // ({ Letztes Betreten durch Spieler, durch Seher }), Parawelt })
486
487 // Alle Verbindungen des Raumes durchgehen
488 mixed conns = pathmap[pre][path[0]];
489 // Kommandos der Verbindungen sammeln. Wenn es zwei Verbindungen mit dem
490 // gleichen Kommando gibt, sind beide unbenutzbar.
491 mixed cmds = m_allocate(10);
492 int i;
493 for ( i = sizeof(conns); i--; )
494 {
495 mixed conn = conns[i];
496 m_add(cmds,conn[CONN_CMD]); // Kommandos aller Conns merken
497 // Wenn Zielraum, Verb und Parawelt passen ...
498 if ( conn[CONN_DEST] == path[1] && conn[CONN_CMD] == path[2]
499 && conn[CONN_PARA] == path[6] )
500 {
501 // Wenn schon genug Leute diese Verbindung genutzt haben, einfach
502 // nur die Zeit der letzten Benutzung aktualisieren.
503 int index = path[3] ? CONN_U_SEERS : CONN_U_PLAYERS; // Seher?
504 if ( conn[CONN_USERS][index] == -1 )
505 {
506 conn[CONN_TIMES][index] = time();
507 break;
508 }
509 // Ansonsten die (neue?) UID hinzufuegen und die Zeit aktualisieren.
510 else
511 {
512 conn[CONN_USERS][index] =
513 conn[CONN_USERS][index] - ({ path[4] }) + ({ path[4] });
514 if ( sizeof(conn[CONN_USERS][index]) >= NEEDED )
515 conn[CONN_USERS][index] = -1;
516
517 conn[CONN_TIMES][index] = time();
518 break;
519 }
520 }
521 }
522
523 // Falls keine Verbindung gepasst hat, eine neue erzeugen.
524 if ( i < 0 ) {
525 int index = path[3] ? CONN_U_SEERS : CONN_U_PLAYERS; // Seher?
526 mixed uids = ({ ({}), ({}) });
527 uids[index] = ({ path[4] });
528 mixed times = ({ 0, 0 });
529 times[index] = time();
530
531 // Aufbau siehe oben
532 mixed conn = ({ path[1], path[2], uids, path[5], times, path[6], 0 });
533 conns += ({ conn });
534 // wenn die neue Verbindung nen Kommando benutzt, welches schon fuer
535 // eine andere Verbindung aus diesem Raum benutzt wird, sind beide
536 // nicht nutzbar, da das Ziel nicht eindeutig ist. In diesem Fall
537 // muessen alle diese als unbenutzbar fuer das Routing markiert
538 // werden.
539 if (member(cmds, conn[CONN_CMD])) {
540 check_and_mark_duplicate_conns_by_conn(conns,conn);
541 }
542 }
543
544 pathmap[pre][path[0]] = conns;
545
546 // Ob 0 oder 1 ist eigentlich total egal, da das Ergebnis-Array sowieso
547 // verworfen wird.
548 return 0;
549}
550
551private void add_to_cache(string from, string to, int para, int costs,
552 string *rooms, string *cmds) {
553 struct path_s p = (<path_s> costs : costs, rooms: rooms, cmds : cmds,
554 para: para, flags: 0, ttl: time()+86400);
555 if (!member(pathcache, from)) {
556 pathcache[from] = m_allocate(1);
557 pathcache[from][to] = m_allocate(1);
558 }
559 else if (!member(pathcache[from], to)) {
560 pathcache[from][to] = m_allocate(1);
561 }
562 pathcache[from][to][para] = p;
563}
564
565// Diese Funktion berechnet die Kosten einer Verbindung.
566// Ein Seherstatus schliesst die Moeglichkeiten von Spielern ein (seher
567// kann Spielerpfade problemlos nutzen).
568// Wenn eine Verbindung in eine andere Parawelt fuehrt, als in <para>
569// angefragt, wird sie erheblich teurer.
570protected int _calc_cost(mixed* path, int seer, int para)
571{
572 mixed* interest=path[CONN_USERS];
573
574 // Basiskosten nach Ausgangsart
575 int costs = COST_EXITS[path[CONN_EXITTYPE]];
576
577 // Verbindungen in andere als die gewuenschte Parawelt werden bei der
578 // suche nicht beruecksichtigt, aber Verbindung von Para nach Normal und
579 // umgekehrt sind erlaubt. Para->Normal soll aber etwas teurer sein, damit
580 // es bevorzugt wird, in der angefragten Welt zu bleiben.
581 // (Hintergrund: wenn man in Para ist, laeuft man meistens trotzdem durch
582 // Normalweltraeume, weil es keine passenden Pararaeume gibt).
583 if (para != path[CONN_PARA])
584 costs += COST_WORLDCHANGE;
585
586 // wenn schon genug unterschiedliche Leute die Verbindung gelaufen sind,
587 // kostet es die Basiskosten. Fuer Seher auch die Spieler einschliessen.
588 if (interest[CONN_U_PLAYERS]==-1
589 || (seer && interest[CONN_U_SEERS]==-1))
590 return costs;
591 else
592 {
593 // Sonst wird die Verbindung teurer.
594 // Anzahl Spielernutzer kann nicht -1 sein (s.o.).
595 int usercount = sizeof(interest[CONN_U_PLAYERS]);
596 // wenn <seer>, wird ggf. die Anzahl an Sehernutzern drauf addiert.
597 // Wert fuer Seher kann nicht -1 sein (s.o.)
598 if (seer)
599 usercount += sizeof(interest[CONN_U_SEERS]);
600 switch (usercount)
601 {
602 case 0:
603 costs=1000000;
604 break;
605 case 1..2:
606 costs*=COST_ONE;
607 case 3..4:
608 costs*=COST_FEW;
609 default:
610 costs*=COST_MANY;
611 }
612 return costs;
613 }
614 DBG(sprintf("Huch, keine Ahnung, Kosten unbestimmbar: %O",path));
615 return 1000;
616}
617
618// Neuimplementation von Humni, benutzt einfach simpel einen
619// Dijkstra-Algorithmus. "Simpel" schreibe ich, bevor ich die
620// Funktion schreibe, fluchen werde ich gleich.
621static void _search(string fname, string from)
622{
623 // <from> ist jetzt anzuguckende/zu bearbeitende Raum.
624
625 // Die aktuelle Liste an abgesuchten Raeumen, Raeume, in denen
626 // alle Wege bereits eingetragen sind.
627 string* rooms_searched=searchlist[fname,SL_VISITED];
628
629 // Zielort
630 string to = searchlist[fname,SL_DESTINATION];
631
632 // moegliche Ziele
633 mapping targets=searchlist[fname,SL_CANDIDATES];
634
635 // wizlevel
636 int seer = searchlist[fname,SL_WIZLEVEL];
637
638 // para
639 int para=searchlist[fname,SL_PARA];
640
641 // Noch zu bearbeitende Raeume
642 string* to_do=searchlist[fname,SL_TODO];
643
644 DBG("_search() start.");
645
646 while ((get_eval_cost()>900000) && from && (from != to))
647 {
648 // Fuege den aktuellen Raum (from) als Weg hinzu
649 DBG(sprintf("Fuege hinzu: %s",from));
650 rooms_searched+=({from});
651 // Aus den Raeumen drumrum werden die Ausgaenge gesucht
652 // und zur Wegliste hinzugefuegt.
653
654 // Pfade von <from> weg aus der Liste holen
655 mixed* paths=pathmap[_get_prefix(from)][from];
656
657 // Liste der Verbindungen von <from> durchgehen
658 foreach (mixed conn:paths)
659 {
660 int newcost;
661 // wenn der Raum schonmal gesehen wurde, ist hier nix mehr noetig.
662 if (member(rooms_searched,conn[CONN_DEST])>-1)
663 {
664 DBG(sprintf("Raum %s hab ich schon!",conn[CONN_DEST]));
665 }
666 else
667 {
668 // Verbindung je nach Flag nicht nutzen. Ausserdem:
669 // wenn die Verbindung in eine Parawelt fuehrt, aber kein
670 // Seherstatus gegeben ist, existiert die Verbindung nicht.
671 // Weiterhin kommt eine Verbindung nicht in Frage, wenn sie in
672 // eine andere Parawelt fuehrt, weil der Weltuebergang nur an
673 // bestimmten Orten moeglich ist. Ausnahme davon sind Wechsel
674 // zwischen Normalwelt und Parawelt.
675 if (
676 (conn[CONN_FLAGS] & CFLAG_DONTUSE)
677 || (conn[CONN_FLAGS] & CFLAG_DUPLICATE)
678 || (!seer && conn[CONN_PARA])
679 || (conn[CONN_PARA] && conn[CONN_PARA] != para)
680 )
681 continue;
682 newcost = targets[from,SLT_COSTS]; // kosten bis hierher
683 // + Kosten in naechsten Raum.
684 newcost += _calc_cost(conn,seer,para);
685 // es koennte sein, dass es Verbindungen mit gleichem
686 // Start/Ziel gibt, aber unterschiedlichen Kosten. In diesem
687 // Fall wuerde das Ziel der aktuellen Verbindung mehrfach
688 // hinzugefuegt und das letzte gewinnt. Daher sollte diese
689 // Verbindung nur hinzugefuegt werden, wenn noch keine
690 // Verbindung in den Zielraum existiert, die billiger ist.
691 if (member(targets,conn[CONN_DEST])
692 && newcost >= targets[conn[CONN_DEST],SLT_COSTS])
693 continue;
694 // Weg bis hierher plus naechsten Raum
695 string* new_way = targets[from,SLT_WAY];
696 new_way += ({conn[CONN_DEST]});
697 // Kommandos bis hierher plus naechstes Kommando
698 string* new_commands = targets[from,SLT_COMMANDS];
699 new_commands += ({conn[CONN_CMD]});
700 // naechsten Raum in Todo fuer die Pruefung unten vermerken
701 to_do += ({conn[CONN_DEST]});
702 // Und Kosten/Weg/Kommandos bis zum naechsten Raum unter
703 // targets/Kandidaten ablegen.
704 targets += ([conn[CONN_DEST]:newcost;new_way;new_commands]);
705 }
706 }
707 // Nachdem die Raeume alle zu den Kandidaten an moeglichen Wegen
708 // hinzugefuegt wurden, wird nun der neueste kuerzeste Weg gesucht.
709 // Natuerlich nur aus denen, die schon da sind.
710 if (sizeof(to_do)>0)
711 {
712 // Kosten des ersten todo als Startwert nehmen
713 string minraum;
714 int mincosts=__INT_MAX__;
715 // und ueber alle todos laufen um das Minimum zu finden.
716 foreach(string raum: to_do)
717 {
718 if (mincosts>targets[raum,SLT_COSTS])
719 {
720 minraum = raum;
721 mincosts=targets[raum,SLT_COSTS];
722 }
723 }
724 DBG(sprintf("Neuer kuerzester Raum: %s",minraum));
725
726 // der billigst zu erreichende Raum wird das neue <from> fuer den
727 // naechsten Durchlauf
728 from=minraum;
729 // und natuerlich aus dem to_do werfen.
730 to_do-=({minraum});
731 DBG(sprintf("Anzahl untersuchter Raeume: %d, Todo: %d, "
732 "Kandidaten: %d",
733 sizeof(rooms_searched),sizeof(to_do),sizeof(targets)));
734 }
735 else
736 {
737 from=0;
738 }
739 } // while ende
740
741 if (!from)
742 {
743 // Hmpf...
744 TELL_USER("Kein Weg gefunden!");
745 if (searchlist[fname, SL_CALLBACK])
746 funcall(searchlist[fname,SL_CALLBACK],
747 searchlist[fname,SL_START], to, para,
748 0,0,0);
749 m_delete( searchlist, fname ); // suchauftrag entsorgen
750 return;
751 }
752 else if (from==to)
753 {
754 // JUCHU!
755 TELL_USER(sprintf("Weg gefunden! %O,%O,%O",
756 targets[to,SLT_COSTS],targets[to,SLT_WAY],
757 targets[to,SLT_COMMANDS]));
758 add_to_cache(searchlist[fname,SL_START], to, para,
759 targets[to,SLT_COSTS],targets[to,SLT_WAY],
760 targets[to,SLT_COMMANDS]);
761 if (searchlist[fname, SL_CALLBACK])
762 funcall(searchlist[fname,SL_CALLBACK],
763 searchlist[fname,SL_START], to, para,
764 targets[to,SLT_COSTS],targets[to,SLT_WAY],
765 targets[to,SLT_COMMANDS]);
766 m_delete( searchlist, fname ); // suchauftrag entsorgen
767 return;
768 }
769
770 // Wenn das alles nicht war, waren es die Eval-Ticks. Mist. Spaeter
771 // weitersuchen...
772 searchlist[fname,SL_VISITED]=rooms_searched;
773 searchlist[fname,SL_CANDIDATES]=targets;
774 searchlist[fname,SL_TODO]=to_do;
775 call_out("_search",2,fname,from);
776}
777
778
779// Die Daten ueber Raeume werden quasi gehasht abgespeichert, damit wir nicht
780// so schnell an die Begrenzung bei Arrays und Mappings stossen.
781// Dabei ist der 'Hash' der Anfang des Pfades.
782private string _get_prefix( string path )
783{
784 string *tmp;
785
786 tmp = explode( path, "/" );
787
788 // Bei Raeumen unterhalb von /d/* wird /d/region/magiername benutzt
789 if ( strstr(path, "/d/") == 0)
790 return implode( tmp[0..3], "/" );
791 // Ansonsten die ersten beiden Teilpfade, falls soviele vorhanden sind
792 else if ( sizeof(tmp) < 4 )
793 return implode( tmp[0..1], "/" );
794 else
795 return implode( tmp[0..2], "/" );
796}
797
798// Reset und Datenhaltung
799// reset wird alle 3h gerufen, um das Savefile immer mal wieder zu speichern.
800// Datenaufraeumen aber nur einmal pro Tag.
801public void reset()
802{
803 if ( time_to_clean_up <= time() )
804 {
805 // Einmal pro Tag Reset zum Aufraeumen der Datenbank
806 rm(DUMPFILE".raeume");
807 rm(DUMPFILE".conns");
808 time_to_clean_up = time() + 86400;
809 expire_path_cache(m_indices(pathcache));
810 call_out(#'cleanup_data, 30,
811 sort_array(m_indices(pathmap), #'</*'*/), 0 );
812
813 }
814 save_object(SAVEFILE);
815 set_next_reset(10800);
816}
817
818protected void expire_path_cache(string *startrooms) {
819 foreach(string start : startrooms) {
820 mapping targets = pathcache[start];
821 foreach (string target, mapping paths: targets) {
822 foreach(int para, struct path_s p: paths) {
823 if (p->ttl < time()
824 || !(p->flags & PFLAG_PERMANENT) )
825 m_delete(paths,para);
826 }
827 if (!sizeof(paths))
828 m_delete(targets, target);
829 }
830 startrooms-=({start});
831 if (!sizeof(targets))
832 m_delete(pathcache, start);
833 // recht grosser Wert, weil immer komplette Startraeume in einem
834 // erledigt werden.
835 if (get_eval_cost() < 1000000)
836 break;
837 }
838 if (sizeof(startrooms))
839 call_out(#'expire_path_cache, 4, startrooms);
840}
841
842// Datenbank aufraeumen
843protected void cleanup_data( string *names, int idx )
844{
845 int size, i, j, k;
846 string *rooms;
847 mixed *paths;
848
849 size = sizeof(names);
850
851 // Ein bisserl mitloggen, damit wir Schwachstellen im System auch finden.
852 if ( !idx ){
853 LOG( sprintf("=== %s: Starte cleanup_data(): %O Gebiete, %O Raeume "
854 + "...\n", strftime("%y%m%d-%H%M%S"), size,
855 show_statistic(1, 1) ) );
856 }
857 else {
858 LOG( sprintf("%s: Setze cleanup_data() fort.\n",
859 strftime("%y%m%d-%H%M%S") ) );
860 }
861
862 // Brav gesplittet, damit es kein Lag gibt.
863 // Die Grenze ist recht hoch angesetzt, da immer gleich komplette
864 // Teilbaeume aufgeraeumt werden.
865 while ( get_eval_cost() > 1100000 && idx < size ){
866 rooms = sort_array( m_indices(pathmap[names[idx]]), #'</*'*/ );
867
868 for ( i = sizeof(rooms); i--; ){
869 paths = pathmap[names[idx]][rooms[i]];
870 int conn_count = sizeof(paths);
871 mapping cmds=m_allocate(sizeof(paths));
872
873 for ( j = conn_count; j--; ) {
874 mixed conn = paths[j];
875 for ( k = 0; k < 2; k++ ) { // Spieler/Sehereintraege
876 // Diese Verbindung hat noch keiner genutzt bisher
877 if ( !conn[CONN_TIMES][k] )
878 continue;
879 // Wenn Verbindung permanent, ueberspringen
880 if (conn[CONN_FLAGS] & CFLAG_PERMANENT)
881 continue;
882
883 if ( conn[CONN_USERS][k] == -1 // 'bekanntes' Gebiet
884 && time() - conn[CONN_TIMES][k] > TIMEOUT_OLD ){
885 // LOG( sprintf("*** Loesche alte "
886 // + (k ? "Seher" : "Spieler")
887 // + "-Verbindung %O.\n", paths[j]) );
888 conn[CONN_USERS][k] = ({});
889 conn[CONN_TIMES][k] = 0;
890 }
891 else if ( conn[CONN_USERS][k] != -1 // 'neues' Gebiet
892 && time() - conn[CONN_TIMES][k] > TIMEOUT_NEW ){
893 conn[CONN_USERS][k] = ({});
894 conn[CONN_TIMES][k] = 0;
895 }
896 }
897
898 // Wenn eine Verbindung weder von Spielern noch von Sehern
899 // benutzt wurde in letzter Zeit und sie keine permanented
900 // ist, Verbindung ganz loeschen.
901 if (!(conn[CONN_FLAGS] & CFLAG_PERMANENT)
902 && !conn[CONN_TIMES][CONN_T_PLAYERS]
903 && !conn[CONN_TIMES][CONN_T_SEERS] ) {
904 paths[j..j] = ({}); // conn rauswerfen
905 conn_count--;
906 }
907 else {
908 // Connections nach Kommandos speichern.
909 if (member(cmds, conn[CONN_CMD]))
910 cmds[conn[CONN_CMD]] += ({conn});
911 else
912 cmds[conn[CONN_CMD]] = ({conn});
913 // und das duplicate flag loeschen, das wird spaeter neu
914 // gesetzt, wenn noetig.
915 // (There is no chance that a concurrent search will check
916 // these connections until they are marked again.)
917 conn[CONN_FLAGS] &= ~CFLAG_DUPLICATE;
918 // Connections dumpen
919 if (!(conn[CONN_FLAGS] & CFLAG_DUPLICATE))
920 {
921 mixed u=({conn[CONN_USERS][CONN_U_PLAYERS],
922 conn[CONN_USERS][CONN_U_SEERS] });
923 write_file(DUMPFILE".conns",sprintf(
924 "%s|%s|%s|%d|%d|%d|%d\n",
925 rooms[i],conn[CONN_DEST],conn[CONN_CMD],
926 conn[CONN_EXITTYPE],conn[CONN_PARA],
927 (u[0]==-1 ? 0 : NEEDED-sizeof(u[0])),
928 (u[0]==-1 ? 0 : NEEDED-sizeof(u[0]))
929 ));
930 }
931 }
932 }
933
934 // Ein Raum ohne Verbindungen frisst nur Platz in der Datenbank
935 if ( !conn_count ){
936 // LOG( sprintf("*** Loesche kompletten Raum %O\n", rooms[i]) );
937 m_delete( pathmap[names[idx]], rooms[i] );
938 }
939 else {
940 // wenn Kommandos nicht eindeutig sind, dann werden die
941 // entsprechenden Verbindungen gekennzeichnet. Alle in Frage
942 // kommenden Verbindungen sind jeweils schon zusammensortiert.
943 foreach(string cmd, mixed conns : cmds) {
944 if (sizeof(conns)>1)
945 check_and_mark_duplicate_conns(conns);
946 }
947 // ggf. geaendertes Verbindungsarray wieder ins Mapping
948 // schreiben.
949 pathmap[names[idx]][rooms[i]] = paths;
950 // Raum/Node ins Dump schreiben
951 write_file(DUMPFILE".raeume",sprintf(
952 "%s\n",rooms[i]));
953 }
954 }
955 idx++;
956 }
957 if ( idx >= size ) {
958 LOG( sprintf("=== %s: Beende cleanup_data()! Uebrig: %O Raeume.\n",
959 strftime("%y%m%d-%H%M%S"), show_statistic(1, 1) ) );
960 }
961 else {
962 call_out( #'cleanup_data, 2, names, idx );
963 LOG( sprintf("%s: WARTE 20s bei Evalcost %O\n",
964 strftime("%y%m%d-%H%M%S"), get_eval_cost()) );
965 }
966}
967
968// Beim Entladen speichern
969public varargs int remove( int silent )
970{
971 // Vor dem Entfernen noch schnell die Daten sichern
972 save_object(SAVEFILE);
973 destruct(this_object());
974
975 return 1;
976}
977
978
979// Zum Debuggen. Nur für Tiamak. Bzw. nun fuer Zook, Vanion, Rumata
980#define ALLOWED ({"zook","vanion","rumata","zesstra","humni"})
981#define MATCH(x,y) (sizeof(regexp(x,y)))
982public mapping get_pathmap()
983{
984 if ( !this_interactive() || !MATCH(ALLOWED,getuid(this_interactive()))
985 || !previous_object() || !MATCH(ALLOWED,getuid(previous_object())))
986 return ([]);
987
988 return pathmap;
989}
990public mapping get_pathcache()
991{
992 if ( !this_interactive() || !MATCH(ALLOWED,getuid(this_interactive()))
993 || !previous_object() || !MATCH(ALLOWED,getuid(previous_object())))
994 return ([]);
995
996 return pathcache;
997}
998
999#undef ALLOWED
1000#undef MATCH