Movement algorithm for Pocket Civ game

I am developing a Pocket Civ game engine. (You can check the process at www.pocketciv.com). Basically there is maximum of 8 Areas (round nodes in the pic) that have Tribes (number inside the node). So area 3 has three tribes and area 5 has two tribes.

There is basic movement rules see page 7 and then the movement rules change after new advances are acquired. There is only one movement phase and you can move the tribes in any order you want.

• Basic: A single tribe can cross a border once (by land)
• Advancement: You can move a stack of tribes across the sea at the cost of 1 tribe (so every tribe in the stack then crosses a border)
• Advancement: A single tribe can cross a border two times
• Advancement: A single tribe can cross any number of borders (crossing the sea still costs one tribe)
• Advancement: When you move the stack across the sea, it doesn't cost anything

Essentially, if you have the last two advancements you can move any tribes anywhere you like.

The naive way to implement this would be to track what tribes are moved where when user moves them. But this is hard for the user (for example if you move one tribe 3->5 and one tribe 5->3 you have not moved anything. My approach is to let the user move tribes around and always check if the given situation is valid. For example valid end situations from above starting point are (shown as list [area1, area2, area3, area4, area5]:

• [0, 0, 3, 0, 2] (no movement at all, also the starting point)
• [0, 0, 3, 1, 1] (5 -> 4)
• [0, 0, 0, 5, 0] (5 -> 4, 3 -> 4)
• [0, 0, 5, 0, 0] (5 -> 3)
• [0, 0, 2, 2, 1] (5 -> 4, 3 -> 4)
• ... etc

I have implemented some kind of way to check if the proposed situation is valid. It gets hard when we take the sea movement cost into account. We would need to know what is the cheapest way to make the movement and recognize when tribes moved over the sea. For this I would need all the permutations about what tribes moved where.

For example if we have starting position: [0, 0, 3, 2, 0]

• [3, 0, 2, 0, 0] (3 -s> 1, 4 -> 3) would cost 1 tribe at minimum
• [2, 2, 1, 0, 0] (3 -s> 1, 3 -s> 2) would cost 2 tribes at minimum

Can anyone help me phrase this problem or say what would be the correct algorithm to find that the proposed situation is valid and what is the minimum cost. Is this a graph problem? Can this be solved with matrices? I have studied Prolog a little but haven't managed to get anything usable out of it. I can tell my implementation later but I would like a "clean-table" view of this problem.

• This is definitely a graph problem, I'm unclear on your movement rules. In the game you cited, units move one at a time. It looks like you want to move multiple tribes in the same movement. Does the stack have the same movement points as the tribe with the least amount of movement points? Or when you try to move does it only move tribes with movement points left? For example, what if I was in the third advancement (tribes can move twice) and I move all of the tribes from 5 to 3. Now I want to move the tribes in 3. Can I move them one time? Twice? – UristMcSparks Jan 14 '16 at 18:50
• The movement rules are in the Pocket Civ rules: backglass.org/scotts/games/PocketCiv/files/pocketciv_ver2.0.pdf page 7. So you can think that you have (for example) 5 tribe tokens (the illustrated example). If you have no advancements acquired, every token can cross one border (not overseas). If you have the third advancement, every token can cross two borders. The advancements just change the limitations of the basic movement rule. When you move the tribes as a stack (only relevant when crossing the sea), every token in the stack must have not yet crossed maximum amount of borders. – Juho Rutila Jan 15 '16 at 12:19
• That document still doesn't specify what happens if stacks combine. Or do they not combine until all tribes have moved? I again will cite my example with a little more detail. Let's say the map you drew above is the current game state. I have the first two advancements (move twice, cross water). I move all my tribes from Area 5 to Area 3. Does that mean I now get to move all 5 of my tribes from Area 3 to Area1 as one stack? If so, will I have 4 tribes when I get there? – UristMcSparks Jan 15 '16 at 17:47
• The document indeed does not specify. But yes you can move all 5 tribes 3->1. After that you have 4 tribes in area 1 and you can move three of them (originally from area 3) to area 2 (or some other area behind area 1). The one remaining tribe has already crossed two borders and one (orig. from area 5) was lost due to crossing cost. – Juho Rutila Jan 16 '16 at 5:29