Good day to you all! I am currently programming a quite general 2D transportation simulator (car traffic, pedestrians, or whichever mathematical model one writes and plugs in) and would like to get your opinion on how best to implement the mapping part. The simulator has to be quite general and be able to simulate both macroscopic and microscopic discrete movement (not simultaneously though). For the macroscopic movement, an undirected graph would be convenient. For microscopic movement one would like a grid with some obstacles and walkable tiles, hence an undirected graph could do as well. The part where I am having some trouble is trying to find a proper structure which would not make it overly complicated. With what sort of structure could one embed the graph into a 2D-space in order to be able to use both the convenience of the graph (for pathfinding for example) and the spatial location of each node (for example if one wants to get all tiles visible to one pedestrian)? For example in Java, I was thinking of using a HashMap of node objects (which contain the node and a reference to the nodes it is linked to) indexed by their spatial location. Any comments on that? Thank you

How about a 2D array of booleans (with the booleans indicating passable/not passable)?

Thanks for your interest.

This would work for the microscopic level, but not for the macroscopic level, since for example one town could be linked to 12 other towns, which cannot really conveniently be represented on a 2-d grid. The difficult question is what structure should be used in order to associate a spatial representation to a graph.

It depends on what information you need in order to perform both the microscopic and the macroscopic simulations. At the microscopic level, you have an array of tiles that contain individual cars, pedestrians, obstacles, etc., and they have little AI routines running which determine how they behave and interact with other agents. The collection of these AI routines can be considered your microscopic model. However at the macroscopic level you're not simulating individual agents, but rather an entire collection of agents. Each node in the undirected graph can contain a 2D position which helps determine the distance between two nodes and allows you to perform simple pathfinding to optimizes distance, number of nodes traveled through, etc., but you'd still use a separate macroscopic model of a node to simulate the system that doesn't necessarily take into account 2D position of individual agents.

The best example I have off the top of my head is the X3 game series (of which ApochPiQ knows quite a bit so he can probably chime in and add anything I miss). The game is divided into a series of sectors which are connected by jump gates to form a giant undirected (mostly) graph. Each sector has a ton of agents (ships, space stations, etc.) going about their daily business, however how they are simulated depends on the player's location. Whichever sector the player is in gets a full physical simulation of space flight, where things collide and ships need to maneuver properly to dock at space stations and turn to face enemies to fire, etc. However all other sectors use a separate simulation where each agent is just a position and velocity. Whenever two ships get into combat, a stochastic model based on their relative strengths and weaknesses it used to determine the victor. Ships are considered docked at space stations simply by flying over the location of the space station. In essence, the game uses a lower-resolution, faster "macrosimulation" for these sectors (of which there are hundreds).