Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections.Generic;
- using System.Linq;
- using System.Text;
- using System.Threading.Tasks;
- namespace Kruskal
- {
- class Room
- {
- private int xPos, yPos;
- private int group;
- private bool isOn;
- private bool[] isConnected = new bool[4];
- public Room(int Y, int X, int nGroup)
- {
- xPos = X;
- yPos = Y;
- group = nGroup;
- isOn = true;
- isConnected[0] = false;
- isConnected[1] = false;
- isConnected[2] = false;
- isConnected[3] = false;
- }
- public int getXPos()
- {
- return xPos;
- }
- public void setXPos(int value)
- {
- xPos = value;
- }
- public int getYPos()
- {
- return yPos;
- }
- public void setYPos(int value)
- {
- yPos = value;
- }
- public int getGroup()
- {
- return group;
- }
- public void setGroup(int value)
- {
- group = value;
- }
- public bool getIsOn()
- {
- return isOn;
- }
- public void setIsOn(bool value)
- {
- isOn = value;
- }
- public bool getIsConnected(int index)
- {
- try
- {
- return isConnected[index];
- }
- catch
- {
- Console.Write("Connection Array Out of Range");
- return true;
- }
- }
- public void setIsConnected(int index, bool value)
- {
- try
- {
- isConnected[index] = value;
- }
- catch
- {
- Console.SetCursorPosition(0, 20);
- Console.Write("Connection Array out of Range");
- }
- }
- }
- class Program
- {
- static void Main(string[] args)
- {
- List<Room> mazeToCheck = new List<Room>();
- List<Room> mazeChecked = new List<Room>();
- int sizeX, sizeY;
- sizeY = Convert.ToInt32(Console.ReadLine());
- sizeX = Convert.ToInt32(Console.ReadLine());
- Console.Clear();
- Room[] maze = new Room[sizeX * sizeY];
- HashSet<Room>[] vertexSets = new HashSet<Room>[sizeX * sizeY];
- /*
- *
- *Inicialização dos nodes do labirinto
- * e inserção dos nodes em grupos isolados
- *
- */
- for (int i = 0; i < sizeY; i++){
- for(int j = 0; j < sizeX; j++){
- int curIndex = i * sizeX + j;
- maze[curIndex] = new Room(i, j, curIndex);
- mazeToCheck.Add(maze[curIndex]);
- vertexSets[curIndex] = new HashSet<Room>();
- vertexSets[curIndex].Add(maze[curIndex]);
- }
- }
- Random random = new Random();
- int randNode;
- /*
- * Enquanto houver nodes para serem checados
- * escolher um node aleatorio na lista de nodes
- * descobrir sua coordenada, e procurar nodes vizinhos
- */
- int nodes = 0;
- while(mazeToCheck.Count > 0)
- {
- nodes++;
- randNode = random.Next(0, mazeToCheck.Count);
- Room currentNode = mazeToCheck[randNode];
- Room destNode;
- List<int> connectionsToCheck = new List<int>();
- //Condições de checagem
- ///Se o node estiver no extremo esquerdo: nao procurar no X- (West-0)
- ///Se o node estiver no extremo direito: nao procurar no X+ (East-2)
- ///se o node estiver no extremo topo: nao procurar no Y- (North-1)
- ///Se o node estiver no extremo baixo: nao procurar no Y+ (South-3)
- //Extrema esquerda (west)
- if(currentNode.getXPos() > 0)
- {
- connectionsToCheck.Add(0);
- }
- //Extrema direita (east)
- if(currentNode.getXPos() < sizeX - 1)
- {
- connectionsToCheck.Add(2);
- }
- //Extremo topo (north)
- if(currentNode.getYPos() > 0)
- {
- connectionsToCheck.Add(1);
- }
- //Extremo baixo (south)
- if(currentNode.getYPos() < sizeY - 1)
- {
- connectionsToCheck.Add(3);
- }
- //Placeholder
- //Placeholder
- //Checar o vertice escolhido
- //Se o node linkado ao vertice for do mesmo grupo do node atual, descartar vertice e tentar novamente (tentar ate a lista de vertices esvaziar)
- //Se a lista de vertices esvaziar e nenhum vertice for escolhido, desconsiderar node (para nao criar loops) e continuar para o proximo
- //Aqui o node tera uma lista de possiveis conexões
- //Deve agora comparar o node da conexão escolhida aleatoriamente para saber se esta no mesmo grupo
- bool foundConnection = false;
- while (connectionsToCheck.Count > 0 && foundConnection == false)
- {
- int randomConnection = connectionsToCheck[random.Next(0, connectionsToCheck.Count)];
- //Console.WriteLine("Current Node: {2} Connection Count: {0} RandomConnection: {1}", connectionsToCheck.Count, randomConnection, nodes);
- int destGroup;
- switch (randomConnection)
- {
- //West Check (X - 1)
- case 0:
- //armazena o node ligado ao vertice escolhido
- destNode = maze[currentNode.getYPos() * sizeX + currentNode.getXPos() - 1];
- /*
- * se os nodes pertencem ao mesmo grupo
- * remover o vertice atual da checagem, e continuar tentando se houver mais vertices
- *
- * se os nodes forem de grupos diferentes, transferir o node destino ao grupo do node atual
- */
- if (CheckRoomsGroup(currentNode, destNode))
- {
- connectionsToCheck.RemoveAt(connectionsToCheck.IndexOf(0));
- }
- else
- {
- //armazena o indice do node destino
- destGroup = maze[currentNode.getYPos() * sizeX + currentNode.getXPos() - 1].getGroup();
- //faz a união do conjunto de sets
- vertexSets[currentNode.getGroup()].UnionWith(vertexSets[destGroup]);
- foreach(Room r in vertexSets[destGroup])
- {
- maze[r.getYPos() * sizeX + r.getXPos()].setGroup(currentNode.getGroup());
- }
- maze[currentNode.getYPos() * sizeX + currentNode.getXPos()].setIsConnected(randomConnection, true);
- //indica que uma conexão foi feita
- foundConnection = true;
- }
- break;
- //North Check (Y - 1)
- case 1:
- destNode = maze[(currentNode.getYPos() - 1) * sizeX + currentNode.getXPos()];
- if (CheckRoomsGroup(currentNode, destNode)){
- connectionsToCheck.RemoveAt(connectionsToCheck.IndexOf(1));
- }else
- {
- destGroup = maze[(currentNode.getYPos() - 1) * sizeX + currentNode.getXPos()].getGroup();
- vertexSets[currentNode.getGroup()].UnionWith(vertexSets[destGroup]);
- foreach (Room r in vertexSets[destGroup])
- {
- maze[r.getYPos() * sizeX + r.getXPos()].setGroup(currentNode.getGroup());
- }
- maze[currentNode.getYPos() * sizeX + currentNode.getXPos()].setIsConnected(randomConnection, true);
- foundConnection = true;
- }
- break;
- //East Check (X + 1)
- case 2:
- destNode = maze[(currentNode.getYPos() * sizeX + currentNode.getXPos() + 1)];
- if (CheckRoomsGroup(currentNode, destNode))
- {
- connectionsToCheck.RemoveAt(connectionsToCheck.IndexOf(2));
- }
- else
- {
- destGroup = maze[(currentNode.getYPos() * sizeX + currentNode.getXPos() + 1)].getGroup();
- vertexSets[currentNode.getGroup()].UnionWith(vertexSets[destGroup]);
- foreach (Room r in vertexSets[destGroup])
- {
- maze[r.getYPos() * sizeX + r.getXPos()].setGroup(currentNode.getGroup());
- }
- maze[currentNode.getYPos() * sizeX + currentNode.getXPos()].setIsConnected(randomConnection, true);
- foundConnection = true;
- }
- break;
- //South Check (Y + 1)
- case 3:
- destNode = maze[((currentNode.getYPos() + 1) * sizeX + currentNode.getXPos())];
- if (CheckRoomsGroup(currentNode, destNode))
- {
- connectionsToCheck.RemoveAt(connectionsToCheck.IndexOf(3));
- }
- else
- {
- destGroup = maze[((currentNode.getYPos() + 1) * sizeX + currentNode.getXPos())].getGroup();
- vertexSets[currentNode.getGroup()].UnionWith(vertexSets[destGroup]);
- foreach (Room r in vertexSets[destGroup])
- {
- maze[r.getYPos() * sizeX + r.getXPos()].setGroup(currentNode.getGroup());
- }
- foundConnection = true;
- maze[currentNode.getYPos() * sizeX + currentNode.getXPos()].setIsConnected(randomConnection, true);
- }
- break;
- }
- PrintMaze(maze, sizeY, sizeX);
- Console.ReadLine();
- }
- mazeChecked.Add(mazeToCheck[randNode]);
- mazeToCheck.RemoveAt(randNode);
- connectionsToCheck.Clear();
- }
- //InitMaze(maze, sizeY, sizeX);
- PrintMaze(maze, sizeY, sizeX);
- Console.Read();
- }
- ///<summary>Check if two rooms are in the same group</summary>
- static bool CheckRoomsGroup(Room room1, Room room2)
- {
- if(room1.getGroup() == room2.getGroup())
- {
- return true;
- }else
- {
- return false;
- }
- }
- static void PrintMaze(Room[] maze, int sizeY, int sizeX)
- {
- for (int i = 0; i < sizeY; i++)
- {
- for (int j = 0; j < sizeX; j++)
- {
- int curIndex = i * sizeX + j;
- Console.SetCursorPosition(maze[curIndex].getXPos() * 2, maze[curIndex].getYPos() * 2);
- if (maze[curIndex].getIsOn())
- {
- Console.Write("{0}",maze[curIndex].getGroup());
- }
- //West Check
- if (maze[curIndex].getIsConnected(0) == true && maze[curIndex].getXPos() * 2 - 1 > 0)
- {
- Console.SetCursorPosition(maze[curIndex].getXPos() * 2 - 1, maze[curIndex].getYPos() * 2 + 0);
- Console.Write("─");
- }
- //North Check
- if (maze[curIndex].getIsConnected(1) == true && maze[curIndex].getYPos() * 2 - 1 > 0)
- {
- Console.SetCursorPosition(maze[curIndex].getXPos() * 2 + 0, maze[curIndex].getYPos() * 2 - 1);
- Console.Write("│");
- }
- //East Check
- if (maze[curIndex].getIsConnected(2) == true && maze[curIndex].getXPos() * 2 + 1 < sizeX * 2 - 2)
- {
- Console.SetCursorPosition(maze[curIndex].getXPos() * 2 + 1, maze[curIndex].getYPos() * 2 + 0);
- Console.Write("─");
- }
- //South Check
- if (maze[curIndex].getIsConnected(3) == true && maze[curIndex].getYPos() * 2 + 1 < sizeY * 2 - 2)
- {
- Console.SetCursorPosition(maze[curIndex].getXPos() * 2 + 0, maze[curIndex].getYPos() * 2 + 1);
- Console.Write("│");
- }
- }
- }
- }
- }
- }
Add Comment
Please, Sign In to add comment