ComputerBase Menü
Aktuelles

C++ Heightmap-Generierung mit libnoise

Es ging mir hier nur darum, einmal etwas auszuprobieren, du hast recht, es ist nicht praktikabel für das Spiel.

Werde mich mal genauer in den A*-Algorithmus einarbeiten. Wenn man diesen benutzen würde, dann die Kosten auf die Höhe beziehen würde und dann diesen Pfad weichzeichnen etc. würde, sollte das Resultat eigentlich ganz ansehnlich sein ;)

Gruß,

badday
 
Mh aber wenn du Wegplanungs-Algos einsetzt ist die Idee mit der Taktik-Map im Prinzip überflüssig

Die Idee sollte ja gerade sein, dass du eben nicht das Rauschen analysieren musst um dort Wege und Punkte entsprechend einfügst sondern dass du die Noise-Map nachträglich der Taktik-Map durch Filter anpasst.

Es funktonieren natürlich beide Ansätz.! Aber ich vermute mal, dass man mit der Vorgabe von Taktik-Maps weniger Arbeit hat und auch stärker beeinflussen kann, dass die Maps zB fair (=symetrisch) sind.
 
Klar, beim dem Ansatz gibt es keine Taktik-Map mehr. Aber das wäre wohl durchaus i. O.

Ich probiere es einfach mal aus, melde mich dann wieder.


Gruß,

badday
 
So, ich habe mit mal am A* Algo versucht, bin aber bisher gescheitert, weiß allerdings momentan auch nicht mehr weiter, bin mir aber sicher, dass ihr mir helfen könnt.

Hier erstmal der Code:

Code: 
class Node
{
public:
	Node(int _x, int _y, int _h, double _cost, double _way, double _heuristic, Node* _parent) : x(_x), y(_y), h(_h), cost(_cost), way(_way), heuristic(_heuristic), parent(_parent) {}
	int x, y;
	unsigned int h;
	Node *parent;
	double cost, way, heuristic;
};


bool checkNext(Node *next, std::list<Node*> &opened, const std::list<Node*> &closed)
{
	
	for(std::list<Node*>::const_iterator it = closed.begin(); it!=closed.end(); ++it)
	{
		if((*it)->x==next->x && (*it)->y==next->y)
			return false;
	}
	for(std::list<Node*>::iterator iter = opened.begin(); iter!=opened.end(); ++iter)
	{
		if((*iter)->x==next->x && (*iter)->y==next->y){
			if((*iter)->cost>next->cost) {
				opened.erase(iter);
				return true;
			}
			else
				return false;
		}
	}

	return true;
}

bool compare_cost(Node *first, Node *second)
{
	if(first->cost < second->cost)
		return true;

	return false;
}


