A test map for the script above:
all_rooms = []
for i in range(68):
all_rooms.append((str(i), i))
all_links =((0,1),(1,0), (1,2), (2,1), (1,3), (3,1),
(2,3), (3,2), (2,7), (7,2), (2,8), (8,2), (3,7), (7,3),
(3,4), (4,3), (3,5), (5,3),(5,4), (4,5),(4,6), (6,4),
(6,9), (9,6), (6,7), (7,6), (7,8), (8,7), (8,9), (9,8),
(9,10), (10,9), (6,11), (11,6), (11,12), (12,11), (12,13), (13,12),
(12,6), (6,12), (12,4), (4,12),(13,14), (14,13), (13,5), (5,13),
(13,19), (19,13),(14,15), (15,14),(14,16), (16,14),(14,17), (17,14),
(14,5), (5,14),(15,5), (5,15),(15,16), (16,15),(16,17), (17,16),
(17,18), (18,17),(18,19), (19,18),(18,22), (22,18),(22,20), (20,22),
(22,53), (53,22),(22,21), (21,22),(21,23), (23,21),(23,24), (24,23),
(24,25), (25,24),(25,26), (26,25),(26,48), (48,26),(48,49), (49,48),
(49,50), (50,49),(50,51), (51,50),(51,52), (52,51),(53,27), (27,53),
(27,28), (28,28),(28,29), (29,28),(28,31), (31,28),(28,30), (30,28),
(31,30), (30,31),(30,29), (29,30),(30,32), (32,30),(30,34), (34,30),
(29,33), (33,29),(31,33), (33,31),(30,33), (33,30),(34,33), (33,34),
(31,32), (32,31),(29,34), (34,29),(34,35), (35,34),(32,35), (35,32),
(33,35), (35,33),(35,38), (38,35),(35,37), (37,35),(35,36), (36,35),
(36,37), (37,36),(37,38), (38,37),(37,40), (40,37),(38,41), (41,38),
(36,39), (39,36),(39,40), (40,39),(40,41), (41,40),(40,43), (43,40),
(39,44), (44,39),(41,42), (42,41),(42,43), (43,42),(43,44), (44,43),
(44,45), (45,44),(45,46), (46,45),(46,47), (47,46),(43,46), (46,43),
(47,42), (42,47),(46,54), (54,46),(54,55), (55,54),(54,56), (56,54),
(55,56), (56,55),(56,57), (57,56),(57,58), (58,57),(58,59), (59,58),
(57,60), (60,57),(59,60), (60,59),(60,56), (56,60),(56,61), (61,56),
(61,62), (62,61),(62,63), (63,62),(63,64), (64,63),(64,65), (65,64),
(64,67), (67,64),(66,67), (67,66)
)
map = Map()
map.loadMap(all_rooms, all_links)
from time import clock
print "========"
start = clock()
path = map.getShortestPath(0,66)
timing = clock() - start
print timing
print path
print "========"
Additionally using Psyco gives about a 40% improvement in speed. I find that psyco.proxy()'ing just the Map.getShortestPath() method (as opposed to psyco.full() on the whole script) yields the best result with Psyco. |