Algorithm to check for legal moves in Cluedo boardgame

Question

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?

Answer 1

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.