void generatePathImpl(Node *act, Node *end, const video::IImage &hmap, std::list<Node*> &opened, std::list<Node*> &closed)
{
	
		if((act->x+10)<hmap.getDimension().Width) //the next one on the right side
		{
			
			double heur = sqrt(double((pow((act->x+10)-(end->x), 2.0)+pow((act->y)-(end->y), 2.0))));
			double cost = (((unsigned)hmap.getPixel(act->x, act->y).getAverage()-(unsigned)(hmap.getPixel(act->x+10, act->y).getAverage())/255)*0.4)+0.3;			
		
			Node *next = new Node(act->x+10, act->y, hmap.getPixel(act->x+10, act->y).getAverage(), cost+heur, 10, heur, act);

			if(checkNext(next, opened, closed))
				opened.push_back(next);
		}

		if((act->x+10)<hmap.getDimension().Width && (act->y+10)<hmap.getDimension().Height) //the next one 10 steps right and 10 steps up
		{
			
			double heur = sqrt(double((pow((act->x+10)-(end->x), 2.0)+pow((act->y+10)-(end->y), 2.0))));
			double cost = (((unsigned)hmap.getPixel(act->x, act->y+10).getAverage()-(unsigned)(hmap.getPixel(act->x+10, act->y+10).getAverage())/255)*0.4)+0.3;			
		
			Node *next = new Node(act->x+10, act->y+10, hmap.getPixel(act->x+10, act->y+10).getAverage(), cost+heur, 10, heur, act);
			if(checkNext(next, opened, closed))
				opened.push_back(next);
		}

		if((act->y+10)<hmap.getDimension().Height) //3
		{
			
			double heur = sqrt(double((pow((act->x)-(end->x), 2.0)+pow((act->y+10)-(end->y), 2.0))));
			double cost = (((unsigned)hmap.getPixel(act->x, act->y+10).getAverage()-(unsigned)(hmap.getPixel(act->x, act->y+10).getAverage())/255)*0.4)+0.3;			
		
			Node *next = new Node(act->x, act->y+10, hmap.getPixel(act->x, act->y+10).getAverage(), cost+heur, 10, heur, act);
			if(checkNext(next, opened, closed))
				opened.push_back(next);
		}

		if((act->x-10)>0 && (act->y+10)<hmap.getDimension().Height) //4
		{
			
			double heur = sqrt(double((pow((act->x-10)-(end->x), 2.0)+pow((act->y-10)-(end->y), 2.0))));
			double cost = (((unsigned)hmap.getPixel(act->x, act->y-10).getAverage()-(unsigned)(hmap.getPixel(act->x-10, act->y-10).getAverage())/255)*0.4)+0.3;			
		
			Node *next = new Node(act->x-10, act->y-10, hmap.getPixel(act->x-10, act->y-10).getAverage(), cost+heur, 10, heur, act);
			if(checkNext(next, opened, closed))
				opened.push_back(next);
		}

		if((act->x-10)>0) //5
		{
			
			double heur = sqrt(double((pow((act->x-10)-(end->x), 2.0)+pow((act->y)-(end->y), 2.0))));
			double cost = (((unsigned)hmap.getPixel(act->x, act->y).getAverage()-(unsigned)(hmap.getPixel(act->x-10, act->y).getAverage())/255)*0.4)+0.3;			
		
			Node *next = new Node(act->x-10, act->y, hmap.getPixel(act->x-10, act->y).getAverage(), cost+heur, 10, heur, act);
			if(checkNext(next, opened, closed))
				opened.push_back(next);
		}

		if((act->x-10)>0 && (act->y-10)>0) //6
		{
			
			double heur = sqrt(double((pow((act->x-10)-(end->x), 2.0)+pow((act->y-10)-(end->y), 2.0))));
			double cost = (((unsigned)hmap.getPixel(act->x, act->y-10).getAverage()-(unsigned)(hmap.getPixel(act->x-10, act->y-10).getAverage())/255)*0.4)+0.3;			
		
			Node *next = new Node(act->x-10, act->y-10, hmap.getPixel(act->x-10, act->y-10).getAverage(), cost+heur, 10, heur, act);
			if(checkNext(next, opened, closed))
				opened.push_back(next);
		}

		if((act->y-10)>0) //7
		{
			
			double heur = sqrt(double((pow((act->x)-(end->x), 2.0)+pow((act->y-10)-(end->y), 2.0))));
			double cost = (((unsigned)hmap.getPixel(act->x, act->y-10).getAverage()-(unsigned)(hmap.getPixel(act->x, act->y-10).getAverage())/255)*0.4)+0.3;			
		
			Node *next = new Node(act->x, act->y-10, hmap.getPixel(act->x, act->y-10).getAverage(), cost+heur, 10, heur, act);
			if(checkNext(next, opened, closed))
				opened.push_back(next);
		}

		if((act->x+10)<hmap.getDimension().Width && (act->y-10)>0) //8
		{
			
			double heur = sqrt(double((pow((act->x+10)-(end->x), 2.0)+pow((act->y-10)-(end->y), 2.0))));
			double cost = (((unsigned)hmap.getPixel(act->x, act->y-10).getAverage()-(unsigned)(hmap.getPixel(act->x+10, act->y-10).getAverage())/255)*0.4)+0.3;			
		
			Node *next = new Node(act->x+10, act->y-10, hmap.getPixel(act->x+10, act->y-10).getAverage(), cost+heur, 10, heur, act);
			if(checkNext(next, opened, closed))
				opened.push_back(next);
		}

		closed.push_back(act);
		if(find(opened.begin(), opened.end(), act)!=opened.end())
			opened.erase(find(opened.begin(), opened.end(), act));

		opened.sort(compare_cost);

	
	
}			
		


			




