Как реализовать Алгоритм A* или Алгоритм Дейкстры на PHP? Нужно найти кратчайший путь от старта (зеленым) по цели например тут: Уже полгода мучаюсь... помогите. Зарание спасибо
Да я и с тем не разобрался... Можно пример кода? Я делал цикл с условиями - работает но очень плохо обходит преграды... нужно что-то более эффективное... а как?
если делать, то по порядку. 1. как хранится матрица поля? или как бы ты хотел, чтобы она хранилась 2. нужно словесное описание алгоритма дейкстры 3. есть ли под руками реализация алгоритма дейкстры на другом языке программирования? а дальше будем думать, как из этого что-то слепить
Пусть будет A*. 1. Я думаю не хранить, т.к. я могу обратиться к базе и проверить проходимость. 2. http://www.policyalmanac.org/games/aSta ... al_rus.htm 3. Есть А*, на C++ (Visual Studio) Исходник есть в этой статье
т.е. хранить всё равно надо. и портировать из базы в php всё равно придётся (хотя бы прямоугольную область, которая содержит старт и финиш). зы: алгоритм посмотрел поверхностно. реализацию на сях посмотрел подробно. буду смотреть, что можно сделать
titch, Вот как я перевел на PHP код с С++; PHP: <? function FindPath($pathfinderID, $startX, $startY, $targetX, $targetY, $stepByStep = false) { global $pathBank; $onOpenList=0; $parentXval=0; $parentYval=0; $a=0; $b=0; $m=0; $u=0; $v=0; $temp=0; $corner=0; $numberOfOpenListItems=0; $addedGCost=0; $tempGcost=0; $path=0; $x=0; $y=0; $newOpenListItemID=0; $mapWidth = 5; $mapHeight = 5; //tempx, pathX, pathY, cellPosition != 0 ò.å. = null //2.Quick Path Checks: Under the some circumstances no path needs to // be generated ... // If starting location and target are in the same location... if ($startX == $targetX && $startY == $targetY && $pathLocation[$pathfinderID] > 0) return 'found'; if ($startX == $targetX && $startY == $targetY && $pathLocation[$pathfinderID] == 0) return 'nonexistent'; echo $pathfinderID; //3.Reset some variables that need to be cleared for ($x = 0; $x < $mapWidth; $x++) { for ($y = 0; $y < $mapHeight; $y++) $whichList[$x][$y] = 0; } $onClosedList = 2; //changing the values of onOpenList and onClosed list is faster than redimming whichList() array $onOpenList = 1; $pathLength[$pathfinderID] = 0; $pathLocation [$pathfinderID] = 0; $Gcost[$startX][$startY] = 0; //reset starting square's G value to 0 //4.Add the starting location to the open list of squares to be checked. $numberOfOpenListItems = 1; $openList[1] = 1;//assign it as the top (and currently only) item in the open list, which is maintained as a binary heap (explained below) $openX[1] = $startX; $openY[1] = $startY; //5.Do the following until a path is found or deemed nonexistent. do { //6.If the open list is not empty, take the first cell off of the list. // This is the lowest F cost cell on the open list. if ($numberOfOpenListItems != 0) { //7. Pop the first item off the open list. $parentXval = $openX[$openList[1]]; $parentYval = $openY[$openList[1]]; //record cell coordinates of the item $whichList[$parentXval][$parentYval] = $onClosedList;//add the item to the closed list // Open List = Binary Heap: Delete this item from the open list, which // is maintained as a binary heap. For more information on binary heaps, see: // [url=http://www.policyalmanac.org/games/binaryHeaps.htm]http://www.policyalmanac.org/games/binaryHeaps.htm[/url] $numberOfOpenListItems = $numberOfOpenListItems - 1;//reduce number of open list items by 1 // Delete the top item in binary heap and reorder the heap, with the lowest F cost item rising to the top. $openList[1] = $openList[$numberOfOpenListItems+1];//move the last item in the heap up to slot #1 $v = 1; // Repeat the following until the new item in slot #1 sinks to its proper spot in the heap. do { $u = $v; if (2*$u+1 <= $numberOfOpenListItems) //if both children exist { //Check if the F cost of the parent is greater than each child. //Select the lowest of the two children. if ($Fcost[$openList[$u]] >= $Fcost[$openList[2*$u]]) $v = 2*$u; if ($Fcost[$openList[$v]] >= $Fcost[$openList[2*$u+1]]) $v = 2*$u+1; } else { if (2*$u <= $numberOfOpenListItems) //if only child #1 exists { //Check if the F cost of the parent is greater than child #1 if ($Fcost[$openList[$u]] >= $Fcost[$openList[2*$u]]) $v = 2*$u; } } if ($u != $v) //if parent's F is > one of its children, swap them { $temp = $openList[$u]; $openList[$u] = $openList[$v]; $openList[$v] = $temp; } else break; //otherwise, exit loop } while (1);//reorder the binary heap // while (!KeyDown(27)); //7.Check the adjacent squares. (Its "children" -- these path children // are similar, conceptually, to the binary heap children mentioned // above, but don't confuse them. They are different. Path children // are portrayed in Demo 1 with grey pointers pointing toward // their parents.) Add these adjacent child squares to the open list // for later consideration if appropriate (see various if statements // below). for ($b = $parentYval-1; $b <= $parentYval+1; $b++){ for ($a = $parentXval-1; $a <= $parentXval+1; $a++){ // If not off the map (do this first to avoid array out-of-bounds errors) if ($a != -1 && $b != -1 && $a != $mapWidth && $b != $mapHeight){ // If not already on the closed list (items on the closed list have // already been considered and can now be ignored). if ($whichList[$a][$b] != $onClosedList) { // If not a wall/obstacle square. if ($walkability [$a][$b] != $unwalkable) { // Don't cut across corners $corner = 'walkable'; if ($a == $parentXval-1) { if ($b == $parentYval-1) { if ($walkability[$parentXval-1][$parentYval] == 'unwalkable' || $walkability[$parentXval][$parentYval-1] == 'unwalkable') $corner = 'unwalkable'; } elseif ($b == $parentYval+1) { if ($walkability[$parentXval][$parentYval+1] == 'unwalkable' || $walkability[$parentXval-1][$parentYval] == 'unwalkable') $corner = 'unwalkable'; } } elseif ($a == $parentXval+1) { if ($b == $parentYval-1) { if ($walkability[$parentXval][$parentYval-1] == 'unwalkable' || $walkability[$parentXval+1][$parentYval] == 'unwalkable') $corner = 'unwalkable'; } else if ($b == $parentYval+1) { if ($walkability[$parentXval+1][$parentYval] == 'unwalkable' || $walkability[$parentXval][$parentYval+1] == 'unwalkable') $corner = 'unwalkable'; } } if ($corner == 'walkable') { // If not already on the open list, add it to the open list. if ($whichList[$a][$b] != $onOpenList) { //Create a new open list item in the binary heap. $newOpenListItemID = $newOpenListItemID+1; //each new item has a unique ID # $m = $numberOfOpenListItems+1; $openList[$m] = $newOpenListItemID;//place the new open list item (actually, its ID#) at the bottom of the heap $openX[$newOpenListItemID] = $a; $openY[$newOpenListItemID] = $b;//record the x and y coordinates of the new item //Figure out its G cost if (abs($a- $parentXval) == 1 && abs($b - $parentYval) == 1) $addedGCost = 14;//cost of going to diagonal squares else $addedGCost = 10;//cost of going to non-diagonal squares $Gcost[$a][$b] = $Gcost[$parentXval][$parentYval] + $addedGCost; //Figure out its H and F costs and parent $Hcost[$openList[$m]] = 10*(abs($a - $targetX) + abs($b - $targetY)); $Fcost[$openList[$m]] = $Gcost[$a][$b] + $Hcost[$openList[$m]]; $parentX[$a][$b] = $parentXval ; $parentY[$a][$b] = $parentYval; while ($m != 1) //While item hasn't bubbled to the top (m=1) { //Check if child's F cost is < parent's F cost. If so, swap them. if ($Fcost[$openList[$m]] <= $Fcost[$openList[$m/2]]) { $temp = $openList[$m/2]; $openList[$m/2] = $openList[$m]; $openList[$m] = $temp; $m = $m/2; } else break; } $numberOfOpenListItems = $numberOfOpenListItems+1;//add one to the number of items in the heap //Change whichList to show that the new item is on the open list. $whichList[$a][$b] = $onOpenList; } //8.If adjacent cell is already on the open list, check to see if this // path to that cell from the starting location is a better one. // If so, change the parent of the cell and its G and F costs. else //If whichList(a,b) = onOpenList { //Figure out the G cost of this possible new path if (abs($a - $parentXval) == 1 && abs($b - $parentYval) == 1) $addedGCost = 14;//cost of going to diagonal tiles else $addedGCost = 10;//cost of going to non-diagonal tiles $tempGcost = $Gcost[$parentXval][$parentYval] + $addedGCost; //If this path is shorter (G cost is lower) then change //the parent cell, G cost and F cost. if ($tempGcost < $Gcost[$a][$b]) //if G cost is less, { $parentX[$a][$b] = $parentXval; //change the square's parent $parentY[$a][$b] = $parentYval; $Gcost[$a][$b] = $tempGcost;//change the G cost //Because changing the G cost also changes the F cost, if //the item is on the open list we need to change the item's //recorded F cost and its position on the open list to make //sure that we maintain a properly ordered open list. for($x = 1; $x <= $numberOfOpenListItems; $x++) //look for the item in the heap { if ($openX[$openList[$x]] == $a && $openY[$openList[$x]] == $b) //item found { $Fcost[$openList[$x]] = $Gcost[$a][$b] + $Hcost[$openList[$x]];//change the F cost //See if changing the F score bubbles the item up from it's current location in the heap $m = $x; while($m != 1) //While item hasn't bubbled to the top (m=1) { //Check if child is < parent. If so, swap them. if ($Fcost[$openList[$m]] < $Fcost[$openList[$m/2]]) { $temp = $openList[$m/2]; $openList[$m/2] = $openList[$m]; $openList[$m] = $temp; $m = $m/2; } else break; } break; //exit for x = loop } //If openX(openList(x)) = a } //For x = 1 To numberOfOpenListItems }//If tempGcost < Gcost(a,b) }//else If whichList(a,b) = onOpenList }//If not cutting a corner }//If not a wall/obstacle square. }//If not already on the closed list }//If not off the map }//for (a = parentXval-1; a <= parentXval+1; a++){ }//for (b = parentYval-1; b <= parentYval+1; b++){ }//if (numberOfOpenListItems != 0) //9.If open list is empty then there is no path. else { $path = 'nonexistent'; break; } //If target is added to open list then path has been found. if ($whichList[$targetX][$targetY] == $onOpenList) { $path = 'found'; break; } } while (1);//Do until path is found or deemed nonexistent // while (!(KeyDown(27))); //10.Save the path if it exists. if ($path == 'found') { //a.Working backwards from the target to the starting location by checking // each cell's parent, figure out the length of the path. $pathX = $targetX; $pathY = $targetY; do { //Look up the parent of the current cell. $tempx = $parentX[$pathX][$pathY]; $pathY = $parentY[$pathX][$pathY]; $pathX = $tempx; //Figure out the path length $pathLength[$pathfinderID] = $pathLength[$pathfinderID] + 1; } while ($pathX != $startX || $pathY != $startY); //b.Resize the data bank to the right size in bytes /* pathBank[$pathfinderID] = (int*) realloc (pathBank[$pathfinderID], pathLength[$pathfinderID]*8); */ //c. Now copy the path information over to the databank. Since we are // working backwards from the target to the start location, we copy // the information to the data bank in reverse order. The result is // a properly ordered set of path data, from the first step to the // last. $pathX = $targetX; $pathY = $targetY; $cellPosition = $pathLength[$pathfinderID]*2;//start at the end do { $cellPosition = $cellPosition - 2;//work backwards 2 integers $pathBank[$pathfinderID][$cellPosition] = $pathX; $pathBank[$pathfinderID][$cellPosition+1] = $pathY; //d.Look up the parent of the current cell. $tempx = $parentX[$pathX][$pathY]; $pathY = $parentY[$pathX][$pathY]; $pathX = $tempx; //e.If we have reached the starting square, exit the loop. } while ($pathX != $startX || $pathY != $startY); } return $path; } $test = FindPath(1, 1, 0, 4, 5); echo $test; ?>
Отредактировал. Теперь нужно получить путь... На СИ она так: Код (Text): void ReadPath(int pathfinderID) //If a path exists, read the path data // from the pathbank. { pathLocation[pathfinderID] = 1; //set pathLocation to 1st step while (pathLocation[pathfinderID] < pathLength[pathfinderID]) { int a = pathBank[pathfinderID] [pathLocation[pathfinderID]*2-2]; int b = pathBank[pathfinderID] [pathLocation[pathfinderID]*2-1]; pathLocation[pathfinderID] = pathLocation[pathfinderID] + 1; whichList[a][b] = 3;//draw dotted path } } Только не пойму, как она получает pathBank, если он не глобальный
php это не c++ верни путь сразу из функции. у тебя же не типизированный язык. ты можешь вернуть результат сразу хоть false, хоть массив
смотри, что делает функция. она восстанавливает путь. в контексте php это не выгодно. лучше сразу вернуть путь вида array(array(x1,y1),array(x2,y2),array(x3,y3),...,array(xN,yN))