Hi,

I'm creating a strategy-based kingdom expansion game, where you start with one city and try to expand as far as possible from there. All the cities fit on a hexagon-grid and are connected by the edges of the hexagons.

Here's a diagram to illustrate what I'm trying to achieve:

Each city must be connected to another city by road, which means that all the cities are connected. At this point, I began to realize that this map is very similar to a graph, with the cities being nodes, and the roads being edges. I've already done some graph theory and implement multiple algorithms. However, when implementing it in a graph format (Map<Node, List<Edge>>), I ran into 2 problems:

1. There is no way to force that each node can only have 3 connections, with each being a multiple of 120º
2. If it was stored in this format, it would be very difficult to render just loop it through for updating.

I'm wondering if any of you have any better data structures that can be used for this. Any criticism, suggestions, or advice is welcome.

Thanks!

There are many ways to store a graph. What's best depends on if it is static or dynamic, and what algorithms you use with it.

E.g. you could use vector<pair<node, array<adjacentNode,3>>>,

or something completely different, like a regular grid with bits indicating cities and roads.

You could implement graph algorithms with any format, so you have to figure out if it is mainly about ease of implementation, or about max performance.

So to narrow the question, you might wanna tell what will happen in the game for most.

hs12503 said:
1. There is no way to force that each node can only have 3 connections, with each being a multiple of 120º
2. If it was stored in this format, it would be very difficult to render just loop it through for updating.

It is not unusual to maintain two separate representations of this sort of map: one used for gameplay logic, and the other for rendering.

The gameplay logic can be a pure graph, since it's pretty unlikely that the specifics of things like 3x 120º angles are important there. By comparison the rendering side cares very much about that sort of thing, and also about how to convert the map into triangles for rendering.

@swiftcoder @joej Thanks for your reply! From what I'm hearing, I can use a pretty standard graph representation for the logic, and keep a more strict one for rendering. I've thought about it for awhile, and I'm thinking about using a hexagon-grid to store the cities, but I'm unsure on the edges. Do you guys have any ideas?

I end up storing all components of a hex map. An array of hex vertices, an array of hex edges stored as (start, end) indices into the points array, and an array of the hexes themselves (with appropriate indices into the vertex and edge arrays). It's quite a bit of data, but it means you can traverse the graph with a lot of flexibility.

@swiftcoder

Thanks for your reply! From your advice I have decided to use 2 separate structures:

1. A graph to represent the cities (nodes) and roads (edges). The graph API is completely separate from the games API, with no dependencies between the 2. The graph is purely used for AI/logic.
2. One list of all the cities, and another list of the roads. This list is used for rendering, and some updating.

I'm thinking of making a bi-directional map to easily transform between the graphs nodes and the list of cities. Does this seem like the right way to go?

I'm not so sure what you mean when you advise storing “an array of the hexes themselves”. Isn't this irrelevant because I only need to access roads and cities.

Also, I am thinking of using an entity component system in my game. Does this change how this should be arranged?

Sorry for all the questions, I'm not really that experienced with designing/making games.

Thanks for all your help!