Dragon took incorrect path!

[Tim]

Ok thx. Bad for your Barb Moonknight.

[Moonknight]

Ok thx. Bad for your Barb Moonknight.

Yeah, I expected better end results than that for sure...

[SnotlinG]

Please let me know if you see this bug again somewhere, as I didnt even know it existed until it was reported here.

KGB, I have gone through the pathfinding algorithm a few times without finding the issue. Our problem i think is due to two things:
1. Ports, which if moved via that square changes the entire move-cost table used when calculating.
2. Impossible terrain, im not sure the A* algorithm has impossible terrain into consideration.

With this said, if you like i can post the code we use and maybe you can see if i have made any misstakes (not so unlikely)

[KGB]

SnotlinG,

Post the code including your support routines.

I've written A* before a couple years ago. It included impassible terrain (cost is infinity for that square). Ports should not matter either.

The algorithm itself is very straight forward. But it does require some good supporting functions (move cost for a square type thing).

My guess from whats happening is that your paths are wrapping back across squares you've already evaluated because otherwise it's impossible to get into an infinite loop given there are finite map squares AND you only evaluate each square one time.

KGB

[SnotlinG]

As far as I remember we evaluate squares more than once, checking if we can reach it for a lower cost than the current lowest cost path. And Ports means we need to check it in two ways, as the stack can be reaching the square either in Landmode or in Seamode...

Let me know if you find anything, I´d be more than happy to optimize the code

