I read an interesting article about pathfinding in Japanese. Let me show you their ideas. They also published about it in English, Precomputed Pathfinding for Large and Detailed Worlds on MMO Servers (Fabien Gravot, Takanori Yokoyama, Youichiro Miyake), so you can read the details from that book. They are developers of FINAL FANTASY XIV, a famous Japanese multiplayer online RPG. There are about 1,000 NPCs in a single map so they couldn't use real time pathfinding. Instead they use tables to store precomputed pathfindings. To reduce memory footprint for tables, they devide the map into grids and make hierarchal tables. The result is drastic. If a map has 20,000 locations for destination, the single table costs 1.1GB. Then dividing to 100 locations for each grid, the cost reduce to 11MB. I hope this could help.