Optimal programmatic solving of video game movement pathing has been done for
Worms Armageddon battle race maps.
BRSolver is a program which, partially by mapping the possible movements by trying input, finds the optimal (shortest time taken) path through a battle race map. By doing this, BRSolver discovered the
flipwalking glitch and can generate an optimal
WA replay file given any map with start and finish coordinate data.
Here is an archive containing a normally very difficult Yoshi's Island themed battle race map by Wyvern and its BRSolver solution which includes:
-the batch file used to run BRSolver which has start and finish coordinates, plus a couple map-specific flags
-an image which traces the path taken by BRSolver through the possible movement space from start to finish
-a human-readable log of the path taken by BRSolver
-a
Worms Armageddon replay file
http://lex.clansfx.co.uk/worms/Wyvern_YoshisMercilessIsland_BRSolver.zip
Due to the nature of offline competitions in the Worms Armageddon community, the developers of BRSolver (CyberShadow and Deadcode) have decided against releasing the program itself to the public, as it could possibly be used in some way to fabricate competition-winning replays, which would then have to be policed more closely; a great inconvenience for all involved.
I've posted this as a possible inspiration for other similar programs yet to be written because I believe BRSolver to be a program which produces 100% optimal TASes, something that I have not otherwise seen achieved.