I’m a moderately experienced self-taught Unity programmer, and I’m trying to learn how to recreate the gameplay of Scotland Yard - movement and pursuit across a map of nodes.
Adapting any turn-based boardgame could start with understanding/using a State Machine model. Play the game physically once or twice, taking notes on the kinds of decisions each player must make on their turn, and what kind of information the player can learn from other players’ moves which will inform those decisions.
As for A*, yes, any graph of nodes is a good starting point for a pursuit game like Scotland Yard. The only times a decision is relevant is at the junctions or nodes. If you want to figure out how to get from node 108 to 91, without touching 105, you just flag 105 as not “walkable” and ask the A* for the right path, and if it seems appropriate, take the first edge on that path.
I’m pretty good with state machines, push-down automata, etc. I think I can probably get a round-based system up and running.
My main issue is trying to work out the navigation. That’s a helpful point on getting A* to navigate appropriately across the environment… I guess I’m having most trouble working out how I get something that looks as adhoc as the London map, above, in a grid format…! I’m really failing to grasp that. =/
AStar is happy to take any graph. 
Just glancing over the rules it looks like there are multiple graphs in play: the taxi graph, which is every stop, and then the underground and bus lines, which are only a subset of the nodes connected.
If I were doing this, I would make a test board with six or eight stops on it, and add two graphs:
Now with two graphs in play, iterate until you get the “choose mode, move destination” main game loop going.
The AStar will only be used to find a good route or direction, returned as a list of traversed nodes. This is the standard “product” of AStar.
Once you know you’re going from A to B via a set of nodes, ASTar is out of the picture and you are just playing out preset waypoints, something you can easily do with a tweener like LeanTween or DOTween.
Looks like a fun problem to solve!
Man. I don’t even know where I’d start. Although, now that I’m typing… I guess I could just do a bunch of gameObjects with a Node monobehavior with an array list of neighbouring nodes that I could then just drag on in the inspector. Draw the edges with slightly offset gizmos you can see the difference between the taxi and bus edges…
Christ, at that point I dunno. When I’m looking this up, I tend to see people mentioning Monte Carlo Tree Search, so I guess I’ll read up on that, then back into A*.
sigh Honestly, I’d like to buy DOTween, but Unity won’t let me buy things in the Assetstore any more (complete mystery, I’m in good standing w/my bank and Paypal and I should be with Unity, but they just won’t let me purchase stuff. Very frustrating)
Thanks for the notes, folks. I’ll have a think…!
The asset store stopped working for me in 2017 and no amount of support emails back and forth ever got it working again. I used to dedicate $100/month to buying whatever asset I deemed was most interesting, but those days are long gone, unfortunately. And I am one of the biggest Unity tankies on the board! I would GLADLY restart doing this but every time I have tried, it just does not work, and I am using credit cards I use EVERY DAY for other things.
I reasoned that it might eventually get fixed, but apparently not. It’s absolutely incredible to behold. My only explanation is that the manager in charge of asset store sales must be completely unaware of what a mess it is.
Thankfully you can just get DOTween off github:
https://github.com/Demigiant/dotween
Try this: make the nodes and links as I suggested above, and then put a piece on one square, but only let that piece move to nodes that are linked to it when you click on those nodes.
That’s the hard part. Once that is running and reasonably data driven, then you can reason about where to go next, and begin to cause that “click next node” to come from something more complex like AStar, or even just a brute-force search if the board only has a few dozen / hundred squares.
Thanks Kurt! I’ll rub my brain all over those notes.
Christ. That’s so strange about the asset store thing. And really disheartening - it’s one thing for some yokel like me having problems with it, but, like you said man, I’ve seen you helping out here since forever.
Good grief. If I had an asset on their store I’d be really pissed off. =/
I’m super confused what you’re actually asking here. Not about the game, I know it very well and have played it as a child (I think my mum still has it). My issue here is: the game is a board game that requires multiple players. The minimum number of players is usually 3 because one is playing “mister X” and all the other players are playing detectives and try to catch him.
Your title is about “recreating the gameplay”. That means you would have 3 - 6 players which would play the game, just digitally. If that’s the case, there’s no need for A*. You “may” need a path finding algorithm if you want to create an AI for the game. However A* is just a path finding algorithm that gets you from A to B as cheap / fast as possible. I’m not sure how this would help here since you barely have a clear target that involves a larger distance. The game is played round by round.
So if this is about creating an AI, the next question is, which side? Both sides play quite differently and have to consider quite different things. So creating an AI for the detectives would require some sort of planing so here a path finding algorithm may come in handy. An AI for Mister X would usually be implemented without any long term goals (it would just evaluate the situation and tries to find the best move based on some criterion), an AI for the detectives would be quite tricky. They have to coordinate their moves.
So it would be great if you could say how you want to actually implement the gameplay:
Those are the 4 possible variants I could think of. Though this would only be the start. Each variant has countless other decisions how you may implement that variant, especially multiplayer.
That was about the “gameplay”. However your other posts seems to be more about how to realise the pure techincal basis of the game which is not really relevant for the gameplay. It’s not clear if you want to recreate the whole board (could cause copyright issues ^^) or just something similar. Note that even though the subway connections “follow” or “go though” other nodes, since they are not connected to those nodes they actually have nothing to do with those nodes. This is just a visual representation. Technically two nodes are connected by a subway line. That line could be represented with as many waypoints as you like. Maybe several bezier splines or what not. In the end from the pure logical point of view it’s still just a single connection, just like in the real world. When you take a train from station A to station B, there may be 10 bus stops on the streets above, however the train doesn’t really care, it goes from A to B, that’s it
Hi @Bunny83 - thanks for the input!
I brought up A* specifically as it’s the most experience I have with a node/graph-based system or navigation - I’ve followed a bunch of Sebastian Lague’s tutorials on the topic, up to the point where he vanished into the weeds on optimisation and I became super-confused.
My intention is to create something like Single Player Mr. X - I encountered something like it in the old Hal Barwood game ‘Mata Hari’, see here and here and investigating that led me to Scotland Yard. Mata Hari is obviously missing elements such as the imperfect information, the cards, deducing Mr. X’s position and alternate travel routes. As you state, there are countless other decisions on how to implement the singleplayer Mr. X variant.
I would not be recreating the board, I think! Ultimately, I’d like to generate a (hex?) map of nodes proceedurally, I think (though that seems quite challenging) with a set of points between each node to indicate distance/movement cost, so the player (Mr. X) would have to budget their funds etc. as they travelled.
The maps of Pathway might be a good visual reference (though the gameplay is obviously completely different):
…But that’s all far in the future. As you’ve also noted, I’m mostly stuck on sitting down and trying to get started with this damned thing, though I think Kurt Dekker has given me a good commencement point for my investigation, when I sit down and go to it. In the meantime, any advice or thoughts are appreciated.
For a starter you could just make a grid and set a few nodes in this grid then either change the square colors or draw lines between the nodes. Once it works you can make the grid invisible and put a well designed map on the top.
As for the asset store I use paypal and have no issues with it.
Those are two fairly different things. They are pretty large subjects, but in a nutshell:
A* is a search algorithm, basically runs through available options/states until it finds a solution. Many problems can be treated as a search problem, but most visually understandable is something like a maze. Like Kurt said, search algorithms don’t need a grid to function, but a 2D maze is a good visual starting point. Now, if you just started programming, you are likely to try and solve this by just walking in a direction until you hit a dead end and then back track to the next option. This is the depth first approach. Might work fine for some problems, but if the maze is very big and the exit is actually very near, you might spend most time looking at parts of the maze that are not really close to the solution. Depth first search visually:
https://www.youtube.com/watch?v=yXfwgmyNzGw
So, in comes breadth first searching, where you look in all directions at the same time. You do this by keeping track of all active states (positions in the maze) sorted by the cost needed (steps taken for a maze) to get to this state. And then you continuously expand the state with the lowest cost. The nice thing about this is that as soon as you hit the exit/solution, you can be sure that the chosen path is also the path with the lowest cost (shortest), so the best solution. (This is not the case with a depth first search.) So, initially you have your starting position as state with cost 0. Say you can go in two directions from there. Then after expanding that single state, you have two states with cost 1. If you continue like this the set of states will act like the front of a flood fill through the maze. Breadth first search visually:
https://www.youtube.com/watch?v=vf817b882Uw
Beyond breadth first there are various improvements. The most well known is probably A* because of it’s illustrious name maybe. It is very similar to plain breadth first, but instead of sorting only by cost, you sort by cost plus an estimated future cost to get to the target. This actively shapes the search area towards the intended goal. If this estimate is optimistic (meaning never more than the actual cost) the algorithm still has the guarantee that the first solution found is also the best solution. For things like a maze or navigation, the distance between the current position and the goal is a simple optimistic estimate for the future cost, you will never be able to get there faster than in a straight line. A* search visually:
https://www.youtube.com/watch?v=wnNQ_1RxWJA
Monte Carlo Tree Search can be applied to many things, but is commonly used for game playing. It does not guarantee any optimal solution like A*, instead it makes an estimate by using random sampling. The reason it is used is simply because the search space to find the optimal solution in for example chess, is simply too big. So once A* doesn’t do the job anymore because the search space is too big, you can switch to MCTS. What the algorithm does in a nutshell is to do a randomized depth first search. So, consider the maze again. You start walking left 1000 times and then randomly continue and you start walking right 1000 times and then randomly continue. Now on the left you have hit the exit 2 times and on the right 5 times. Then you decide to move right and use the same algorithm again for the next step. It does not guarantee that the exit is actually closer by on the right, but it allows you to get an estimate with a limited amount of computation.
@dlorre - Delighted to hear the Asset Store is working for you! Not totally sure what you mean by ‘change the square colours’ in this context, but thank you for the advice!
@jvo3dc - As I’ve stated, I’m moderately familiar with A*, minus the more complex optimisations. I’m also familiar with the pathfinding methods that lead up to A* - thank you for those great illustrations!
Especially thank you for the explanation of the Monte Carlo Tree Search. Hmm. That’s a great starting point for my research - cheers!
