3
\$\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:

module MapConnections =
    let IsUncertain array row col =
        Array2D.get array row col = -1

    let IsDisconnected array row col =
        Array2D.get array row col = 0

    let IsConnected array row col =
        Array2D.get array row col = 1

    let ListUncertain array =
        let mutable list : (int*int) list = list.Empty
        for i  in 0 .. Array2D.length1 array - 1 do
            for j in 0 .. Array2D.length2 array - 1 do
                if IsUncertain array i j then
                    list <- list @ [(i,j)]
        list

    let ListDisconnected array = // ...
    let ListConnected array = // ...

    let CountUncertain array =
        ListUncertain array |> Seq.length<int*int>        
    let CountDisconnection array = // ...        
    let CountConnection array = // ...

    let Disconnect array row col =
        if IsUncertain array row col then
            Array2D.set array row col 0
        IsDisconnected array row col

    let Connect array row col =
        if IsUncertain array row col then
            Array2D.set array row col 1
            for i in 0 .. row - 1 do
                for j in col + 1 .. Array2D.length2 array - 1 do
                    Disconnect array i j |> ignore
            for i in row + 1 .. Array2D.length1 array - 1 do
                for j in 0 .. col - 1 do
                    Disconnect array i j |> ignore
        IsConnected array row col

    let Create rows cols =
        let matrix = Array2D.create rows cols -1
        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)
{
    int min = Math.Max(from.Size, to.Size);
    int max = from.Size + to.Size;
    int count = StaticRandom.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[StaticRandom.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\$ Looks much better - thanks. \$\endgroup\$ – Henrik Hansen Oct 19 '18 at 6:35
  • \$\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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.