A* vs Shortest Path

Been dabbling with an A* pathing algorithm applied to the graph of CPs in the game, and getting interesting results. For some reason, I missed the fact that A* doesn’t ensure a shortest path.

[osmith@fedex src]$ ./test
cpMap contains 526 city CPs, total links 1966, with factories in 10 CPs.
 Köln, Düsseldorf, Amiens, Montreuil, Abbeville, Canterbury, Whitstable, Ashford, Frankfurt, Essen
Test factories: Köln Amiens Canterbury

Success:  Kalmthout to Faversham took 0ms.
   Kalmthout>Antw>Wals>Tern>Ijze>Bres>Mald>Zeeb
    ->Oost>Rams>Marg>Whit>Fave
A* result: 12 hops, my algorithm says: 12 but took 0ms.
Success:  Faversham to Kalmthout took 0ms.
   Faversham>Whit>Marg>Rams>Oost>Zeeb>Mald>Bres
    ->Ijze>Tern>Wals>Antw>Kalm
A* result: 12 hops, my algorithm says: 12 but took 1ms.
Success:  Kalmthout to Amiens took 0ms.
   Kalmthout>Antw>Tems>Dend>Wett>Zott>Oude>Avel
    ->Roub>Lill>Secl>Lens>Arra>Saul>Doul>Talm
    ->Amie
A* result: 16 hops, my algorithm says: 15 but took 0ms.
Success:  Ouddorp to Hahn took 0ms.
   Ouddorp>Stel>West>Hell>Spij>Crom>Dord>Moer
    ->Oost>Waal>S-He>Boxt>Eind>Helm>Grie>Pann
    ->Roer>Roer>Hein>Erke>Juli>Dure>Woll>Nett
    ->Musc>Daun>Witt>Zell>Hahn
A* result: 28 hops, my algorithm says: 24 but took 1ms.
Success:  Hahn to Ouddorp took 0ms.
   Hahn>Bern>Witt>Bitb>Prum>St.V>Malm>Stav
    ->Spa>Verv>Lieg>Ware>St.T>Hass>Paal>Geel
    ->Grob>Oost>Wuus>Zund>Bred>Moer>Will>Crom
    ->Spij>Hell>West>Stel>Oudd
A* result: 28 hops, my algorithm says: 24 but took 0ms.
Success:  Faversham to St.Avold took 0ms.
   Faversham>Ashf>Lymp>Le T>Mont>Hesd>St.P>Aubi
    ->Arra>Marq>Camb>Caud>Cati>Nouv>LaCa>Hirs
    ->Aube>Liar>Sign>Laun>LeCh>Buza>Sten>Mont
    ->Long>Spin>Pien>Font>Thio>Metz>Bouz>Creu
    ->St.A
A* result: 32 hops, my algorithm says: 27 but took 1ms.
Success:  St.Avold to Faversham took 0ms.
   St.Avold>Faul>Ravi>Metz>Jarn>Etai>Verd>Mont
    ->Gran>Sech>Somm>Beth>Reim>Berr>Laon>La F
    ->St.Q>Rois>Pero>Bapa>Arra>Aubi>St.P>Hesd
    ->Mont>Same>Boul>Folk>Lymp>Ashf>Fave
A* result: 30 hops, my algorithm says: 27 but took 0ms.
Success:  Faversham to Hahn took 7ms.
   No route
A* result: 0 hops, my algorithm says: 0 but took 0ms.
Success:  Hahn to Faversham took 2ms.
   No route
A* result: 0 hops, my algorithm says: 0 but took 0ms.

1000 iterations of factory link propagation took 70ms
520 cps are factory linked.

Time taken for 5155000 steps thru 1000 iterations: 3326ms
Towns that have factory links: 520, towns that don't: 0

My algorithm is pretty simple:

newCandidates = [ start ], closedSet = [ ]
stepCount = 0
repeat until newCandidates is empty

  increment stepCount

  add newCandidates to closedSet
  openSet = newCandidates
  newCandidates = [ ]

  for lhs in openSet    (lhs = left hand side)
    for rhs in lhs.links  (rhs = right hand side)
      if rhs == goal then return stepCount
      if closedSet contains rhs then skip
      insert rhs into newCandidates
    end                    (rhs loop)
  end                      (lhs loop)