std::stack<Node* > generatePath(Node *start, Node *end, const video::IImage &hmap)
{
	
	std::stack<Node*> paths;
	std::list<Node*> opened;
	std::list<Node*> closed;
	

	if(start->x == end->x && start->y == start->y)
	{
		return paths;
	}

	opened.push_back(start);

	generatePathImpl(start, end, hmap, opened, closed);
	
	while (opened.size() != 0)
	{
		start = (*opened.begin());
		opened.pop_front();
		generatePathImpl(start, end, hmap, opened, closed);
	}
	for(std::list<Node*>::iterator iter = closed.begin(); iter!=closed.end(); ++iter)
	{
		if((*iter)->x == end->x && (*iter)->y == end->y)
		{
			for(Node* act = (*iter); act != 0; act=act->parent)	{
				paths.push(act);				
			}

			return paths;
		}
	}


	return paths;
	
		
}


Ich denke für Leute, die den Algorithmus kennen, brauche ich nicht viel weiter sagen. Die Kosten werden anhand einer Gewichtung von Weg und Höhenunterschied errechnet, die Heuristik ist lediglich jeweils die Luftlinie ohne Höhenunterschied. hmap ist lediglich das Bild, ich hole mir jeweils die Farbwerte für den Höhenunterschied. Die Schritte sind jeweils sozusagen von einem Punkt, dort jeweils die angrenzenden Punkte (d. h. seitlich/oben/unten/Diagonalen), die Diagonalen sind teurer vom Weg her als "normale"(hier wird der Satz von Pythagoras verwendet).

Bei Fragen, bitte melden.

Momentan läuft und läuft das ganze und wird nicht fertig. Ich habe das ganze lediglich auf dem Wikipediaartikel aufgebaut: http://de.wikipedia.org/wiki/A*-Algorithmus ; daher bitte ich um Nachsicht ;)


Vielen Dank!
 
Zuletzt bearbeitet:
Ohne jetzt den Code angeguckt zu haben: Funktionieren nichtmal Minimalbeispiele wie von 1,2 nach 2,2 zu gehen?

Wenn ich dich richtig verstanden habe, ist prinzipiell jeder der 7 (von einem kommt man ja) Nachbarpixel ein möglicher Nachfolger, da Steigung nie zu hoch sein kann - nur unverhältnismäßig teuer.
Evtl sprengts einfach den Rahmen, weil der Möglichkeitenraum ja stark mit der Anzahl der Pixel im Bild wächst? Darum auch meineFrage nach dem Minimalbeispiel.
Wie verhält sich denn ansonsten der Speicherbedarf beim endlosen laufen?

Der begrenzende Faktor bei A* ist oft nicht die Rechenzeit, sondern der Speicherplatz. Da alle bekannten Knoten im Speicher gehalten werden (Open und Closed List), ist A* für viele Probleme nicht geeignet. Schon beim einfachen 15-Puzzle hat der komplette Graph bereits 16! = 20.922.789.888.000 Knoten. Bei einem entsprechend langen Lösungsweg reicht der verfügbare Speicher nicht aus und A* kann keine Lösung finden. Im Abschnitt Verwandte Algorithmen finden sich ähnliche Algorithmen, die versuchen, den Speicherplatzverbrauch zu beschränken.
Zum Vergrößern anklicken....
von http://de.wikipedia.org/wiki/A*-Algorithmus#Nachteile
 
