• View
• Edit
• History
• Print

Pathfinder

Current pathfinder needs some changes.

The current sectors/regions concept doesn't work very well because often you get regions composed of just a couple of cells. Such regions decrease pathfinding quality.
Also, there are too many regions in general and pathfinder doesn't make much difference between empty regions and regions with many items (e.g. forests).

Thus I'm planning to completely drop current sectors. The map would only be divided into regions.
The only thing that would get slower would be finding all regions in a given rectangular area, but I hope it won't affect us much.

High-level pathfinder

High-level pf is the one that uses regions.

Regions

Regions would have those properties:

• bool water - if true, it's a water region, otherwise land one.
  • This assumes that every cell can be either land or water. But it would be great to have certain amphibious cells, which would be passable for both land and water units (e.g. shallow water).
  • Maybe have ground types or ground classes instead. Every cell would have a ground class property and every unit would know which ground classes it can use for movement.
    E.g. you have land, swamp and water ground types. Soldiers would be able to move on both land and swamp, tanks only on land and ships only on water.
    Each region would then consist of cells of only one ground types.
    We could even create those ground classes dynamically, e.g. land is where waterDeepness == 0.0, water is where waterDeepness >= 1.0 and coast is where 0.0 < waterDeepness < 1.0. Then we could have both land and sea units to be able to move in coastal regions.
    The bad thing about this is that it will lead to higher number of regions which might be bad for performance.
• bool forest - if true, then the region is a forest region. When moving, forest regions should be avoided when possible (i.e. they have very high cost)
  • Is having a single bool enough here? Maybe we'll one different types of special region in the future?
  • We need to make difference between passable forest (high movement cost) and impassable forest (infinite movement cost). Probably forests should be divided into several regions just as normal areas (and forest regions would have same properties as normal ones).
• bofixed cost - movement cost of the region.
  It would be influenced by:
  • forest flag - forest region have much higher cost
  • number of cells - the more cells, the bigger the region and the higher the cost.
  • number of units in the region - the more units in a region, the higher cost. Possibly use number of units / number of cells instead of absolute metrics.
  • region's compactness - size of the bounding rect / number of cells - the more compact regions (which would be mostly rectangular or circular) would have lower cost while irregular (e.g. thin and streched) regions have higher one.
  • number of units using the region in their path -> this might allow us to balance out the routes of the units, so that if you order a large group of units to move, they will choose different routes.
    Actually the regions will probably be big enough to make this pointless - you can easily have tens of units in a 30x30 region without too much crowding. It would be more useful (but more difficult to implement) in low-level pathfinder.

Every cell would store a pointer to the region where it belongs or 0 if it's not in any region (it's works the same way atm).

Constructing regions

We need a way to divide the map into regions. Possibilities are:

• First divide the map into subregions. They should have same properties as regions, but should be smaller (e.g. 5x5 to 10x10 cells). After it's done we can join subregions with similar properties to form bigger regions.
  • How do we divide the map into subregions?
    • Use floodfill algo. E.g. for every cell, if it's not in any subregion yet, start a floodfill algo with this cell as a starting point. Floodfill would be limited to certain number of cells.
      The quality of subregions shouldn't matter much, because they'll be merged into real regions anyway.
• Some kind of logical division of the map, maybe using a voronoi diagram as show in this paper: http://www.qrg.northwestern.edu/aigames.org/2001/Forbus.pdf
  It would probably be quite difficult to implement though...
• Quite interesting multi-level hierarchical A* algorithm: http://www.cs.ualberta.ca/~jonathan/Papers/Papers/jogd.pdf
  Source code of the article is available at http://www.cs.ualberta.ca/~adib/Home/Download/hpa.tgz and is licensed under the GPL so we could use it. Then again, this code is 245kb big...
• Andi thinks a simple breadth-first algorithm will do. I (Rivo) remain sceptical about it. Guess we'll just have to try...

Average region should be about 20x20 to 30x30 cells big

Special regions

We should also add support for special regions. Those are regions which have some special properties. An example of it could be a forest. We can find forested areas using terrain analysis and influence maps and them put them into separate regions and assign higher costs to them in order to prevent units from going there.

The problem here might be keeping those regions up-to-date, since when the map changes, you'll probably need to recalculate the influence maps which might be costly.

Updating the map

