#include "copyright.h" #include <stdio.h> #include "db.h" #include "config.h" /* Compute shortest path to each room */ /* Locks cost extra */ #define INFINITY 2148575 /* MAXINT or thereabouts */ #define LOCK_COST 10000 /* extra cost for a lock */ /* This code blasts a lot of fields in the database, so */ /* you don't ever want to write it back out afterwards. */ /* Where things get stored: */ /* cost to get here gets put in pennies */ /* location is the previous room that gets you here */ /* next is the next room in the search queue */ /* key non-zero means already queued */ /* contents is previous exit that gets you here */ /* this should be a priority queue, but we're cheap */ dbref search_queue_head = NOTHING; dbref search_queue_tail = NOTHING; void queue_room(dbref room) { if(db[room].key) return; if(search_queue_tail == NOTHING) { search_queue_head = room; } else { db[search_queue_tail].next = room; } search_queue_tail = room; db[room].next = NOTHING; db[room].key = 1; } dbref dequeue_room() { dbref room; if((room = search_queue_head) == NOTHING) return NOTHING; if((search_queue_head = db[room].next) == NOTHING) { search_queue_tail = NOTHING; } db[room].next = NOTHING; db[room].key = 0; return room; } void find_paths() { dbref room; dbref exit; dbref mycost; /* dbref[room].pennies */ dbref cost; /* mycost + cost to use exit */ dbref dest; /* exit destination */ while((room = dequeue_room()) != NOTHING) { /* get first one */ /* check its exits */ mycost = db[room].pennies; DOLIST(exit, db[room].exits) { if((dest = db[exit].location) < 0) continue; cost = mycost + 1; if(db[exit].key != NOTHING) { if(!(db[exit].flags & ANTILOCK) && Typeof(db[exit].key) != TYPE_THING) { continue; /* we can't get it */ } else { cost += LOCK_COST; } } if(cost < db[dest].pennies) { /* it's cheaper, set and queue it */ db[dest].pennies = cost; db[dest].location = room; db[dest].contents = exit; queue_room(dest); } } } } void compute_paths(dbref start) { dbref room; /* clear out all fields we use */ for(room = 0; room < db_top; room++) { if(Typeof(room) == TYPE_ROOM) { db[room].location = db[room].next = db[room].contents = NOTHING; db[room].pennies = INFINITY; db[room].key = 0; } } /* set up start */ db[start].pennies = 0; queue_room(start); find_paths(); } void print_path(dbref room) { dbref prev; dbref exit; dbref key; if((prev = db[room].location) != NOTHING) { print_path(prev); exit = db[room].contents; if((key = db[exit].key) != NOTHING) { printf("LOCKED[%s(%d)] ", db[key].name, key); } printf("%s => %s\n", db[exit].name, db[room].name); } } void print_paths() { dbref room; for(room = 0; room < db_top; room++) { if(Typeof(room) == TYPE_ROOM) { printf("%s(%d)[%s]: ", db[room].name, room, db[db[room].owner].name); if(db[room].pennies == INFINITY) { puts("UNREACHABLE"); } else { printf("%d + %d locks\n", db[room].pennies % LOCK_COST, db[room].pennies / LOCK_COST); } print_path(room); putchar('\n'); } } } void main(int argc, char **argv) { dbref start = 0; if(argc >= 2) { start = atol(argv[2]); } else { start = PLAYER_START; } if(db_read(stdin) < 0) { fprintf(stderr, "%s: bad input\n", argv[0]); exit(5); } compute_paths(start); print_paths(); exit(0); }