I am trying to understand your concept of splitting up the planets surface into smaller subareas to speed up pathfinding, but I always end up with problems that might lead to suboptimal pathfinding. Look at this situation: Red shows where subareas for the pathfinding are. Green shows a big army that blocks everything. We want to go from the blue to the black cross. Scenario 1 (yellow line): We just go straight into the direction of the target and flow around obstacles. Since the flowfields are split up we don't notice the obstacle until we are already off the optimal path. Scenario 2: (orange line): We do an A* over the whole surface first and follow its path. While we follow it we generate flowfields for the subareas we pass through and use them to handle dynamic obstacles. This looks fine on the image. But what if the green army partly moves away in the middle-north and opens a new path we could go through. This would go unnoticed to us if we already did the A* run, since we don't go through the subarea that now offers a new path. To put it simply: How can you make sure that you find an optimal path if you are not considering the whole surface area?
Well i try to explain how i understood it. If i am wrong uber feel free to destroy my post The first thing is the area/sector thing, i think that is mainly to mapping issues as for: What do i need to load into RAM and such. Also its hard to actually make a good mapping of the RAM to a sphere, So you brake up the sphere into some areas that could be easy mapped like a rectangular image. Second: The cost - map, is something like how much does you one step cost. So imagine a step on a street is easy so it may have a cost of 1, a step hill upwards maybe 2 and a step in a swamp maybe 5. Third: Now with this you create a second cumulative cost map, this time for the goal. You start at the goal and add costs (based of the upper cost map) to a pixel. But now its not about what a step would cost from one to another pixel. Now you save your previous costs(steps) also into it. Well i suck a explaining i make a example: imagine the following cost map: Code: 112111111 123211111 112111111 111111111 122221111 123232111 122322211 112222111 111111111 We are originated into upper left corner. We want to go to the lower right conner so we start there at 0 Code: 0 As we go backwards we will add to the next possible pixels the minimum of the previouse pixel that is directly accessible: Directly accessible to a is every surrounding b: Code: bbb bab bbb Code: 11 10 Code: 322 211 210 hint we go from lower rigth to upper left, in the engine that would be made for every direction Code: 5333 4322 4211 3210 Code: 74444 75333 64322 54211 43210 Code: 855555 974444 875333 864322 654211 543210 i will stop here because the lag of digits, and not everybody understands hex. But now imagine your unit is upper left, it will ever go into the direction of the lowest value. which would be 8 5 4 3 2 1 0 Now back to sectors: if you calulated the cumulative map for one sector, which would you chose first? The contiguous sector with the lowest entryvalue of cost. Now you caluclate this sector, after that which sector would you chose next, the contiguous sector with the lowest entry costs of both former sectors. And so on. Eventually you will reach the sector with you units. The good thing of this algorithm is you only need to calculate the cumulativ map once for every goal and movement type.
This is the part where the problems I described occur. If you always just chose the sector with the cheapest entry-cost you will end up on the yellow line, wont you?
that soley depends on the former costs and you have to view it backwards dont start at the unit, start at the goal. What do i mean with entry costs: imagine two boarders: 1.left one: Code: 9 8 8 8 7 7 6 7 7 8 8 9 2. lower one: Code: 99999999999 Both are parts of one sectors boarders. Now which sector would you chose to calculated next: Answer: the left sector that continues the 6 if you have the same value at different boarders you will calculate all regarding sectors. You will continue this calculation till you reach all units of the current movement type assigned to this goal. In the last step you may check if there is a uncalculated border with a lower value as the value direct at the place where your unit is sitting. So final conclusion: Maybe both ways are possible, this is just based on the values in the cummulative map around your unit. If two or more different fields have the same value. You unit is free to chose. Maybe random, or it will chose clockwise or some neural net AI comes into play or or or.
Cola, you can't expect the system to always find a globally and dynamically optimal path. That's just too expensive to compute. The goal is to have a system that finds "good" paths in most situations with reasonable computational costs (and without generating catastrophically bad ones).
I just realized the good thing of this is: The cost(as in computing-costs) oft the algorithm scale only to the number of goals not to the number of units(well and to the scale of the planet). That is indeed great for massive unit RTS.
Ding ding ding. Although there is still work to be done per unit of course. Also calculating flow fields per sector gives us a nice chunk of work for a task queue system for multi threading.
Check out Hierarchical A*, where you A* across higher level nodes (sectors) then on the lower level you run A* to build out your final path. I would say.. that this is what is used in most games today. And you might pose the same question to that technique, as you can't leave the chosen higher level A* nodes. (unless you repath) I don't have that limitation. For flow fields I do something similar but different.. I fill out estimated costs for the higher level nodes (there is one for each sector boundary) such that the resulting flow fields built are more likely to take you to the optimal path found in your example. Check out minute 34 second 50 in the video where units leave the higher level sectors chosen: http://www.youtube.com/watch?v=5Qyl7h7D ... e&t=34m50s Think of the higher level sector traversal more as a culling mechanism, units are not forced to follow those sector results. hope this helps, Elijah
Thanks for the clarifications, so my basic mistake is to assume that the system always finds an optimal path, it will rather search for a near optimal path in most cases, plus it is not as rigid as I thought, as shown in that video-snippet you posted, elitron. I'll read up on hierarchical A*. It's great to be able to so directly ask the devs about this stuff
Any pathfinding system relying on hierarchical subdivision will *always* (you can prove this mathematically) introduce local suboptimality of some sort, but that does not matter so much if the resulting paths are within some fixed margin of error wrt. the global min-cost path and still "look alright" to players. More importantly, if you can get to 90% of the min-cost path with 10% of the CPU cycles, it becomes a no-brainer which to use. Note that the original paper ("Continuum Crowds") on which all this flowfield work is based makes no mention of an A* pass, the CC algorithm as defined by Treuille et all finds the globally optimal solution directly. However it is extremely slow (to quote from the paper: "Simulation updates took between 2 and 5 frames per second (fps)", I also implemented CC myself and quickly came to the same conclusion) to run at decent grid resolution on all but the smallest maps, which simply doesn't work well for games. PS: thanks for the tech-talk, I'm in the 0.1% who can appreciate the gory details and debugging visualisations
Correct me if I'm wrong, but the reason why you do a very coarse A* pass is to hammer down on the size of that expensive CC computation?
Can you give me a link for that or a reference, i am curious about that. BTW: my assumed algorithm above doesnt work right. Going symetrical outwards could generate wrong solutions. You need to go step by step and calculating the neighbors of the cheapest costs first.
