Organizing node graph for simulator

As several of my friends here know, I'm working on simulating complicated level geometry as efficiently as possible, so I can keep track of where NPCs move and what they do when the player isn't around. I almost have it finished, but since this is going to be so huge I want to make sure that I'm not setting myself up for a memory management/efficiency nightmare.

As a quick preamble, my simulator needs to do three big things:
1) Remember where every NPC is
2) Remember what each NPC is doing
3) Simulate NPC movement from chunk-chunk

I'm modelling the entire world with two classes: Rooms, and Doors. Room corresponds to a chunk that gets rendered in-game (outdoors areas and terrain slices are also tracked in Rooms), and a Door connects two Rooms together.

To simulate movement in a sufficiently realistic manner that will also let me run pathfinding in chunks that the player is in, it seems like the easiest method is creating a very basic node graph consisting of every Room and Door in the map, and whenever an NPC wants to move from one room to another, using A*/any other efficient pathfinding algorithmn to compute a least-distance route of connecting nodes. Before I realized that I needed Doors, this was my basic model:

Code (csharp):

1. class GraphNode{
2. public Location location;
3. public List<GraphNode> neighbors;
4. };
5.  
6. class Location{}
7.  
8. class Room:Location{}
9.  
10. class Door:Location{}
11.  
12. class Graph{
13.  
14. public Dictionary<Location, GraphNode> nodes;
15.  
16. public List<Location> GetPath(Location from, Room to){ //Setting the destination to a room ensures an NPC will never get to a doorway and freeze in it
17. GraphNode start = nodes[from];
18. List<Location> desiredPath = new List<Location>();
19.  
20. // A*/Dijkstra's/whatever
21.  
22. return desiredPath; //return list of rooms that connect A and B, sorted in the order the NPC will traverse them
23. }
24. };

This looks okay, but I have two big concerns:

1) Is this an alright way to manage a large dataset? The final game will likely have 500-1,000 rooms and many more doors, and I don't want to saddle myself with a behemoth simulator that bottlenecks constantly and hogs memory

2) Is there an easy way I could eliminate doors altogether? At the very least they double the number of nodes in my graph, but they provide a very important utility: right now pathfinding works completely differently for NPCs in the simulation and NPCs in rendered sections, and getting an NPC to leave a chunk is a big challenge. If doors and rooms are contained in the same grid, all I would need to do to make an NPC walk from one corner of the map to another while the player watches is route them to desiredPath[n].gameObject.transform instead of teleporting them directly to desiredPath[n].

 

Looks fine to me. You should keep Doors and Rooms (i.e., edges and nodes). They provide a standard abstraction for your hierarchical pathfinding algorithms. With only 500-1,000 nodes, you probably don't need to bother with spatial partitioning structures like octrees. If necessary, you could add another level to the hierarchy -- for example, Zones, that contain a subgraph of Doors and Rooms.

 

Awesome, thanks or taking a look!