Operating on partialy loaded data. Mapping

[DarkLightning7]

I am working on a mapping system to support pathfinding over areas that are too large to hold in memory. The problem i have run into is how to load only a small part of the map when its all linked together and then dynamicaly load more of the map when it is needed and dump unnecessary pieces to disk.
I was thinking I could use seralization to save the objects to disk only problem i have is they are all linked together multiple times and im not sure how to keep track of which links need to be updated when chunks are loaded/unloaded.

Here is the class that makes up the structure of the map:

public class Chunk {
    private ArrayList<Terminal> connections;
    private Vector3f location;
    private static int width;
    private static int height;

    public Chunk() {
        connections = new ArrayList<Terminal>();
    }
    //Class continues . . . getter setter and manipulation methods
}

Connections between chunks are defined by the Terminal class:

public class Terminal {

    //connection data
    private ConcurrentHashMap<Terminal, ArrayList<Flag>> linkFlags;
    private ArrayList<Flag> localFlags;
    private ArrayList<Terminal> links;  //The Terminals this Terminal is connected to within the same chunk.
    private ConcurrentHashMap<Terminal, Integer> distance;
    //Terminal data
    private Chunk parent;
    private Link connection;  //the connection to a neighboring chunk terminals only exist at the connections between chunks.
    private Vector3f position;  //position relative to parent chunk may be unnecessary will be used for render though

    public Terminal() {
        links = new ArrayList<Terminal>();
        distance = new ConcurrentHashMap<Terminal, Integer>();
        linkFlags = new ConcurrentHashMap<Terminal, ArrayList<Flag>>();
        parent = null;
        connection = null;
    }
    //Class continues . . . getter setter and manipulation methods
}

I am using the Link class as a way to seperate chunks so they are easier to load and store but am having trouble figuring out how to distinguish chunks so I can load the right ones into memory and link the correct terminals togetherd.

Any ideas on how to "individualize" chunks would be great along with how to deal with "hanging link pointers" in terminals caused by neighboring chunks not being loaded would be great.

Thanks

[JamesCherrill]

Just a quick answer beause I'm going to bed now.... but situations like this are often solved by having an abstract Chunk superclass, with all the getters/setters defined, and two concrete subclasses InMemoryChunk and OnDiskChunk. The in memory version just works as expected, but the on disk version's methods trigger a read from disk and creation of an in memory version.
The application code refers to Chunks via a ChunkProxy wrapper class that allows on disk Chunks to be replaced by in memory Chunks without the application knowing. This means that all your links/Terminals etc refer to ChunkProxies and never get involved with in memory/on disk issues at all.

ps (next norning) In any given case you may chose to merge two or more of those classes into one for a simpler solution - it depends on data volumes, complexity of interface, cost to read/write disk versions etc.

[DarkLightning7]

Thanks for the reply james. Sorry it took so long for me to get back to this(was gone on a trip).

Im not exactly sure how to use a proxy to wrap the chunks when the Terminals are the connectors and the chunks know nothing about their neighbors. Should I use an id system for the terminals? So the connected terminal asks the chunk proxy for its paired terminal if the chunk has been loaded into mem the proxy passes the request to the chunk and the chunk returns the terminal's pair.

Also how would I go about creating a unique id for each chunk so its easy to load the correct one from a database?

[JamesCherrill]

I'm also just back from a trip, so good timing!

Unique object IDs for database use is a standard problem with many standard solutions - just Google.

Probably the easiest way to explain the proxy idea is with some (pseudo) code - but remember this hasn't been in any way optimised for your (unpublished) complete requirement...

    abstract class Chunk { 
       int ID;
       ...
       abstract public void doStuff();
       ...
    }

    class RealChunk extends Chunk {
       // this is a real chunk that is fully populated with data
       ArrayList<Chunk> chunksThisLinksTo = ... // could be real or just proxies
       ...
       public RealChunk(int ID) {
          // load chunk data from database
          // populate chunksThisLinksTo with new ChunkProxies
       )
       public void doStuff() { ...
       ...
    }

    class ChunkProxy extends Chunk {
       private RealChunk realChunk = null; // the chunk this is a proxy for

       public ChunkProxy(int ID) {
          this.ID = ID:
       }

       public void doStuff() { 
          if (realChunk == null) loadRealChunk();
          realChunk.doStuff();   // proxy the calls
       }
       ...

       void loadRealChunk() {
          // may need to free memory by unloading a real chunk...
          // ... just set its proxy realChuck variable to null and let GC do the rest
          // (implies you maintain a list of proxies whose realChunks are in memory)
          realChunk =  new RealChunk(ID);
          (list of proxies whose realChunks are in memory).add(this);
      }
   }

So now when you are loading Chunks from the database you create create ChunkProxies for all the chunksThisLinksTo values. They just sit there until the program tries to call one of the methods on that Chunk, in which case the proxy loads the real chuck and passes all the calls through.

What's so great about this approach is that the rest of your code never knows anything about which Chunks are in memory and which aren't, or if/when chunks are being swapped in or out. Your program just has references to Chunks and uses them.

[DarkLightning7]

Thanks for the sample code I was having trouble figuring out how to use java.lang.reflect.proxy because I could not find any real good examples. Depending on how many total chunks there are the proxy method could use up a lot of memory for all the "empty" proxies?

I came up with another way to handle chunks that are not in memory. Using a chunk manager in a seperate thread I can keep track of which chunks are being accessed through a linking class which will report to the chunk manager when the algorithm changes chunks and using a simple prediction algorithm load necessary chunks into memory usually before they are needed. Should the chunk be accessed before the manager has time to load it a request from the link class will be sent to the manager for the chunk which will hang the path algorithm till the chunk is loaded. The linking object will only exist if it is connected to a chunk. So no "extra" objects in memory.

Im not sure yet if the linking object will exist between every terminal or just between every pair of neighboring chunks. I can also use a chunk manager with the proxy method to load the chunks into memory before they are needed.

Now I just need to figure out which implementation is more flexible, uses the least memory and is fastest(there could be several hundred ai accessing the system every second).

Any additional thoughts on either implementation are apreciated.

Thanks for all the help james.

[JamesCherrill]

The proxy class has just a ref to the real chunk (in addition to the inherited vars - which I just edited because the linked chunks var isn't needed execpt in a real chunk), so thats one ref and one ID (int?), so it's about as small as a class instance can be. You should be OK for many millions of those at least.

The mechanism you are describing seems pretty complex to code, and harder to test/validate fully, but only you will know if the application justifies that investment. I was suggesting a scheme that you can implement very easily and at very low risk, without changing a single line of code that uses Chunks. Anyway, I hope it gave you some interesting options to consider!
J