I make a game and among others I have nations, provinces, tiles and armies. Each army belongs to exactly one tile, each tile belongs to exactly one province, each province to exactly one nation. I want to ask the following questions:
- Which armies/tiles/provinces belong to a nation?
- Which armies/tiles belong to a province?
- Which armies belong to a tile?
- To which tile/province/nation belongs this army?
- To which province/nation belongs this tile?
- To which nation belongs this province?
These questions are multidirectional. A hierachical tree with nations on top and provinces, tiles, armies below will only answer questions 1-3 efficiently while answers 4-6 would require a loop over all nations/provinces/tiles to find the nation/province/tile that belongs to a province/tile/army.
So one could store 4 different trees, each time with nations/provinces/tiles or armies on top to enable a fast lookup. However then modifying the whole structure (adding/deleting/modifying a nation/province/tile/army) gets a complex task and therefore prone to errors.
I'm a bit lost here. I would like to keep the code and the underlying data structures simple to prevent errors when modifying the structure or when adding more functionality but I would not like to give up speed for answering the mentioned questions. I'm looking for a balance of code complexity and speed where code simplicity is more important.
In particular: Can I have a single data structure (and easy adding/deleting) while not having to loop over all nations/... when asking the reverse question? What is the simplest data structure/algorithm that allows asking all these questions with reasonable speed, i.e. without having to loop over every nation/...?