Алгоритм Эллера для генерации лабиринтов генерирует петли

Question

[Gebrauchsanweis]

Стараюсь на java написать генератор лабиринтов с использованием алгоритма Эллера, алгоритм смотрел здесь: habrahabr.ru/post/176671

Исходя из того, что встретил ещё сайт, где лабиринт по этому алгоритму строится нормально, значит мой косяк, но там код на java script и я ничего не понял :(

вот какие куски у меня получаются не правильно:
(точками пустые места обозначаю, иначе пробелы схлопываются)
первый:
__ __ __
|__ .... ....|
|.... .... ....|

т.е. в этом случае в первом ряду множества получаются 1 1 1, а во втором при создании строки 4 1 1, после чего при пункте "добавление правой стены" получается, что сначала стена может не поставиться если шанс не прокнет и множества станут 4 4 1, а в итоге при сравнении 4 1 стена не поставится, хотя по идее она там должна ставиться обязательно, т.к. в противном случае получается петля.

второй:
__ __ __
|__ .... ....|
|__ ....|....|
|....|.... ....|
в этом куске в первом ряду множества опять 1 1 1, во втором 4 4 1, т.е. множества разделяются, но в третьей строке они снова объединяются (5 4 4), что приводит к петле.

Подскажите, пожалуйста, какое условие я пропустил?

Comments

[Deerenaros]

Без кода (хотя бы генератора лабиринтов) очень сложно использовать свои телепатические способности. И да, дабы лабиринт не "хлопывался", можно (и нужно) использовать тег
code

[Gebrauchsanweis]

Вот код, но в нём последняя строка ещё не работает - потом сам, наверное, разберусь.

кот

public class Maze 
{	
	protected class Walls
	{
		private boolean topWall, bottomWall, rightWall, leftWall;
		
		public Walls()
		{
			topWall=false;
			bottomWall=false;
			rightWall=false;
			leftWall=false;
		}
		
		public void SetTopWall()
		{
			topWall=true;
		}
		
		public void BreakTopWall()
		{
			topWall=false;
		}
		
		public boolean GetTopWall()
		{
			return topWall;
		}
		
		public void SetBottomWall()
		{
			bottomWall=true;
		}
		
		public void BreakBottomWall()
		{
			bottomWall=false;
		}
		
		public boolean GetBottomWall()
		{
			return bottomWall;
		}
		
		public void SetRightWall()
		{
			rightWall=true;
		}
		
		public void BreakRightWall()
		{
			rightWall=false;
		}
		
		public boolean GetRightWall()
		{
			return rightWall;
		}
		
		public void SetLeftWall()
		{
			leftWall=true;
		}
		
		public void BreakLeftWall()
		{
			leftWall=false;
		}
		
		public boolean GetLeftWall()
		{
			return leftWall;
		}
	}

	
	
	private int length;
	public Walls walls[][];
	
	public Maze (int _length)
	{
		if (_length>10)
		{
		length = _length;
		}
		else
		{
			length=10;
		}
		
		walls = new Walls[length][length];   //initialization
		for (int j=0;j<length;j++)
		{
			for(int i=0;i<length;i++)
			{
				walls[i][j] = new Walls();
			}
		}
		
	}
	
	public Maze()
	{
		length = 10;
		
		walls = new Walls[length][length]; 	 //initialization
		for (int j=0;j<length;j++)
		{
			for(int i=0;i<length;i++)
			{
				walls[i][j] = new Walls();
			}
		}
		
	}
	
	
	//Creating Maze properties.
	boolean isTruth[][] = new boolean[length][length];
	public int fact[][] = new int[length][length];
	public int explore[][] = new int[length][length];
	

	
	//eller's algorithm
	public void CreateMaze()
	{
		int multiplicity[] = new int[length];		//current multiplicities
		int lowWall[] = new int[length];			//to remember in cycle where bottom wall were made

			
		int m=1;									//iterator for multiplicities
		int madeWall=0;
		
		
		for (int i=0; i<length; i++)				//set
		{
			lowWall[i] = 0;
		}
		
		for(int i=0; i<length; i++)					//set
		{
			multiplicity[i]=m;
			m++;
		}
		
		for(int j=0; j<length-1;j++)				//first length-1 strings have the same algorithm
		{
			
			for (int k=0;k<length;k++)
			{
				System.out.print("  " + multiplicity[k]);
				
			}
			System.out.println();
			madeWall=0;
			
			for(int i=0; i<length-1; i++)			//we don't need last column
			{
				
				
				//PREPEARING NEW STRING
				if(i>0)								//first string is unique
				{
					for(int k=0; k<length;k++)		//deleting previous bottom walls and multiplicities. see eller's algorithm.
					{
						if (lowWall[k]==1)
						{
							multiplicity[k]=m++;
							lowWall[k]=0;
						}
					}
				}
				
				
				//RIGHT WALLS
				if ( AddRightWall(i,j,multiplicity) == true)
				{
					//it's nothing here
				}
				else
				{
					multiplicity[i+1]=multiplicity[i];
				}
				
				
				//BOTTOM WALLS
				if (AddBottomWall(i,j,multiplicity) == true)
				{
					lowWall[i]=1;
					madeWall++;
				}
				
				
				if(i==length-2)
				{
					if (AddBottomWall(i+1,j,multiplicity) == true)
					{
						lowWall[i+1]=1;
						madeWall++;
					}
					

					if (madeWall==0)
					{

						madeWall=0;
						for(int k=0;k<length;k++)
						{
							if (AddBottomWall(k,j,multiplicity) == true)
							{
								lowWall[k]=1;
							}
						}
						
					}
				}
				
				
				
			}
			
			
			
		}
		
		//LAST STRING
		int upperCheck[] = {0,0};
		for (int i=0; i<length-1; i++)
		{
			if( multiplicity[i]==multiplicity[i+1] && multiplicity[i]!=upperCheck[0] )
			{
				upperCheck[0]=multiplicity[i];
				upperCheck[1]=0;
			}
			if(upperCheck[0]==multiplicity[i])
			{
				if (walls[i][length-1].GetTopWall())
				{
					upperCheck[1]++;
				}
				if (upperCheck[1]>1)
				{
					walls[i][length-1].SetLeftWall();
					walls[i-1][length-1].SetRightWall();
					upperCheck[1]--;
				}
			}
			
			
			
			
		}
		
		for(int i=0;i<length;i++)
		{
			walls[i][0].SetTopWall();
			walls[i][length-1].SetBottomWall();
		}
		for(int j=0;j<length;j++)
		{
			walls[0][j].SetLeftWall();
			walls[length-1][j].SetRightWall();
		}
	}
	
	public boolean AddRightWall(int _i, int _j, int _multiplicity[])
	{
		System.out.println("Add Wall " + _i + _j + " Mult " + _multiplicity[_i] + " " + _multiplicity[_i+1]);
		if ( ((int)(Math.random()*3)==1) || (_multiplicity[_i+1]==_multiplicity[_i]) )  //chance to create a right wall.
		{
			walls[_i][_j].SetRightWall();
			walls[_i+1][_j].SetLeftWall();		//if this cell has right wall, this wall is the left one for next cell
			return true;
		}
		else
		{
			return false;
		}
	}
	
	public boolean AddBottomWall(int _i, int _j, int _multiplicity[])  //create bottom wall
	{
		if (!OneOfaKind(_i, _multiplicity))	
		{
			if ( (int)(Math.random()*3)==1 )
			{
				walls[_i][_j].SetBottomWall();
				walls[_i][_j+1].SetTopWall();;
				return true;
			}
			else
			{
				return false;
			}
		}
		else
		{
			return false;
		}
	}
	
	public boolean OneOfaKind(int _i, int _multiplicity[]) //looking for the same muliplicity near i;
	{
		boolean sameright, sameleft;
		try
		{
			sameleft=_multiplicity[_i-1]==_multiplicity[_i];
		}
		catch (ArrayIndexOutOfBoundsException e)
		{
			sameleft=false;
		}
		try
		{
			sameright=_multiplicity[_i+1]==_multiplicity[_i];
		}
		catch (ArrayIndexOutOfBoundsException e)
		{
			sameright=false;
		}
		
		
		return !(sameleft || sameright);
	}
	
	public Walls GetWalls(int _x, int _y)
	{
		return walls[_x][_y];
	}
	
	public int GetLength()
	{
		return length;
	}
	
	public void ShowMazeInConsol()
	{
		for(int i=0;i<length;i++)
		{
			System.out.print(" __");
		}
		System.out.println();
		
		for (int j=0;j<length;j++)
		{
			System.out.print("|");
			for(int i=0;i<length;i++)
			{
				if (walls[i][j].GetBottomWall())
				{
					System.out.print("__");
				}
				else
				{
					System.out.print("  ");
				}
				if (walls[i][j].GetRightWall())
				{
					System.out.print("|");
				}
				else
				{
					System.out.print(" ");
				}
			}
			System.out.println();
		}
	}
}

Answer 1

[Deerenaros]

Читал про алгоритм Эллера, так и не понял его красоту. Имхо, намного лучше использовать обход в глубину и в качестве лабиринта использовать остовное дерево. В коде увидеть его можно здесь (извиняюсь за ужасный код).

Comments

[Gebrauchsanweis]

мне понравился тем, что много отворотов, мне не нужны длинные ветви.

[Deerenaros]

@Gebrauchsanweis Если случайно выбирать направление движения, остовное дерево будет примерно таким же - обход в глубину рекурсивен и будут появляться тупики, которые и будут отворотами.