''' path.py Plugs into the routine module to allow for the easy construction of paths and path following. ''' from mud import * from mudsys import add_cmd import mud, mudsys ################################################################################ # functions ################################################################################ def leads_to(frm, to): '''returns whether from leads directly to to''' for ex in frm.exnames: if frm.exit(ex).dest is to: return True return False def shortest_path_bfs(frm, to, ignore_doors = False, ignore = None): '''calculates the shortest path, but uses a breadth first search. More efficient than depth-first seach for very short paths with lots of branches or very large muds.''' if frm == to: return [frm] rooms = [] depth = [] if ignore == None: ignore = set() ignore.add(frm) # what is our highest depth i = 1 # the index of the room our last depth started at j = 0 # append ourself and our depth rooms.append(frm) depth.append(i) # keep going until we find To, or we can't go any deeper found = False while not found: prev_depth = rooms[j:] for rm in prev_depth: for ex in rm.exnames: dest = rm.exit(ex).dest if dest in ignore: continue rooms.append(dest) depth.append(i) if dest is to: found = True break ignore.add(rm) if found: break i += 1 j += len(prev_depth) # go backwards from our destination rooms.reverse() depth.reverse() # first step, pull out our destination room path = [to] # pull out all other rooms on the shortest path while len(rooms) > 0: curr_depth = depth[0] # figure out which room in our current layer # links to our previous room in the shortest path for next in rooms: if leads_to(next, path[len(path)-1]): path.append(next) break # clear our last layer i = 0 while i < len(depth) and depth[i] == curr_depth: i += 1 rooms = rooms[i:] depth = depth[i:] # put it back in order path.reverse() return path def shortest_path_dfs(frm, to, ignore_doors = False, ignore = None): '''returns the steps needed to take to go from one room to another. More efficient than breadth-first search for very long paths with only a few branches, or very small muds.''' path = [] if ignore == None: ignore = set() # a list of rooms we ignore for tracking. Add ourself so we don't loop back ignore.add(frm) # if we're the target room, return an empty list if frm is to: return [frm] # build the shortest path for ex in frm.exnames: # check if it has a door, and if we ignore it if frm.exit(ex).is_closed: continue # get the dest room. if there is none, skip this exit next_room = frm.exit(ex).dest if next_room is None: continue # if we already know this is a dead end or a loopback, skip it if next_room in ignore: continue next_path = shortest_path(next_room, to, ignore_doors, ignore) # dead end if len(next_path) == 0: continue # we found a path, append ourself next_path.insert(0, frm) # are we shorter than the previous one? if len(path) == 0 or len(path) > len(next_path): path = next_path return path # set whether we are using bfs or dfs as our main pathing method shortest_path = shortest_path_bfs def path_to_dirs(path): '''takes a path of rooms and converts it to directions''' dirs = [] i = 0 while i < len(path) - 1: for ex in path[i].exnames: if path[i].exit(ex).dest == path[i+1]: dirs.append(ex) break i = i + 1 # return the directions we generated, if any return dirs def build_patrol(rms, reverse = True): '''builds a set of directions that need to be followed to do a patrol between the rooms. If reverse is true, also supplies the directions to loop back on itself''' if reverse == True: loopback = [x for x in rms] loopback.reverse() rms = rms + loopback[1:] path = [] i = 0 while i < len(rms) - 1: path = path + shortest_path(rms[i], rms[i+1]) i += 1 return path_to_dirs(path) def step(frm, to, ignore_doors = False): '''returns the first step needed to take to go from one room to another''' steps = shortest_path(frm, to, ignore_doors) if steps == None or len(steps) <= 1: return None return path_to_dirs(steps)[0] ################################################################################ # commands ################################################################################ def cmd_path(ch, cmd, arg): '''Usage: path <person> Prints out a Python list of the directions needed to move from your current location to the location of the specified person.''' try: tgt, = parse_args(ch, True, cmd, arg, "ch.world.noself") except: return path = build_patrol([ch.room, tgt.room]) if len(path) == 0: ch.send("Path doesn't exist") else: ch.send(str(path)) ################################################################################ # initialization ################################################################################ # add our commands add_cmd("path", None, cmd_path, "admin", False) # mud initialization mud.build_patrol = build_patrol