end                        (until newCandidates empty)

return -1                  (there was no route)

The separation of openSet and newCandidates ensures ensures that we consider all paths of a given length first. closedSet is the set of nodes that have been added into consideration already and prevents doubling back.

If all I want to know is “how far away is it”, this is a great algorithm. But if I want to know “how do I get there”, well it doesn’t do that :)

The one shortest path algorithm I looked at (a) I couldn’t make heads or tails of and (b) was incredibly inefficient.

12 Comments

I think you are confusing two cost metrics here – A* would produce lowest-cost (least hops, it seems) route if your heuristic (geographic distance to target CP, I guess) was an admissible. With geographic distance heuristic A* should produce a route with shortest possible total geographic path length .

*nod* In my A* algorithm I started out calculating ‘h’ as the distance to the goal node in physical terms.

AStarWeight GoalDistanceEstimate(const CPSearchNode* goal) const
{
AStarWeight xd = this->octetX() – goal->octetX() ;
AStarWeight yd = this->octetY() – goal->octetY() ;
return ((xd*xd) + (yd*yd)) ;
}

template bool GetSuccessors( AStarSearch<_t>* astarsearch, const CPSearchNode* parent ) const
{
if ( m_friendlyLinked == false )
return true ;

LINKS::const_iterator it ;
for ( it = m_links.begin() ; it != m_links.end() ; ++it )
{
CPStruct* rhs = (CPStruct*)((*it)->endDepot->cp) ;
if ( rhs == parent )
continue ;
// Base on control
if ( rhs->controllingSide != this->side )
continue ;
if ( astarsearch->AddSuccessor((_T*)rhs) == false )
return false ;
}
return true ;
}
AStarWeight GetCost( CPSearchNode* successor ) const
{
AStarWeight xd = (AStarWeight)(this->octetX() – successor->octetX()) ;
AStarWeight yd = (AStarWeight)(this->octetY() – successor->octetY()) ;
AStarWeight cost = ((xd*xd) + (yd*yd)) ;
// Contention hurts bigtime.
if ( successor->contention )
{
cost = (AStarWeight)(cost * (this->contention ? 3 : 2)) ;
}
// Moving towards the frontline should be avoided
// while moving away from it should be advantageous
// and moving along the frontline should be unpopular
if ( this->enemyLinked == false && successor->enemyLinked ) // Towards frontline
{
cost = (AStarWeight)(cost * 1.1) ;
}
else if ( this->enemyLinked == true && successor->enemyLinked ) // Away from
{
// 0.9 or less would undo the cost of moving towards the frontline
// 0.95 will only apologize for a move towards slightly
cost = (AStarWeight)(cost * 0.95) ;
}
else if ( this->enemyLinked && successor->enemyLinked )
{
cost = (AStarWeight)(cost * 1.25) ;
}
return (int)cost ;
}

Obviously, I also tried it without the fancy weight building but what I want is shortest path.

static UINT32 _myAlgorithm(const char* from, const char* to)
{
CPStruct* start = strtGetCPByName(from) ;
CPStruct* goal = strtGetCPByName(to) ;
assert( start != NULL && goal != NULL ) ;

UINT32 steps = 0 ;
if ( start == goal )
return steps ;
// Check feasibility
if ( goal->side != start->side || goal->controllingSide != start->side )
return -1 ;

std::set openset[2], closedset ;
UINT32 useset = 0 ;
std::set
::iterator lhs ;
CPStruct::LINKS::iterator it ;

openset[useset].insert(start) ;

do
{
++steps ;

UINT32 writeset = 1 – useset ;
openset[writeset].clear() ;

for ( lhs = openset[useset].begin() ; lhs != openset[useset].end() ; ++lhs )
{
closedset.insert(*lhs) ;
for ( it = (*lhs)->m_links.begin() ; it != (*lhs)->m_links.end() ; ++it )
{
CPStruct* rhs = (*it)->endDepot->cp ;
if ( rhs == goal )
return steps ;
if ( (rhs->side != start->side || rhs->controllingSide != start->side) && rhs->country != WWII_CHINA )
continue ;
if ( openset[useset].find(rhs) != openset[useset].end() )
continue ;
if ( closedset.find(rhs) != closedset.end() )
continue ;
openset[writeset].insert(rhs) ;
}
}
useset = writeset ;
}
while ( openset[useset].empty() == false ) ;

return -2 ;
}

