[人工智能与算法]等高线算法(C语言粗糙版)

来源：互联网   发布日期：2011-09-16 11:54:01   浏览：8508次  

等高线算法(C语言粗糙版) visualxyk 发表于 2007-6-8 14:19:00等高线算法用来在地图寻找最短路径与最优路径的算法.它通过像地图中的等高线一样从终点向四周扩散开来,一直扩散到开始点为止.则从开始点开始,沿着"高度"逐渐降低的路径,一直到最"低谷",就是从起点到终点的最短路径.它可以绕开障碍物,并且通过加权运算的话,可以考虑到各种地形的影响.源代码如下:＃i nclude <stdio.h>＃i nclude <stdlib.h>#define MAP_WIDTH 10#define MAP_HEIGHT 10#define MAP_SIZE (MAP_WIDTH * MAP_HEIGHT)int map_data[MAP_SIZE] = { 1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,0,1,1,1,1, 1,1,1,1,1,0,1,1,1,1, 1,1,1,1,1,0,0,0,0,1, 1,1,0,1,1,0,1,1,1,1, 1,1,0,1,0,0,1,0,0,0, 1,1,0,1,0,1,1,1,1,1, 1,1,1,0,1,1,1,1,1,1, 1,1,1,0,1,1,1,1,1,1, 1,1,1,0,1,1,1,1,1,1};int temp_data[MAP_SIZE] = {0};void set_marker(int pos, int step_no, int target_pos);int get_path(int start_pos, int targetd_pos, int *path);int get_step(int pos);void set_marker(int pos, int step_no, int target_pos, bool &Found){ int up = pos - MAP_WIDTH, down = pos + MAP_WIDTH, left = pos - 1, right = pos + 1; if (up >= 0) if (map_data[up] != 0)   if (temp_data[up] == 0 || temp_data[up] > step_no)   {   temp_data[up] = step_no;   if (up == target_pos)   Found = true;   } if (down < MAP_SIZE) if (map_data[down] != 0)   if (temp_data[down] == 0 || temp_data[down] > step_no)   {   temp_data[down] = step_no;   if (down == target_pos)   Found = true;   } if (pos%MAP_WIDTH != 0) if (map_data[left] != 0)   if (temp_data[left] == 0 || temp_data[down] > step_no)   {   temp_data[left] = step_no;   if (left == target_pos)   Found = true;   } if (right%MAP_WIDTH != 0) if (map_data[right] != 0)   if (temp_data[right] == 0 || temp_data[right] > step_no)   {   temp_data[right] = step_no;   if (right == target_pos)   Found = true;   }}int get_step(int pos){ int temp_pos = pos - MAP_WIDTH; if (temp_pos >= 0) if (map_data[temp_pos] != 0)   if (temp_data[temp_pos] != 0 && temp_data[temp_pos] < temp_data[pos])   return temp_pos; temp_pos = pos + MAP_WIDTH; if (temp_pos < MAP_SIZE) if (map_data[temp_pos] != 0)   if (temp_data[temp_pos] != 0 && temp_data[temp_pos] < temp_data[pos])   return temp_pos; temp_pos = pos - 1; if (pos%MAP_WIDTH != 0) if (map_data[temp_pos] != 0)   if (temp_data[temp_pos] != 0 && temp_data[temp_pos] < temp_data[pos])   return temp_pos; temp_pos = pos + 1; if (temp_pos%MAP_WIDTH != 0) if (map_data[temp_pos] != 0)   if (temp_data[temp_pos] != 0 && temp_data[temp_pos] < temp_data[pos])   return temp_pos; return -1;}int get_path(int start_pos, int target_pos, int *path){ int index = 0; path[index] = get_step(start_pos); index++; while (true) { path[index] = get_step(path[index-1]); if (path[index] == target_pos)   break; index++; } return ++index;} void show_map(){ int i, j; for (i=0; i<MAP_HEIGHT; i++) { for (j=0; j<MAP_WIDTH; j++)   printf(" %02d", map_data[i * MAP_WIDTH + j]); printf("\n"); }}void show_temp(){ int i, j; for (i=0; i<MAP_HEIGHT; i++) { for (j=0; j<MAP_WIDTH; j++)   printf(" %02d", temp_data[i * MAP_WIDTH + j]); printf("\n"); }}void main(){ printf("map data:\n"); show_map(); printf("\ntemp_data:\n"); show_temp(); int i, j, index; int step = 1; int start_pos = 11, end_pos = 88; temp_data[end_pos] = step; bool Found = false; do { for (i=0; i<MAP_HEIGHT; i++)   for (j=0; j<MAP_WIDTH; j++)   {   index = i * MAP_WIDTH + j;   if (temp_data[index] == step)   set_marker(index, step+1, start_pos, Found);   } step++; }while (!Found); printf("after setting markers...\n"); show_temp(); getchar(); int path[30]; int counter = get_path(start_pos, end_pos, path); for (i = 0; i<counter; i++) map_data[path] = 99; printf("The road is like that...\n"); show_map(); getchar();}这是第一个版本,在其中,设置标志部分用了强制的整张地图搜索,效率很低,可以用两个容器来解决上面问题.这将在下一个版本提到.

赞助本站