Testköra min A* algoritm - Vad tycker ni?

[DanielM]

Men då måste jag sätta ut dessa kostnader manuellt?
Hur ska jag tala om för min algoritm att det är kortare väg att gå till höger än vänster, på grund utav att det finns en mur i vägen?

Som jag gör just nu så använder jag bara L2 norm för att beräkna kortaste vägen. Eller andra ord, fågelvägen.
Om du har några andra sätt att låta algoritmen, från en slumpmässig godtycklig karta, skapa alla vikter, helt automatiskt. Då är jag riktigt intresserad.

Tror ni att L1 norm skulle passa bättre ?

[DanielM]

Uppdatering! Nu använder jag L1 Norm och L2 norm. Här är ett exempel.

Markering_001.png

För er som är intresserad utav praktiken.

Norm.png

Ni kan själv köra mitt exempel:

Kod: Markera allt

int main() {

	// Beginning coordinates
	int x_start = 1;
	int y_start = 8;

	// End coordinates
	int x_stop = 8;
	int y_stop = 8;

	// Path - Our goal is to find them
	int path_x[height_map * width_map];
	int path_y[height_map * width_map];

	// Norm modes
	int norm1 = 1; // L1-Norm
	int norm2 = 2; // L2-Norm

	// Steps
	int steps1 = 0;
	int steps2 = 0;

	// Map size
	int map[height_map*width_map] = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
									 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
									 -1, -1,  0,  0,  0,  0,  0,  0,  0, -1,
									 -1, -1,  0, -1, -1, -1, -1, -1,  0, -1,
									 -1, -1,  0, -1,  0,  0,  0, -1,  0, -1,
									 -1, -1,  0, -1,  0, -1,  0, -1,  0, -1,
									 -1, -1,  0, -1,  0, -1,  0, -1,  0, -1,
									 -1, -1,  0, -1,  0, -1,  0, -1,  0, -1,
									 -1,  0,  0,  0,  0, -1,  0, -1,  0, -1,
									 -1, -1, -1, -1, -1, -1,  0, -1,  0, -1,
									 -1, -1,  0,  0,  0,  0,  0, -1,  0, -1,
									 -1, -1,  0,  0, -1, -1, -1, -1,  0, -1,
									 -1, -1,  0,  0,  0,  0,  0,  0,  0, -1,
									 -1, -1, -1, -1, -1,  0, -1, -1,  0, -1,
									 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1};

	// Print the map
	printf("Initial map\n");
	print_int(map, height_map, width_map);

	// Compute the "shortest" path
	printf("Compute the coordinates\n");
	clock_t start, end;
	float cpu_time_used;
	start = clock();

	// First compute with L1-Norm and check the steps
	Astar(map, path_x, path_y, x_start, y_start, x_stop, y_stop, height_map, width_map, norm1, &steps1);
	// Then compute with L2-norm and check the steps
	Astar(map, path_x, path_y, x_start, y_start, x_stop, y_stop, height_map, width_map, norm2, &steps2);
	// Check the steps now - Which of the norms results less steps
	if(steps2 > steps1){
		Astar(map, path_x, path_y, x_start, y_start, x_stop, y_stop, height_map, width_map, norm1, &steps1); // Get the path again
		printf("Shortest step is = %d\n", steps1);
	}else{
		printf("Shortest step is = %d\n", steps2);
	}

	end = clock();
	cpu_time_used = ((float) (end - start)) / CLOCKS_PER_SEC;
	printf("\nTotal speed  was %f,", cpu_time_used);

	// Show the path
	printf("\nComputed map\n");
	show_path(map, path_x, path_y, height_map, width_map);

	// Show the path
	for (int i = 0; i < height_map * width_map; i++)
		printf("x = %d, y = %d\n", path_x[i], path_y[i]);


	return EXIT_SUCCESS;
}

Nu har jag även gjort det superenkelt för er att kunna lägga till heuristik i programmet.Bara fyll på här och testa algoritmen. En god rekommendation är att använda olika former av normer.

Kod: Markera allt

// norm_mode = 2 -> L2 norm
// norm_mode = 1 -> L1 norm
static void heuristic_map(int *map, int x_stop, int y_stop, int height, int width, int norm_mode) {
	for (int i = 0; i < width; i++) {
		for (int j = 0; j < height; j++) {
			if (*(map + j * width + i) != -1) {
				int dx = (j + x_stop) - (j + i); 	// Distance we want to go in x-axis
				int dy = (y_stop + i) - (j + i);  	// Distance we want to go in y-axis
				if (norm_mode == 1)
					*(map + j * width + i) = abs(dx) + abs(dy); // L1-Norm
				if (norm_mode == 2)
					*(map + j * width + i) = dx * dx + dy * dy; // L2-Norm (without square root, not needed due to integers)
				// You can add more heuristic here!
			}
		}
	}
}

[adent]

Algoritmen kommer om den heuretiska (stavning?) funktionen är vettig alltid att generera den kortaste vägen även om du har hinder ivägen.

Min kod är inget vidare vacker och inte avsedd för embedded och lite obegriplig. Jag gjorde min karta till ett rutnät där det kostar 1 mellan vinkelräta rutor och rotenur(2) för diagonala rutor. Funktionen h() ger fågelvägen till målet.

