I just wrapped up another week of my work for the project. Most of my work was spent handling ‘move conflicts’ in our simulation. For a (simple) example, imagine species 1 wants to move from A -> B. Species 2 wants to move from B -> C. Since our simulation executes all moves in parallel, how do you determine which move occurs? And how do you fairly resolve the move that doesn’t occur?

Building off that example above, what if there was a third species moving from C -> A? Now you have a cycle of moves, and suddenly we’re dealing with everyone’s favorite data structure, graphs. Essentially, the entire set of moves forms a series of Directed Graphs, which can be cyclic. To execute all the moves without conflict, every graph needs to either consist of 2 nodes with an edge between them (species moving to a blank space OR eating a species), or a single node (species standing still).

With that end goal in mind, this is the algorithm I used to fairly resolve moves. First, generate the directed graphs from the set of moves. Right now moves are stored in dictionaries, and I used the handy NetworkX python library to handle the graph manipulations (sidenote: this is an excellent library and really allowed me to focus on HOW I could fix the problem, and not worry about making sure I was implementing things like topological sort correctly. After creating the graphs, I then check if they are cyclic or acyclic. If they are cyclic, I remove any self loops (species staying still, not an issue in move execution), and convert any other loops into acyclic DAGs by finding the move in the loop that has the highest “speed” stat. Speed is one of our underlying stats on a species genome. After finding this move, I remove the back edge leading to this move and change that move to stand still. Thus, all cycles are broken.

Next, we need to break the graphs down into single nodes or graphs of 2 nodes. I topologically sort each weakly connect component. I then iterate through each node in order in each component. If at any point, a node has a path length > 1, I remove the move/edge directly following this current nodes move (represents a species eating another species). I then break for the current component, continue checking the other components, and restart the process. This continues until all components have a max path length from any node of 1.

Finally, we have to resolve components that have a ‘wheel-spoke’ structure, i.e. multiple species are moving into the same space. The approach I took was to simply find the move with the highest speed again, and force the remaining species to standstill.

This process guarantees all moves will execute without conflict. There is some room to tweak it. One piece that I don’t love is that I force species to standstill and commit a non-optimal move. I reconcile this by just imagining it as the species planned to do something else, but a faster species beat them to the punch so they’re just biding their time. Either way, a different approach could be used in these instances.

I really enjoyed working on this problem. It was fun to apply traditionally classroom/leetcode type problem solving (identify cycles in this graph, remove cycles in this graph, sort the graph etc.) to an actual app that I’m creating.