1

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:

  1. Which armies/tiles/provinces belong to a nation?
  2. Which armies/tiles belong to a province?
  3. Which armies belong to a tile?
  4. To which tile/province/nation belongs this army?
  5. To which province/nation belongs this tile?
  6. 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/...?

Improve this question
3
  • 3
    Why don't you give every of your provinces, tiles and armies a (redundant) reference to its parent tile/province/nation? You then have to consider this reference on each update of course, but it gives you instant access to the answers for questions 4-6. Would that be already too messy/complex?
    – valenterry
    Commented Nov 19, 2014 at 22:08
  • @valenterry Thank you for this helpful comment. This seems like the obvious way to go and now I ask myself why I haven't seen this for myself. It's not too complex although the number of tiles, armies and provinces is quite large, so storing a back reference induces some overhead, but not too much. Thanks again.
    – NoDataDumpNoContribution
    Commented Nov 21, 2014 at 8:49
  • Glad I could help you. I created an answer so that you can mark the answer as accepted solution.
    – valenterry
    Commented Nov 21, 2014 at 9:53

1 Answer 1

Reset to default
2

One Option is to give every of your provinces, tiles and armies a reference to its parent tile/province/nation. You then have to consider this reference on each update of course as you now have some redundancy in your code and a little memory overhead. Though, the good thing is that it gives you the answers for questions 4-6 in an instant (constant time).

(From my comment to the question, see also: https://meta.stackexchange.com/questions/1555/mark-a-comment-as-answer-to-a-question)

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.