How should I store a city map on disk?

Question

I'm working on a game where players travel in a city.

This city is defined by streets (names, positions...), points of interest (cinemas, restaurants...) and different zones (high criminality zones, rich zones, poor zones...). I still don't know if this city will be based on a real one (using OpenStreet map data) or made by game designers. In either case, I need to be able to modify the map data (add a cinema here, move a restaurant there...).

I also want to be able to search it for stuff like "Where is the closest restaurant?" or "How long would it take to travel to that street?".

How should I best store such information on disk, to be loaded or modified later?

(I'm working with Unity, but this isn't a Unity-specific question.)

Answer 1

Sounds like you want a graph data type. Nodes could store their positions, plus references to features like restaurants, as well as references to other graph nodes. This is effectively an adjacency list.

Existing pathfinding algorithms work well on such graphs. You could easily calculate the weight of a graph edge (the "difficulty" of that link) as the distance between two nodes' positions.

The remaining issue is serialisation: specifically, converting a graph into a character sequence that can be stored on disk, to load later. This StackOverflow question has some ideas, but the exact implementation will depend on your needs and tastes. If you like XML, you might like to use xs:ID/-REF. If you want to be minimalist, maybe roll your own?

I like JSON, so I would serialise your type of game map as

{
  "nodes" : {
    "0" : {
      "features" : [
          "bs5xgsgfg"
       ],
       "position" : { "x" : "0", "y" : "0" }
    },
    "1" : { "features" : [], "position" : { "x" : "100", "y" : "0" } },
    "2" : { "features" : [], "position" : { "x" : "0", "y" : "100" } },
    "3" : { "features" : [], "position" : { "x" : "100", "y" : "100" } }
  },
  "edges" : [
    { "from-id" : "0", "to-id" : "1" },
    { "from-id" : "1", "to-id" : "2" },
    { "from-id" : "2", "to-id" : "3" },
    { "from-id" : "3", "to-id" : "0" }
  ],
  "features" : {
      "bs5xgsgfg" : {
        "type" : "nightclub",
        "name" : "Cyberia",
        "dangerousness-level-or-something" : 15
      }
   }
}

That would encode a fairly boring city, with 4 street corners arranged in a square, with a nightclub at one corner and a one-way street going clockwise along the streets of that square. I think you see where I'm going with this though.

Answer 2

I would store the data in a graph to help with pathfinding - nodes are intersections and edges are streets (with one-way, no pedestrian, etc flags). Then for storing the data I would take a multi-layered approach

Gather the Source Data

First find some way to define (or import) the data. Likely a visual tool would help, but you could get away with something that supports real-world coordinates (latitude, longitude, etc). You will want to support connectivity at this stage, but also allow objects to be just 'placed' in the world (cinemas, etc), since writing the tedious connectivity code in XML, JSON or a non-visual tool will be cumbersome. File format of this might be useful to be somewhat human readable, so XML or JSON, as long as the format supports circular references and links. Nodes likely should be stored in a text-editor searchable format - GUID, or some such - to help authoring and debugging.

Add Connections & Validate

Now you need a tool that takes **all* of the world data and creates any game-specific connections, intersects roads and makes connections, annotates the world with one-way-streets. The data should be loaded all at once, in an offline tool, into some kind of verbose/fat format. It would have all the useful information in it so you can write validation steps. It should also allow debug pathfinding so you can run offline tests that you can truly get from the Eiffel Tower to the Louvre. Having a separate tool in an offline process for this is great because you can add as much cumbersome debugging information to it but you never have to feel like your game code is getting dirty. Plus the format you store this in memory will likely be vary different than in games - adjacent nodes will be in a dynamic list, whereas at runtime it will be in a fixed sized array, or a linked list, for example.

Emit Data

To make searches efficient you will want to store the data in some kind of efficient representation. That means your GUIDS will be compressed down to some kind of incrementing ID, and adjacency/edge information will be stored in flat arrays, or linked lists. All of this is really important to get your searches fast. Furthermore, specific entities (such as restaurants, or cinemas, would be stored in a separate data structure so you can quickly locate their positions in the world. That structure might be a database of restaurants, say, or it might be a uniform grid where each grid stores all of the buildings in it in order to make searches for 'nearest things' faster, or both. I suspect both. By making the emitting stage separate from the validate stage you can write code that compresses the data into game-ready format without worrying that you've broken the preprocessing or validation stage. Your writing code might be sharable with the reading code in the game, too. You might also want to chunk up the data into pieces to stream in, or implement a hierarchical path finding system on top of it so you don't need all of the fine-grained data loaded all the time.

Load the data

Now the game loads the data and starts working on it. Ideally the data is loaded with as little work possible. I always strive to make my data memory imaged so it loads in place without any allocations, but that's for my commercial production game environment.

Good luck.