(Apologies for lack of comments, I really rattled that out as a simple bench and shocked myself by it working flawlessly and efficiently first time!)

I’d need to use “myAlgorithm” to calculate the hops in the first place to do otherwise.

I’ll probably need to spend more time looking at the routes it calculates. I think I might snag the source code to BEGM and use Xiper’s rather nice map system as a UI for it :)

Adleman imagined testing his DNA computer with something called a directed Hamiltonian path problem. (The Hamiltonian path was named after Irish mathematician William Rowan Hamilton, who devised the routing conundrum in 1857.) A simplified version of this, known as the traveling salesman problem, poses the following question: Given an arbitrary collection of cities a salesman has to travel between, what is the shortest route linking those cities? Adleman’s version limited the number of connecting routes between cities by specifying in which cities the salesman should begin and end his journey. Since not all cities are directly connected, the challenge lay in discovering the one continuous path to link them all.

A Hamiltonian path problem involving four or five cities can be solved by doodling on a piece of paper, but when the number of cities grows by even a small amount, the problem’s difficulty balloons – it becomes what is known in mathematical terms as “hard.” Hard problems cannot be solved efficiently by algebraic equations. Answers can only be found by crunching through every possible solution, and most hard problems are too difficult for humans or computers to solve. Finding a Hamiltonian path connecting 100 cities using a well-known algorithm, for example, would take 10147 operations. Assuming one was trying to solve the problem on a computer working at 1 trillion operations per second, this computation would take 10135 seconds – vastly longer than the age of the universe!

I do know a *tad* about GAs, pathing etc, which is perhaps why I produced such an efficient little routine while half asleep on a 15 minute break that is surprisingly resistant to further optimization :) I tried it on a facility map (5187 nodes) and it still generally tends to complete in very short orders :) TS algorithms tend not to be helpful in this case because I’m not trying to analyze the graph, just solve a specific subset of it :)

I just haven’t done much work with named algorithms (haven’t had a dataset and an incentive at the same time, and I learn best when I have something meaningful to apply the knowledge to; practical learner – no back propagation = no long term store)

“…10135 seconds – vastly longer than the age of the universe!”

Is that missing a few exponents in the original article.

10135 seconds is less than 3 hours.

I think an acceptable solution for my need might just be to tag each node in the route with “which exit did I take from the origin”. I don’t need to know the route, I only need to know the best next hop.

1. Always complete the last “shell”;
2. Choose the next-hop with the most vias – which will probably be 1 most of the time but at least if there are multiple options you’ll have the least chance of having your route disrupted during transit.

I think it was supposed to be 10^135 seconds?

@kfs1 – with 5k nodes to check, but only from either left side or right side, can’t you set ‘landmarks’ such as “Antwerp in supply” so set hops from Antwerp? (or LUX, or any major node?).

Why not just use dijkstra’s algorithim?

It was an excuse to try out A*. The two Dijkstra algorithms I tried both proved to frequently have a high cpu-cycles cost with our map. My little algorithm is pretty close to Dijkstra but takes a lot of shortcuts since it’s working with a specific dataset.

The sad thing is, the official algorithms are routed in the 50s and 60s and so they are rather cryptic and algebraic – variables with names like f, g and h… *sigh*

Remember not to accept the goal node when first discovered, only after it is taken off the open list.

Leave a Reply

Name and email address are required. Your email address will not be published.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

You may use these HTML tags and attributes:

<a href="" title="" rel=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <pre> <q cite=""> <s> <strike> <strong> 

%d bloggers like this: