# Algorithm to check for legal moves in Cluedo boardgame

I'm making a Clue(do) board game in Java to improve my programming skills. I've done a lot of work so far, but now I'm stuck at finding an algorithm to make sure if a player can make a certain move.

Quick draw of how it's organised:

• Superclass GameTile
• Subclasses for each roomtype (RoomTile, DefaultTile, StartTile & OutsideTile)

The goal is to show the players all the possible moves a player can do when he throws the dice. I have found a way to look "around" the player to see which tiles it can reach, but the problem to see if a player can enter the room through a door (or if the player can reach that default tile), remains.

All squares you can see are presenting one of the classes previously mentioned:

• Black: outside
• white/pink: default
• lightblue: rooms (doors are inside the roomclass flagged with boolean, no visual representation yet)
• colored: start tiles

Anyone have an idea to solve this?

• I approve your use of mspaint and red lines. Oct 29, 2016 at 14:25
• lol, it's not looking very pretty but it does the job right ;)
– JC97
Oct 29, 2016 at 14:30
• You have all the data you need no ? Just allow any movement to door-flagged tiles and forbid otherwise exterior/interior movement ? Then you just have to make the pathfinding correct. Oct 29, 2016 at 14:32
• Yeah I know the ultimate target tiles, but I don't have a path really. Any idea how I could get all tiles that are between the token and the targettile? I'm thinking about this for days.
– JC97
Oct 29, 2016 at 14:35
• Welcome to Software Engineering! Oct 29, 2016 at 14:59

The problem you have is you are trying to use the destination square to determine the path the player should take to reach it, but it's actually not how you do a path-finding algorithm. There is a lot of ways to do this depending of how you want to optimise your stuff, but here is a simple algorithm which suits your need for a tile-based game.

1. Flag all your board except player position as unreachable from the player position.
2. Based on the dice score, start an exploration. You start a search with depth X, X being the score of your dice. Each step consist of:
• If depth is exceeded, return and do nothing
• For all adjacent tiles, check if the move is legal and not already tagged reachable. If it is, tag as reachable and schedule an exploration call with depth - 1.

There is a pitfall though, it's that you need to iterate in a breadth-first fashion, not depth-first.

Ultimately you will have your board tagged with all the reachable tiles from your position with a given dice score. You can highlight them. Player can click one and teleport there. In a first version, no need to build path :)

In case you do want to build the path for displaying it or something, then during your exploration you tag each tile with the previous tile (the one that discovered it). Then, when you hover a tile, you build the list of tiles that led there.

• BFS is definitely the way to find all the legal destinations for a given die roll. Once a destination has been selected, A* or Dijkstra's algorithm can find the shortest path to it. Oct 29, 2016 at 14:57