Designing the Graph Data Structure to Manage Board Pieces

TLDR

Adding PLACE_SETTLEMENT action to the backend service and command line testing tool. Starting design of graph data structures and algorithms for piece placement.

Sketching out what the nodes of the graph should represent. Should all pieces be connected in a single graph? Could each node have a field that indicates which piece type the node refers to? For example, nodeType = ROAD | SETTLEMENT | HEXAGON? Do we hardcode the adjacency information in a lookup table?

Showing we can display settlements and roads on the UI by simply hardcoding an initial value for the underlying graph data structure.

Main work

• Working through the “first draft” of the graph logic that will drive Settlement and Road placements.
• Sketching graph approach and visualizing design options.
• Creating an additional CatanGraph model for “re-organizing” the CatanGame for later processing.
• Creating CatanGraphService that has static methods for modified graph operations.
  • e.g., Finding the longest path in the graph while considering Settlement’s unique effect on the longest paths of Roads.

Challenges

• Ran across issues with up-casting collections of objects while making Settlement and Road implement a ICatanNode interface. See explanation of issue below.
• Also suspect I’m having pass-by-reference issues while building a CatanGraph from existing collections. I likely need to think about the graph structure of the board more before diving into this implementation.
• The CatanGraph is actually a graph of both roads and settlements (based on my chosen approach). If we wanted the longest road, we have to consider if there is another player’s settlement breaking that path. For this reason, standard algorithms like Dijkstra’s shortest path do not work without modification. We not only have the consideration of “adjacent” nodes, but nodes that could be “skipped” (no settlement placed), or nodes that could be “owned” by another player.
  • On top of this, we are also working with a clear restriction on possible graph edges / connections. Settlement 17 in the screenshot, for example, will only ever have at most three edges. I’ve chosen to hardcode the potential connections, since they are inherent to the board structure and are essentially data.
• Game logic is now the main concern, so writing fully-automated tests may be worth it at this point. Then, I will be able to continue moving quickly and be confident earlier logic is not broken.
  • This is weighed against just pushing through to a MVP full-game and then retroactively adding test coverage.
  • Because this is a solo project, I may choose the later.

Learnings

• Thanks to this article,, I understand why up-casting is an issue for my proposed ICatanNode inheritence. Key is from this part of the article:

  List<String> stringList = new ArrayList<String>();
  List<Object> objectList = stringList;  // Let's pretend this is possible
  objectList.add(1); // Hey, 1 is not a String!
  String element = stringList.get(0); // Wonder what will happen...

  This is interesting, because I had not considered multiple references to the same object. My original assumption was that you could assign to a more generic container type, since the more generic type loses type information and therefore makes less type assumptions. That ignores the original reference though, which still assumes a specific String type.

  List<String> stringList = new ArrayList<String>();
  List<Object> objectList = stringList; // I expected this to be possible (it is not)
  
  // Then, I expected this to throw compile error and protect us
  // However, you would never have been able to instantiate objectList
  List<String> l = objectList;

• I am very comfortable with graphs, but working with a graph having mixed node types is error-prone and mentally taxing. This brings my design approach under scrutiny, since its implementation is possible but likely not an elegant solution.