Recommend
 
 Thumb up
 Hide
13 Posts

BoardGameGeek» Forums » Board Game Design » Board Game Design

Subject: Programming help rss

Your Tags: Add tags
Popular Tags: [View All]
Bryan Thunkd
United States
Florence
MA
flag msg tools
badge
Avatar
mbmbmbmbmb
I'm not sure this is the correct forum, but I couldn't find a better one.

I’m trying to learn to program. I’m starting with Python. My ultimate goal is to create my own digital board game. I figure that doing it digitally will let me focus on how the game works and allow me to iterate and change things quickly. I want to design my own game, but I might try to implement an existing game just to learn how programming a game works.

My first challenge came up as I was playing Five Tribes recently. I noticed how players struggled to figure out if there was a move that would get them to particular tiles. They’d keep looking and relooking at different routes trying to figure out a legal move that would get them to the destination tile they wanted. As I was watching this I thought that it was probably trivial for a computer to calculate, but then got lost in trying to figure out how you’d program that.

Five Tribes Overview
The game is played on a 5 x 6 grid of tiles. The game starts with 3 meeples randomly assigned to each tile. On a player’s turn they pick a tile, take all the meeples there and then begin assigning them to tiles, following certain placement restrictions. The last tile they place a meeple on (the “destination tile”) triggers an effect.

Movement restrictions
The first meeple must be placed in a tile orthogonally adjacent to the tile they were picked up from. Subsequently each meeple must be placed on a tile that is orthogonally adjacent to the last tile a meeple was placed on. Additionally, you cannot immediately return to a tile. So in the grid below, you could not pick up three meeples from Tile A and place them B-C-B as that would be returning to B after you just came from there. However, if you picked up 5 meeples from A, it could be possible to place them B-C-F-E-B though. So you can return to a tile, just not immediately after leaving it.
__________________
| A | B | C |
|_____|_____|_____|
| D | E | F |
|_____|_____|_____|


Lastly, the final meeple you place on your destination tile must color match a meeple that is on that tile. So if you're placing a blue meeple as your last placement, there must be a blue meeple on the tile you're placing on. So you can't place your last meeple on an empty tile for example, as there's nothing to color match. However, note that as in the example above, you could end your turn on a destination tile that didn’t have a meeple on it at the beginning of your turn. You’d simply need to pick up a group of meeples that had two meeples of the same color, then loop them in a circle, making sure to drop one of the matching meeples on your final destination on the first time pass and placing the matching meeple on that tile as your last placement.



My challenge is that I want to make a program that you can feed in the initial meeple distribution, select a start square and it will return all the valid destination tiles you could reach. I’m trying to figure out how best to program this. I’m imagining a recursive situation where the program moves through every possible path.

So for example, it randomly picks a valid tile that connects to A, like B, then randomly picks a valid tile that connects to B, like C, etc. and continues until that path terminates as there are no more movement points (meeples). So in this example, A -> B -> C -> F

Then it jumps back to the last node and tries a different branch for the last leg. But in this example there’s no valid option from C as it only links to F and B and we came from B on the previous leg.

