Search Unity

  1. Unity 2019.2 is now released.
    Dismiss Notice

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

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

  1. Arookas

    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

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,832
    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
  3. Lka

    Lka

    Joined:
    Aug 6, 2006
    Posts:
    297
  4. rab236

    rab236

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

    tasadar

    Joined:
    Nov 23, 2010
    Posts:
    241
  6. Gamepulp

    Gamepulp

    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

    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

    Arookas

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

    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.
    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.