Recommend
37 
 Thumb up
 Hide
29 Posts
1 , 2  Next »   | 

BoardGameGeek» Forums » Board Game Design » Board Game Design

Subject: Ticket to Ride: Random Board Generator rss

Your Tags: Add tags
Popular Tags: custom [+] [View All]
Tom P
msg tools
mbmb
This thread may be a little unorthodox for the game design forum but I felt it was the best fit.

I recently wrote a program to generate completely new random maps for TTR. Of course the map isn't completely random because that would be worthless. I gathered a bunch of statistical data from the American TTR board and used it to guide the algorithm. The result being that the generated map should provide balanced and interesting gameplay similar to the official TTR board. The program also generates the ticket cards needed to play the new map.

Here's an example map that the program generated.


Just by looking over dozens of maps that the program generates, they look reasonable and playable. Statistically they're in the same ballpark as the official board. Unfortunately, you can't truly be sure about the balance of a map without actually playing it.

I'm interested in some thoughts, feedback, suggestions, questions (anything) from others. If you want to try out a map, I'll generate the files for you as a print and play. I can't give out the code in it's current state (it's written fairly sloppily so it crashes regularly).


EDIT: General algorithm description.
The program starts by randomly placing a random number of nodes (between 30 and 40) within a randomly defined area and creates all the edges between those nodes.

Before going further, I should note that I'm going to use the word random a lot but rarely do I mean truly random. Random values are subject to various limits, restrictions, and skewing that I impose based on statistics gathered from the official board.

With the base map set, it needs to be refined. The program goes through a series of logic steps looking for obvious flaws. For example, nodes with only a single connection or edges that cross each other. The map is adjusted to eliminate these.

At this point, the map is technically playable. It's analyzed for a number of statistics and these are compared to those of the official map. If it fails this test (which it almost always does) then a few nodes are chosen and moved and the edges are rearranged to accommodate. The process repeats until the random map statistics are similar to those of the official map.

Now the double routes are assigned. Several random candidates for routes are generated and considered. A few are chosen to achieve the desired statistics and applied to the map.

Now colors are assigned. This is actually one of the trickiest parts to code. The program figures out the number of trains and edges that each color gets based on the generated map characteristics. It begins to distribute edges to the various colors at random to reach the quotas. Some logic is applied along the way mostly with regards to the coloring of double edges.

At this point the map is complete and program generates the new ticket cards. Again, the distribution of the tickets is based on statistics of the official tickets. It chooses the destination nodes for the tickets and then calculates the point values.

Finally the program spits out all the necessary data as well as the pretty map picture (and a bunch of relevant telemetry and statistic data gathered along the way).
32 
 Thumb up
7.51
 tip
 Hide
  • [+] Dice rolls
Clive Lovett
Canada
Kamloops
British Columbia
flag msg tools
designer
Avatar
mbmbmbmbmb
What data do you need to put in the algorithm? Can you determine how many cities or is it based on the number of cities on the US map?

Looks awesome!
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
John Kornhaus
United States
Bothell
Washington
flag msg tools
Avatar
mbmbmbmbmb
Interesting idea. I'd suggest an additional rule to avoid situations with multiple same-colored routes going into the same city (6, 11, 12, 31 and especially 23). On the USA map, this is always handled as in 37, where a dual-route connection has the duplicate color. I can only find one other instance of this; Zurich on the Swiss map.

You might also want to avoid all-gray double routes, or perhaps include some options to control the coloring of the doubles.

Have you balanced the coloring of routes of different lengths, or balanced the colors and route lengths in different areas of the maps?
6 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Sam Mercer
United Kingdom
Southampton
Hampshire
flag msg tools
designer
Avatar
mbmb
Tom, that is phenomenal

very impressed!

sam
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Old Gamer
United Kingdom
flag msg tools
badge
Avatar
mbmbmbmbmb
Very nice work. :)

What did you write it in?
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Mr T.
Australia
KILLARA
VIC
flag msg tools
badge
May 2018 be all you dreamed it would be and be all that you dreamed...
Avatar
mbmbmbmbmb
Yeah 23 looks screwed if you are denied Green cards.