Zuletzt bearbeitet:
So, ich habe zunächst mal den Code eben geändert. Nun funktioniert es soweit. Also bie 50x50 ist es kein Problem, bei 640x640 dagegen schon, da es einfach zu lange dauert.

Ich denke mal, dass das mehr an meinem Code liegt, vll. weiß ja jemand weiter.

@kuddlmuddl: Richtig, allerdings habe ich ja eigentlich nur 64x64 Knoten bei 640x640, da ich nur alle 10 Pixel einen Knoten mache, das sollte doch machbar sein (?).

Hier mal das Ergebnis (grüne Punkte sind jeweils die ausgewählten Knoten):
newPicture.bmp
 
Zuletzt bearbeitet:
Kleiner Tipp:
Nimm lieber blau zur Veranschaulichung der Punkte.
Mein Bruder hat bei seinem neuen Monitor einen blauen Subpixel defekt. Den sieht man bei allen Grau- und Schwarztönen verdammt stark aufleuchten. :D
 
Eben ausprobiert, sieht man bei mir aber um einiges schlechter^^. Liegt vll. auch am Monitor ;)
 
badday schrieb:
Richtig, allerdings habe ich ja eigentlich nur 64x64 Knoten bei 640x640, da ich nur alle 10 Pixel einen Knoten mache, das sollte doch machbar sein (?).
Zum Vergrößern anklicken....
Ist der richtige Ansatz.
In vielen Spielen werden sogar zwei oder drei Ebenen an Knoten verwendet.
Auf kurzen Entfernungen sind die Knoten dann z.B. 10x10 Pixel groß und je weiter die Entfernung desto größer werden die Knoten.
Also z.B. 50x50 Pixel oder sogar 100x100 Pixel für einen Knoten.

Ein weiteres Kriterium ist, dass du die Knoten in einer Liste speicherst. Das ist nicht sehr effizient. Da würde sich ein "Binary Heap" besser eignen.

Noch ein paar Links:
http://www.policyalmanac.org/games/aStarTutorial_de.html
Nach einer Erklärung des A*-Algorithmus folgen noch weitere Anmerkungen.
Da sind besonders Punkt 6: "Einige Tipps zur Geschwindigkeit" und Punkt 7: "Verwaltung der offenen Liste" interessant.

Ansonsten hätte ich noch http://theory.stanford.edu/~amitp/GameProgramming/ (habs mir aber nicht weiter angeschaut).
 
So, ich habe das ganze nun optimiert, bin nun im ms Bereich :)

Ich habe folgendes gemacht: Neuer Knoten wird nur erstellt, wenn x und y noch nicht vorhanden waren, sprich, wenn der Knoten "wirklich neu" ist. Sonst (wenn es einen besseren Weg gibt) werden nur Kosten und parent-Knoten angepasst. Des weiteren wird nun nicht mehr immer die komplette Liste durchlaufen, um jeweils x/y zu vergleichen, sondern es gibt ein kleines openedSet und closedSet, die jeweils nur x/y Koordinaten enthalten. Damit kann ich immer einfach schauen, ob ein Knoten in der closed list ist etc.


Danke nochmal an alle, die mir geholfen haben! Und: Man sieht grün doch besser als blau ;)
 
Oh was mir beim Lesen deiner Optimierungen gerade einfällt - habe ich von wem anderen mal gehört die Idee:
Anstatt in den Listen zu suchen, ob schon ein bestimmtes Element drin ist und es nur einzufügen falls nicht kann man auch eine leere Kopie des Bildes (schwarze Pixel) als "Datenbank" verwenden.
8bit je pixel kann man ja wie 8 flags behandeln.
zB das erste Bit setzen, falls der korrespondierende Pixel in der closed eingefügt wurde und das 2te wenn es in die opened Liste eingefügt wurde etc.
So hat man nur O(1) Nachschlagezeit je Pixel. Und da das Nachsehen ja sehr oft geschieht, spart man so evtl auch viel Zeit

