RTS - Pathfinding A*

[kopi0hun]

nice how did you do the different cell size?

[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!

[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.

[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.

[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!

[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...

[inricheetos]

Never mind I already found out

[daivuk]

Hehe cool. Ya, you split in a quad tree (Always in 4 tiles) until the node is empty (Or maximum size, 4 in my case).

And yea, the A* operates just on them, not on the tiles.

[inricheetos]

Hi, how do you split the map into nodes? And the a* operates just on them, not on the tiles right? I want to make a RTS but I'm kind of technically challenged

[Dalahai]

Have you finally made your tutorial?

[daivuk]

No Sorry.

I don't really have time with the development of Babo Invasion.

And before making a tutorial, I would optimize the algo even more.

[Dalahai]

Another question:

You wrote you calculate your quadtree recursively before you start the pathfinding.

Does that mean that you can't insert new obstacles after having calculated the quadtree without lags?

[daivuk]

I dont think inserting new nodes would make it lags at all. But the algo is indeed made for static maps. Like Starcraft. Building being "units" and not map obstacles.

[Dalahai]

Okay, thanks

:)

[conradhw]

Something like this could be used for creating paths/roads/rivers for generated/procedural terrain.

[diegoyotta]

How did you do it? You do it by levels(Bigger nodes are searched first, and soo on?), how did you put your graph in a data structure?

[daivuk]

It's a quad tree, based on the detail required. Then nodes are attached to all neighbor. A A* pathfinding doesn't have to be a tiled map, it can be anything, because after all they are just nodes connected to each other with heuristic between them.

Having quad tree, the algo is faster and the unit turns left often.

[diegoyotta]

So you actually put everything in a data structure where the leaves are actual tiles? How do you convert a 2d array into a quad tree(efficiently)

[daivuk]

Creating the quad tree is done recursively,

you can google how there are a lot of tutorials about this.

Then I keep my 2D array, which is now an array of pointers on the quad nodes. So At any position I can know in which quad node I am.

I wanted to write a small tutorial about this, but I don't really have the time.

[diegoyotta]

How fast is it? Ok, Let me resume: I make a quad tree out of a 2d array, then I can usa A* to traverse the tree, just like any other graph.

Thanks!

[daivuk]

It is really fast, because I don't travers the quadtree, at that point they are only nodes like normal A* nodes. And I traverse them in a single function I optimized to 1 page, and I while() NOT RECURSIVE in real time. The recursive part is only at the level loading.

[diegoyotta]

I'm kind of confused. Could you give me some code I can look at? or the sequence followed by the program?. Correct me if I'm wrong, the top level tiles(big ones) are traversed first, and then you look at subtiles on demand, like when a top level tile is too big(0:12 min). Can we use E-mail. mine is tetraminx (at gmail).

[daivuk]

Yes you are confused, and you are wrong :P

There is no top level nodes. They are just nodes, with a center position, and a list of all touching nodes with heuristic between them.

I will not give the code I am sorry. But I will probably do a tutorial about this.

[diegoyotta]

Sorry, I't hard to understand.

[conradhw]

Tutorial would be nice (even with some example code if you reconsider releasing 'something').

[outbreakz]

cool

[CryptRat]

I enjoyed this. :)