Example map above also seems a little short on 6 routes but that may be desirable.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Danilo
Brazil
Águas Claras
Brasilia / DF
flag msg tools
badge
Avatar
mbmbmbmbmb
Great work Tom!
Considering that the original map it´s very funny and balanced, you could correlate data of each generated map with the original, for any analysis (e.g. number of cities, routes of each color, balance).
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Tom P
msg tools
mbmb
@Clive:
The program doesn't take any user input currently. You just run it and it spits out a map. Currently it chooses a random number of nodes between 30 and 40 (official board has 36).


@John:
I was definitely considering more logic with edge color selection to eliminate issues like that. It's not an easy problem to solve, though, and I'm uncertain just how big of an issue that would be in actual play.

The official board does have all grey double edges though they tend to be short edges. I'm not sure why that decision was made or how big of an impact it would have on gameplay. I did add logic to remove the possibility of color/grey double edges.

All colors have the same number of edges and the same number of total trains (as in the official board). In the example board each color has 5 edges and 17 trains. The program picks these numbers based on characteristics of the map it generates.

I'm debating if I should add logic to limit the number of edges connected to any particular node. In the official board, nodes have a maximum of seven connections. I'm not sure if that was done for gamelpay reasons or for aesthetic reasons (to keep the board clean). You'll notice cities with seven connections on the official board are completely surrounded with no room for additional connections.


@Neil
The example map definitely has fewer edges with six trains than the official board. The number, of course, fluctuates from one random map to the next but in general it's difficult to achieve so many long edges on a random map.

It's not obvious from just looking at the American TTR map but the cities are actually placed in a surprisingly uniform grid pattern (it's more apparent in the western half). This allows the official map to remain well connected despite having more long edges.

Again, I'm uncertain how big of an effect this would have on actual gameplay.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Nolan Lichti
United States
Indianapolis
Indiana
flag msg tools
mbmbmbmbmb
First, this is really cool. I can't imagine what all went in to determining this.

tpapp157 wrote:
Now colors are assigned. This is actually one of the trickiest parts to code. The program figures out the number of trains and edges that each color gets based on the generated map characteristics. It begins to distribute edges to the various colors at random to reach the quotas. Some logic is applied along the way mostly with regards to the coloring of double edges.

Do you take into consideration the number of routes of a particular length in each color?

For example, in the base game* there is one 6-length route of each color including gray. There is one 5-length route of each color except there is no gray, and two green and white.

I guess my concern with the example you show it that there are a lot of 5- and 6-length gray routes. In the original game, most of the high-scoring routes are colored, and the vast majority of gray routes are 1-, 2-, or 3-length. I presume this is in order to make it more difficult to score on the higher-length routes.

* first edition -- used an image on BGG as reference so I don't know if there were any changes
4 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Leon Hendee
United States
Atlanta
Georgia
flag msg tools
Avatar
mbmbmbmbmb
This looks good. I can see additional uses for it if you could define the size and shape of the board and define where at least some of the nodes go.

 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Michelle Martino
United States
Wausau
Wisconsin
flag msg tools
designer
publisher
badge
Avatar
mbmbmbmbmb
This is awesome! You are amazing!
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Brian
United States
Illinois
flag msg tools
mbmbmbmb
This is really cool and a good fit for this forum. Some designers may be interested in using this program to generate maps for their original game designs.

tpapp157 wrote:
@Clive:
The program doesn't take any user input currently. You just run it and it spits out a map. Currently it chooses a random number of nodes between 30 and 40 (official board has 36).

Eventually, it would be cool if you could set up a google map with like 50 cities/towns identified and let the program select 30-40 of them to build a map around. The example map is very impressive mechanically, but theme is an important part of TTR.

tpapp157 wrote:
The official board does have all grey double edges though they tend to be short edges. I'm not sure why that decision was made or how big of an impact it would have on gameplay. I did add logic to remove the possibility of color/grey double edges.

In my view, the short gray edges add a lot of tension to the game because anyone can claim them at any time.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Tom P
msg tools
mbmb
@Nolan
You make a good point. The program doesn't explicitly try to color the longer edges. I'll play around with some parameters and see what I come up with.

