From UBC Wiki


Authors: Tyler House, Billy Cromb

What is the problem?

Our team will implement the Board Game Settlers of Catan in Haskell

What is the something extra?

Settlers has more than one way to win and gain points, which will make it a little more complex than some of the games we discussed in class. If we have time we'll try to add a rudimentary GUI and an AI opponent.

What did we learn from doing this?

A game like settlers needs a graph, and it turns out that mutually recursive data structures are a little tricky to implement in Haskell.

We did some research and found that there were two ways of implementing a graph in haskell, one is with an adjacency list, which is relatively simple, the other is to something that isn't really a graph at all, but an tree of infinite length that repeats in such a fashion that it appears to be a graph. The adjacency list seemed simpler and more appropriate (since we would need to tag elements in the graph with some sort of id to use graph algorithms on it) so we went with that.

Implementing an adjacency list (really two, since there are overlapping relationships) turned out to be a lot trickier than we thought, since a settlers board has a fairly complex set of relationships. We could have decided to use a fixed board to focus on the gameplay, but instead we decided to model the random board setup project accurately, which took a fair amount of time.

Using an adjacency list takes a lot of the convenience out of functional programming, since you are essentially using references just like in a procedural programming language. The ids that we tagged are elements with aren't that different from pointers.

From the viewpoint of feasibility, we feel that while this type of thing *can* be done in Haskell, it is much better suited to be done in an Object Oriented programming paradigm. This is because from our experience, dealing with graphs in Haskell quickly gets out of hand and you lose many of the benefits of functional programming. We created algorithms for determining the layout of the Catan board, but the amount of time taken to do so would be greatly reduced using OO programming.