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

Discussion in 'General Discussion' started by Arookas, Dec 25, 2012.

1. ### Arookas

Joined:
Aug 17, 2012
Posts:
2
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. ### npsf3000

Joined:
Sep 19, 2010
Posts:
3,830
The distance to be travelled is fairly small? If so I'd just brute force it - storing all valid paths in a list.

Last edited: Dec 25, 2012

Joined:
Aug 6, 2006
Posts:
297
4. ### UnknownProfile

Joined:
Jan 17, 2009
Posts:
2,311
Couldn't this be worked out with use of the A* algorithm?

Joined:
Nov 23, 2010
Posts:
268
6. ### Pulpsoft

Joined:
Jul 5, 2012
Posts:
11
+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. ### Sirex

Joined:
Feb 7, 2011
Posts:
77
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. ### Arookas

Joined:
Aug 17, 2012
Posts:
2
Thanks much everyone for the help so far; I'll try these out! Happy holidays!

9. ### Steiba

Joined:
Dec 26, 2012
Posts:
3
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.