| theme | background | title | info | class | layout | highlighter | drawings | transition | mdc | |
|---|---|---|---|---|---|---|---|---|---|---|
seriph |
/images/gopherAndRail.jpg |
Graphs, games and Go |
## Graphs and Games: can Go take a ticket to ride?
Slides for GoLab 2024
|
text-center |
cover |
shiki |
|
slide-left |
true |
Games help you develop skills
I am a proud Gopher since 2018
- with experiences in other programming languages too
I work (in Go) in Amadeus
- a company that creates applications for the travel industry
I like sharing my Go knowledge at conferences
- But on my free time I enjoy swimming, cooking, learning languages and playing board games
Ticket to Ride
The board represents the United States map
- The dots are cities/railway stations
- The lines are railway lines that connect them
The resources are train tokens and colored cards that are spent to occupy railway lines
- For example to occupy the line between Miami and Atlanta you'll need to spend 5 trains tokens and 5 blue cards
The objective is to get the highest score
- By occupying railway lines
- By connecting cities from objective cards
Let's see how we can play the game in Go
We Go random and simplify a bit the rules
The number of player will be 2
The railway line chosen by each player will be random
Each player has unlimited resources
- which means that each player will take turns to select a line and occupy it
Each player has no objectives
- which means that the final score will be determined by which lines they occupy
Let's see the code
```go {all|4-9|10-21}
package main
func main() {
// Collect all the railway lines
railwaylines, err := data.RailwayLines()
if err != nil { /* log and exit */ }
// create the two players
p1, p2 := player.NewRandom(1), player.NewRandom(2)
// use a coin to select the player who takes the turn and play until all lines are occupied
var coin bool
for game.FreeRoutesAvailable(railwaylines) {
playRound := p1.Play()
if !coin {
playRound = p2.Play()
}
playRound(railwaylines)
// pass the turn
coin = !coin
}
slog.Info("end game", "Score P1", player.Score(p1), "Score P2", player.Score(p2))
}
```
```go {all|1-7|8-15|16-23|all}
package player
type Random struct {
id int
owned []*game.TrainLine
}
func NewRandom(id int) *Random { return &Random{id: id} }
func (p *Random) Play() func(g game.Board) {
return func(g game.Board) {
// select and remove a random railway line from the board
chosenLine := game.PopRandomLine(g)
// add it to the owned list
p.owned = append(p.owned, (*game.TrainLine)(chosenLine))
}
}
// Score sums up the value of each owned railway line
func (p *Random) Score() int {
var score int
for i := range p.owned {
score += p.owned[i].Value()
}
return score
}
```Demo time!
Let's focus on the board for one second
transition: fade-out layout: image-right image: /images/aGraphToMeReallyYeah.jpeg backgroundSize: 90%
Let's model Ticket to Ride board as a graph
This is where we introduce graphs algorithms
- graphgo: my library to learn graph algorithms in Go
- Use gonum instead of my library for appliaction that manages graphs
- go-ticket-to-ride: the implementation of the ticket to ride game in Go
Vertices, Edges and Graphs
How we can implement them in Go and how they translate in Ticket to Ride
```go {1-4|all}
// A vertex is a node that is holding data, for simplicity we will have it comparable
type Vertex[T comparable] struct {
E T
}
// An edge is a pair of vertices that can hold any property
type Edge[T comparable] struct {
X, Y *Vertex[T]
P EdgeProperty
}
type EdgeProperty any
```
```go {1|2-5|all}
// A Ticket to Ride example
// We create city stations as vertices of our Ticket to Ride graph
type City string
newYork := Vertex[City]{E: "New York"}
washington := Vertex[City]{E: "Washington"}
// We define a property for the Edge between city station vertices
type TrainLineProperty struct {
Distance int
}
// We create a train line as an edge between two city station vertices
newYorkWashington := Edge[City]{X: &newYork, Y: &washington, P: TrainLineProperty{Distance: 2}}
```How we can implement them in Go and how they translate in Ticket to Ride
```go
// ArcsList is graph representation of a collection of edges and vertices
type ArcsList[T comparable] struct {
v []*Vertex[T]
e []*Edge[T]
}
```
```go {1-4|all}
// A Ticket to Ride example
newYork := Vertex[City]{E: "New York"}
washington := Vertex[City]{E: "Washington"}
newYorkWashington := Edge[City]{X: &newYork, Y: washington, P: TrainLineProperty{Distance: 2}}
// Keep adding cities (vertices) and railway lines (edges)
// And add all them to the board
board := ArcsList[City]{
v: []*Vertex[City]{ &newYork ,&washington /*, ...*/ }
e: []*Edge[City]{ &newYorkWashington /*, ...*/ }
}
```
```go
// ArcsList is graph representation of a collection of edges and vertices
type ArcsList[T comparable] struct {
v []*Vertex[T]
e []*Edge[T]
}
```There are other graph representations and the choice of the representation is based on memory and time efficiency with respect to the operations done
All graph representations share a common behavior that can be captured by creating an interface
type Graph[T comparable] interface {
Vertices() []*Vertex[T]
Edges() []*Edge[T]
AddVertex(v *Vertex[T])
RemoveVertex(v *Vertex[T])
AddEdge(e *Edge[T])
RemoveEdge(e *Edge[T])
// ...
}What algorithms can we use for Ticket to Ride?
Connected vertices in a graph
The game starts with all of the cities connected by the edges representing the railway lines
As soon as players occupy railway lines, the correspondent edge is removed from the graph
To check if two cities are still connected by railway lines we'll use
- visit of a graph
- connectivity of two vertices in a graph
Let's see the code
```go {all|4-10,20|6,7,10-13,14-15,20,21|5,10,16-19,20,22|all}
// GenericVisit walks the graph from a source node, visiting each node it can visit only once
func GenericVisit[T comparable](g Graph[T], s *Vertex[T]) *Tree[T] {
if !g.ContainsVertex(s) { return nil }
s.Visit()
t := &Tree[T]{element: &s.E}
queue := []*Vertex[T]{s}
for len(queue) != 0 {
var next *Vertex[T]
next, queue = queue[0], queue[1:]
for _, v := range g.AdjacentNodes(next) {
if v.Visited() {
continue
}
v.Visit()
queue = append(queue, v)
parentNode := t.Find(&next.E)
if subtree != nil {
parentNode.children = append(parentNode.children, &Tree[T]{element: &v.E})
}
}
}
return t
}
```
```go
// Connected verifies that the vertices x and y are connected in the graph g
// by visiting g using x as a source and checking that the output tree contains the vertex v
func Connected[T comparable](g Graph[T], x, y *Vertex[T]) bool {
return GenericVisit(g, x).Find(&y.E) != nil
}
```Shortest path algorithm
If two cities are connected, there is at least one route between them
To check the shortest route between two cities we'll use the Bellman-Ford algorithm
Let's see the code
```go {all|2-8|9-21|all}
func BellmanFordDistances[T comparable](g Graph[T], s *Vertex[T]) map[*Vertex[T]]*Distance[T] {
d := make(map[*graph.Vertex[T]]*Distance[T]) // type Distance[T comparable] struct { v, u *Vertex[T]; d int }
for _, v := range g.Vertices() {
d[v] = &Distance[T]{v: s, u: v}
if v != s {
d[v].d = math.MaxInt
}
}
canRelax := (x, y *graph.Vertex[T], w Weighter) bool { return d[x].d+w.Weight() < d[y].d && d[x].d+w.Weight() > 0 }
relax := (x, y *graph.Vertex[T], w Weighter) { d[y].setDistance(w.Weight() + d[x].d)}
for range g.Vertices() {
for _, e := range g.Edges() {
w := e.P.(Weighter) // type Weighter interface{ Weight() int }
switch {
case canRelax(e.X, e.Y, w):
relax(e.X, e.Y, w)
case canRelax(e.Y, e.X, w):
relax(e.Y, e.X, w)
}
}
}
return d
}
```Let's see the code
```go {all|5-7,23|3,4,8-22|all}
func Shortest[T comparable](g graph.Graph[T], d map[*graph.Vertex[T]]*Distance[T], x, y *graph.Vertex[T]) []*graph.Vertex[T] {
if len(g.Vertices()) < 2 { return nil }
isShortestDist := func(u, v *graph.Vertex[T], w Weighter) bool { return d[u].d+w.Weight() == d[v].d }
isConnectingEdge := func(u, v *graph.Vertex[T], e *graph.Edge[T]) bool { return (e.X == u && e.Y == v) || (e.X == v && e.Y == u) }
path := []*graph.Vertex[T]{y}
v := y
for v != x {
neighbourSearch:
for _, u := range g.AdjacentNodes(v) {
for _, edge := range g.Edges() {
if !isConnectingEdge(u, v, edge) {
continue
}
if !isShortestDist(u, v, edge.P.(Weighter)) {
continue
}
path = append([]*graph.Vertex[T]{u}, path...)
v = u
break neighbourSearch
}
}
}
return path
}
```Go's simplicity vs the algorithms' complexity
Updated rules
- each player now has 3 objectives
- which means the railway line chosen by each player will be made by looking at the shortest path available for the routes on their objective list
Let's see the code
```go {all|7-12}
package main
func main() {
// Collect all the railway lines
railwaylines, err := data.RailwayLines()
if err != nil { /* log and exit */ }
// Collect all the tickets/objectives
tickets, err := data.Tickets()
if err != nil { /* log and exit */ }
// create the two players
p1, p2 := player.NewWithTickets(1, game.GetTickets(3, &tickets)),player.NewWithTickets(2, game.GetTickets(3, &tickets))
// use a coin to select the player who takes the turn and play until all lines are occupied
var coin bool
for game.FreeRoutesAvailable(railwaylines) {
play := p1.Play()
if !coin {
play = p2.Play()
}
play(railwaylines)
// pass the turn
coin = !coin
}
slog.Info("end game", "Score P1", player.Score(p1), "Score P2", player.Score(p2))
}
```
```go {all|3-10|11-22|all}
package player
type WithTickets struct {
id int
ownedLines game.Board
tickets []game.Ticket
}
func NewWithTickets(id int, t []game.Ticket) *WithTickets {
return &WithTickets{id: id, tickets: t, ownedLines: graph.NewUndirected[game.City](graph.ArcsListType)}
}
func (p *Random) Play() func(g game.Board) {
randomSelection := func(b game.Board) {
// same as the random player but storing ownedLines in the graph
}
shortestPath := func(b game.Board) { //...
}
if !p.HasTicketsToComplete() {
return randomSelection
}
return shortestPath
}
```
```go {all}
shortestPath := func(b game.Board) {
localBoard := graph.Copy(b)
updatedBoard:
for len(localBoard.Edges()) > 0 {
// Part 1: keep the door open to random selection if there are no available tickets
ticket, err := p.NextAvailableTicket()
if err != nil { return randomSelection(localBoard) }
// Part 2: if there is no path between the two cities, the ticket is done and you move to the next one
if !visit.ExistsPath(localBoard, ticket.X, ticket.Y) { ticket.Done = true; ticket.Ok = false; continue }
// Part 3: if there is a path between the two cities in the objective select the shortest path and take the first segment available
shortest := path.Shortest(localBoard, path.BellmanFordDist(localBoard, ticket.X), ticket.X, ticket.Y)
for i := 0; i < len(shortest)-1; i++ {
chosenLine := game.FindLineFunc(game.ShortestSegment(ticket, shortest[i], shortest[i+1]), localBoard)
// ...
}
}
return
}
```
```go {all}
shortestPath := func(b game.Board) {
// ...
// Part 3: if there is a path between the two cities in the objective select the shortest path and take the first segment available
shortest := path.Shortest(localBoard, path.BellmanFordDist(localBoard, ticket.X), ticket.X, ticket.Y)
for i := 0; i < len(shortest)-1; i++ {
chosenLine := game.FindLineFunc(game.ShortestSegment(ticket, shortest[i], shortest[i+1]), localBoard)
// Is the line owned by me?
owned := p.ownedLines.ContainsEdge(chosenLineEdge)
if owned { continue }
// Is the line owned by someone else?
occupiedNotOwned := chosenLine.P.(*game.TrainLineProperty).Occupied
if occupiedNotOwned {
localBoard.RemoveEdge(chosenLineEdge); continue updatedBoard;
}
// Occupy the selected line
chosenLine.P.(*game.TrainLineProperty).Occupy()
p.ownedLines.AddVertex(chosenLine.X)
p.ownedLines.AddVertex(chosenLine.Y)
p.ownedLines.AddEdge(chosenLineEdge)
// Check if ticket is completed after taking the line
if visit.ExistsPath(p.ownedLines, tX, tY) {
ticket.Done, ticket.Ok = true, true
}
}
}
```Demo time!
Can Go take the Ticket to Ride? Yes!
Games are a good opportunity to practise and learn new skills
- About Go and beyond
Go makes it easy to translate pseudo-code in actual code and to implement algorithms
- No matter how complex the algorithm is
Take advantage of the simplicity that Go brings you
And you'll be able to create awesome things with Go!
Thank you very much!
Other examples of game development in Go:
- Daniela Petruzalek's talks Building an Indie Game in GO and Pacman from scratch;
- Drishti Jain's talk Go Beyond the Console: Developing 2D Games in Go;
- Othello style game
The repositories used in this presentation are:
- graphgo: my library to learn graph algorithms in Go on my free time
- go-ticket-to-ride: the implementation of the ticket to ride game in Go
- golab24-GraphsNGo-slides: the link to the code of these slides
Prefer to use gonum instead of graphgo for working with graphs as it is a more complete library