Code: Select all



    // ----- CALCULATE PATH -----
    function calculatepath($startpos, $endpos)
        {
        $pathvector = array();

         $start =  explode("_",startpos);
         $startx = $start[0];
         $starty = $start[1];

         $end = explode("_",$endpos);
         $endx = $end[0];
         $endy = $end[1];

         $optimalpath ="";
         $returnarray = array();

        $returnarray = $this->findpath2($startpos,$endpos);

        $cost = $returnarray[0];

        //error_log("ai.php: Found path cost: $cost in game: $this->gameid for startpos: $startpos");

        $optimalpath = $returnarray[1] . "#" . $endpos;

        return array($cost,$optimalpath);
     }


    // ----- GET TARGET DISTANCE -----
     function gettargetdistance($coord1,$coord2)
        {
         $coord1=explode("_",$coord1);
         $coord2=explode("_",$coord2);

         $x1 = $coord1[0];
         $y1 = $coord1[1];
         $x2 = $coord2[0];
         $y2 = $coord2[1];

         $deltax = abs($x1-$x2);
         $deltay = abs($y1-$y2);


        // Check for difficult terrain - lets us detect if there is water/mountain between us and target
        $difficultterrain = 0;
        while ($x1 != $x2 && $y1 != $y2)
            {
            if ($x1 < $x2)
                {
                $x1++;
                }
            else if ($x1 > $x2)
                {
                $x1--;
                }
            if ($y1 < $y2)
                {
                $y1++;
                }
            else if ($y1 > $y2)
                {
                $y1--;
                }
            $coord = $x1 . "_" . $y1;
            $terraintype = $this->terrainhash[$this->maphash[$coord]];
           
            if ($terraintype == "Vo" || $terraintype == "Mo" || $terraintype == "Wa" || $terraintype == "Ob" || $terraintype == "Rv" || $terraintype == "Oc")           
                {
                $difficultterrain = 5; // Distance add-on if we pass difficult terrain as this means there is a greater risk we have trouble finding a good path
                // error_log("difficultterrain found!");
                break;
                }
            }

         if ($deltax > $deltay)
            {
            return $deltax+$difficultterrain;
            }
        return $deltay+$difficultterrain;
        }



     // ----- GET DISTANCE ----
     function getdistance($coord1,$coord2)
        {
         $coord1=explode("_",$coord1);
         $coord2=explode("_",$coord2);

         $x1 = $coord1[0];
         $y1 = $coord1[1];
         $x2 = $coord2[0];
         $y2 = $coord2[1];

         $deltax = abs($x1-$x2);
         $deltay = abs($y1-$y2);

         if ($deltax > $deltay)
            {
            return $deltax;
            }
        return $deltay;

        // WB world...
        //  $x = $deltax*$deltax;
        //  $y = $deltay*$deltay;
        //  $newdistance = sqrt($x+$y);
        //  return $newdistance;
        }


    // ----- GET NUMBER OF SQUARES TO TARGET -----
    function getnumberofsquarestotarget($startcoord,$endcoord)
        {

        $coord2 = explode("_",$startcoord);
        $orginalx = $coord2[0];
        $orginaly = $coord2[1];

        $coord1 = explode("_",$endcoord);
        $endx = $coord1[0];
        $endy = $coord1[1];

        $diffx = abs(orginalx-endx);
        $diffy = abs(orginaly-endy);

        if ($diffx > $diffy){return $diffx;}
        else {return $diffy;}

        }

    // ----- GET ADJACENT SQUARES -----
    function getadjacentsquares($coord)
        {
        // Returnerar intilliggande rutor på ett smart sätt i förhållande till målet, dvs närmst rutor kommer först
        $c = explode("_",$coord);

        $orginalx = $c[0];
        $orginaly = $c[1];

        $minx = $orginalx-1;
        $maxx = $orginalx+1;
        $miny = $orginaly-1;
        $maxy = $orginaly+1;


        if ($minx < 0){$minx = 0;}
        if ($maxx == $this->mapwidth){$maxx = $this->mapwidth-1;}

        if ($miny < 0){$miny = 0;}
        if ($maxy == $this->mapheight){$maxy = $this->mapheight-1;}

        $returnarray = array();
        $k = 0;

        $diffx = abs($orginalx-$endx);
        $diffy = abs($orginaly-$endy);

        if ($endx == $orginalx)
            {
            $xarray = array($orginalx,$minx,$maxx);
            }
        else if ($endx > $orginalx)
            {
            $xarray = array($maxx,$orginalx,$minx);
            }
        else
             {
             $xarray = array($minx,$orginalx,$maxx);
             }
        if ($endy == $orginaly)
             {
             $yarray = array($orginaly,$miny,$maxy);
             }
        else if ($endy > $orginaly)
             {
             $yarray = array($maxy,$orginaly,$miny);
             }
        else
             {
             $yarray = array($miny,$orginaly,$maxy);
             }
        $n = count($xarray);
        $o = count($yarray);

        if ($diffx > $diffy)
            {
            for ($x=0;$x<$n;$x++)
                {
                for ($y=0;$y<$o;$y++)
                    {
                    if (!($yarray[$y]==$orginaly && $xarray[$x]==$orginalx))
                        {
                        $returnarray[$k] = $xarray[$x] . "_" . $yarray[$y];
                        $k++;
                        }
                    }
                }
             }
         else
                {
                for ($y=0;$y<$o;$y++)
                    {
                     for ($x=0;$x<$n;$x++)
                        {
                        if (!($yarray[$y]==$orginaly && $xarray[$x]==$orginalx))
                            {
                            $returnarray[$k] = $xarray[$x] . "_" . $yarray[$y];
                            $k++;
                            }
                        }
                    }
                }
           return $returnarray;
        }

    // ----- GET COST FOR -----
    function getcostfor($coord,$prevcoord,$movecosttable, $currentmovetype)
        {
        $terrainid      = $this->maphash[$coord];
        $terraintype    = $this->terrainhash[$terrainid];

        $terrainid      = $this->maphash[$prevcoord];
        $previousterraintype = $this->terrainhash[$terrainid];

        if ($movecosttable['affectedbyanchor'] == "yes" && $currentmovetype == "Sea" && $previousterraintype == "An" && $terraintype != "Wa" && $terraintype != "Sh" && $terraintype != "An" && $terraintype != "Br" && $terraintype != "Ob")
            {
            $currentmovetype = "Land";
            //echo "Anchor convert to LAND<br>";
            }

        if ($movecosttable['affectedbyanchor'] == "yes" && $currentmovetype == "Land" && $terraintype=="An")
            {
            // Om man är landgående och går till en Anchor så ska man omvandlas till movetype Sea
            $currentmovetype="Sea";
            }

        return array($movecosttable[$currentmovetype][$terraintype],$currentmovetype);
        }




    // ----- RECONSTRUCT PATH -----
    function  reconstruct_path($came_from, $current_node)
        {
        if ($came_from[$current_node])
            {
            $p = $this->reconstruct_path($came_from, $came_from[$current_node]);
            $current_node = explode("#",$current_node);
            $current_node = $current_node[0];
            return $p . "#" . $current_node;
            }
        else
            {
            $current_node = explode("#",$current_node);
            $current_node = $current_node[0];
            return $current_node;
            }
        }

    // ----- FINDPATH2 -----
    function findpath2($startpos,$endpos)
            {
            $movetype = $this->movetype;
            $pathfindinggroupmovecosttable = $this->groupmovecosttable;

            $tentative_g_score;
            $tentative_is_better;
            $lowestcost = 1000;
            $node       = $startpos . "#" . $movetype;
            $openset    = array();
            $openset[$startpos . "#" . $movetype] =1;

            $closedset = array();
            $came_from = array();
            $g_score = array();
            $h_score = array();
            $f_score = array();
            $returnarray = array();
            $current_movetype = array();
            $mover;
            $splitnode;
            $nodemovetype;
            $adjsquarenode;

            $current_movetype[$startpos . "#" . $movetype] = $movetype;
            $g_score[$startpos . "#" . $movetype] = 0;
            $h_score[$startpos . "#" . $movetype] = $this->getnumberofsquarestotarget($startpos,$endpos);
            $f_score[$startpos . "#" . $movetype] = $h_score[$startpos . "#" . $movetype];
            $adjsquares;
            $n;
            $k;

            while ($openset)
                {
                $lowestcost = 10000;
                foreach ($openset as $k => $v)
                    {
                    if ($f_score[$k]<$lowestcost)
                        {
                        $lowestcost= $f_score[$k];
                        $node = $k;
                        }
                    }


                if ($lowestcost == 10000)
                    {
                    unset($openset);
                    break;
                    }
              $mover = $current_movetype[$node];
              $splitnode =  explode("#",$node);
              $node = $splitnode[0];
              $nodemovetype = $splitnode[1];

                if ($node == $endpos)
                    {
                    $urban = $node . "#" . $nodemovetype;
                    return array($g_score[$urban],$this->reconstruct_path($came_from, $came_from[$endpos . "#" . $nodemovetype]));
                    }
                unset($openset[$node . "#" . $nodemovetype]) ;
                $closedset[$node . "#" . $nodemovetype] = 1;

                $adjsquares = $this->getadjacentsquares($node);

                        $n= count($adjsquares); // adjsquares.length;

                        for ($k=0;$k<$n;$k++)
                            {
                            $adjsquarenode = $adjsquares[$k] . "#" . $mover;
                            if ($closedset[$adjsquarenode] )
                                {
                                continue;
                                }
                            $returnarray = $this->getcostfor($adjsquares[$k], $node, $pathfindinggroupmovecosttable, $mover);   // move.getcostfor(adjsquares[k], node, pathfindinggroupmovecosttable, mover);
                            $tentative_g_score = $g_score[$node . "#" . $nodemovetype] + $returnarray[0];

                            if (!$openset[$adjsquarenode])
                                {
                                $tentative_is_better = "yes";
                                $openset[$adjsquarenode] = 1;
                                }
                            else if ($tentative_g_score < $g_score[$adjsquarenode])
                                {
                                $tentative_is_better = "yes";
                                }
                            else
                                {
                                $tentative_is_better = "no";
                                }
                            if ($tentative_is_better == "yes")
                                {
                                $came_from[$adjsquarenode] = $node . "#" . $nodemovetype;
                                $g_score[$adjsquarenode] = $tentative_g_score;
                                $h_score[$adjsquarenode] = $this->getnumberofsquarestotarget($adjsquares[$k],$endpos);
                                $f_score[$adjsquarenode] = $g_score[$adjsquarenode] + $h_score[$adjsquarenode];
                                $current_movetype[$adjsquarenode] = $returnarray[1];
                                }
                          }
                }
            return "failure";
                }




