A* is working, check it out (click on image)
It works now on tiles but its too slow, got to find a different solution.
Written by MM. Posted at 5:48 am on September 2nd, 2009
11 comments.
Post a comment.
So, it’s a way to set a bots path? Can the path be learned automatically?
hallelujah, michal. but why is it too slow? the bot doesn’t need to be updating its path every tick. can’t it just figure out part of the algorithm per tick, and put together a path every few ticks?
Pre-computation and/or subdivide the path finding area’s?
i want the bots to learn the paths the players use :D:DD
options:
* improve algorithm implementation for speed
* don’t recalculate the path every tick
* limited length of the precalculated path
How many nodes do you have in each tile? A* is very fast for hundreds of nodes if the graph is highly connected (lots of paths). Is it just slow between tiles? If so use a coarser grained graph with a node for each tile for the overall plan, then use a fine grained search just for seeing how to get to the next tile.
It can be updated every couple seconds. Still it can calculate for more than 30ms which is unacceptable.
Updating part of the path each tick? Don’t know if that’s possible with A*?
Tinman: good idea. It is slow between tiles because there is lots of them. On the screen I posted there is a couple hundred nodes.
How pathfinding works in Soldat?
1) Create a list of points, 200 per map or so
2) Create paths between those points
3) Cache them
Result? subdivided paths. The algorithm then composes a path from currnt location to B, B to F, F to Your Face, where the actual path is composed of many, many points.
If a bot needs to go to a location in a straight path (up to 2 hops) from a waypoint, it just goes there. If a bot needs to go to some weird location that requires more than 2 hops or crossing barriers, add a newpoint there.
And this all coming from a guy who didn’t know how to write a bubble sort up until 15 years old. Lol at me, yeah.
@yv3:
There is no pathfinding in soldat. The bots follow waypoints placed by the map creator.
Hey MM — this article on hierarchical clearance-based pathfinding might be of interest to you. It incorporates a great many techniques including subdivision and areas passable for some units but not others.
http://harablog.wordpress.com/2009/02/05/hierarchical-clearance-based-pathfinding/