impossible terrain - path finding crash

[SnotlinG]

Thanks,
it is very good feedback. I will dig into it deeper when I start making the changes. Most important is for the Seacreatures, so probably I will start with the boat/seacreature issue and see how it works from there.

This development wont start for at least another few weeks (have some other stuff in the pipeline first), but I´ll get back here when I start working on it, and brainstorm some more...

Thanks!

[Chazar]

Okay, I am sure that pathfinding itself might be tweaked to benefit from the area information (aborting searches whenever they enter new area code that is "disconnected" to the target area), but I have not thought much about it yet - and it is hard to tell anyway, since I do not know your pathfinding algorithm (but I can think fresh about pathfinding).

[SnotlinG]

Pathfinding is based on:
http://en.wikipedia.org/wiki/A*_search_algorithm

But obviously tweaked to take into account the annoying Land/Sea conversions that can happen to units

[tabanli]

Another strange case is when you click on a lake without ports with land units. This was not a ladder map.

[Chazar]

Are there still any open questions with respect to this?

I reread it and don't think there is much to add. Beyond the shortcut for infeasible paths, I do not see an obvious way on how to improve the A* search algorithm with using the area codes. The only thing that comes to my mind would require to store how the the different areas are connected with each other, so instead of the simple representative, a proper graph is required that tells us, for example, that ocean 1 is connected to ocean 5 only via swamp 2, then ocean 3, then swamp 4. However, I doubt that this effort will speed up pathfinding any more - and it does not seem necessary either.

So the simple area codes with one array to store the representative area codes for each of the combined movements (aquatic=combines water, swamp, city, temple, ruin, port area codes; boat combines water, port and all land area codes, etc.) seems easy enough to store and will fix these long waiting times.

[KGB]

There must be a bug in the current A* implementation because it should not be hanging like it is when clicking on impossible terrain. I've implemented A* before and never had this occur.

My *guess* is that the search path is folding back on itself (visiting squares that have already been visited) in some manner where you aren't marking squares as visited so that you put them in the queue to be evaluated again. Once there are no more 'unsearched squares' in the queue it should exit with a 'path not found'. Even on a 150x150 map it should take less than a second to search all 22500 squares (absolute worst case).

KGB

[SnotlinG]

Its some time since I wrote the code so I probably dont remember everything. But I think the algorithm is always trying to find a cheaper way to the goal, so it cant really mark tiles as complete.
So it saves the total cost for moving to a tile a specific way, and then tries to find a cheaper way if possible. The problem with the impossible terrain things (which usually are a land area if you are a seacreature or something like this) is that there is no cheaper way, but the algorithm cant know this, and is checking further and further away to see if there is any way around. Until it has pretty much calculated the way to all tiles on the map. Another issue is that in warbarons we have 2 modes (Land and Sea), compared to the original A* algorithm which just has a cost for moving into a tile. For us, the cost depends on which mode you are in, which in turn is changed depending on specific tiles you move on (Anchors).

Here is the main part of the code:

Code: Select all

           function findpath2(startpos,endpos)
              {
                 
            var pathfindinggroupmovecosttable = misc.clone(move.groupmovecosttable);

            if (pathfindinggroupmovecosttable['mixedgroup'] == "yes")
                {
                pathfindinggroupmovecosttable['Land']['GX'] = 1.9; 
                pathfindinggroupmovecosttable['Land']['DX'] = 1.9; 
                pathfindinggroupmovecosttable['Land']['FX'] = 1.9; 
                pathfindinggroupmovecosttable['Land']['HX'] = 1.9; 
                pathfindinggroupmovecosttable['Land']['MX'] = 1.9; 
                pathfindinggroupmovecosttable['Land']['SX'] = 1.9; 
                pathfindinggroupmovecosttable['Land']['VX'] = 1.9;
                pathfindinggroupmovecosttable['Land']['Br'] = 1.9;
                pathfindinggroupmovecosttable['Land']['RB'] = 1.9;   
                }
      
               
              var tentative_g_score;
              var tentative_is_better;
              var lowestcost = 1000;
              var node =startpos+'#'+movetype ;
              var openset = new Array;
              openset[startpos+'#'+movetype] =1;
              
              var closedset = new Array;
              var came_from = new Array;
              var g_score = new Array;
              var h_score = new Array;
              var f_score = new Array;
              var returnarray = new Array;
              var current_movetype = new Array;
          var mover;
          var splitnode;
          var nodemovetype;
          var adjsquarenode;
   
              current_movetype[startpos+'#'+movetype] = movetype;
              g_score[startpos+'#'+movetype] = 0;
              h_score[startpos+'#'+movetype] = getnumberofsquarestotarget(startpos,endpos);
              f_score[startpos+'#'+movetype] = h_score[startpos+'#'+movetype];
              var adjsquares;
              var n;
              var k;
           
              while (openset)
                 {
                 lowestcost = 10000;
                 for (var x in openset)
                    {
                    if (f_score[x] < lowestcost)
                       {
                       lowestcost=f_score[x];
                       node=x;
                       }
                    }
                 if (lowestcost == 10000)
                    {
            delete openset;
                    break;
                    }
            mover = current_movetype[node];
            splitnode = node.split("#");
            node = splitnode[0];
            nodemovetype = splitnode[1];

                 if (node == endpos)
                    {
                    return reconstruct_path(came_from, came_from[endpos+'#'+nodemovetype]);
                    }
                 delete openset[node+'#'+nodemovetype];
                 closedset[node+'#'+nodemovetype] = 1;

                        adjsquares = getadjacentsquares(node);
                       
                        n=adjsquares.length;
   
                        for (k=0;k<n;k++)
                           {
                           adjsquarenode = adjsquares[k]+'#'+mover;
                             if (closedset[adjsquarenode] )
                              {
                                 continue;
                              }
   
                           //returnarray = move.getcostfor(adjsquares[k],node,mover,"pathfinding");
                           returnarray = 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] = getnumberofsquarestotarget(adjsquares[k],endpos);
                              f_score[adjsquarenode] = g_score[adjsquarenode] + h_score[adjsquarenode];
                              current_movetype[adjsquarenode] = returnarray[1];
                              }
                          }
                 }
                  return "failure";
               }


[KGB]

SnotlinG,

What makes A* so great is that once you visit a node (square) you never visit it again. The idea is that each time you check a new node (square) it's supposed to be the cheapest path to get to that particular square. So there is no need to check again to see if there is a better way because by definition the first time you visit you have the cheapest path.

For impossible terrain you should not add it to the search path (land units on mountains or sea units on land).

For example consider the following. Stack wants to move from X to Y. Cost of the nodes (A-F plus Y) in brackets. Any node can reach any node above/below it.

X-A(1)-B(1)-C(5)-Y(2)
\D(3)-E(2)-F(2)/

Time1: From X, add (A-1) and (D-3) to the path. Pick the cheapest one (A) from (A,D)
Time2: From A (total cost 1), add (B-2 which is A+B cost), (E-3 which is A+E cost). Pick cheapest one (B) from (B,D,E)
Time3: From B (total cost 2), add (C-7 which is B+C cost), (F-4) which is B+F cost). Pick cheapest one (D) from (D,E,F,C)
Time4: From D (total cost 3) there is nothing new to add (already visited everywhere D can reach so its not in the optimal path). Pick cheapest one (E) from (E,F,C)
Time5: From E (total cost 3) there is nothing to add (already visited everywhere E can reach so its not in the optimal path). Pick cheapest one (F) from (F,C)
Time 6: From F (total cost 4), add (Y-6 which is F+Y cost). Pick cheapest one (Y) from Y,C)
Time 7: Stop, we reached destination. Total cost 6. We never even visited C nor computed paths from many other ways because we didn't need to.

If you don't put impossible squares in the search path (which you shouldn't) then for impossible paths, you will eventually run out of nodes in your path to select from. If that happens and you aren't at Y, then you have an impossible path and can tell the user.

KGB

P.S. I looked quickly at the code. Some of the functions you call, I don't see but I can guess at.

Definitely this call:

adjsquares = getadjacentsquares(node);

Should not return any impossible squares for the stack to move on. It should also not return any square you have already visited prior to this (or you need another function/array that tracks what you visited and ignore already visited squares).

This call

returnarray = move.getcostfor(adjsquares[k], node, pathfindinggroupmovecosttable, mover);

I assume returns the cost for moving to that square. But the full value should be the move cost for the square PLUS the sum of all the path required to get here. That's how you ensure you get the cheapest cost to reach any square along the movement path.

The rest of the tentative logic I won't pretend to understand since I know it involves trying other paths. Which you won't need to do if you track the full cost for each square rather than just the cost to move into it. You also won't need the lowest cost = 10000 stuff either.

And your openset should always be sorted cheapest to most expensive so you start with the cheapest node. Just sort once after you all all the new nodes (squares) to the openset.