Men min kod är i princip en direkt implementation av beskrivningen här:

https://en.wikipedia.org/wiki/A*_search ... Pseudocode

MVH: Mikael

[davidi]

För kartor av denna storlek, börja med att implementera Dijkstras algoritm. Den är lite enklare och hittar alltid kortaste vägen, så den kan åtminstone fungera som referens.

A* är en variant av Dijkstra som prioriterar noder som ligger närmare målet. Fördelen är att den inte i samma utsträckning räknar på noder som ligger längre bort från målet, men beroende på hur man viktar avståndet kan det innebära att den faktiskt missar närmaste vägen.

Här är två filmer från Computerphile som förklarar hur de fungerar på ett föredömligt pedagogiskt sätt:

[hummel]

Koden kompilerar inte. Har du någon version som faktiskt går igenom kompilatorn?

[DanielM]

Vad får du för felmeddelande?

[hummel]

Beror på vilket av dina program jag testar. Ett är en funktion som saknas Undefined symbols for architecture x86_64:
"_print_int", referenced from:
_main in main.o

Kan du själv kompilera det du skrivit i den här tråden?

[DanielM]

Finns en funktion som heter print. Döp om print till print_int.

Testa med programmet från första inlägg. Den uppdaterar jag hela tiden. Har åtgärdat print nu i första inlägg.

[DanielM]

Algoritmen kommer om den heuretiska (stavning?) funktionen är vettig alltid att generera den kortaste vägen även om du har hinder ivägen.

Min kod är inget vidare vacker och inte avsedd för embedded och lite obegriplig. Jag gjorde min karta till ett rutnät där det kostar 1 mellan vinkelräta rutor och rotenur(2) för diagonala rutor. Funktionen h() ger fågelvägen till målet.

Men min kod är i princip en direkt implementation av beskrivningen här:

https://en.wikipedia.org/wiki/A*_search ... Pseudocode

MVH: Mikael

Jo men....heruistik är ju inte gjort manuellt. Det är ju någon som har skapat t.ex funktioner och suttit och tänkt på hur funktionerna ska se ut.

[DanielM]

För kartor av denna storlek, börja med att implementera Dijkstras algoritm. Den är lite enklare och hittar alltid kortaste vägen, så den kan åtminstone fungera som referens.

A* är en variant av Dijkstra som prioriterar noder som ligger närmare målet. Fördelen är att den inte i samma utsträckning räknar på noder som ligger längre bort från målet, men beroende på hur man viktar avståndet kan det innebära att den faktiskt missar närmaste vägen.

Här är två filmer från Computerphile som förklarar hur de fungerar på ett föredömligt pedagogiskt sätt:

A* är alltid bättre än Dijkstra. Finns undantag där Dijkstra är snabbare. Men det är inte många hundradelar.

[davidi]

I grunden är de samma algoritm. Som jag just skrev så kommer Dijkstra alltid att hitta närmaste vägen. Det garanterar inte A*, även om den oftast gör det. Därför är Dijkstra en utmärkt referensalgoritm när du trimmar in din A*. Dessutom är den aningen enklare att implementera, eftersom man slipper bekymret med att räkna avstånd till målet.

[hummel]

Finns en funktion som heter print. Döp om print till print_int.

Testa med programmet från första inlägg. Den uppdaterar jag hela tiden. Har åtgärdat print nu i första inlägg.

Funkar fortfarande inte, lyckas du själv kompilera det du laddat upp i tråden?
Undefined symbols for architecture x86_64:
"_print", referenced from:
_show_path in main.o

[DanielM]

Jag lyckas med mycket. Även det omöjliga.

Testa nu då? Första inlägg.

[DanielM]

För kartor av denna storlek, börja med att implementera Dijkstras algoritm. Den är lite enklare och hittar alltid kortaste vägen, så den kan åtminstone fungera som referens.

A* är en variant av Dijkstra som prioriterar noder som ligger närmare målet. Fördelen är att den inte i samma utsträckning räknar på noder som ligger längre bort från målet, men beroende på hur man viktar avståndet kan det innebära att den faktiskt missar närmaste vägen.

Här är två filmer från Computerphile som förklarar hur de fungerar på ett föredömligt pedagogiskt sätt:

Det är enkelt att visa teori och tanke bekom det hela. Men att praktiskt tillämpa set är annat.

A* är bättre än Dijkstra av alla gånger i verkligheten.

[DanielM]

I grunden är de samma algoritm. Som jag just skrev så kommer Dijkstra alltid att hitta närmaste vägen. Det garanterar inte A*, även om den oftast gör det. Därför är Dijkstra en utmärkt referensalgoritm när du trimmar in din A*. Dessutom är den aningen enklare att implementera, eftersom man slipper bekymret med att räkna avstånd till målet.

Dijkstra är dessutom stegare. Använder du t.ex 2-3 normer för att beräkna distans så kommer du hitta den kortaste vägen med A*.

Det viktigaste inom planering är inte att hitta kortaste vägen. Det viktigaste är att den är snabb.