Cyklus algoritmu bludiště nechce dojít konce – .NET – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Toto vlákno bylo označeno za vyřešené — příspěvek s řešením.
Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Matěj Andrle+1
Grafoman
1. 7. 2014   #1
-
0
-

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.

Nahlásit jako SPAM
IP: 78.136.140.–
Reklama
Reklama
RomanZ
~ Anonymní uživatel
244 příspěvků
1. 7. 2014   #2
-
0
-

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.

Nahlásit jako SPAM
IP: 89.24.105.–
Satik0
Stálý člen
1. 7. 2014   #3
-
0
-

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.

Nahlásit jako SPAM
IP: 86.49.188.–
Matěj Andrle+1
Grafoman
1. 7. 2014   #4
-
0
-

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...

Nahlásit jako SPAM
IP: 78.136.140.–
Satik0
Stálý člen
1. 7. 2014   #5
-
0
-

#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 :)

Nahlásit jako SPAM
IP: 86.49.188.–
Matěj Andrle+1
Grafoman
1. 7. 2014   #6
-
0
-

#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...

Nahlásit jako SPAM
IP: 78.136.140.–
Satik0
Stálý člen
1. 7. 2014   #7
-
0
-

#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 :)

Nahlásit jako SPAM
IP: 86.49.188.–
RomanZ
~ Anonymní uživatel
244 příspěvků
1. 7. 2014   #8
-
+1
-
Zajímavé
Nahlásit jako SPAM
IP: 89.24.105.–
Matěj Andrle+1
Grafoman
1. 7. 2014   #9
-
0
-

#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

Nahlásit jako SPAM
IP: 78.136.140.–
Řešení
Matěj Andrle+1
Grafoman
1. 7. 2014   #10
-
0
-
Vyřešeno Nejlepší odpověď

Jediná chyba - x2 -> x1 má být! :D

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];
				path.RemoveAt(index);
				
				x1 = currentPath.X + currentPath.DirectionX;
				y1 = currentPath.Y + currentPath.DirectionY;
				x2 = x1 + currentPath.DirectionX;
				y2 = y1 + currentPath.DirectionY;
								
				try
				{
					value = tile[x2, y2];
				}
				catch
				{
					continue;	
				}
				
				if(value == 0)
				{
					tile[x1, y1] = 1;
					
					x2 = x1;
					y2 = y1 + 1;
					
					if(Neighbor(tile, x2, y2))
						path.Add(new Path(x1, y1, 0, 1));
					
					x2 = x1;
					y2 = y1 - 1;
					
					if(Neighbor(tile, x2, y2))
						path.Add(new Path(x1, y1, 0, -1));
					
					x2 = x1 + 1;
					y2 = y1;
					
					if(Neighbor(tile, x2, y2))
						path.Add(new Path(x1, y1, 1, 0));
					
					x2 = x1 - 1;
					y2 = y1;
					
					if(Neighbor(tile, x2, y2))
						path.Add(new Path(x1, y1, -1, 0));
				}
			}
			
			return output;
		}
		
		static bool Neighbor(int[,] tile, int x, int y)
		{
			try
			{
				return tile[x, y] == 0;
			}
			catch
			{
				return false;
			}
		}
	}
}

Nebojte - nezopomínám. Hned předělám výjimky na podmínky.

Nahlásit jako SPAM
IP: 78.136.140.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 52 hostů

Podobná vlákna

Zjištění konce řádků — založil Paul

Oddělení konce textu — založil dragon124

C#-bludiště — založil Systém

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý