tgstation/-tg-station — pull request #592 by Yvar (2013-05-15 11:54:17+00:00)
Title: A-star replacement

(I submitted a manual patch for this a year ago on the old forum, but then forgot and did nothing about it. This version is much better anyway. Oh, and I did have more in-between commits but I'm new to Git, messed things up and just copied the file into a fresh clone.)

Changes:
* Astar.dm rewritten. This version creates paths of identical lengths (not necessarily the
same paths!) while evaluating, on average, only *35%* of the tiles that
the original algorithm would. Seems like a decent improvement!
* Also fixes some grammar and missing full stops in the mulebot file.

Testing:
* See http://i.imgur.com/XHnOuWf.png and http://i.imgur.com/ckSR4wN.png
(image attaching isn't working, sorry) Bias refers to a preference to search along discovered paths, where 1 is no preference and 0 only considers how close the destination is and not the path length. The committed version has a bias of 0.5, which is far more efficient while still finding perfect paths on the initial station layout. (Original is the previous Astar file with an implicit bias of 1, and Replaced is my new file with a bias of 1.) Below 0.5 the improvements are minimal and the discovered paths get worse.
* No runtime errors! At least not in my testing of 'send mulebots to their beacons and home again, sometimes putting things in the way, and see if beepsky can get around quickly'.

Notes:
* Could be further improved with a binary search in one loop but for some reason I couldn't get it to produce equally good results. It's still much better as-is and that can be switched over later painlessly if anyone ever bothers.
* Most of the extra file-size is comments. If the old one was commented I could have saved a lot of time... there's definitely an error in it somewhere that makes it worse than my replacement, but I couldn't track it down.