2

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

Visual example of what I'm meaning

Anyone have an idea to solve this?

  • 2
    I approve your use of mspaint and red lines. – MetaFight Oct 29 '16 at 14:25
  • 1
    lol, it's not looking very pretty but it does the job right ;) – JC97 Oct 29 '16 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. – Arthur Havlicek Oct 29 '16 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 '16 at 14:35
  • 2
    Welcome to Software Engineering! – Dan Pichelman Oct 29 '16 at 14:59
6

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. – Dan Pichelman Oct 29 '16 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.