When the map changes (e.g. unit's moving status changes), regions have to be updated.
We need to find all regions in the changed area -> probably need to go over all the cells in the changed area and create a list of regions.
Then we need to check if regions are still intact. We may need to split or join some regions.

• subregions (if we store them) could possibly be helpful here because it would restrict search space to a smaller area and we could do the tests faster.
• Andi's idea: use 2 layers of regions: 1st layer is a set of connected cells of the same properties and 2nd layer is regions inside this 1st layer that take units into account. That'd speed things up greatly, as the dynamic layer can be recreated more easily (only cells from the parent layer need to be considered).

Regions would need to be updated when:

• Unit's move status changes in the region (e.g. units start to move)
• Cell's height changes. We don't have realtime terrain deformations atm, but that might change in the future...
• Unit in the region is destoryed/created. The unit might split the region into two...
  If the destoryed (or created) unit is tree, we might need to recalc influence maps to check if the region is still a forest region.

Low-level pathfinder

Low-level pathfinder takes the high-level path and finds accurate low-level path (via cells) using the regions in the high-level path.

Low-level pathing would still use cells, just like atm.
Some improvements would be good though:

• Support for bigger units (units which are several cells big). Current pathfinder only supports single-cell units, a hack is used to make all units a single cell big.
  It shouldn't be too difficult, we'd just need to check occupied status of multiple cells at once (in the main pathfinder loop).
  The much worse problem might be that regions and high-level pathfinder still assume that every unit is exactly 1 cell big.
• To improve pathing quality, we should find an optimal path not to the next region, but to the 2nd next region. It will probably decrease a performace though.

Plans

Here are actual plans/ideas of how the new pathfinder will be implemented:

Idea 1

• The pathfinder will be hierarchical pathfinder with multiple levels of hierarchy:
  • Cells - lowest level of hierarchy are single cells.
  • Subregions - these are small areas (about 20 cells?) of (almost) identical cells. Subregions have region properties (they are traversable without leaving the subregion).
  • Regions - composed of subregions, regions are simply bigger collections of cells, consisting of up to 1000 cells each.
    Regions still consist of only single type of cells (i.e. land-cells, water-cells, forest-cells), so it might be that some regions are very small and consist only of a single subregion (and perhaps even of a single cell).
  • Superregions (better name wanted) - collections of regions which are connected to each other. Superregions have two classes: those consisting of regions which are passable for land unit (e.g. both land-regions and forest-regions) and those which are not (e.g. water-regions).
    This can be used to very quickly eliminate destinations which are not reachable without using transport units. If the starting point and the destination are in a single superregions then might be, otherwise not). Note that whether or not the destination actually is reachable can not be found out just by looking at superregions. E.g. the only path to destination might go through a forest region which is not passable for heavy units (e.g. tanks).
    • Note that ATM every region belongs to a single superregion. In the future if we'll have regions which are passable for both land and water units (e.g. low water), it might make sense to enable regions to belong to multiple supergroups.
• Air units will not use this pathfinder, they'll have their own pathfinder (in the future). As a temporary solution, they might use the low-level pathfinder (maybe a custom version of it), but the main pathfinder will be built for non-air units only!
• Region composition is still a bit unclear.
  Probably first the subregions will be composed (using a flood fill algorithm), then the regions and finally subregions (moving higher in hierarchy).
• Region updating is also not 100% clear yet.
  • When something in a subregion becomes an obstacle, we choose a cell in this subregion and start a flood-fill algorithm from that cell. The floodfill is restricted only to the cells of this subregion. If all cells of the subregion (except for those which became unpassable) are found, then the subregion was not split. Then we can just update the costs of subregion/region/superregion and be happy.
  • If the subregion was split, then we need to choose another cell (not among those that were found by the floodfill) and start another floodfill from that cell to create a new subregion. As that will eventually lead to fragmentation of regions (the subregions will be split and split and will become really small), we should also merge small subregion with their neighbors when possible.
  • If the subregion was split, we also need to check if the region itself was split. For this we can go through all neighbors of the split subregion(s) and check whether there exists a route between every pair of subregions (which lies inside the region). If not, then the region itself was also split.
  • If the region was split, we can take the new subregions which were created by splitting the original subregion and use each one as a starting point for a floodfill search among the subregions of the old region. Each of those searches should then create a new region. Again, if the resulting region is too small, it should be merged with a neighboring region if possible.
  • If the region was split, the superregion might also be split. Checking for this and splitting the superregion should be analogical to that of the regions.
• Use UnitGroups proposal. This should tremendously reduce number of pathfinding queries made when moving big groups.
• There will path cache which will cache high-level paths so that they can be used by multiple units.
• Follow mode for units should be improved a lot. This includes support for formations as written in the UnitGroups proposal.
  • Units must at least try to preserve their relative position with the group leader.
  • It would be good if the whole formation (group) would try to head to a single direction... Might be too difficult to implement though...
  • Units will need to know where the leader is going, so that they can make assumptions about leader's movement (e.g. when will he stop) to improve their own movement. At the moment, in follow mode, units just follow the leader blindly.