OpenCL Pathfinding

Здравствуйте, друзья.
Возникла задача написать алгоритм поиска пути на OpenCL. Никак не получается получить верный результат, а проблема заключается в следующем. Есть карта размером width x height и есть определенное количество агентов, которые расположены на карте. Распараллеливание подразумевает расчет пути каждым агентом. Никак не могу разобраться с тем как это реализовать. Я создаю поле width * height - это поле откуда мы считываем область на которой происходит поиск, в данном случае это линейный массив со значениями 0 и 1. Так же существует массив width * agentsNum * height * agentsNum - выходной массив где будут отмечены пути. Как мне запустить алгоритм поиска agentsNum - раз на поле width * height?

Forums: 

Как мне запустить алгоритм

Как мне запустить алгоритм поиска agentsNum - раз на поле width * height?

Вы уже ознакомились с документацией и примерами OpenCL (либо Cuda)?

width * agentsNum * height * agentsNum

Опечатка?

К сожалению не было совсем

К сожалению не было совсем времени вдумчиво ознакомиться в документацией, так как задачу надо было уже сделать "вчера". В конечном итоге с горем пополам был написан кернель, данного вида:

Как всегда, скажу, что код абсолютно не оптимизирован, возможно есть какие-либо неточности.
Алгоритм был взят из википедии. Пожалуйста, критика, поправки и т.д. приветствуется.

  1. float heuristic(int2 start, int2 end)
  2. {
  3.         float result = 0;
  4.        
  5.         int x, y;
  6.        
  7.         x = (int)(start.x - end.x);
  8.         y = (int)(start.y - end.y);
  9.        
  10.         if (x < 0)
  11.         {
  12.                 x = -x;
  13.         }
  14.        
  15.         if (y < 0)
  16.         {
  17.                 y = -y;
  18.         }
  19.        
  20.         result = sqrt((x * x) + (y * y));
  21.         return result;
  22. }
  23.  
  24. __kernel
  25. void findPath(__global char * output,
  26.               __global bool * input,
  27.               const    int    width,
  28.               const    int    height,
  29.               const    int    agentsNum,
  30.                          __global int2 * startIndexes,
  31.              __global int2 * destIndexes)
  32. {      
  33.         uint globalIdx = get_global_id(0);
  34.  
  35.         barrier(CLK_LOCAL_MEM_FENCE);
  36.        
  37.         int2 closedList[1024];
  38.         int2 openedList[1024];
  39.        
  40.         int openedListLength = 0;
  41.         int closedListLength = 0;
  42.        
  43.         int2 start = (int2)startIndexes[globalIdx];
  44.         int2 end = (int2)destIndexes[globalIdx];
  45.        
  46.         if (start.x != end.x && start.y != end.y)
  47.         {
  48.                 openedList[0] = (int2)start;
  49.                 openedListLength++;
  50.         }
  51.  
  52.         int2 currentPoint, tempPoint;
  53.        
  54.         float currentH = 0;
  55.         float tempH = 0;
  56.        
  57.         int i = 0;
  58.         int x = 0;
  59.         int y = 0;
  60.        
  61.         bool found = false;
  62.         bool inClosedList;
  63.         bool inOpenedList;
  64.         bool betterPath;
  65.        
  66.         int stX, stY, enX, enY;
  67.         int index;
  68.         float hScore[1024];
  69.         float fScore[1024];
  70.         float gScore[1024];
  71.         int cameFrom[1024];
  72.        
  73.         gScore[start.x + (start.y * width)] = (float)0.0f;
  74.        
  75.         tempH = (float)heuristic(start, end);
  76.        
  77.         index = (int)(start.x + (start.y * width));
  78.        
  79.     hScore[index] = (float)tempH;
  80.     fScore[index] = (float)hScore[index];
  81.        
  82.         cameFrom[start.x + (start.y * width)] = (int)-1;
  83.        
  84.         output[index + ((width * height) * globalIdx)] = 'O';
  85.         output[(int)(end.x + (end.y * width)) + ((width * height) * globalIdx)] = 'X';
  86.        
  87.         while ((openedListLength > 0) && (!found))
  88.         {
  89.                 currentH = -1.0f;
  90.                 currentPoint = (int2)(-1,-1);
  91.                
  92.                 for (i=0; i<openedListLength; i++)
  93.                 {
  94.                         tempPoint = (int2)openedList[i];
  95.                         tempH = (float)heuristic(tempPoint, end);//(float)fScore[(int)(tempPoint.x + (width * tempPoint.y))]
  96.                        
  97.                         if ((currentH < 0.0f) || (currentH > tempH))
  98.                         {
  99.                                 currentH = tempH;
  100.                                 currentPoint = tempPoint;
  101.                         }
  102.                 }
  103.                
  104.                 openedListLength--;
  105.                
  106.                 if (currentPoint.x == -1)
  107.                 {
  108.                         openedListLength = 0;
  109.                         break;
  110.                 }
  111.                
  112.                 if ((end.x == currentPoint.x) && (end.y == currentPoint.y))
  113.                 {
  114.                         found = true;
  115.                         break;
  116.                 }
  117.                
  118.                 closedList[closedListLength++] = (int2)currentPoint;
  119.                
  120.                 stX = currentPoint.x - 1;
  121.                 enX = currentPoint.x + 1;
  122.                
  123.                 if (stX < 0)
  124.                 {
  125.                         stX = 0;
  126.                 }
  127.                 if(enX > (width - 1))
  128.                 {
  129.                         enX = width - 1;
  130.                 }
  131.                        
  132.                 stY = currentPoint.y - 1;
  133.                 enY = currentPoint.y + 1;
  134.                
  135.                 if (stY < 0)
  136.                 {
  137.                         stY = 0;
  138.                 }
  139.                 if(enY > (height - 1))
  140.                 {
  141.                         enY = height - 1;
  142.                 }
  143.  
  144.                 for (x = stX; x <= enX; x++)
  145.                 {
  146.                         for (y = stY; y <= enY; y++)
  147.                         {
  148.                                 index = (int)(x + (width * y));
  149.                        
  150.                                 if (((x == currentPoint.x) && (y == currentPoint.y)) || (input[index]) == true)
  151.                                 {
  152.                                         continue;
  153.                                 }
  154.  
  155.                                 inClosedList = false;
  156.                                 for (i=0; i<closedListLength; i++)
  157.                                 {
  158.                                         tempPoint = (int2)closedList[i];
  159.                                        
  160.                                         if ((tempPoint.x == x) && (tempPoint.y == y))
  161.                                         {
  162.                                                 inClosedList = true;
  163.                                                 break;
  164.                                         }
  165.                                 }
  166.  
  167.                                 if (inClosedList)
  168.                                 {
  169.                                         continue;
  170.                                 }
  171.  
  172.                                 inOpenedList = false;
  173.  
  174.                                 for (i=0; i<openedListLength; i++)
  175.                                 {
  176.                                         tempPoint = (int2)openedList[i];
  177.  
  178.                                         if ((tempPoint.x == x) && (tempPoint.y == y))
  179.                                         {
  180.                                                 inOpenedList = true;
  181.                                                 break;
  182.                                         }
  183.                                 }
  184.                                
  185.                                 tempH = (float)(gScore[(int)(currentPoint.x + (currentPoint.y * width))] + heuristic(currentPoint, (int2)(x, y)));
  186.                                
  187.                                 if (!inOpenedList)
  188.                                 {
  189.                                         openedList[openedListLength++] = (int2)(x, y);
  190.                                         betterPath = true;
  191.                                 }
  192.                                 else if (tempH < (float)gScore[index])
  193.                                 {
  194.                                         betterPath = true;
  195.                                 }
  196.                                 else
  197.                                 {
  198.                                         betterPath = false;
  199.                                 }
  200.                                
  201.                                 if (betterPath)
  202.                                 {
  203.                                         cameFrom[index] = (int)(currentPoint.x + (currentPoint.y * width));
  204.                                        
  205.                                         gScore[index] = (float)tempH;
  206.                                         tempH = (float)heuristic((int2)(x, y), end);
  207.                                        
  208.                                         hScore[index] = (float)tempH;
  209.                                         fScore[index] = (float)gScore[index] + (float)hScore[index];
  210.                                 }
  211.                         }
  212.                 }              
  213.         }
  214.        
  215.         if (found)
  216.         {
  217.                 int currentNode = cameFrom[end.x + (end.y * width)];
  218.  
  219.                 while (currentNode != -1)
  220.                 {
  221.                         if ((currentNode != (int)(start.x + (width * start.y))) && (currentNode != (int)(end.x + (width * end.y))))
  222.                         {
  223.                                 output[currentNode + ((width * height) * globalIdx)] = '*';
  224.                         }
  225.                        
  226.                         currentNode = (int)cameFrom[currentNode];
  227.                 }
  228.         }
  229. }

Продублируйте в

Продублируйте в http://pastebin.com/ , читать будет удобней.
(я не говорю что буду его сейчас смотреть - дел много. но если кто захочет, удобней будет pastebin читать)

Я ваш код не смотрел, но

Я ваш код не смотрел, но сразу вопрос - разрешено ли использовать волновой алгоритм? Он по-идеи прекрасно параллелится, даже в пределах одного "агента"

Думаю, что волновой алгоритм

Думаю, что волновой алгоритм поиска тоже возможен, но насколько я понимаю, A* эффективнее волнового алгоритма и он и его производные чаще применяются в робототехнике и компьютерных играх.

Ну A* вроде как производный

Ну A* вроде как производный от волнового алгоритма.
Я ещё раз говорю, код ещё не изучал - у вас там A* ?