[KGB]

Thanks for the code post. I'm trying to work my way through it now.

In the meantime here's some A* code you can check out already done in JS.

Here's the demo
http://bgrins.github.io/javascript-astar/demo/
Note the demo has a minor bug. If you regenerate the grid it 'forgets' your check box options like diagonal movement so you need to check/uncheck after each regen. But if you turn on 'random weights' you can see how it works in a Warbarons like manner since the weights are the costs of movement. With lots of walls (impassible terrain) you can see it immediately returns no-path.

The code is here if you want to take it. He shows 2 algorithms. You want the 2nd one since it has diagonal moves / weights costs.
http://www.briangrinstead.com/blog/asta ... ent-page-2

I think all you need to do is change his neighbors function. Rather than 'auto push' all 8 neighbors you have to run your GetCostFor() call for each of the 8 squares to get the cost AND whether it's legal (move from land to water, mountains, lava) for the stack.

I'll let you know more once I finish going through your code.

KGB

[gil]

Let me know if you find anything, I´d be more than happy to optimize the code

[/code]

Why does a flying unit and walking unit take the same path?

i think moving the unit with the smallest amount of moves onto a spot where all stack units can stand and then calc movement to that spot for every unit

if you did that moon would not have to split his group to move instead the code automatically does that for him.

[KGB]

Gil,

That won't work.

The reason is the unit with the smallest moves may still move further than units with more movement. How you ask? Well move costs aren't equal so a Dwarf with only 8 moves can move 8 squares on hills while a flying unit like a Gryphon with 15 moves can only move 7 squares.

The hard part is trying to decide whether the path algorithm should be trying to maximize the number of squares that can be traveled in 1 turn or minimize movement costs for multi-turn paths. It can realistically only do one of these.

KGB