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.
VERSIONS
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.
v1.6
Bugs
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.
Do hope you can add support to create artificial pathing (blocking only a select few units from going down an otherwise unblocked path for other units) via trigger if you could.
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
Skype
KageNinpo = SN
My Libraries
DialogLeaderboard & TeamSort
My Projects
SPACEWAR Tribute
Infinite TD
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. :)
I am currently thinking about how the found path could be delivered to the unit. I want to avoid adding waypoints on every found node. At the moment the marine is still using the SC2 pathfinding.
SC2 probably uses A* too :P but i don't know. How about custom nodes? A* can find a way not only on grid ;) I found it useful on hex-based games ;) There are often small arenas in maps like that.
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.
credits go to maverck for his pioneering work
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.
VERSIONS
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.6
Bugs
@petrov1: Go
Go on..
Do hope you can add support to create artificial pathing (blocking only a select few units from going down an otherwise unblocked path for other units) via trigger if you could.
@petrov1: Go
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
@SouLCarveRR: Go
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.
@petrov1: Go
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.'
@SouLCarveRR: Go
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. :)
@rpc190: Go
I am currently thinking about how the found path could be delivered to the unit. I want to avoid adding waypoints on every found node. At the moment the marine is still using the SC2 pathfinding.
SC2 probably uses A* too :P but i don't know. How about custom nodes? A* can find a way not only on grid ;) I found it useful on hex-based games ;) There are often small arenas in maps like that.
@Frizi: Go
Well, I am a A* noob. What you mean with custom nodes? Could you be a little bit elaborate about it or guide me to a tutorial.
btw I uploaded v1.3. The found path is now delivered to the marine.
edit: v1.4 with "TriggerTookTooLong" protection is up
edit edit: v1.5 roads have higher priority than usual terrain.
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.
updated first post + vid
I think I got it as close as it can get to the pathfinding system of Z. :)
@petrov1: Go
Well done, very impressive.