5
\$\begingroup\$

What I want to do is build a Slay-the-Spire-like Map. As you can see in the following image, the map is splitted in ISteps and IRooms. Each IStep is connected to the next one by its IRooms. There is no dead-end, so each IRooms is connected with the previous and next ISteps.

Slay the Spire - Generated map

Firstly, I have these two C# interfaces:

public interface IStep
{
    IRoom this[int index] { get; }
    int Size { get; }
    void Connect(IStep nextStep, int[,] matrix);
}

public interface IRoom
{
    IRoom[] NextRooms { get; }
    void Connect(IRoom nextRoom);
}

Here is what I want to achieve:

  • A IStep has a set of 3-to-5 IRooms.
  • I can connect two ISteps together, which connects the IRooms.
  • Each IRoom has at least one connection to the other IStep ...
  • ... and at most three
  • Connections cannot cross, but can begin from / end to the same IRoom

Here is what is true:

  • The minimum number of connections is equal to the larger IStep.Size
  • The maximum number is equal to both IStep.Size minus 1
  • Each row and each column has to contains at least one 1

I decided to represent these connections in a matrix-like display:
\begin{bmatrix} 1 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 1\\ 0 & 0 & 0 & 0 & 1 \end{bmatrix} This matrix says:

  • IStep from is connected to IStep to
  • from.Size = 3 and to.Size = 5
  • There is a total of 6 connections
  • from[0] is connected to to[0]
  • from[0] is also connected to to[1]
  • ...
  • from[2] is connected to to[4]

To create this matrix, I use the following F# module:

type CellType =
| Uncertain
| Disconnected
| Connected

module Connector2D =

    let getAt array row col = Array2D.get array row col
    let setAt array row col value = Array2D.set array row col value

    let len1 array = Array2D.length1 array
    let len2 array = Array2D.length2 array

    let IsUncertain array row col = getAt array row col = Uncertain

    let IsDisconnected array row col = getAt array row col = Disconnected

    let IsConnected array row col = getAt array row col = Connected

    let filterBy predicate array =
        seq {   for i  in 0 .. len1 array - 1 do
                    for j in 0 .. len2 array - 1 do
                        if predicate array i j then
                            yield (i, j)
            }

    let ListUncertain array = array |> filterBy IsUncertain

    let ListDisconnected array = array |> filterBy IsDisconnected

    let ListConnected array = array |> filterBy IsConnected


    let CountUncertain array = ListUncertain array |> Seq.length

    let CountDisconnection array = ListDisconnected array |> Seq.length

    let CountConnection array = ListConnected array |> Seq.length

    let Disconnect array row col =
        match getAt array row col with
        | Uncertain -> 
            setAt array row col Disconnected
            true
        | Connected -> false
        | Disconnected -> true

    // Check no-cross rule
    let Connect array row col =
        if IsUncertain array row col then
            setAt array row col Connected
            // Disconnect all 'top-right' connections
            for i in 0 .. row - 1 do
                for j in col + 1 .. len2 array - 1 do
                    Disconnect array i j |> ignore
            // Disconnect all 'bottom-left' connections
            for i in row + 1 .. len1 array - 1 do
                for j in 0 .. col - 1 do
                    Disconnect array i j |> ignore
        IsConnected array row col

    // Check no-more-than-three rule
    let Create rows cols =
        let matrix = Array2D.create rows cols Uncertain
        Connect matrix 0 0 |> ignore
        Connect matrix (rows - 1) (cols - 1) |> ignore
        for i in 3 .. rows - 1 do
            Disconnect matrix i 0 |> ignore
        for i in 0 .. rows - 4 do
            Disconnect matrix i (cols - 1) |> ignore
        for j in 3 .. cols - 1 do
            Disconnect matrix 0 j |> ignore
        for j in 0 .. cols - 4 do
            Disconnect matrix (rows - 1) j |> ignore
        matrix

And my matrix creation method is this one:

public void Connect(IStep from, IStep to)
{
    Random rnd = new Random();
    int min = Math.Max(from.Size, to.Size);
    int max = from.Size + to.Size;
    int count = rnd.Next(min, max);

    int[,] matrix = MapConnections.Create(from.Size, to.Size);
    List<int> emptyRows = Enumerable.Range(1, from.Size - 2).ToList();
    List<int> emptyCols = Enumerable.Range(1, to.Size - 2).ToList();
    while (MapConnections.CountConnection(matrix) < count)
    {
        var possibleConnections = MapConnections.ListUncertain(matrix).ToList();

        var tmp = possibleConnections.Where(pc => emptyRows.Contains(pc.Item1) && emptyCols.Contains(pc.Item2)).ToList();
        if (tmp.Count == 0)
            tmp = possibleConnections.Where(pc => emptyRows.Contains(pc.Item1) || emptyCols.Contains(pc.Item2)).ToList();
        if (tmp.Count != 0)
            possibleConnections = tmp;

        var connection = possibleConnections[rnd.Next(possibleConnections.Count)];
        MapConnections.Connect(matrix, connection.Item1, connection.Item2);
        emptyRows.Remove(connection.Item1);
        emptyCols.Remove(connection.Item2);
    }

    from.Connect(to, matrix);
}

An example of what my algorithm should do is (for 5 connections goal):

\begin{bmatrix} 1 & - & - & 0\\ - & - & - & -\\ - & - & - & -\\ 0 & - & - & 1 \end{bmatrix} \begin{bmatrix} 1 & - & - & 0\\ - & - & 1 & -\\ 0 & 0 & - & -\\ 0 & 0 & - & 1 \end{bmatrix} \begin{bmatrix} 1 & - & - & 0\\ - & - & 1 & -\\ 0 & 0 & - & 1\\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & - & 0 & 0\\ - & 1 & 1 & -\\ 0 & 0 & - & 1\\ 0 & 0 & 0 & 1 \end{bmatrix}


My actual problem is that I can encounter this scenario (for 4 connections goal):

\begin{bmatrix} 1 & - & - & 0\\ - & - & - & -\\ - & - & - & -\\ 0 & - & - & 1 \end{bmatrix} \begin{bmatrix} 1 & - & - & 0\\ - & - & 1 & -\\ 0 & 0 & - & -\\ 0 & 0 & - & 1 \end{bmatrix} \begin{bmatrix} 1 & - & - & 0\\ - & - & 1 & -\\ 0 & 0 & - & 1\\ 0 & 0 & 0 & 1 \end{bmatrix}

Finally, nothing is connected to my to[1]. For this very example, I could force the ones to be in the diagonal, but I want to achieve is a generic algorithm, not a case-by-case one.


If you wonder, there are all the bad selections for a first-connection, in every case (apply symmetry):

  • For 4 connections: \begin{bmatrix} 1 & - & - & 0\\ - & - & * & -\\ - & * & - & -\\ 0 & - & - & 1 \end{bmatrix}

  • For 5 connections: \begin{bmatrix} 1 & - & - & 0\\ - & - & * & 0\\ - & - & - & -\\ 0 & * & - & -\\ 0 & - & - & 1 \end{bmatrix} \begin{bmatrix} 1 & - & - & 0 & 0\\ - & - & * & * & 0\\ - & * & - & * & -\\ 0 & * & * & - & -\\ 0 & 0 & - & - & 1 \end{bmatrix}

  • For 6 connections: \begin{bmatrix} 1 & - & - & 0 & 0\\ - & - & - & * & 0\\ - & - & - & - & -\\ 0 & * & - & - & -\\ 0 & 0 & - & - & 1 \end{bmatrix}


As asked, here are my classes and tests:

public class Step : IStep
{
    private IRoom[] Rooms { get; set; }
    public IRoom this[int index] { get { return Rooms[index]; } }
    public int Size { get { return Rooms.Length; } }

    public Step(IRoom first, IEnumerable<IRoom> rooms) : this(first, rooms.ToArray())
    { }
    public Step(IRoom first, params IRoom[] rooms)
    { Rooms = new IRoom[] { first }.Concat(rooms).ToArray(); }

    public void Connect(IStep nextStep, int[,] matrix)
    {
        for (int i = 0; i < Size; i++)
            for (int j = 0; j < nextStep.Size; j++)
                if (MapConnections.IsConnected(matrix, i, j))
                    this[i].Connect(nextStep[j]);
    }
}

