 |
Club Builder
Foro de C++Builder en español
|
| Ver tema anterior :: Ver tema siguiente |
| Autor |
Mensaje |
Alpinador
Lt Cmdr
Registrado: 21 Abr 2014Mensajes: 123
|
 Publicado: Mar 05 Ene, 2021 6:15 pm Asunto: ayuda con algoritmo A-Star |
 |
|
Hola people..... que tal.....estoy intentando implementar el AStar para busqueda de caminos teniendo en cuenta que puede haber "muros"
que impidan pasar por ahi (el numero 98 indica un muro) ....
el caso es que parece ser que hace mal el calculo de la "ruta" porque
cuando encuentra un muro en vez de evitarlo es como si no lo "viese"
lo que tengo es esto:
| Código: | using namespace std;
// Global data
// The world map
const int MAP_WIDTH = 140;
const int MAP_HEIGHT = 70;
int world_map[ MAP_WIDTH * MAP_HEIGHT ] =
{
1,2,2,2,2,2,2,2,2,98,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,
4,2,5,98,98,98,98,98,98,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,2,5,98,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,98,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,98,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
98,98,98,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,
10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,
1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,
10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,
1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,
10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,
1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,
10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,
1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,
10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,
1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,
10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,
1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,0,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,
7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,
10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,0,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,
};
// map helper functions
int GetMap( int x, int y )
{
if( x < 0 ||
x >= MAP_WIDTH ||
y < 0 ||
y >= MAP_HEIGHT
)
{
return 99;
}
return world_map[(y*MAP_WIDTH)+x];
}
// Definitions
class MapSearchNode
{
public:
int x; // the (x,y) positions of the node
int y;
MapSearchNode() { x = y = 0; }
MapSearchNode( int px, int py ) { x=px; y=py; }
float GoalDistanceEstimate( MapSearchNode &nodeGoal );
bool IsGoal( MapSearchNode &nodeGoal );
bool GetSuccessors( AStarSearch<MapSearchNode> *astarsearch, MapSearchNode *parent_node );
float GetCost( MapSearchNode &successor );
bool IsSameState( MapSearchNode &rhs );
void PrintNodeInfo();
};
bool MapSearchNode::IsSameState( MapSearchNode &rhs )
{
// same state in a maze search is simply when (x,y) are the same
if( (x == rhs.x) &&
(y == rhs.y) )
{
return true;
}
else
{
return false;
}
}
void MapSearchNode::PrintNodeInfo()
{
char str[100];
sprintf( str, "Node position : (%d,%d)\n", x,y );
path_map[path_count].coords.x = x;
path_map[path_count].coords.y = y;
//ShowMessage(AnsiString(path_map[path_count].coords.x) + "," + AnsiString(path_map[path_count].coords.y));
path_count++;
Form3->Memo2->Lines->Add(str);
Form3->Memo1->Lines->Add(IntToStr(x) + "::" + IntToStr(y));
}
// Here's the heuristic function that estimates the distance from a Node
// to the Goal.
float MapSearchNode::GoalDistanceEstimate( MapSearchNode &nodeGoal )
{
return abs(x - nodeGoal.x) + abs(y - nodeGoal.y);
}
bool MapSearchNode::IsGoal( MapSearchNode &nodeGoal )
{
if( (x == nodeGoal.x) &&
(y == nodeGoal.y) )
{
return true;
}
return false;
}
// This generates the successors to the given Node. It uses a helper function called
// AddSuccessor to give the successors to the AStar class. The A* specific initialisation
// is done for each node internally, so here you just set the state information that
// is specific to the application
bool MapSearchNode::GetSuccessors( AStarSearch<MapSearchNode> *astarsearch, MapSearchNode *parent_node )
{
int parent_x = -1;
int parent_y = -1;
if( parent_node )
{
parent_x = parent_node->x;
parent_y = parent_node->y;
}
MapSearchNode NewNode;
// push each possible move except allowing the search to go backwards
if( (GetMap( x-1, y ) < 98)
&& !((parent_x == x-1) && (parent_y == y))
)
{
NewNode = MapSearchNode( x-1, y );
astarsearch->AddSuccessor( NewNode );
}
if( (GetMap( x, y-1 ) < 98)
&& !((parent_x == x) && (parent_y == y-1))
)
{
NewNode = MapSearchNode( x, y-1 );
astarsearch->AddSuccessor( NewNode );
}
if( (GetMap( x+1, y ) < 98)
&& !((parent_x == x+1) && (parent_y == y))
)
{
NewNode = MapSearchNode( x+1, y );
astarsearch->AddSuccessor( NewNode );
}
if( (GetMap( x, y+1 ) < 98)
&& !((parent_x == x) && (parent_y == y+1))
)
{
NewNode = MapSearchNode( x, y+1 );
astarsearch->AddSuccessor( NewNode );
}
return true;
}
// given this node, what does it cost to move to successor. In the case
// of our map the answer is the map terrain value at this node since that is
// conceptually where we're moving
float MapSearchNode::GetCost( MapSearchNode &successor )
{
return (float) GetMap( x, y );
}
// Main
int ASTAR_pathfind(void)
{
Form3->Memo2->Clear();
Form3->Memo2->Lines->Add("STL A* Search implementation\n(C)2001 Justin Heyes-Jones\n");
path_count = 0;
// Our sample problem defines the world as a 2d array representing a terrain
// Each element contains an integer from 0 to 5 which indicates the cost
// of travel across the terrain. Zero means the least possible difficulty
// in travelling (think ice rink if you can skate) whilst 5 represents the
// most difficult. 9 indicates that we cannot pass.
// Create an instance of the search class...
AStarSearch<MapSearchNode> astarsearch;
unsigned int SearchCount = 0;
const unsigned int NumSearches = 1;
while(SearchCount < NumSearches)
{
// Create a start state
MapSearchNode nodeStart;
//nodeStart.x = rand()%MAP_WIDTH;
//nodeStart.y = rand()%MAP_HEIGHT;
nodeStart.x = 18;
nodeStart.y = 18;
// Define the goal state
MapSearchNode nodeEnd;
nodeEnd.x = 8;
nodeEnd.y = 0;
// Set Start and goal states
astarsearch.SetStartAndGoalStates( nodeStart, nodeEnd );
unsigned int SearchState;
unsigned int SearchSteps = 0;
do
{
SearchState = astarsearch.SearchStep();
SearchSteps++;
#if DEBUG_LISTS
Form3->Memo2->Lines->Add("Steps:" + IntToStr(SearchSteps) + "\n");
int len = 0;
Form3->Memo2->Lines->Add("Open:\n");
MapSearchNode *p = astarsearch.GetOpenListStart();
while( p )
{
len++;
#if !DEBUG_LIST_LENGTHS_ONLY
((MapSearchNode *)p)->PrintNodeInfo();
#endif
p = astarsearch.GetOpenListNext();
}
Form3->Memo2->Lines->Add("Open list has " + IntToStr(len) + " nodes\n");
len = 0;
Form3->Memo2->Lines->Add("Closed:\n");
p = astarsearch.GetClosedListStart();
while( p )
{
len++;
#if !DEBUG_LIST_LENGTHS_ONLY
p->PrintNodeInfo();
#endif
p = astarsearch.GetClosedListNext();
}
Form3->Memo2->Lines->Add("Closed list has " + IntToStr(len) + " nodes\n");
#endif
}
while( SearchState == AStarSearch<MapSearchNode>::SEARCH_STATE_SEARCHING );
if( SearchState == AStarSearch<MapSearchNode>::SEARCH_STATE_SUCCEEDED )
{
Form3->Memo2->Lines->Add("Search found goal state\n");
MapSearchNode *node = astarsearch.GetSolutionStart();
#if DISPLAY_SOLUTION
Form3->Memo2->Lines->Add("Displaying solution\n");
#endif
int steps = 0;
node->PrintNodeInfo();
for( ;; )
{
node = astarsearch.GetSolutionNext();
if( !node )
{
break;
}
node->PrintNodeInfo();
steps ++;
};
Form3->Memo2->Lines->Add("Solution steps " + IntToStr(steps));
path_map[path_count].coords.x = -1;
path_map[path_count].coords.y = -1;
// Once you're done with the solution you can free the nodes up
astarsearch.FreeSolutionNodes();
}
else if( SearchState == AStarSearch<MapSearchNode>::SEARCH_STATE_FAILED )
{
Form3->Memo2->Lines->Add("Search terminated. Did not find goal state\n");
}
// Display the number of loops the search went through
Form3->Memo2->Lines->Add("SearchSteps : " + AnsiString(SearchSteps) + "\n");
SearchCount ++;
astarsearch.EnsureMemoryFreed();
}
return 0;
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////
|
y luego un archivo de funciones que es este:
| Código: | /*
A* Algorithm Implementation using STL is
Copyright (C)2001-2005 Justin Heyes-Jones
Permission is given by the author to freely redistribute and
include this code in any program as long as this credit is
given where due.
COVERED CODE IS PROVIDED UNDER THIS LICENSE ON AN "AS IS" BASIS,
WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED,
INCLUDING, WITHOUT LIMITATION, WARRANTIES THAT THE COVERED CODE
IS FREE OF DEFECTS, MERCHANTABLE, FIT FOR A PARTICULAR PURPOSE
OR NON-INFRINGING. THE ENTIRE RISK AS TO THE QUALITY AND
PERFORMANCE OF THE COVERED CODE IS WITH YOU. SHOULD ANY COVERED
CODE PROVE DEFECTIVE IN ANY RESPECT, YOU (NOT THE INITIAL
DEVELOPER OR ANY OTHER CONTRIBUTOR) ASSUME THE COST OF ANY
NECESSARY SERVICING, REPAIR OR CORRECTION. THIS DISCLAIMER OF
WARRANTY CONSTITUTES AN ESSENTIAL PART OF THIS LICENSE. NO USE
OF ANY COVERED CODE IS AUTHORIZED HEREUNDER EXCEPT UNDER
THIS DISCLAIMER.
Use at your own risk!
*/
#ifndef STLASTAR_H
#define STLASTAR_H
// used for text debugging
#include <iostream>
#include <stdio.h>
//#include <conio.h>
#include <assert.h>
// stl includes
#include <algorithm>
#include <set>
#include <vector>
#include <cfloat>
using namespace std;
// fast fixed size memory allocator, used for fast node memory management
#include "fsa.h"
// Fixed size memory allocator can be disabled to compare performance
// Uses std new and delete instead if you turn it off
#define USE_FSA_MEMORY 1
// disable warning that debugging information has lines that are truncated
// occurs in stl headers
#if defined(WIN32) && defined(_WINDOWS)
#pragma warning( disable : 4786 )
#endif
template <class T> class AStarState;
// The AStar search class. UserState is the users state space type
template <class UserState> class AStarSearch
{
public: // data
enum
{
SEARCH_STATE_NOT_INITIALISED,
SEARCH_STATE_SEARCHING,
SEARCH_STATE_SUCCEEDED,
SEARCH_STATE_FAILED,
SEARCH_STATE_OUT_OF_MEMORY,
SEARCH_STATE_INVALID
};
// A node represents a possible state in the search
// The user provided state type is included inside this type
public:
class Node
{
public:
Node *parent; // used during the search to record the parent of successor nodes
Node *child; // used after the search for the application to view the search in reverse
float g; // cost of this node + it's predecessors
float h; // heuristic estimate of distance to goal
float f; // sum of cumulative cost of predecessors and self and heuristic
Node() :
parent( 0 ),
child( 0 ),
g( 0.0f ),
h( 0.0f ),
f( 0.0f )
{
}
UserState m_UserState;
};
// For sorting the heap the STL needs compare function that lets us compare
// the f value of two nodes
class HeapCompare_f
{
public:
bool operator() ( const Node *x, const Node *y ) const
{
return x->f > y->f;
}
};
public: // methods
// constructor just initialises private data
AStarSearch() :
m_State( SEARCH_STATE_NOT_INITIALISED ),
m_CurrentSolutionNode( NULL ),
#if USE_FSA_MEMORY
m_FixedSizeAllocator( 1000 ),
#endif
m_AllocateNodeCount(0),
m_CancelRequest( false )
{
}
AStarSearch( int MaxNodes ) :
m_State( SEARCH_STATE_NOT_INITIALISED ),
m_CurrentSolutionNode( NULL ),
#if USE_FSA_MEMORY
m_FixedSizeAllocator( MaxNodes ),
#endif
m_AllocateNodeCount(0),
m_CancelRequest( false )
{
}
// call at any time to cancel the search and free up all the memory
void CancelSearch()
{
m_CancelRequest = true;
}
// Set Start and goal states
void SetStartAndGoalStates( UserState &Start, UserState &Goal )
{
m_CancelRequest = false;
m_Start = AllocateNode();
m_Goal = AllocateNode();
assert((m_Start != NULL && m_Goal != NULL));
m_Start->m_UserState = Start;
m_Goal->m_UserState = Goal;
m_State = SEARCH_STATE_SEARCHING;
// Initialise the AStar specific parts of the Start Node
// The user only needs fill out the state information
m_Start->g = 0;
m_Start->h = m_Start->m_UserState.GoalDistanceEstimate( m_Goal->m_UserState );
m_Start->f = m_Start->g + m_Start->h;
m_Start->parent = 0;
// Push the start node on the Open list
m_OpenList.push_back( m_Start ); // heap now unsorted
// Sort back element into heap
push_heap( m_OpenList.begin(), m_OpenList.end(), HeapCompare_f() );
// Initialise counter for search steps
m_Steps = 0;
}
// Advances search one step
unsigned int SearchStep()
{
// Firstly break if the user has not initialised the search
assert( (m_State > SEARCH_STATE_NOT_INITIALISED) &&
(m_State < SEARCH_STATE_INVALID) );
// Next I want it to be safe to do a searchstep once the search has succeeded...
if( (m_State == SEARCH_STATE_SUCCEEDED) ||
(m_State == SEARCH_STATE_FAILED)
)
{
return m_State;
}
// Failure is defined as emptying the open list as there is nothing left to
// search...
// New: Allow user abort
if( m_OpenList.empty() || m_CancelRequest )
{
FreeAllNodes();
m_State = SEARCH_STATE_FAILED;
return m_State;
}
// Incremement step count
m_Steps ++;
// Pop the best node (the one with the lowest f)
Node *n = m_OpenList.front(); // get pointer to the node
pop_heap( m_OpenList.begin(), m_OpenList.end(), HeapCompare_f() );
m_OpenList.pop_back();
// Check for the goal, once we pop that we're done
if( n->m_UserState.IsGoal( m_Goal->m_UserState ) )
{
// The user is going to use the Goal Node he passed in
// so copy the parent pointer of n
m_Goal->parent = n->parent;
m_Goal->g = n->g;
// A special case is that the goal was passed in as the start state
// so handle that here
if( false == n->m_UserState.IsSameState( m_Start->m_UserState ) )
{
FreeNode( n );
// set the child pointers in each node (except Goal which has no child)
Node *nodeChild = m_Goal;
Node *nodeParent = m_Goal->parent;
do
{
nodeParent->child = nodeChild;
nodeChild = nodeParent;
nodeParent = nodeParent->parent;
}
while( nodeChild != m_Start ); // Start is always the first node by definition
}
// delete nodes that aren't needed for the solution
FreeUnusedNodes();
m_State = SEARCH_STATE_SUCCEEDED;
return m_State;
}
else // not goal
{
// We now need to generate the successors of this node
// The user helps us to do this, and we keep the new nodes in
// m_Successors ...
m_Successors.clear(); // empty vector of successor nodes to n
// User provides this functions and uses AddSuccessor to add each successor of
// node 'n' to m_Successors
bool ret = n->m_UserState.GetSuccessors( this, n->parent ? &n->parent->m_UserState : NULL );
if( !ret )
{
typename vector< Node * >::iterator successor;
// free the nodes that may previously have been added
for( successor = m_Successors.begin(); successor != m_Successors.end(); successor ++ )
{
FreeNode( (*successor) );
}
m_Successors.clear(); // empty vector of successor nodes to n
// free up everything else we allocated
FreeNode( (n) );
FreeAllNodes();
m_State = SEARCH_STATE_OUT_OF_MEMORY;
return m_State;
}
// Now handle each successor to the current node ...
for( typename vector< Node * >::iterator successor = m_Successors.begin(); successor != m_Successors.end(); successor ++ )
{
// The g value for this successor ...
float newg = n->g + n->m_UserState.GetCost( (*successor)->m_UserState );
// Now we need to find whether the node is on the open or closed lists
// If it is but the node that is already on them is better (lower g)
// then we can forget about this successor
// First linear search of open list to find node
typename vector< Node * >::iterator openlist_result;
for( openlist_result = m_OpenList.begin(); openlist_result != m_OpenList.end(); openlist_result ++ )
{
if( (*openlist_result)->m_UserState.IsSameState( (*successor)->m_UserState ) )
{
break;
}
}
if( openlist_result != m_OpenList.end() )
{
// we found this state on open
if( (*openlist_result)->g <= newg )
{
FreeNode( (*successor) );
// the one on Open is cheaper than this one
continue;
}
}
typename vector< Node * >::iterator closedlist_result;
for( closedlist_result = m_ClosedList.begin(); closedlist_result != m_ClosedList.end(); closedlist_result ++ )
{
if( (*closedlist_result)->m_UserState.IsSameState( (*successor)->m_UserState ) )
{
break;
}
}
if( closedlist_result != m_ClosedList.end() )
{
// we found this state on closed
if( (*closedlist_result)->g <= newg )
{
// the one on Closed is cheaper than this one
FreeNode( (*successor) );
continue;
}
}
// This node is the best node so far with this particular state
// so lets keep it and set up its AStar specific data ...
(*successor)->parent = n;
(*successor)->g = newg;
(*successor)->h = (*successor)->m_UserState.GoalDistanceEstimate( m_Goal->m_UserState );
(*successor)->f = (*successor)->g + (*successor)->h;
// Successor in closed list
// 1 - Update old version of this node in closed list
// 2 - Move it from closed to open list
// 3 - Sort heap again in open list
if( closedlist_result != m_ClosedList.end() )
{
// Update closed node with successor node AStar data
//*(*closedlist_result) = *(*successor);
(*closedlist_result)->parent = (*successor)->parent;
(*closedlist_result)->g = (*successor)->g;
(*closedlist_result)->h = (*successor)->h;
(*closedlist_result)->f = (*successor)->f;
// Free successor node
FreeNode( (*successor) );
// Push closed node into open list
m_OpenList.push_back( (*closedlist_result) );
// Remove closed node from closed list
m_ClosedList.erase( closedlist_result );
// Sort back element into heap
push_heap( m_OpenList.begin(), m_OpenList.end(), HeapCompare_f() );
// Fix thanks to ...
// Greg Douglas <gregdouglasmail@gmail.com>
// who noticed that this code path was incorrect
// Here we have found a new state which is already CLOSED
}
// Successor in open list
// 1 - Update old version of this node in open list
// 2 - sort heap again in open list
else if( openlist_result != m_OpenList.end() )
{
// Update open node with successor node AStar data
//*(*openlist_result) = *(*successor);
(*openlist_result)->parent = (*successor)->parent;
(*openlist_result)->g = (*successor)->g;
(*openlist_result)->h = (*successor)->h;
(*openlist_result)->f = (*successor)->f;
// Free successor node
FreeNode( (*successor) );
// re-make the heap
// make_heap rather than sort_heap is an essential bug fix
// thanks to Mike Ryynanen for pointing this out and then explaining
// it in detail. sort_heap called on an invalid heap does not work
make_heap( m_OpenList.begin(), m_OpenList.end(), HeapCompare_f() );
}
// New successor
// 1 - Move it from successors to open list
// 2 - sort heap again in open list
else
{
// Push successor node into open list
m_OpenList.push_back( (*successor) );
// Sort back element into heap
push_heap( m_OpenList.begin(), m_OpenList.end(), HeapCompare_f() );
}
}
// push n onto Closed, as we have expanded it now
m_ClosedList.push_back( n );
} // end else (not goal so expand)
return m_State; // Succeeded bool is false at this point.
}
// User calls this to add a successor to a list of successors
// when expanding the search frontier
bool AddSuccessor( UserState &State )
{
Node *node = AllocateNode();
if( node )
{
node->m_UserState = State;
m_Successors.push_back( node );
return true;
}
return false;
}
// Free the solution nodes
// This is done to clean up all used Node memory when you are done with the
// search
void FreeSolutionNodes()
{
Node *n = m_Start;
if( m_Start->child )
{
do
{
Node *del = n;
n = n->child;
FreeNode( del );
del = NULL;
} while( n != m_Goal );
FreeNode( n ); // Delete the goal
}
else
{
// if the start node is the solution we need to just delete the start and goal
// nodes
FreeNode( m_Start );
FreeNode( m_Goal );
}
}
// Functions for traversing the solution
// Get start node
UserState *GetSolutionStart()
{
m_CurrentSolutionNode = m_Start;
if( m_Start )
{
return &m_Start->m_UserState;
}
else
{
return NULL;
}
}
// Get next node
UserState *GetSolutionNext()
{
if( m_CurrentSolutionNode )
{
if( m_CurrentSolutionNode->child )
{
Node *child = m_CurrentSolutionNode->child;
m_CurrentSolutionNode = m_CurrentSolutionNode->child;
return &child->m_UserState;
}
}
return NULL;
}
// Get end node
UserState *GetSolutionEnd()
{
m_CurrentSolutionNode = m_Goal;
if( m_Goal )
{
return &m_Goal->m_UserState;
}
else
{
return NULL;
}
}
// Step solution iterator backwards
UserState *GetSolutionPrev()
{
if( m_CurrentSolutionNode )
{
if( m_CurrentSolutionNode->parent )
{
Node *parent = m_CurrentSolutionNode->parent;
m_CurrentSolutionNode = m_CurrentSolutionNode->parent;
return &parent->m_UserState;
}
}
return NULL;
}
// Get final cost of solution
// Returns FLT_MAX if goal is not defined or there is no solution
float GetSolutionCost()
{
if( m_Goal && m_State == SEARCH_STATE_SUCCEEDED )
{
return m_Goal->g;
}
else
{
return FLT_MAX;
}
}
// For educational use and debugging it is useful to be able to view
// the open and closed list at each step, here are two functions to allow that.
UserState *GetOpenListStart()
{
float f,g,h;
return GetOpenListStart( f,g,h );
}
UserState *GetOpenListStart( float &f, float &g, float &h )
{
iterDbgOpen = m_OpenList.begin();
if( iterDbgOpen != m_OpenList.end() )
{
f = (*iterDbgOpen)->f;
g = (*iterDbgOpen)->g;
h = (*iterDbgOpen)->h;
return &(*iterDbgOpen)->m_UserState;
}
return NULL;
}
UserState *GetOpenListNext()
{
float f,g,h;
return GetOpenListNext( f,g,h );
}
UserState *GetOpenListNext( float &f, float &g, float &h )
{
iterDbgOpen++;
if( iterDbgOpen != m_OpenList.end() )
{
f = (*iterDbgOpen)->f;
g = (*iterDbgOpen)->g;
h = (*iterDbgOpen)->h;
return &(*iterDbgOpen)->m_UserState;
}
return NULL;
}
UserState *GetClosedListStart()
{
float f,g,h;
return GetClosedListStart( f,g,h );
}
UserState *GetClosedListStart( float &f, float &g, float &h )
{
iterDbgClosed = m_ClosedList.begin();
if( iterDbgClosed != m_ClosedList.end() )
{
f = (*iterDbgClosed)->f;
g = (*iterDbgClosed)->g;
h = (*iterDbgClosed)->h;
return &(*iterDbgClosed)->m_UserState;
}
return NULL;
}
UserState *GetClosedListNext()
{
float f,g,h;
return GetClosedListNext( f,g,h );
}
UserState *GetClosedListNext( float &f, float &g, float &h )
{
iterDbgClosed++;
if( iterDbgClosed != m_ClosedList.end() )
{
f = (*iterDbgClosed)->f;
g = (*iterDbgClosed)->g;
h = (*iterDbgClosed)->h;
return &(*iterDbgClosed)->m_UserState;
}
return NULL;
}
// Get the number of steps
int GetStepCount() { return m_Steps; }
void EnsureMemoryFreed()
{
#if USE_FSA_MEMORY
assert(m_AllocateNodeCount == 0);
#endif
}
private: // methods
// This is called when a search fails or is cancelled to free all used
// memory
void FreeAllNodes()
{
// iterate open list and delete all nodes
typename vector< Node * >::iterator iterOpen = m_OpenList.begin();
while( iterOpen != m_OpenList.end() )
{
Node *n = (*iterOpen);
FreeNode( n );
iterOpen ++;
}
m_OpenList.clear();
// iterate closed list and delete unused nodes
typename vector< Node * >::iterator iterClosed;
for( iterClosed = m_ClosedList.begin(); iterClosed != m_ClosedList.end(); iterClosed ++ )
{
Node *n = (*iterClosed);
FreeNode( n );
}
m_ClosedList.clear();
// delete the goal
FreeNode(m_Goal);
}
// This call is made by the search class when the search ends. A lot of nodes may be
// created that are still present when the search ends. They will be deleted by this
// routine once the search ends
void FreeUnusedNodes()
{
// iterate open list and delete unused nodes
typename vector< Node * >::iterator iterOpen = m_OpenList.begin();
while( iterOpen != m_OpenList.end() )
{
Node *n = (*iterOpen);
if( !n->child )
{
FreeNode( n );
n = NULL;
}
iterOpen ++;
}
m_OpenList.clear();
// iterate closed list and delete unused nodes
typename vector< Node * >::iterator iterClosed;
for( iterClosed = m_ClosedList.begin(); iterClosed != m_ClosedList.end(); iterClosed ++ )
{
Node *n = (*iterClosed);
if( !n->child )
{
FreeNode( n );
n = NULL;
}
}
m_ClosedList.clear();
}
// Node memory management
Node *AllocateNode()
{
#if !USE_FSA_MEMORY
m_AllocateNodeCount ++;
Node *p = new Node;
return p;
#else
Node *address = m_FixedSizeAllocator.alloc();
if( !address )
{
return NULL;
}
m_AllocateNodeCount ++;
Node *p = new (address) Node;
return p;
#endif
}
void FreeNode( Node *node )
{
m_AllocateNodeCount --;
#if !USE_FSA_MEMORY
delete node;
#else
node->~Node();
m_FixedSizeAllocator.free( node );
#endif
}
private: // data
// Heap (simple vector but used as a heap, cf. Steve Rabin's game gems article)
vector< Node *> m_OpenList;
// Closed list is a vector.
vector< Node * > m_ClosedList;
// Successors is a vector filled out by the user each type successors to a node
// are generated
vector< Node * > m_Successors;
// State
unsigned int m_State;
// Counts steps
int m_Steps;
// Start and goal state pointers
Node *m_Start;
Node *m_Goal;
Node *m_CurrentSolutionNode;
#if USE_FSA_MEMORY
// Memory
FixedSizeAllocator<Node> m_FixedSizeAllocator;
#endif
//Debug : need to keep these two iterators around
// for the user Dbg functions
typename vector< Node * >::iterator iterDbgOpen;
typename vector< Node * >::iterator iterDbgClosed;
// debugging : count memory allocation and free's
int m_AllocateNodeCount;
bool m_CancelRequest;
};
template <class T> class AStarState
{
public:
virtual ~AStarState() {}
virtual float GoalDistanceEstimate( T &nodeGoal ) = 0; // Heuristic function which computes the estimated cost to the goal node
virtual bool IsGoal( T &nodeGoal ) = 0; // Returns true if this node is the goal node
virtual bool GetSuccessors( AStarSearch<T> *astarsearch, T *parent_node ) = 0; // Retrieves all successors to this node and adds them via astarsearch.addSuccessor()
virtual float GetCost( T &successor ) = 0; // Computes the cost of travelling from this node to the successor node
virtual bool IsSameState( T &rhs ) = 0; // Returns true if this node is the same as the rhs node
};
#endif
|
no se.... no me acaba de funcionar bien.....alguien podria ayudarme?
lo que obtengo es esto:
https://image.prntscr.com/image/AWwffk8cRN2OqU3Q-4WAPw.png |
|
| Volver arriba |
|
 |
Alpinador
Lt Cmdr
Registrado: 21 Abr 2014Mensajes: 123
|
| Publicado: Mie 06 Ene, 2021 12:44 pm Asunto: |
|
|
por ejemplo ahi el punto de partida es el tile 18,18 (abajo) y sube hasta el 8,0 que es el destino pero como ves....el muro lo pasa por encima
cuando lo que deberia hacer es pasar entre el hueco de los 2 trozos de muro de arriba a la izquierda y entrar por el hueco libre
por mas que miro no veo donde "comprueba" si es un MURO (valor 9 porque la funcion GetMap() solo devuelve 99 si esta fuera de los limites del mapa (que en principio era 9 y pense que se referia al 9 del no pasar del mapa original que era este:
| Código: |
int world_map[ MAP_WIDTH * MAP_HEIGHT ] =
{
// 0001020304050607080910111213141516171819
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 00
1,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,1, // 01
1,9,9,1,1,9,9,9,1,9,1,9,1,9,1,9,9,9,1,1, // 02
1,9,9,1,1,9,9,9,1,9,1,9,1,9,1,9,9,9,1,1, // 03
1,9,1,1,1,1,9,9,1,9,1,9,1,1,1,1,9,9,1,1, // 04
1,9,1,1,9,1,1,1,1,9,1,1,1,1,9,1,1,1,1,1, // 05
1,9,9,9,9,1,1,1,1,1,1,9,9,9,9,1,1,1,1,1, // 06
1,9,9,9,9,9,9,9,9,1,1,1,9,9,9,9,9,9,9,1, // 07
1,9,1,1,1,1,1,1,1,1,1,9,1,1,1,1,1,1,1,1, // 08
1,9,1,9,9,9,9,9,9,9,1,1,9,9,9,9,9,9,9,1, // 09
1,9,1,1,1,1,9,1,1,9,1,1,1,1,1,1,1,1,1,1, // 10
1,9,9,9,9,9,1,9,1,9,1,9,9,9,9,9,1,1,1,1, // 11
1,9,1,9,1,9,9,9,1,9,1,9,1,9,1,9,9,9,1,1, // 12
1,9,1,9,1,9,9,9,1,9,1,9,1,9,1,9,9,9,1,1, // 13
1,9,1,1,1,1,9,9,1,9,1,9,1,1,1,1,9,9,1,1, // 14
1,9,1,1,9,1,1,1,1,9,1,1,1,1,9,1,1,1,1,1, // 15
1,9,9,9,9,1,1,1,1,1,1,9,9,9,9,1,1,1,1,1, // 16
1,1,9,9,9,9,9,9,9,1,1,1,9,9,9,1,9,9,9,9, // 17
1,9,1,1,1,1,1,1,1,1,1,9,1,1,1,1,1,1,1,1, // 18
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 19
};
// map helper functions
int GetMap( int x, int y )
{
if( x < 0 ||
x >= MAP_WIDTH ||
y < 0 ||
y >= MAP_HEIGHT
)
{
return 9;
}
return world_map[(y*MAP_WIDTH)+x];
}
// Definitions
class MapSearchNode
{
public:
int x; // the (x,y) positions of the node
int y;
MapSearchNode() { x = y = 0; }
MapSearchNode( int px, int py ) { x=px; y=py; }
float GoalDistanceEstimate( MapSearchNode &nodeGoal );
bool IsGoal( MapSearchNode &nodeGoal );
bool GetSuccessors( AStarSearch<MapSearchNode> *astarsearch, MapSearchNode *parent_node );
float GetCost( MapSearchNode &successor );
bool IsSameState( MapSearchNode &rhs );
void PrintNodeInfo();
};
bool MapSearchNode::IsSameState( MapSearchNode &rhs )
{
// same state in a maze search is simply when (x,y) are the same
if( (x == rhs.x) &&
(y == rhs.y) )
{
return true;
}
else
{
return false;
}
}
void MapSearchNode::PrintNodeInfo()
{
char str[100];
sprintf( str, "Node position : (%d,%d)\n", x,y );
cout << str;
}
// Here's the heuristic function that estimates the distance from a Node
// to the Goal.
float MapSearchNode::GoalDistanceEstimate( MapSearchNode &nodeGoal )
{
return abs(x - nodeGoal.x) + abs(y - nodeGoal.y);
}
bool MapSearchNode::IsGoal( MapSearchNode &nodeGoal )
{
if( (x == nodeGoal.x) &&
(y == nodeGoal.y) )
{
return true;
}
return false;
}
// This generates the successors to the given Node. It uses a helper function called
// AddSuccessor to give the successors to the AStar class. The A* specific initialisation
// is done for each node internally, so here you just set the state information that
// is specific to the application
bool MapSearchNode::GetSuccessors( AStarSearch<MapSearchNode> *astarsearch, MapSearchNode *parent_node )
{
int parent_x = -1;
int parent_y = -1;
if( parent_node )
{
parent_x = parent_node->x;
parent_y = parent_node->y;
}
MapSearchNode NewNode;
// push each possible move except allowing the search to go backwards
if( (GetMap( x-1, y ) < 9)
&& !((parent_x == x-1) && (parent_y == y))
)
{
NewNode = MapSearchNode( x-1, y );
astarsearch->AddSuccessor( NewNode );
}
if( (GetMap( x, y-1 ) < 9)
&& !((parent_x == x) && (parent_y == y-1))
)
{
NewNode = MapSearchNode( x, y-1 );
astarsearch->AddSuccessor( NewNode );
}
if( (GetMap( x+1, y ) < 9)
&& !((parent_x == x+1) && (parent_y == y))
)
{
NewNode = MapSearchNode( x+1, y );
astarsearch->AddSuccessor( NewNode );
}
if( (GetMap( x, y+1 ) < 9)
&& !((parent_x == x) && (parent_y == y+1))
)
{
NewNode = MapSearchNode( x, y+1 );
astarsearch->AddSuccessor( NewNode );
}
return true;
}
|
|
|
| Volver arriba |
|
|
|
|
No puedes publicar temas nuevos en este foro
No puedes responder a temas en este foro
No puedes editar tus mensajes en este foro
No puedes borrar tus mensajes en este foro
No puedes votar en las encuestas de este foro
|
© 2002–2026 Club Builder · Funciona con phpBB.
|
FAQ
Buscar
Miembros
Grupos de Usuarios
Registrarse
Perfil
Entra para ver tus mensajes privados
Entrar
