RTS - Pathfinding A*

It's an A* (A star) path finding using quad tree nodes. It's incredibly fast.

The fps on the video is low because of the recording, the real has not FPS hit at all.

Category:

Entertainment

Tags:

• RTS
• game
• path
• finding
• a*
• astar
• star
• AI
• IA
• pathfinding

[Freeman0119]

hi nice vid and good work:)

i got a question - isn't A* supposed to find the shortest path? at 0:23 in your video the path doesn't seem like shortest to me. I don't know if it's because of your choice of the heuristic func or what.

would love to see your tutorial btw, i'm trying to learn this stuff and your video looks awesome!

[daivuk]

Ya, maybe the heuristic function needs tweaking. But this code is also very fast. In Starcraft, I can see units doing stuff like that, and it's not that *that* important unless the path finding is very important (Like a simulation or real world problem).

I didn't do the tutorial after all. Too busy :(

[Freeman0119]

thanks. yeah i'm sure the path your algo finds is good enough for any RTS game.

by "fast", do yo mean you have custom optimization in your A* implementation, or are you saying A* is fast itself?

also, do you think starcraft uses similar algorithm (A* + quad tree)? i've been experimenting with warcraft3 but really can't see how it works... it seems that units walk around obstacles via an exact route calculated from obstacle polygons, not via grid cells like in A*.

[daivuk]

Ya, I think starcraft uses quad tree. Because you can see in open area, the units travel on bigger cells.

[Freeman0119]

i played little sc so i don't remember clearly, but suppose a unit goes from (0, 0) to (2, 4), a graph-based algo like A* would create a "zig-zaged" path - first down, then right-down, then down, then right-down ... but the ideal path would be a straight line from (0, 0) to (2, 4). is that what happens in sc? I know in war3 the path is a straight line.

[daivuk]

Yes, they go zigzag, and it looks good because the units are sprite. So they only have 16 directions they can look. In war3, they are 3D mesh, so they can look in the right direction right away.

[kopi0hun]

nice how did you do the different cell size?

[sutasman]

@daivuk nice vid. sorry to bitch on a year old comment, but you should (if you haven't already) at least make the heuristic admissible - this will guarantee you always find the optimal path. if you are smart and make the heuristic consistent then a* is optimally efficient, meaning you get the optimal path in the optimal time (by opening/expanding the optimal number of nodes). also, consistency implies admissibility so if you can just make it consistent. good luck in your future programming!

[Symeon94]

i'm programming a RTS Engine and i first discover * today and try to apply it in my engine, it's hard for me because it's the first time i'm using this algorithm

[Riddicard]

I suspect SC's quad trees handle unit size as well

[decay]

very clever

[DasAntiNaziBroetchen]

wow! nice work bro!

i like the idea with the different sizes of nodes! but still, the best would be to have a polygonal path!

[DarkChris92]

It's the shortest path... The program here doesn't work with pixels, it work with a binary quad tree... This means that the picture is always divided in 2 pieces... And this 2 pieces as well.. Until the map is defined... So some places use bigger rectangles and some use smaller rectangles... The algorithm used this system as well, so that it increased its speed... But this means that the algorithm isn't really as accurate as it could be...

[Freeman0119]

i see... so the algo they use in war3 is quite different? i heard people saying war3 uses A* too but i can't imagine how it works.