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.