The Tequila Den

Combines the world of Tequila with Games.

Finally got it…

At least, I think I do. I thought I had it all figured out before hand, but then a bug came out. A nasty little bastard that basically crippled the damn game.

Okay, that’s a bit extreme. The game is fine without it, but the problem was though you wouldn’t be credited with your feat unless you kept building and hopefully it picked the right set, sigh. Yup, longest road issues struck again.

I scoured the crap out of my code and found a slight oversight. My first “correct” stab at the process had all the roads tied together with it’s only possibility. Thus, if a player does place all 15 of their roads. The code would flip through each road and see if it can find it’s little soul-mate. So essentially what I thought I created was a set of road segments that could only go together. The problem was that once you see that particular set from the other end, it’s a cheating bastard. So what I thought I had wasn’t what I had at all. Re-write time.

I googled and lou-oogled (hot tub time machine, great movie,) around the web about how people have been implementing Catan’s longest road and really I have seen a lot of forum/blog posts about the situation. None of which I’ve been able to successfully implemented in Javascript. They did however spark my brain and come up with a valuable solution to the issue at hand. The biggest issue I had with the process was how do I loop through the same set of roads twice, without repeating myself and going through a loop I have no idea how to stop or how many times it’d have to iterate as the list of possibilities grew exponentially as the amount of roads were being added. God forbid the player built “trees” and “circles” out of their roads. Headaches ensued.

The solution to world hunger… err…. finding the Longest Road in Catan, pseudo-style.

Take all roads and toss them into an array by themselves.
//roads[x] = the entire chain, r1,r2,r3 ; roads[x][y] = road in roads[x] in pos. y, r1.

Keep track of the ends of each of these roads, represented by settlement spots (which I refer to as corners) in an array that correlates to the roads’ array.
//ends[x][y] = x is equal to the x in roads, y = is the ‘left’ & ‘right’ of the roads’ x.

Set maxMisses to the amount of roads and misses to zero, and make to false.
//this is the control to see if a new chain of roads were created.

while (misses < maxMisses) Loop through all of the player’s roads. Loop through all the chains that were made. If the current road in the loop isn’t in the current chain, proceed, Now, if the current road links to the current chain and it’s not already in that chain,
– Clone the current chain along with the ends of that chain.
– Add the current road to the cloned chain  and update the new ‘ends’ of the chain, add to the database of chains.
– set make to true. end the loop of the chains.

If the make is false, misses++, otherwise it’s set back to zero. end all loops… That will give you all the possible set of chains for the given player’s roads. It amounts to a bunch of roads, many of which are duplicate of themselves. This is because of the starting points of the roads; do remember that we clone each time we add a new road. They can easily be filtered out afterwards by seeing if the length is greater than 4 (Catan rules), you can eliminate more if you’ve stored the current longest road.

You can always comment / email me if you’ve got questions about my implementation or if you want to see some code. (Warning, I’m not a pro-scripter by any means and some stuff is kind of messy, and not exactly ‘efficient’.) Next time, how to see if the chain has been interrupted by an opposing settlement/city.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: