# Shortest distance for X city to city1/source node
Board game ticket to ride full#
My full implementation can be seen below: def findShortestPath(map, city1, city2): I also reverse the list to have it go from start to finish.
These grab the distance from our start to destination, and using a traceback through previous, get an ordered list of the cities we visit on said path. Second, for formatting reasons, I have added a couple lines to the end. Since Dijkstra’s algorithm makes no attempt at directly finding our destination, only exploring every path in order from shortest to longest, once our destination is “u” we can break from the loop. This is because we only care about finding the shortest path to our destination. First, I have added two lines after we remove the smallest distance city, from the current set of unexplored cities. Our implementation has a couple of important things I wish to discuss.
Board game ticket to ride code#
The code is based on the code given by the Wikipedia Page on Dijkstra’s algorithm function Dijkstra(Graph, source):įor each neighbor v of u: // only v that are still in Q Sudo code for the algorithm can be seen below. I have done so for the USA board, and the full code for that can be seen in the GitHub repository linked at the bottom.įinally, we must implement Dijkstra’s algorithm. Then, to create the model of the board, one must build a set of Cities and Routes, modeled on the specific board you wish to analyze. class Route:ĭef _init_(self, city1, city2, cost, color = "Grey"): Each instance variable has a getter method, and the code can be seen below. For this project, the color is not needed, but will be used in a future post. The class has 4 instance variables, the two cities it connects, its length or cost, and the color of the route. # Gets all possible Destinations with cost, returned in a list of tuplesĪllDestinations.append((destination, cost))įor Routes(edges) I have also created a unique class. # Class init requires the Cities name and a list of all Routes that touch it.ĭef _init_(self, nameOfCity, listOfRoutes=None): The code for Cities is seen below: class City: Two getters, one for each of the instance variables and third for adding a Route to the City. I have also implemented three member functions. Cities are nodes, each containing two instance variables, a name and a list of all possible routes(edges) that are connected to the City. To do so, I have created two main objects – Cities and Routes. There are multiple versions of Dijkstra’s algorithm, but for our purposes we will focus on the original.įirst, we must create a graph based on the Ticket to Ride map. To do this, we will use Dijkstra’s Algorithm.ĭijkstra’s algorithm is a popular computer science algorithm used to find the shortest paths between nodes in a weighted graph. By doing so, we should be able to increase the amount of destination tickets we can score in one game of Ticket to Ride. Our goal is to write a program that will find the most optimal path between any two cities on the Ticket to Ride board, assuming that no other routes have been claimed. As for the color system, that is beyond the scope of this post, but may be touched on in a later post. The routes can be thought of as edges, with their associated weight being the amount of trains required to claim the route.
Ticket to Ride USA MapĮach city is a node, connected to other cities by colored routes. In fact, the entire game board is basically a weighted graph. Much of Ticket to Ride can be analyzed through graph theory. It is this mechanic that we will take a look at, and use Dijkstra’s algorithm to “solve”. One of the key parts of the game is Destination Tickets – cards that give bonus points to the player if the cities are connected. Ticket to Ride has seen mass market successes, in part because of its simple rules. In Ticket to Ride, two to five players try and traverse North America by building a railroad, connecting cities, and completing tickets.
0 kommentar(er)
