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.