How does pathfinding work when there's several units involved? Do you check for each entity in sequence...

How does pathfinding work when there's several units involved? Do you check for each entity in sequence, do you have update/refresh cycles, or what's the deal with that?

Serious question

Attached: Screenshot-4 (1).png (640x480, 55K)

Other urls found in this thread:

openra.net/
youtube.com/watch?v=WGH891NRW1o
twitter.com/AnonBabble

Depends on the game, it's easy to tell depending on how several units split up.

That is obviously implementation defined. The simple thing to do would be to do it for each unit and then re-calculcate upon unexpected collission.
A more interesting question is how pathfinding is done when you have a game with fog of war.

That's easy, just treat fog as wall. Done

There may be no explored path to the destination. In that case treating fog as a wall would just lead to a halt.

Every frame:
>sort units based on proximity to destination
>move closest units first

If you do it the other way around you can create blockages.

What about unit to unit collision? I don't get it because the first unit sees the path, but the second unit needs to route around that path, and then the third unit routs around all of those paths, but by the time they get there it's already clear since the first unit moved forward. So wouldn't all units beyond the first move in circles?

>the second unit needs to route around that path
I meant a route around that unit*

A - You treat the several units as a horde, you calculate exactly one path for it, then you try to move everybody without making overlap with each other, this is the fastest solutions.
B - You generate a vector map, then you just make units move based on the vector of the cell they're currently in, this generally avoid collision between units in open maps, they can collide in choke points, but it isn't anything special about it, this is somewhat slow.
C - A mix between A and B, instead of generating a vector map for the whole map, you only do so for a certain path, it'll be a partial vector map, or a flow field map, this is the most optimal option for when you have two friendly armies clashing with each other and you try to achieve collision avoidance between units, you update the flow field map to go around opposing units.
D - The laziest solution, A without caring about units collision, units in the same group will just phase through each other until they reach the target, then they fix their formation.

>Take the shortest path regardless of wether there's another unit in the way.
>Check for collision each frame.
Upon collision:
>if both units are moving make the slowest one wait.
>If only one is moving, recalc its path around the stationary one OR make the stationary one move out of the way (move it to closest the space not in the path of the moving one).

>treat several units as a horde
Impossible when you have a situation like this. If you select the green circled units, you have to treat each as a separate unit

Attached: 4258921_orig.png (640x400, 285K)

>>Check for collision each frame.
Wouldn't it be better to set paths every few frames? I imagine this gets really slow the more units you add. Plus wouldn't the result be the same anyway? If a unit takes for example 40 frames to get from square to square, then why not check every 20 or 40 frames, etc? Saves a lot of computation.

The other stuff makes sense though

I remember units in wc3 stand idle if there are many of them, try placing 1000+ of them in a custom map in the editor. Perhaps they say there is a max time per frame spent calculating pathfinding and use that in a round robin fashion.

>I imagine this gets really slow the more units you add.
If you use a space partitioning algorithm (as you should when doing collision detection) it's not too bad.

>If a unit takes for example 40 frames to get from square to square, then why not check every 20 or 40 frames, etc?
Well yeah if units are very slow then obviously you can afford to do work less often.

You just add a step of pathfinding towards the most relevant point of the horde (either the center or the closest unit to the target), you can collapse single units to mini hordes, and mini hordes to bigger hordes, level of detail method is really useful for pathfinding and horde behavior.
It really depends on the type of the map, what works for open maps will obviously lead to problems in maze like maps, sometimes you have to mix multiple approaches.
Since you have a fixed game in mind, there's nothing better than checking the open source version of it
>openra.net/

>How does pathfinding work
in warcraft ? like shit

check zero-k it has path finding and is open source and far more advanced than most rts made. spring engine.

Fair enough, thanks!

Well in general but Warcraft can be a starting point. I think C&C behaved better in general though

also age of empires is shit on this matter
stopped playing cause of that

just use machine learning

Well, obviously, the map is generated and loaded into ram before hand, then the fog is rendered on top of it. You seriously don't think that the map is generated when you clear fog of war, right?

Lead unit with pathfinding and the rest follow using particle swarm optimization

What are optimal ways to determine if fog of war have been cleared? Do i need to check every tile at every frame?

In decent games the pathfinding algorithm only takes into consideration what is revealed. So if theres an unpassable mountain under the fog, the unit will not go around it before discovering it is there.

Apparently this is how C&C does it

youtube.com/watch?v=WGH891NRW1o

that's pretty ghetto, is this pre-Dijkstra or what?

>Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later
Doubtful