tgstation/-tg-station — pull request #4138 by Menshin (2014-07-12 21:21:23+00:00)
Title: Dedust an ancient dark ritual : A*

__Polished and bugfixed A*__

There's currently two (main) way of calling A* :
* only moves in cardinal directions (used by bots)
* moves in all 8 directions (used by diseases and changeling stings)

If an ID is provided, it uses it to see if we can go through it.

__Mandatory images :__ (where grass turfs are processed nodes and blue turfs form the actual path)

(_I originally planned to put gifs showing the path being search, but didn't find a way to record it_)

__All directions procs__
![astar_1](https://cloud.githubusercontent.com/assets/7117411/3562776/2b63f19c-0a07-11e4-91b8-bb65067f3159.PNG)
__Cardinals procs__
![astar_card_1](https://cloud.githubusercontent.com/assets/7117411/3562777/2cbe1720-0a07-11e4-903d-ddd37ae7a41d.PNG)
__All directions procs__
![astar_2](https://cloud.githubusercontent.com/assets/7117411/3562778/2daa3a74-0a07-11e4-83a1-822732c290b2.PNG)
__Cardinals procs__
![astar_card_2](https://cloud.githubusercontent.com/assets/7117411/3562779/2eefebae-0a07-11e4-9728-a9501aa848af.PNG)

* Checked that the changeling sting is (still ?) working as intended (two tiles range).
* Fixed an oversight that could make a path goes through denses turfs with diagonal movements (making you able to catch disease even behind windoors, for example)

__Codewise :__ (might miss some)
* Reorganised and commented used procs for better visibility/maintenance
* Redid the PriorityQueue class
* Changed the euclidian distance to the byond one (so that we don't calculate float and square root when it's not necessary)
* Made the AStar algorithm use the closed list instead of just filling it
* Some optimization in the open list sorting : last entered is first in case of f ties, slightly less tiles are checked now
* Changes the order directions are checked when adding adjacents turfs to make for more 'realistic' path (read less 'drunk pathing' with lots of diagonals)
* Fixed some turfs densities not being check for diagonal movement
* Closed firedoors are now correctly seens as blocked by the algorithm
* Cleanbots now only moves in cardinal directions, like other bots.
* Updated the info text at the beginning of the file a bit
* Absolutely unrelated : simplified the turf.Bless() proc

There's (as always for algorithms) room for optimization, notably in the PriorityQueue definition and sorting.

__Note__ : Beepsky's "engaging patrol mode" lag peek probably happens when the last signal beacon is into space and Beepsky keeps on spamming A* to get there (secbots don't use the proc checking for unsimulated turfs). Limiting how many times Beepsky tries to get a path before idling would solve that, i think.