7
\$\begingroup\$

I'm coding a digital version of the Macao board game which has a flat map similar to below. Players have a "ship" which starts in the blue box and can follow the dashed lines in any direction/orientation. The larger rectangles represent city locations.

I'm stuck in the following issues.

  1. How do I record the position of each ship? I'm thinking co-ordinates like X,Y but that doesn't tell me the segment its on

  2. How do I construct the route paths as objects? Do I put them in an array?

  3. Finally; in order to measure distance between 1 rectangle and another, it will need to count how many segments there are to ascertain the shortest distance. I believe this can be resolved via a simple path algorithm.

I've not created a map like this before in a project but would welcome any help on how to move this forward.

map concept

\$\endgroup\$
  • \$\begingroup\$ Seeing the confusion brought by my answer, you could edit your question and specify if the spaces between the dashes are spots where ships can stop and stay, or if they are only routes and ships must stop and stay only in cities :) \$\endgroup\$ – Vaillancourt Jul 7 '15 at 22:00
  • \$\begingroup\$ The dashes represent the only legal spots where ships can stop/stay.They also act as legal routes. The cities also count. A sailing ship will need to physically land at the desired city. Ignore the spaces. \$\endgroup\$ – Atilla Jax Jul 8 '15 at 15:31
8
\$\begingroup\$

I would suggest you start by building a node graph (a bunch of nodes and arcs (sometimes called edges)).

  • The nodes are the cities and "dash" intersection
  • The arcs link cities and "dash" intersection

Then all these nodes have info like their 'physical' location (x/y coordinates on the map).

To solve your issues:

  1. you use the position that are set in the nodes to infer the location and the orientation.
  2. this will depend on the implementation of your node graph.
  3. use a path-finding algorithm like A* to find the best route between your current location and the destination. Your graph, again, will be used for that.

This should help you to get started.

Edit

The produced node graph could look like this:

The produced node graph

Of course, the arcs depicted in the picture would be the arcs linking the nodes in the graph.

Now, from the question it is not clear if the intersection nodes are spots where the ships could stay, but as it is designed as a board game, I assumed that if there is more than one dash between two cities, it is because it costs more to travel from one city to another (for instance you need a 2 on a dice instead of just 1). With this in mind, I assumed that a ship could stay on these spots (but not on arcs).

If it is not the case, however, the intersection nodes could still be used for navigation purpose between cities. This would give squarish ship tracks, however, so perhaps another approach should be taken for that. For instance: edges could contain data describing how they should be travelled (spline, series of dots, etc.).

\$\endgroup\$
  • \$\begingroup\$ The image OP posted isn't well represented by a node graph. Since there's an intersection of edges without a node (on the right). \$\endgroup\$ – MichaelHouse Jul 7 '15 at 17:32
  • \$\begingroup\$ You can have 2 types of nodes: city nodes and intersection nodes. I assume they are spots where the ship can stay after the players turn, and that a ship can only travel through arcs and not stay on them. Let's see if I can add an image. \$\endgroup\$ – Vaillancourt Jul 7 '15 at 17:41
  • \$\begingroup\$ @Byte56 I've added a bit more details on what I though, maybe it's more clear now! \$\endgroup\$ – Vaillancourt Jul 7 '15 at 18:10
  • 2
    \$\begingroup\$ Ah, this solution is way clearer with the image. +1 for the mad Photoshop skills (and for the good answer). \$\endgroup\$ – Alexandre Desbiens Jul 7 '15 at 18:14
  • \$\begingroup\$ Yes, this my fault, I didn't want to post an actual image for copyright reasons so did a very quick interpretation of it. \$\endgroup\$ – Atilla Jax Jul 8 '15 at 15:32
1
\$\begingroup\$

Alexandre gave a good answer. I thought I'd take a stab at a concrete example.

The example is is C#, but hopefully it is general enough to be implemented in any language you choose to use.

using System;
using System.Collections.Generic;

public class SimpleGraph
{
    private int _numberOfCities;
    private int[] _paths;


    public SimpleGraph()
    {
        _numberOfCities = 9;
        _paths = new int[_numberOfCities * (_numberOfCities + 1) / 2];

        AddPath(0, 2, 1);
        AddPath(0, 3, 2);
        AddPath(3, 4, 2);
        AddPath(3, 5, 1);
        AddPath(3, 2, 1);
        AddPath(2, 1, 1);
        AddPath(2, 6, 1);
        AddPath(5, 6, 1);
        AddPath(6, 7, 1);
        AddPath(5, 7, 1);
        AddPath(6, 8, 5);
        AddPath(7, 8, 5);
        AddPath(1, 8, 6);
    }


    public void AddPath(int cityA, int cityB, int distance)
    {
        int pathIndex = getPathIndex(cityA, cityB);
        if (pathIndex < 0 || _paths.Length <= pathIndex) return;

        _paths[pathIndex] = distance;
    }


    public void RemovePath(int cityA, int cityB)
    {
        AddPath(cityA, cityB, 0);
    }


    public int GetPathDistance(int cityA, int cityB)
    {
        int pathIndex = getPathIndex(cityA, cityB);
        if (pathIndex < 0 || _paths.Length <= pathIndex) return 0;

        return _paths[pathIndex];
    }


    public bool HasPath(int cityA, int cityB)
    {
        return GetPathDistance(cityA, cityB) > 0;
    }


    public List<int> GetAvailableCities(int currentCity)
    {
        var result = new List<int>();

        for (int i = 0; i < _numberOfCities; i++)
        {
            if (HasPath(currentCity, i)) result.Add(i);
        }

        return result;
    }


    private int getPathIndex(int cityA, int cityB)
    {
        if (cityA == cityB) return -1;

        int small, big;

        if (cityA < cityB)
        {
            small = cityA;
            big = cityB;
        }
        else
        {
            small = cityB;
            big = cityA;
        }

        return (big * (big - 1) / 2) + small;
    }
}

This is a graph representation of your map if you number the cities in the following way: Numbered Cities

Then, all you would need to do is keep track of an integer from 0 to 9 which is the current location of your ship and use the methods to find your way around.

\$\endgroup\$
  • \$\begingroup\$ The segments are steps though. Although I appreciate the help. A ship cannot jump from 8-7 without going on the 5 segmented steps (black lines) \$\endgroup\$ – Atilla Jax Jul 8 '15 at 15:33
  • \$\begingroup\$ In that case, you can still use the provided class, but there will be nodes which are not cities and nodes which are. \$\endgroup\$ – PatrickSharbaugh Jul 8 '15 at 15:51

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.