HenryBlatbugIII Posted June 10, 2014 Share Posted June 10, 2014 The pathfinding in the game doesn't take into account the TU cost of turning. It will therefore often plan a route for your soldiers that includes multiple turns back and forth, leaving them with fewer TUs at the end of their turn than would be possible. You can work around this but manually plotting out their entire movement, but the game's default pathfinding should be able to handle this situation itself. I posted about this issue back in V19.6. I took a break for a while, but came back for V1.0 and found that this bug still wasn't fixed. Therefore, I'm submitting some better pathfinding code that I wrote. (See the attached file. The forum wouldn't let me post it with a ".py" extention.) It's a basic A* algorithm that finds a path in three dimensions: (x position, y position, facing direction) Yes, I'm sure my coding style is terrible, python is the wrong language, and my code is bad and I should feel bad. Regardless, anyone who wants to can play with this code, modify it, and/or adapt the algorithm for use in any spiritual successor to X-COM that they choose. xeno_astar.py.txt xeno_astar.py.txt Quote Link to comment Share on other sites More sharing options...
Gijs-Jan Posted June 10, 2014 Share Posted June 10, 2014 This was fixed earlier, and pathfinding does take turning into account. However due to the fact that game has a variable cost (doors, grass, walls, etc) for movement, along with discontinued paths (teleport etc), A* tends to run non-optimally in terms of time with naive estimation functions. (I probably wouldn't have opted for A* to begin with.) This shouldn't be a problem for human players, as the perceived time to create a path is still in the milliseconds range. However, for the AI this proved disastrous. Therefore, some optimizations were made in the cost & estimation function which more optimistically estimate the path, making A* run more performant; but which sometimes result in non-optimal paths. The regression happened because these optimization probably snuck into the human player path calculations as well. Tl;dr: Regression of the fix, should be easily fixed. Thanks for reporting and I will fix it, but to be honest I didn't think anyone would notice as the pathing deviance isn't as bad as before the fix. ;-) Quote Link to comment Share on other sites More sharing options...
HenryBlatbugIII Posted June 10, 2014 Author Share Posted June 10, 2014 Ah, I see. Thanks for the information. I guess I missed the builds where it was fixed. Also, good point about the variable-cost movement and discontinuous paths. I'm glad the developers know more about this area of programming than I do Quote Link to comment Share on other sites More sharing options...
StellarRat Posted June 10, 2014 Share Posted June 10, 2014 (edited) Well, to be fair, Gijs-Jan has a doctorate in AI if I remember correctly, so he should know more than any of us about this. We are very lucky that Chris got him on the project. The AI is worlds better than it was just a year ago and far surpasses the AI in the OG. It's probably better than most anything you'll find in a game like this. Sorry, Gijs-Jan, I can't help but compliment you on your work here. Edited June 10, 2014 by StellarRat Quote Link to comment Share on other sites More sharing options...
OzoneGrif Posted June 10, 2014 Share Posted June 10, 2014 The AI is very good and often surprises me. thank you Gijs-Jan! Quote Link to comment Share on other sites More sharing options...
Gijs-Jan Posted June 10, 2014 Share Posted June 10, 2014 Well, to be fair, Gijs-Jan has a doctorate in AI if I remember correctly, so he should know more than any of us about this. Not a doctorate (not yet anyway) and thanks! But its good that people are critical; especially when we "cut corners"! Quote Link to comment Share on other sites More sharing options...
StellarRat Posted June 10, 2014 Share Posted June 10, 2014 (edited) Not a doctorate (not yet anyway) and thanks!But its good that people are critical; especially when we "cut corners"! I just realized I think I mixed your schooling with someone else on the forums that was working on a doctorate, LOL! Oh well. It's still good. Edited June 10, 2014 by StellarRat Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.