Cyklus algoritmu bludiště nechce dojít konce – .NET – Fórum – Programujte.com

Dobrý den,

using System.Collections.Generic;
using System;

namespace MaGa
{
	public struct Path
	{
		public sbyte DirectionX { get; set; }
		public sbyte DirectionY { get; set; }
		public int X { get; set; }
		public int Y { get; set; }
		
		public Path(int x, int y, sbyte directionX, sbyte directionY) : this()
		{
			DirectionX = directionX;
			DirectionY = directionY;
			X = x;
			Y = y;
		}
	}
	
	public static class MazeGenerator
	{
		static Random numberGenerator = new Random();
		
		public static  List<MazeObject> Generate(int width, int height)
		{
			List<MazeObject> output = new List<MazeObject>();
			List<Path> path = new List<Path>()
			{
				new Path(0, 0, 0, 1),
				new Path(0, 0, 1, 0)
			};
			int[,] tile = new int[width, height];
			int index, value, x1, y1, x2, y2;
			
			tile[0, 0] = 1;
			
			while(path.Count > 0)
			{
				index = numberGenerator.Next(path.Count);
				Path currentPath = path[index];
				
				x1 = currentPath.X + currentPath.DirectionX;
				y1 = currentPath.Y + currentPath.DirectionY;
				x2 = x1 + currentPath.DirectionX;
				y2 = y1 + currentPath.DirectionY;
				
				path.RemoveAt(index);
				
				try
				{
					value = tile[x2, y2];
				}
				catch
				{
					continue;	
				}
				
				if(value == 0)
				{
					tile[x1, y1] = 1;
					
					x2 = x1;
					y2 = y1 + 1;
					
					if(Neighbor(ref tile, x2, y2))
						path.Add(new Path(x2, y2, 0, 1));
					
					x2 = x1;
					y2 = y1 - 1;
					
					if(Neighbor(ref tile, x2, y2))
						path.Add(new Path(x2, y2, 0, -1));
					
					x2 = x1 + 1;
					y2 = y1;
					
					if(Neighbor(ref tile, x2, y2))
						path.Add(new Path(x2, y2, 1, 0));
					
					x2 = x1 - 1;
					y2 = y1;
					
					if(Neighbor(ref tile, x2, y2))
						path.Add(new Path(x2, y2, -1, 0));
				}
			}
			
			return output;
		}
		
		static bool Neighbor(ref int[,] tile, int x, int y)
		{
			try
			{
				return tile[x, y] == 0;
			}
			catch
			{
				return false;
			}
		}
	}
}

Není hotovo, každopádně by se cyklus měl ukončit - po určité chvíli. Ovšem nikdy se nevyčerpají všechny cesty - nevidí někdo, prosím, proč?
Děkuji.

Neskáčeš náhodou na políčko, ze kterýho jsi přišel? Zdá se mi, že jednu path odebereš, ale vzápětí se čtyři přidají (a měly by se přidat 3, protože jedna je asi ta, ze které se přišlo).

Jestli ne, omlouvám se, je to jen první dojem.

Pár poznámek ke kódu:

• Ref je tu použito zbytečně, nemá tu smysl.
• Zjišťovat, jestli nesaháš mimo pole přes výjimky, je prasárna, tvůj algoritmus to zpomalí o několik řádů, dej si tu práci a přepiš to na podmínky.

Dobrá - nechtělo se mi bastlit se s podmínkami... Ano - přidávám i cestu zpět - ovšem test zda je toto políčko 0 vyjde false - takže ne... Ref je tam proto - přeci nebudu posílat celé pole - ne? Nicméně pořád neřešíte proč nakonec není zaplněno celé hrací pole cestami, pročež by už neměla být žádná nová, avšak je...

return tile[x, y] == 0; -> nemůže být přidáno jakékoliv políčko, které by propojilo 2 cesty - aby průchod nebyl tak snadný a současně se nepřidá políčko o jedno zpět...

#4 Matěj Andrle

Ref je tam proto - přeci nebudu posílat celé pole - ne

Pole se přeci neposílá celé ani když tam ref nedáš, posílá se jen reference.

Jinak podle mě máš trochu zmatek v path/currentPath. Ideálně si tam hoď breakpoint a krokuj, aby jsi viděl, co přesně se tam děje :)

#5 Satik
No těch cest je tam asi 10 biliard za minutu (nepřeháním - vážně) a nepřesahují pole - tak se přidají další 3...

#6 Matěj Andrle

A proč to neděláš jako běžní smrtelníci? :)

Algoritmem vlny si celou mapu ohodnoť čísly, podle kterých poznáš jejich vzdálenost od startu.

Pak ti stačí jen jít od cíle po nejnižších hodnotách a podle těch políček konstruovat cestu, dokud nedojdeš do startu.

EDIT: 10 biliard (ani miliard) cest za minutu to nebude, pochybuji, že bys měl tolik operační paměti :)

#1 Matěj Andrle
Prosímtě, nezlob se, nestudoval jsem to do hloubky - co vlastně potřebuješ vyřešit? Nalezení cesty v existujícím bludišti, nebo vyrobit nové bludiště?

Mrkni sem:

http://www.itnetwork.cz/algoritmy-pro-bludiste-nejkratsi-cesta-a-generovani-nahodneho

Zejména ten článek o generování náhodného bludiště se mi hodně líbil.

#8 RomanZ
Toto je nejpopulárnější algoritmus generování bludiště - Prim's algorithm... Kód by měl jet - chybu nevidím.

http://commons.wikimedia.org/w/index.php?title=File%3AMAZE_30x20_Prim.ogv