search

alexweininger / android-catan

Famous Settlers of Catan board game made on Android
MIT License
8 stars 3 forks source link

Calculating the longest road #31

Open alexweininger opened 5 years ago

alexweininger commented 5 years ago

The longest road calculation seems to only work some of the time. Once a player gets the longest road length trophy, it seems like the calculations after that are buggy.

File: Board.java, Graph.java

alexweininger commented 5 years ago

Sadly, my team and I could never get the longest road calculation just right. We have been trying at this for over a month now, and have had no luck.

We have tried depth first search, trees, and recursive algorithms. The implementation that is currently in the game is using depth first search.

This was exceptionally hard scenario because the graph is an undirected, cyclic graph, which makes accounting for cycles extremely hard. We also did a ton of research on hamiltonian cycles but could only find help on directed acyclic graphs. We also found articles saying this was NP-hard. Initially most of the work was done by @alexweininger and @AndrewLang98. But towards the end of the project it was @alexweininger @dborg291.

Some of the errors we encountered were just simply inaccurate results from the road calculation methods. And at one point the methods were taking too long and were getting cut off by the game continuing.