@Leon
I can see the desire for being able to define things like the map dimensions. The only issue I see is that these things need to be kept within certain bounds. For example, if the map dimensions are too rectangular then you won't be able to hit the various stat benchmarks and the map will be imbalanced.

@Brian
I friend of mine mentioned the same idea of using geographical maps and having the code generate a map with theme rather than just a random nodal network. It's definitely possible but it's not easy. It'll either require me to write a lot of image processing algorithms to parse the necessary data out of the image or the user to input all the necessary data by hand. It's definitely something to think about but it's not a trivial undertaking and I'd like to improve the random map generator first.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Matt Riddle
United States
Oxford
Michigan
flag msg tools
designer
badge
Avatar
mbmbmbmbmb
that rules. I would say using actual maps would be cool but the nod alignment... that seems tough. could you feed in a fixed set of nodes and have it generate teh track between them? eiter way... awesome job. I wonder if they are going to have another map constest!
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Tom P
msg tools
mbmb
Allowing the user to input a set of node locations wouldn't be a problem. What would be a problem is the possibility is that those nodes won't be able to achieve the playability statistics necessary for a balanced game. I'm not sure how that problem could be solves without simply spitting back an error message.


A small update. I've been adjusting several of the parameters to get the generated maps closer to the official map. Especially in regard to increasing the number of longer edges. I've also made some usability improvements like renumbering the nodes from top to bottom (makes a huge difference). Finally, the program now spits out pretty printable pictures for all the tickets.

I've printed out this new map which I'll hopefully be playing with some friends later today. I'll let you know how it goes.
If you're interested in trying these out yourself just download and print the images. We can compare gameplay notes. The map needs to be printed at about 34 pixels per inch to be appropriately sized (for reference the TTR trains are exactly 1 inch long). The tickets can be printed on a single sheet of paper (they'll be a little small but still usable).

1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
-=::) Dante (::=-
United States
KEW GARDENS
New York
flag msg tools
badge
Avatar
mbmbmbmbmb
tpapp157 wrote:
@Clive:
The program doesn't take any user input currently. You just run it and it spits out a map. Currently it chooses a random number of nodes between 30 and 40 (official board has 36).


@John:
I was definitely considering more logic with edge color selection to eliminate issues like that. It's not an easy problem to solve, though, and I'm uncertain just how big of an issue that would be in actual play.

The official board does have all grey double edges though they tend to be short edges. I'm not sure why that decision was made or how big of an impact it would have on gameplay. I did add logic to remove the possibility of color/grey double edges.

All colors have the same number of edges and the same number of total trains (as in the official board). In the example board each color has 5 edges and 17 trains. The program picks these numbers based on characteristics of the map it generates.

I'm debating if I should add logic to limit the number of edges connected to any particular node. In the official board, nodes have a maximum of seven connections. I'm not sure if that was done for gamelpay reasons or for aesthetic reasons (to keep the board clean). You'll notice cities with seven connections on the official board are completely surrounded with no room for additional connections.


@Neil
The example map definitely has fewer edges with six trains than the official board. The number, of course, fluctuates from one random map to the next but in general it's difficult to achieve so many long edges on a random map.

It's not obvious from just looking at the American TTR map but the cities are actually placed in a surprisingly uniform grid pattern (it's more apparent in the western half). This allows the official map to remain well connected despite having more long edges.

Again, I'm uncertain how big of an effect this would have on actual gameplay.


For each area you've said "uncertain how big an effect on gameplay", the answer is without a doubt… "Big", at least if you are trying to achieve a similar degree of balance, challenge, player count, and confrontation level (or relative lack thereof) as the USA map.

6 routes is just one glaringly obvious example. It's not coincidence that precisely one 6 route exists for every color in the game along with one additional 6 route that is gray. Any deviation from that dramatically changes how one would approach the map strategically as it would immediately make certain colors more valuable than others from a scoring perspective.

Such deviations may on occasion be entirely playable and interesting but they'll no longer resemble the particular balance and gameplay for which the USA map is well known. This may not be a bad thing as just about every official expansions is wildly different in feel from the original, but of course they were designed with intent and extensively play tested before they were released.

