Testköra min A* algoritm - Vad tycker ni?
Re: Testköra min A* algoritm - Vad tycker ni?
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 ?
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 ?
Re: Testköra min A* algoritm - Vad tycker ni?
Uppdatering! Nu använder jag L1 Norm och L2 norm. Här är ett exempel.
För er som är intresserad utav praktiken. Ni kan själv köra mitt exempel:
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.
För er som är intresserad utav praktiken. 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;
}
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!
}
}
}
}
Du har inte behörighet att öppna de filer som bifogats till detta inlägg.
Re: Testköra min A* algoritm - Vad tycker ni?
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
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
Re: Testköra min A* algoritm - Vad tycker ni?
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 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:
Re: Testköra min A* algoritm - Vad tycker ni?
Koden kompilerar inte. Har du någon version som faktiskt går igenom kompilatorn?
Re: Testköra min A* algoritm - Vad tycker ni?
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?
"_print_int", referenced from:
_main in main.o
Kan du själv kompilera det du skrivit i den här tråden?
Re: Testköra min A* algoritm - Vad tycker ni?
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.
Testa med programmet från första inlägg. Den uppdaterar jag hela tiden. Har åtgärdat print nu i första inlägg.
Re: Testköra min A* algoritm - Vad tycker ni?
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.adent skrev: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
Re: Testköra min A* algoritm - Vad tycker ni?
A* är alltid bättre än Dijkstra. Finns undantag där Dijkstra är snabbare. Men det är inte många hundradelar.davidi skrev: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:
Re: Testköra min A* algoritm - Vad tycker ni?
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.
Re: Testköra min A* algoritm - Vad tycker ni?
Funkar fortfarande inte, lyckas du själv kompilera det du laddat upp i tråden?DanielM skrev: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.
Undefined symbols for architecture x86_64:
"_print", referenced from:
_show_path in main.o
Re: Testköra min A* algoritm - Vad tycker ni?
Jag lyckas med mycket. Även det omöjliga.
Testa nu då? Första inlägg.
Testa nu då? Första inlägg.
Re: Testköra min A* algoritm - Vad tycker ni?
Det är enkelt att visa teori och tanke bekom det hela. Men att praktiskt tillämpa set är annat.davidi skrev: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 bättre än Dijkstra av alla gånger i verkligheten.
Re: Testköra min A* algoritm - Vad tycker ni?
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*.davidi skrev: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.
Det viktigaste inom planering är inte att hitta kortaste vägen. Det viktigaste är att den är snabb.