Was mich persönlich interessieren würde: Läufts nun schnell genug um Pixelweise (ohne 10er Übersprung) Wege zu berechnen? Musst aber nicht ausprobieren, falls es Arbeit macht^^
 
Zuletzt bearbeitet:
ich würde da ja eher dazu tendieren 2 punkte zu setzen und eine funktion zu schreiben die diese punkte sinnvoll verbindet. Dazu würde ich ein multiagentensystem implementieren das dir einen sinvollen weg von PA zu PB findet. Dazu musst du einfach steigungen gewichten (du willst ja einen weg der sich durch "das tal" schlängelt schätze ich. Den ersten gefundenen weg musst du dann "nur" noch mit einem filter nachfahren der die umgebung miteinbezieht und dir einen ebenen weg erstellt.
 
@Dr. Greg House: Von was genau möchtest du Screeens?

@kuddlmuddl: Naja, ich denke es ist schon ein aktzeptabler Grad an Effizienz erreicht für mein Vorhaben. Bei einer Pixelweise Berechnung dauert es nach wie vor relativ lange, allerdings weiß ich nicht, ob es nicht auch bei der Optimierung mit der Datenbank zu einer merklichen Verzögerung kommen würde.

@bluebarcode: Ich gewichte aktuell schon Steigungen, das Resultat ist eigentlich genau, wie ich mir das vorgestellt habe ;)
 
Du musst dich einloggen oder registrieren, um hier zu antworten.

Ähnliche Themen

CyborgBeta
Wie kann man die Generierung von desktop.ini-Dateien stoppen?
Antworten
11
Aufrufe
1.521
PC295
PC295
D
RTX 3090 (oder Alternative) + Netzteil für ComfyUI (AI-Bild-/Video-Generierung)?
Antworten
5
Aufrufe
1.479
dec.fx
D
Shader
Lokale automatische Generierung von Untertiteln? AI vielleicht?
2
Antworten
24
Aufrufe
1.356
andy_m4
andy_m4
T
Eure Erfahrungen: Webhoster für kleines Business (PDF-Generierung/Mailversand)
Antworten
14
Aufrufe
1.326
te one
T
Gameforce
  • Gesperrt
Suche Laserdrucker mit integr. Scanner inkl. ADF und autom. PDF Generierung
Antworten
6
Aufrufe
1.858
AdoK
A
Zurück
Oben

Willkommen auf ComputerBase!

Mit Werbung weiterlesen

Besuche ComputerBase wie gewohnt mit Werbung und Tracking. Die Zustimmung ist jederzeit widerrufbar.

Details im Privacy Center und in der Liste unserer Partner. Ein Widerruf ist möglich in der Datenschutzerklärung.

… oder ComputerBase Pro bestellen

Nutze ComputerBase ohne Werbebanner, Video-Ads und Werbetracking schon für 4 €/Monat oder 36 €/Jahr.

Mehr zu ComputerBase Pro

Bereits Pro-Nutzer? Hier anmelden.

Tracking: Wir und unsere 187 Partner verarbeiten personenbezogene Daten, indem wir mit auf Ihrem Gerät gespeicherten Informationen (z. B. eindeutige Kennungen in Cookies) ein Nutzungsprofil erstellen, um z. B. Anzeigen zu personalisieren. Verarbeitungszwecke: Genaue Standortdaten und Abfrage von Geräteeigenschaften zur Identifikation, Informationen auf einem Gerät speichern und/oder abrufen, Personalisierte Anzeigen und Inhalte, Anzeigen- und Inhaltsmessungen, Erkenntnisse über Zielgruppen und Produktentwicklungen.

Impressum Kontakt Datenschutz