public /*abstract*/ class Room : IRoom
{
    public IRoom[] NextRooms { get; private set; }

    public void Connect(IRoom nextRoom)
    {
        if (NextRooms == null)
            NextRooms = new[] { nextRoom };
        else
            NextRooms = NextRooms.Concat(new[] { nextRoom }).ToArray();
    }
}

public interface IStepConnector
{
    void Connect(IStep from, IStep to);
}

public class StepConnector : IStepConnector
{
    public void Connect(IStep from, IStep to)
    {
        Random rnd = new Random();
        int min = Math.Max(from.Size, to.Size);
        int max = from.Size + to.Size;
        int count = rnd.Next(min, max);

        int[,] matrix = MapConnections.Create(from.Size, to.Size);
        List<int> emptyRows = Enumerable.Range(1, from.Size - 2).ToList();
        List<int> emptyCols = Enumerable.Range(1, to.Size - 2).ToList();
        while (MapConnections.CountConnection(matrix) < count)
        {
            var possibleConnections = MapConnections.ListUncertain(matrix).ToList();

            var tmp = possibleConnections.Where(pc => emptyRows.Contains(pc.Item1) && emptyCols.Contains(pc.Item2)).ToList();
            if (tmp.Count == 0)
                tmp = possibleConnections.Where(pc => emptyRows.Contains(pc.Item1) || emptyCols.Contains(pc.Item2)).ToList();
            if (tmp.Count != 0)
                possibleConnections = tmp;

            var connection = possibleConnections[rnd.Next(possibleConnections.Count)];
            MapConnections.Connect(matrix, connection.Item1, connection.Item2);
            emptyRows.Remove(connection.Item1);
            emptyCols.Remove(connection.Item2);
        }

        from.Connect(to, matrix);
    }
}

[TestMethod]
public void CodeReviewTest()
{
    IStep from = new Step(new FightRoom(), new FightRoom(), new FightRoom(), new FightRoom(), new FightRoom());
    IStep to = new Step(new FightRoom(), new FightRoom(), new FightRoom(), new FightRoom(), new FightRoom());

    IStepConnector connector = new StepConnector();
    connector.Connect(from, to);

    List<IRoom> toRooms = new List<IRoom>();
    for (int i = 0; i < 5; i++)
    {
        Assert.IsTrue(from[i].NextRooms.Length > 0);
        for (int j = 0; j < from[i].NextRooms.Length; j++)
        {
            if (!toRooms.Contains(from[i].NextRooms[j]))
                toRooms.Add(from[i].NextRooms[j]);
        }
    }

    for (int j = 0; j < 5; j++)
    {
        Assert.IsTrue(toRooms.Contains(to[j]));
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to CodeReview. If you want a serious review of your code, I think you have to provide a little more background, context, a simple example and some full implementations of IStep and IRoom. What is it meant to be used for etc.? \$\endgroup\$ – Henrik Hansen Oct 19 '18 at 5:17
  • 1
    \$\begingroup\$ @HenrikHansen Thank you! I did provide what you asked to me, tell me if this isn't enough! \$\endgroup\$ – Maxime Recuerda Oct 19 '18 at 6:19
  • \$\begingroup\$ Just to make things clear: does your code work as intended and are you looking for general improvements, or does it fail for specific edge-cases and you're looking to solve those cases? \$\endgroup\$ – Pieter Witvoet Oct 19 '18 at 9:30
  • 1
    \$\begingroup\$ Currently, my code works, because I added a do { /*create the matrix*/ } while(/*matrix is incorrect*/); but this solution is really ugly, so I would like to get ideas to implements the IStepConnection.Connect without this ugly loop. I didn't talk about this do-while loop because it is futile and useless information in my opinion. To answer you, my code works and I look for improvements, because it fails for specific cases that I look to solve in a single pass. \$\endgroup\$ – Maxime Recuerda Oct 19 '18 at 9:35
  • \$\begingroup\$ You see, to have 2 version of Connect, with slightly different behaviour; which is the 'right' one? \$\endgroup\$ – VisualMelon Jul 28 at 21:24

Your Answer

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

Browse other questions tagged or ask your own question.