Not a library, but a proof of concept for anyone interested in how to implement this algorithm in a SC2 map
What is A* (A-Star)?
It is a pathing algorithm used in SC:BW and many other games. To not just copy and paste walls of text here is a good introduction: A* Pathfinding for Beginners
How can this be useful?
I am trying to recreate the pathfinding system of the old game , where units prefered some terrain over others, like roads over desert. At the moment I can´t promise if it´ll work.
v1.2 I managed to recreate the found path. It is marked with the FeedbackImpact model.
v1.3 The found path is deliverd to the unit with waypoints. I made the waypoint model invisible, so its a little prettier.
v1.4 I added a "TriggerTookTooLong" protection. So more complex paths can be calculated. The drawback is that the trigger is more time-consuming.
v1.5 Roads now have priority over usual terrain.
v1.6 I´ll think this version is as close as it can get to the original pathfinding algorithm of Z. Only thing left to do is apply a speed buff, when a unit enters the road.
v1.7 Just polished the code and the map; including smart waypoints. There should be no more trigger errors, so hopefully the last version I uploaded.
until v.1.5 If the while loop in the "pathfinding" action is executed too long, calculating a more complex path, it can cause a "Execution took to long" error.
not really possible....... Unless your talking a very small map...
youd have to pre place like a million points and then calculate these points over and over again....
the points would require a value ...... in some kinda massive array.....
then youd have to add up the values of all these points find the least costing one then have the unit walk to those specific points one at a time rather than using the built in pathing system......
placing actors as you have in such a manner on your test map would fail on a larger sized map considering actor limitations cap out at about 16000 which is pretty easy to hit when you place them in a 1x1 grid
Rollback Post to RevisionRollBack
KageNinpo = SN
DialogLeaderboard & TeamSort
On a small scale however of say 100x100 or smaller using unit markers would work just fine if you say wanted to have several maps within a map. This is very interesting to me, but far to technical for my understanding.
I'm sure you're aware of what it does and does not do but just in case, while it does identify the best path the unit doesnt actually take it. I would like to see a demo where a unit goes well out of its way to take the path that it deems 'fastest.'
If I´ll take a 256 x 256 map, the largest possible, and add nodes (distance between nodes = 1) I would need an array size of 65536 oO. The limit on arrays is 8190 iirc, so yes its impossible. anyways I´ll had fun creating it. :)
Actually, i never have to write pathfinding for myself (as i never created full game with AI), but i read a bit about it and i i know wikipedia should tell you more about it. See "example" section. In your code you actually created a node for each terrain "cell" and link neighboring cells together.