Board Game Theory: Find all possible destination spaces after dice roll

News & General Discussion
1

Hello, I’m trying to make a digital Clue(do) in Unity for fun, and is, for the most part, going well. A hump in the planning of the game, however, is how to control the suspect pawn. I’d like to make it where you would just click to go to the desired tile (i.e. no keyboard interaction). A perfect example of my goal is the movement in the “Clue Classic” game: after the dice roll, all the possible squares you can go to are highlighted. If you hover over one of these squares, the path the suspect token would take is shown with simple arrow graphics tracing the path. Clicking the tile would make the suspect token follow the path made by the arrow.

The tricky part is path finding. In Clue(do), the same square may not be traversed twice on the same turn, nor can a fellow suspect token be passed over. You also have to move as many tiles as the dice rolled, unless you go through a door. While I think I know how to get which tiles are possible to go to, being able to show the path (and the suspect token follow the path) to that tile is my dilemma.

Any ideas and suggestions on how to find all possible tiles the player can reach after a dice roll in a Clue(do) board and to create a path to that tile would be heavily appreciated!

2

The distance to be travelled is fairly small? If so I’d just brute force it - storing all valid paths in a list.

3

I’d use a flood fill algorithm like this one
http://www.micromouseinfo.com/introduction/floodfill/

4

Couldn’t this be worked out with use of the A* algorithm?

5

http://en.wikipedia.org/wiki/Dijkstra’s_algorithm

6

+1
Here you don’t need real time check for mass entities, don’t bother with a A*, a simple recursive lookup of the adjacent tiles will work just fine while taking far less time.

7

Yes a normal bread first search with an end test works. If you use Boo you can pass in a lambda that is an end test to a search function.
Some tips to handle performance.

  1. Cache everything you need at startup, you don’t want to do things like GetComponent and Find in the search loop.
  2. Make sure you code so that you check all paths. One path may branch out to a tile already discoverd, then you should not quit the search for that branch.
8

Thanks much everyone for the help so far; I’ll try these out! Happy holidays!

9

I agree, brute force is probably the best choice.
I’d suggest the following additional optomizations (they’ll hugely boost the performence)

  • don’t make it recursive in a literal sense: dont’ use method calls at all. Just use loops. If this requires a visually hugly indentation of ten or more for/while loops, the visual and coding pain is a worthy price to pay for the huge performance gain. The price of context switching in a recursive method is too high a price to pay.
  • possibly avoid any use of branching. No “if” should be used unless stricly necessary. Whenever you may add to a number, multiply for a 0/1 number or whatever is just mathematical stuff instead of branching, choose the mathematical option, even if it requires some study and fantasy.
    Arrays (even multidimensional) of 0/1 integers may help you.
  • don’t instantiate anything inside the algorithm. Make it before starting it, outside of the loops. Even if you have to instantiate bigger to be sure to have enought room, that’ll be a huge performance gain. Instantiating inside the loop will kill your caching and performance will suffer.

If you follow these rules, a brute force may very very efficient and win v.s. advanced systems which try to lower the number of possible choices, but make it at the expense of branching, runtime instantiations and recursion.