If the goal of this script is to try and randomly approximate such dramatically different experiences then leave the wide variations in the algo, just realize that it also means much more play testing will be needed to establish whether each map "works" well, and for how many players.

If you want a map generator that is as close to foolproof as you can get then you'll want to stay much closer to the color/length/connection distribution of the original map you're modeling the algo on.
3 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Tom P
msg tools
mbmb
Obviously, as you say, any deviation from the baseline USA map is going to influence the play of the game. In some cases substantially. What I'm more interested is a more black and white playable vs unplayable comparison. Generating a map that doesn't have an edge of each color that's 6 trains long will certainly influence gameplay but it won't suddenly make the game unplayable or even unenjoyable.

This is a good opportunity to really define where I want to get this program. My program is not intended to create perfectly balanced maps that can be replayed hundreds of times (like the original USA map). What I want are maps with random features that provide a novel play experience but are only really intended for a handful of replays at most. At that point you would simply generate a new map for a totally different and new play experience.

The program, therefore, needs to be able to generate maps that balanced enough to be playable and enjoyable but that purposely lack the rigorous polish of the original USA map. It's the imbalances that really drive the novelty of the play experience as players need to adapt to. For example, in the map above there's an obvious choke point around node 7 which players need to accommodate in their strategies. There's no way that map would stand up to very many replays because of such a dominant imbalance but for a couple of games it creates for a novel play experience.

This brings me back to my original point. With all this in mind, how much do various features of the map actually impact gameplay? Does not having a 6 train long edge of each color imbalance the game to the point of unplayability? How far can you push various parameters before the gameplay simply breaks. Can a map support two 6 length edges of the same color (absolutely)? three (maybe not)? four (definitely not)? These are the sort of questions that I'm interested in because their answers tell me how stringent the bounds of my program need to be. I would like to incorporate as much randomization as possible while maintaining overall balance and playability.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Tom P
msg tools
mbmb
I promised an AAR for the map I posted above. This won't detail the step by step play but only my thoughts in hindsight. It was a four player game.

Considering this was the first time a board generated by my program was actually played, it went better than I expected. We did play the game all the way through and no one was overly disappointed by the end. I came in second with 6 completed tickets and 1 uncompleted ticket (same with the player that came in first).

I was unsure how the choke point at node 7 was going to work in practice. Even with the double edges, though, it turned into a real traffic jam. You can see how separated the top left corner is from the rest of the map and by the end of the game, all six edges leading into that area were taken. At first I was really disappointed by this because when I initially looked at the map I felt that the choke point and corresponding 6 length edges would create some interesting strategic decisions for players. After some more thought I realized that the choke point wasn't actually the source of the problem. The problem was that the tickets were driving everyone through the choke point.

If you take a closer look at the tickets we played the game with, you'll see that most of the nodes are either in the bottom right corner or the top left corner of the map. As a result, all four of us were trying to create routes from the bottom right to the top left going right through the choke point. The lower bottom left and top right portions of the map were virtually untouched. I'm optimistic that the gameplay can support a map with such an extreme choke point if the players aren't all trying to cram through it.

