[Question] Easier pathing (maybe faster too)

[NeonStorm]

pathfinder.png (18.09 KiB) Viewed 1380 times

Ravaged_v2 map (edited preview)

--- 1. Handle each path-able|obstructing area as polygon.

Obstructing is everything where the height-difference is too extreme for a unit to walk across.

Tree-structure:
. Obstructing map
. 1 Path-able area (the rectangle you play on)
. 1.1 Obstacle 1
. 1.1.1 Path-able area within obstacle 1 (where you can build LLTs on the middle hills)
. 1.2 Obstacle 2
. 1.3 ...

Obstructing|Path-able is alternating in each hierarchy level of the tree structure.


--- 2. Detect areas: (simplified example)

A passage is at the shortest distance between 2 obstacles in the same tree-level.

For obstacles forming a bay, it is a bit more difficult.
Perhaps you have to check the distance of each node in the polygon to others depending on the sum of angles between these nodes.
But that is not the important part as it rarely changes enough for the performance to be a concern.


--- 3. Pathing:

Now you have areas, separated by passages, containing artificial obstacles (buildings, etc) which have small areas between them.

Units prefer passages which are 2x their size, so that they can evade another unit going the opposite direction …
… for a group of units, either take their group's radius or 2x the biggest unit's size if it is larger.

If a passage has 1/2 size, the unit may take a 10% longer way. if it has 1/3 of the groups radius, they may take 20% longer ways to avoid it if possible …
… it will not be noticed as a passage by units which too large to fit trough. Also groups which have such units and others which fit through the passage may want to avoid it for the sake of their formation.

Within these areas there are no obstacles, except units.

Units just have to register/unregister at map squares to check for collision with each nearby-map-square's units.


--- 4. The improvement:

If units don't align to a 0°, 45°, 90°, 135°, 180°, ... angles, but just move, platoons|groups moving at the same speed (slowest unit) remain their formation.

Units won't go into enemy towers anymore because they align to 45°-steps instead of following the line between origin and destination.

It's also a lot cheaper to calculate pathes:

• Possible? Only if the path-able origin and destination is the same tree-item.
• ETA? You can go from area to area to your destination and if you need to go around obstacles, you can get a list of passages they touch to speed up calculations.

I would like feedback how I can improve my post to make more peoples able to understand this post.

[PicassoCT]

How to path inside the polygons?
Especially if they are complex?
How to path around temporary obsticles (units)?

http://gamedev.stackexchange.com/questi ... games-work

I dont remember everything about springs-pathing, but QTPF (QuadTreePathFinding) was quite efficient.

You are free to build your own pathfinding branch any time.

[NeonStorm]

I know the basic A* algorithm and read a lot about node-pathing in spring forums.
I don't know if the nav-mesh is something I don'T know or just something I know under a different name.

https://en.wikipedia.org/wiki/Navigation_mesh says that it contains convex polygons only, different from my approach.
I try to make areas as large as possible and subdivide them as often as required.

You can go around polygon boundaries, you can go from passage to passage and only have to check against polygon-obstacles inside this area.

The unit position should be kept near (distance: destination - origin) * progress[0..1] |with| progress = time / (duration: start_time - end_time) |and| time = (distance: destination - origin) / speed.


@PicassoCT> How to path inside the polygons?
If they are convex and without artificial obstacles like buildings, you could go a straight line.

Artificial obstacles you encounter on a straight line have a list of nearby passages. If they don't have these, you need to go around them.

If they have passages, you need to go to a straight line to one of the passages because from there the costs between passages touching the same area is known (length, terrain type, width of the passage, perhaps a movement-heat-value for areas+passages).


Single buildings and small obstacles create a soft-obstacle (the diameter is less than the passages between it and other obstacles) and units will chose to go around it depending on their path and the buildings centre left or right of it.
Formations will split left and right of this soft obstacle if they are larger then it, negating the space in shape of a sharp ellipse in the formation-keeping code.

But a bunch of these obstacles in a row along the path, and a the pathfinder reaches a threshold after which it searches for a cheaper path around these.


@PicassoCT> Especially if they are complex?
You have to check against obstacles, but each contains information about how to go around it (left-around, right-around, skipping concave nodes).

@PicassoCT> How to path around temporary obsticles (units)?
Units should flow around each other like water around a ship.

I would calculate a binary preference (flow left-around, right-around) primarily based on weight, formation and if undecided, based on lower/higher unit ID.
Formations which go through each other, spread out their boundary polygon like if all units are in one formation. then there is enough space for going through each other.