So it jumps back to B and tries a new leg (which must be E as we came from A and already did C. So it goes to E and then randomly tries a leg from there A -> B -> E -> F. As that’s 3 movement points it jumps back to E and tries another path, A -> B -> E -> D. As that’s also 3 movement points it jumps back to E, but there are no more valid paths to try, so it jumps back to B.

Then from B there’s no untried paths, so it jumps back to A and tries another path, going to D, etc.

The problem is I’m not sure how best to implement this programmatically. Any suggestions or ideas would be appreciated.

1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Brian Compter
United States
Foxboro
Massachusetts
flag msg tools
mbmbmbmbmb
OK then. You are taking quite a big bite if this is one of your first introductions to programming. Perhaps a bit more information on what you have done / can do in Python right now would give us more insight into how best to help you.

The problem you are learning about is something called graph traversal which can traditionally be done Breadth First or Depth First. If you are not familiar with those terms, head to wikipedia for some reading first and come back.

But again, for me (or anyone) to best help you, we need to know a bit more precisely what programming experience you are starting with.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Andrew Rowse
New Zealand
Wellington
flag msg tools
designer
badge
Avatar
mbmbmbmbmb
I only half-read the challenge, so this is a near-solution that can be generalised to get what you want...

foreach (otherTile)
{
if (otherTile has at least one meeple that matches destination)
{
distanceBetweenTiles = abs(otherTile.x-destination.x) + abs(othertile.y-destination.y)
numSurplusMeeples = otherTile.numMeeples - distanceBetweenTiles
if (numSurplusMeeples >= 0 && numsurplusMeeples % 2 == 0)
{
Hooray - this tile can be used to activate the target!
}
}
}


To get from one tile to another, the number of meeples needs to equal the number of spaces to move, or to exceed it by an even number, and the target tile and origin tile have to share a meeple colour. The pseudocode above can be used to loop through all other tiles to see which ones can connect to a destination. Rewriting it to instead find all possible destinations for a given start point would be trivial.



Edit - graph traversal is an interesting field, and if you wanted to do a really clever AI (that set up compelling board states by making sensible decisions about what routes to take and which meeples to place), you would need to delve into it. For this problem (which tiles connect to which other tiles), you don't need to get that complex.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Bryan Thunkd
United States
Florence
MA
flag msg tools
badge
Avatar
mbmbmbmbmb
I don't really know how to answer that. I mean, 30 years ago in high school I took a basic programming course. And since then I've mucked around with programming lanugages like Excel's visual basic, but purely on a self-taught trial and error basis. I have a pretty basic understanding of control structures and data structures. But I'm pretty much a beginner I guess.

1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Bryan Thunkd
United States
Florence
MA
flag msg tools
badge
Avatar
mbmbmbmbmb
KAndrw wrote:
To get from one tile to another, the number of meeples needs to equal the number of spaces to move, or to exceed it by an even number, and the target tile and origin tile have to share a meeple colour. The pseudocode above can be used to loop through all other tiles to see which ones can connect to a destination.
Hey, that's a smarter way to do it than I was thinking of. And this is why I asked the question rather than trying to muddle through it myself!

But I'm still curious about how to do the graph traversal.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeremy Lennert
United States
California
flag msg tools
designer
Avatar
mbmbmbmbmb
Thunkd wrote:
I’m trying to learn to program...I figure that doing it digitally will let me focus on how the game works and allow me to iterate and change things quickly.

This is generally incorrect; programming is usually much slower than paper prototypes. In fact, people do the opposite: video game designers often start by making a board game version of their planned video game, because it's faster, cheaper, and easier to change.

I already know how to program, and the primary reason I make board games is because it's much faster.



Thunkd wrote:
My challenge is that I want to make a program that you can feed in the initial meeple distribution, select a start square and it will return all the valid destination tiles you could reach.

That specific problem can be greatly simplified by application of mathematics.

The farthest you can go is, of course, the number of meeples you picked up. But on a square grid, the list of which tiles you can reach within that range (ignoring colors) is either "all of the odd ones" or "all of the even ones", whichever one matches the maximum, because you can always spend 3 movement to go 1 step by moving in a U shape, which lets you "waste" any multiple of 2. (Things get more complicated if you care about the path you take to get there, but if you're merely asking whether you can land on that destination or not, it's just parity.)

Then you just check whether there's at least 1 color in common between the start and the destination.

If you're contemplating recursion, though, then programming that is probably not much of a challenge for you. Instead, you probably want to ignore those simplifications and try to implement a naive depth-first search, which is a simple algorithm applicable to many problems.
6 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Josh Kotlowitz
South Africa
Cape Town
Western Cape
flag msg tools
mb
You might have better luck posting this on Stack Overflow in the Python section, but I'll give it my best shot.

The cleanest way to do this in a 'brute force' way would be with a recursive function. That is, a function that repeatedly calls itself until it runs into a dead end and then returns to the root. It would look something like this:

findPath (newTile, meeples, meepleCount, path = [], previousTile = 0):
adjacentTiles = findAdjacentTiles(newTile) //finds all adjacent tiles
for tile in adjacentTiles:
if tile != previousTile:
if meepleCount == 1: //if it is the last meeple to be placed
//some function that checks if any meeples' colour matches a meeple colour on the tile
//tiles should be an object containing a list of meeple objects
//one of the meeple colours should be "None", this helps keep track of meeples placed in your turn
//when this function finds a "None" meeple on a tile, it can then look to see if you have two meeples of the same
//colour in the meeples list
//the function should include this:"""
path.append(finalTile)
possiblePaths.append(path) //this adds the path list to the possiblePaths list
else:
return"""

else:
findPath(tile, meeples, meepleCount - 1, path.append(tile), newTile))


newTile = A
meeples = [meepleObjects()] //list of meepleObjects which just store meeple colour
possiblePaths = []
findPath(newTile, meeples, len(meeples)) //This should return a list of lists with all possible tiles
print possiblePaths

I've probably forgotten a few things and this could probably be done neater, but I hope it gives you an idea of what you need to aim for. This is definitely not the optimal code if you're wanting to minimize computing time, but I think it should take under a minute with a 5 x 6 grid.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Nathaniel Grisham

Indiana
msg tools
mb
Other folks have already replied to this effect, but recursion really isn't what you need in this situation.

You need to start by figuring out how you are going to represent your board state. (Most likely an array (one or two dimensions) with each element of the array representing a square on the board. Each of those objects will need to be able to represent all of the relevant information.

Before you try to think of what your algorithm looks like, you should also make sure that you have all of the requirements figured out. It looks like you have the rules down, but they are not always easy to translate into program logic. Sometimes you might have to break a rule into a few different pieces.

Also, you may want to track more than just possible end points, since the meeples you place on the way are available for opponents to use.

This is a big undertaking. You might be better off trying out a simpler game (tic/tac/toe, rock/paper/scissors, snakes and ladders) if this is your first big programming project. Once you have a feel for how much work it will really take, you can work your way up to something more complex, if you are still up for it.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Chris Robbins
United States
Alcoa
Tennessee
flag msg tools
Avatar
mbmbmbmbmb
I'm fairly certain I've mentioned it in another thread, but I used to program Mastermind or even Royale Mastermind whenever I had a major change in computers or operating systems. It's simple enough to know when you have it right, but is also an exercise in the logic and UI.

(I make it a solitaire game. You can play it many times alone to hone your deductive skills. And I never trust another player to not make a mistake with the solving indicators.)
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Bryan Thunkd
United States
Florence
MA
flag msg tools
badge
Avatar
mbmbmbmbmb
bltzlfsk wrote:
I'm fairly certain I've mentioned it in another thread, but I used to program Mastermind or even Royale Mastermind whenever I had a major change in computers or operating systems. It's simple enough to know when you have it right, but is also an exercise in the logic and UI.
I thought this was a good idea. So I made a program for mastermind. It's text only, as I have no idea how do do anything graphically yet. And it's likely that there are better ways to implement some of the things I did, but it works. So I guess that's a good first step.

Any suggestions for next steps?
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Chris Robbins
United States
Alcoa
Tennessee
flag msg tools
Avatar
mbmbmbmbmb
Thunkd wrote:
bltzlfsk wrote:
I'm fairly certain I've mentioned it in another thread, but I used to program Mastermind or even Royale Mastermind whenever I had a major change in computers or operating systems. It's simple enough to know when you have it right, but is also an exercise in the logic and UI.
I thought this was a good idea. So I made a program for mastermind. It's text only, as I have no idea how do do anything graphically yet. And it's likely that there are better ways to implement some of the things I did, but it works. So I guess that's a good first step.

Any suggestions for next steps?


I always started with the rows of circles or other needed shapes. This includes a well defined center of any object and how to change the color. Then I added in my logic memories. Even Tic-tac-toe needs a structure on screen. Then it's down to a 3x3 array of states, and checking for victory conditions. A worthy AI or online opponent option should be a later stage of development. At least in my workflow.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Chris Robbins
United States
Alcoa
Tennessee
flag msg tools
Avatar
mbmbmbmbmb
And as ideas keep flooding back, you should master the use of the arrow keys (or W-A-S-D) and mouse inputs/outputs to get away from text only.

Dang. Page Up, Page Down, Home, End. There are a lot of considerations now.

"Bullet proof" as it applies to users screwing up while using your program is still a thing.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Leif Carlsen
United States
Kennewick
Washington
flag msg tools
Illegitimi Non Carborundum
badge
Tri-City Area Gaming
Avatar
mbmbmbmb
Thunkd wrote:
Any suggestions for next steps?

Project Euler has a great set of programming exercises if you're also up for some math.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
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.