# Creation of matrix with specific attempts at the end

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.

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]))
}
}

for (int j = 0; j < 5; j++)
{
Assert.IsTrue(toRooms.Contains(to[j]));
}
}

• 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.?
– user73941
Oct 19, 2018 at 5:17
• @HenrikHansen Thank you! I did provide what you asked to me, tell me if this isn't enough! Oct 19, 2018 at 6:19
• 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? Oct 19, 2018 at 9:30
• 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. Oct 19, 2018 at 9:35
• You see, to have 2 version of Connect, with slightly different behaviour; which is the 'right' one? Jul 28, 2019 at 21:24