Hi... Does anyone know which algorithm path finding is based on in PA? The Manhattan algorithm in the following javascript seems pretty good: http://qiao.github.io/PathFinding.js/visual/
yeah, the PA world is basically water and the units are submarines with sonar. At least that's what I understand. Not sure if that's a precise analogy.
How about, when you issue an order to a location, you spill a bucket of paint at that location. But the paint is special, it changes color the further it travels. Then when units move, they look at the paint and determine the direction in which the paint looks more like the spill point. Does that make sense xD?
Wow, nice website! The algorithm name is above the box (e.g. A*, IDA*, Dijkstra, etc.), Manhattan stands for the neighbouring scheme and distance function used by the algorithm EDIT: the heuristic that the algorithm uses to estimate the distance to the goal, the real distance function is always the same (L2) (look here to see why it is called Manhattan). You can choose different algorithms and compare how well they fare on this site very nicely. Those algorithms are discrete path finding algorithms, which means you can use these to find path on worlds which have a discrete geometrical space. Like the site, that has a square tiling or most other RTSes like C&C and SupCom. If you played PA, you will notice that PA doesn't have such a tiling, you can place buildings and units "freely" on planets, that means that you need to find paths from any "point" to any other "point". As far as I can read from the debug outputs, the developers are using a trick: They divide this continuous 3d space up into discrete 3d blocks or boxes, called voxels, then they build a neighbouring graph that follows the planets surface on those voxels. That means if you can walk on the surface of the planet from one voxel to another, they are neighbours in the graph. If this is done you are left with a discrete "subspace" of R3 that is represented by this graph, now you can use the algorithms on your site to find a path (most likely they use A*, see below). But there is another thing: PA tries to find paths not only one unit like those classical path finding algorithms do. Imagine you have an army of 1000 tanks, and you attack an distant base with them, even when A* is really fast (on my computer a simple implementation with an reasonable sized environment takes up 1.2 ms for a single path) it would take ages to calculate a path for each unit (in my example it would be 1000 units * 1.2 ms = 1.2 seconds!). So PA uses a method called potential field path finding (it is usually referred as flow field in this forum) that finds groups of paths for a single target. To do this it calculates - for a given target - a potential field that decays as you go further and further away from the target. A unit just needs to follow that potential field upwards (aka as the gradient of the potential) to find the target. The value of this potential can be stored in the voxels. But there is a catch, and I assume Uber uses this, but this is basically pure speculation): If you instead of calculating the potential field completely, which would take too long, and just estimate the potential field there is usually no guarantee that there are no blind ends in that field where units might get stuck. For this reason you take the A* algorithm from the site you mentioned to find a path to the target, once a path is found you can generate a potential field from the information you gathered during that search. The good thing about this is, that it works incrementally, if you encounter a voxel which has not potential field value, you just start a new A* search to extend the potential field to this voxel. So you see, the algorithms on this site are (probably) related to what Uber uses, but it is a bit more complicated then might look at the first glance. If you want to learn more about those things, there is a nice book that talks about motion planning (just another word for path finding) from Steven LaValle. It's mostly about continuous state spaces, but the discrete methods are mentioned in chapter 2.
Amazing work by the poster above me, just a couple of additions: "inferior javascript path finding" means you didn't visit the page, or really understand pathfinding, sorry The page is demonstrating some of the various techniques used in point-to-point pathfinding (for single entities, as well). It's a really neat little demo. The only thing "JavaScript" about it is that it was written in JavaScript. This is right, to the best of my knowledge.
PA uses a combination of flowfields and A*. A* is used to generate a high level path so that we know what sectors are going to be hit for the pathfinding request, and to help verify that the path will succeed. We then generate a flowfield for the unit to follow to its destination. The flowfield goes voxel by voxel and sets a direction on each voxel for the unit to follow.
Am I right that those sectors are something like 10x10x10 voxels? Enabling Nav-Debug and pressing some keys, I currently can not remember, revealed a psychedelic-coloured looking structure overlayed on the voxel grid, I would now assume that this was the sector display.
So why do students get stuck? Does that have to do with when flow fields are updated? Do units not update their path if they collide with something or don't move for a period of time?
The two bugs I fixed yesterday were as follows: 1) Units, while in motions, would stop moving if a structure was placed over the top of them. The reason for this is complicated, but the gist is units are shoved out of the way during the physics step, which happened after the path update. During the path update the path system would realize the unit was standing inside of a wall and was unable to find a neighboring valid voxel (since structures are large). 2) Units would spin around in circles because a sector border voxel would not have a path direction due to being ignored during the integration step. When the path system hits a voxel with no direction (which normally occurs before the flow field has fully integrated) it is set up to have the unit move to the next border in the A* chain. Since the border was the voxel with the issue, the unit would spin around that voxel like an idiot. Basically, path finding is full of edge cases and is not a simple system to create.
wow nice explaination Sorian, you're able to switch from AI coding to pathfinding bug fixing while you might not be the original coder ! When i consider the amount of academic knowledge one have to acquire in addition to strong dev skills, this is really impressive.
Indeed! I think the PA engine has done really well considering the technical challenges. I'm not sure of any other games that do pathfinding on a spherical body/planet, at such a scale (thousands of units). Also, if you (or any other developer) ever get bored one night and want to go into more detail about the systems you have created for PA, I for one would love to read about them. Another blog update, perhaps Tide us over until the documentary! edited: formatting, last paragraph.
