Algorithm Trax Winning Condition

Question

I tried to implement the game Trax in C++. For those who do not know: http://www.traxgame.com/about_rules.php

I have built the board so far and created the rules where I can put my next Tile and which one I am allowed to set. But now, I am struggling with the winning conditions. As you can see, I need a line of at least 8 tiles..

My first solution attempt had included way to many if-conditions. That is simply not possible. So i need to implement a proper algorithm..

My secong attempt using a bitboard is getting atm quite complicated, so my question would be if there is an easier way, I am simply missing at the moment.

Greets, MC

A tile is having a color (red or white) and a Type (cross, curve1, curve2). There is a simple 2d Array, where i set dependent numbers if a tile is placed and saved in a vector. — MrCotton, Apr 20 '15 at 23:06
You can use recursion or loop for check win condition. From every tile try to go to another tile (by rules) and for every step check whether tile was visited (loop condition) or whether tiles form lite of length 8. — gomons, Apr 20 '15 at 23:13
Tile of type `curve1` or `curve2` can be rotated in different directions? Or you just enumerate only 3 types from all possible? — gomons, Apr 20 '15 at 23:21
I just have 6 types of tiles. Cross, curve1 and curve2. Each either red or white. — MrCotton, Apr 20 '15 at 23:22
As I understand, you should have 2 types of tile: cross and curve. cross tile can be placed in 2 directions, and curve tile can be places in 4 directions. May be I misunderstood something. — gomons, Apr 20 '15 at 23:28
These are the tiles i am using: http://de.tinypic.com/view.php?pic=zkn6fr&s=8#.VTWNLyHtlBc cross, white, cross red curve1 white etc.. — MrCotton, Apr 20 '15 at 23:35
In fact, you use 2 tile types, first 2 tiles are equal, and 4 last are equal too. The difference only in what direction pipes rotated. — gomons, Apr 20 '15 at 23:50

score 0 · Answer 1 · answered Apr 20 '15 at 23:47

0

I can propose you to use recursion. I can misunderstand your, but anyway:

bool isWin(int i, int j, int length) {
    if (length >= 8)
        return true;

    if (canMoveTo(i + 1, j)) {
        if (isWin(i + 1, j, length + 1))
            return true;
    }
    if (canMoveTo(i - 1, j)) {
        if (isWin(i - 1, j, length + 1))
            return true;
    }
    if (canMoveTo(i, j + 1)) {
        if (isWin(i, j + 1, length + 1))
            return true;
    }    
    if (canMoveTo(i, j - 1)) {
        if (isWin(i, j - 1, length + 1))
            return true;
    }      
    return false;
}

bool isWin(int i, int j) {
    int length = 0;
    isWin(i, j, length);
}

..

main() {
    for (int i = 0; i < HEIGHT; ++i) {
        for (int j = 0; j < WIDTH; ++j) {
            if (isTilePresent(i, j)) {
                if (isWin(i, j)) {
                    if (isRed(i, j))
                        std::cout << "Red is won!" << std::endl;
                    else
                        std::cout << "White is won!" << std::endl;
                }
            }
        }
    }
}

answered Apr 20 '15 at 23:47

gomons

1,946
14
25

How would you check in which direction the loop is goin? it doesnt fit for all paths..? if the tile is set i check it only in one direction. But if there are several tiles spreading from the one i check it does not work, – MrCotton Apr 21 '15 at 17:42
Recursion checks every direction. Function `canMoveTo(i + 1, j)` should return true if you can get from tile `i, j` to tile `i + 1, j`. The code not tested, it is kind of pseudo code and illustrate only an idea. – gomons Apr 21 '15 at 17:49
There might be a bug, because if i go case 1 with i+1 and call the recursion, i could also go case 2 with i - 1 and would end in an endless loop.. – MrCotton Apr 22 '15 at 23:00
Ok, canMoveTo() can return false for already visited tiles, or after canMoveTo() we can add condotion notVisited() – gomons Apr 23 '15 at 08:42

Spektre · Answer 2 · 2017-09-05T06:49:15.050

For this kind of game stuff To make things easy I would add a small bitmap to tile representation

create tile maps

smallest resolution able to represent all tiles like this

I think may be also 3x3 resolution will be doable. You need 4 colors:
- Gray - wall
- Red - path plr1
- White - path plr2
- Magenta - path plr1,plr2
after each turn

create board bitmap from tiles bitmaps and use A* start with last edited tile (and may be also 4 neighbors) and do path for each player/path start point (Yellow). When A* is done then analyze the map data (orange) so find the biggest number in map (green mid point). It is point where A* filling stops (no need to searching for it). Then reconstruct shortest path back to start point (brown) setting used map points as unusable. Then try to reconstruct path again if you can then closed loop is present
while reconstructing path

compute bounding box of used points so you will need min,max x,y coordinates x0,x1,y0,y1 (in tiles). From this if loop found you know:
```
columns = x1-x0+1
rows = y1-y0+1
```
so the win condition is just single if from this

Hope this helps, I developed this technique for closed loop path finding/counting in my Carcassonne game

can you explain how you would do this for a program like mine? — MrCotton, Apr 21 '15 at 17:43
@MrCotton you did not provide any info about your program so NO I cant be more specific then this for now Because I would just guessing how your tile structure looks like, how you access it and so on ... provide more specifics first — Spektre, Apr 21 '15 at 22:34

Algorithm Trax Winning Condition

2 Answers2

Linked