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.
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.
Okay, thanks
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.
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?
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.
Have you finally made your tutorial?
Tutorial would be nice (even with some example code if you reconsider releasing ’something’).
Something like this could be used for creating paths/roads/rivers for generated/procedural terrain.
Sorry, I’t hard to understand.
Yes you are confused, and you are wrong
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.
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).
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.
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!
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.
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)
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.
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?
cool
I enjoyed this.