My first job is to rewrite my ticket generator so that ticket nodes are more intelligently distributed around the board and therefore ensure a wider variety of route strategies are viable. Once I decide exactly how I'll do that I'll playtest the same map with new tickets and see how it goes.
3 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
-=::) Dante (::=-
United States
KEW GARDENS
New York
flag msg tools
badge
Avatar
mbmbmbmbmb
The clarifying of the goals definitely helps in formulating feedback. I'm immediately struck by how interesting it will be to have a talent for board assessment playing a significant role not unlike other games with variable starting conditions like Dominion.

One thing to look at is how certain variables affect player count. Choke points, overlap in tickets, overall map size are just a few of the things that come to mind when I think about what makes maps like Nordic and Switzerland perfect for 2 and virtually unplayable for 4+.

So as you play test keep in mind that what would feel unplayable with 5 may be exactly the right mix of challenges for 2-3 and vice versa.

I imagine it would be ideal to eventually have various presets for different player counts when generating each map.

If that can be achieved you can even adjust for the tastes of the players… intentionally selecting one below the actual count for a group that thrives on vicious interaction and going one higher for low confrontation love-fest folks.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Tom P
msg tools
mbmb
Player presets are an interesting idea. I think it would be worthwhile to look into. Right now I'm still trying to get the base program working reliably. The more logic and constraints that I impose on the algorithm, the less likely it is to converge to a solution so these things can be a bit of a tradeoff.

A small update. I've been experimenting with the ticket generator (and rewrote it several times over) trying to get the route distribution that I want. It's definitely better than it used to be but I'm not sure if it's where it needs to be yet. I think I'll have the opportunity to do some more playtesting this weekend and we'll see where things stand then.

I've also been improving several of the other algorithm modules. It runs much faster now for example. I'm also playing around with the idea of initializing the program with a more structured board setup (randomized grid vs purely random) to hopefully get better results out the other end.

Ultimately, what I'm trying to do is boil down the TTR game board to as few key statistics and logic points as possible to maximize randomness while maintaining balance. I've got a pretty good idea of what those are but I'm still experimenting and learning and I'd love to get some more outside perspectives.
1 
 Thumb up
0.02
 tip
 Hide
  • [+] Dice rolls
Tom P
msg tools
mbmb



I recently rewrote the ticket generator and node layout algorithms to provide better results. To test it all out, I played a game with four other people on this map.

At first it felt like the map might be too big and I was worried that there wouldn't be much conflict or tension. As the game progressed and the board filled up there was certainly some conflict though overall the game was fairly tame. That's also partly the result of the group that I was playing with which wasn't very aggressive. Overall the game went well which made me happy. I think I'm on the right track but there's still plenty of work to do.

I've been working on improving the portion of the program that distributes edge colors. This is a fairly difficult chunk of code that's been causing me a ton of headaches. I added functionality so that it won't place edges of the same color adjacent to each other. It still needs a lot of work.

I also added logic to prohibit repeat tickets (as can be seen above).
4 
 Thumb up
1.00
 tip
 Hide
  • [+] Dice rolls
Benjamine Allen
United States
Grand Ledge
Michigan
flag msg tools
mbmbmbmbmb
This is pretty awesome what you are doing...looks good so far!
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
John Gibson
Canada
Calgary
Alberta
flag msg tools
designer
badge
Avatar
mbmbmbmbmb
Great project, Tom. You've probably come a long way since you sat down at your keyboard and decided to create a random map generator for TTR. I think you should be strongly commended for taking on such a task, especially with your attention to the statistics of the original board. After reading this thread I envision a website where you simply select the number of players from a drop-down list and moments later a few PDF files are generated that you can save to your computer. Very kewl! cool
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Tom P
msg tools
mbmb
Thanks. I don't know too much about web coding so I doubt that's what the final form of this project will take. Frankly, I have no idea what the final form of this project will be. I'd like to get it out there in some form so other people can use and enjoy it but at this point I'm not sure how best to do that.

I mentioned in my previous posts how big of a headache the color distribution portion of the code is. I've been brainstorming other more reliable techniques I could use since I first coded it up. The other day, I hit on a much better solution and completely rewrote that chunk of code and I couldn't be happier with the results. The program runs more cleanly and reliably and the new setup allows for easier implementation of color restrictions based on more complex logic if necessary. Victory.

I'm pretty happy with the maps that the program is generating now. I think they're pretty close to where they need to be so I'm not sure how much I can continue to refine the code without more playtesting by a significantly larger group of people.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Fernando Robert Yu
Philippines
flag msg tools
badge
Avatar
mbmbmbmbmb
Make the theme about space shipping or something (ie instead of tunnels you have warp jumps) and the random generator makes more sense!!!
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
1 , 2  Next »   | 
Front Page | Welcome | Contact | Privacy Policy | Terms of Service | Advertise | Support BGG | Feeds RSS
Geekdo, BoardGameGeek, the Geekdo logo, and the BoardGameGeek logo are trademarks of BoardGameGeek, LLC.