9
\$\begingroup\$

I'm doing my first RTS game (something like WarCraft 2) in own game engine using Monogame for graphics. I am wondering how can I implement pathfinding for a selected group of units. Movement is tile-based, I don't want to play with navmesh yet.

First of all my map is tiled (up to 256x256) For a single unit I could definitely go for something like simple shortest path algorithm (maybe Dijkstra or A*). Unfortunately, the found path can be blocked by different unit or a building. So, quick maths 256x256x4 = 262k (edges). 262k * log 262k = 5* 10^6 (no log for A*, 20 times less) That's quite a lot. If I'd want my unit to respond to possible obstacle on the path, I'd have to run the algorithm each time it moves, let's say each second. It's definitely a lot... probably too much.

But what about few units? For each of them I have to run this algorithm once again, so for 10 units the complexity would be 5 * 10^7, quite a lot for a second. And even if I somehow reduce it, the units in the selected group would detect each other, which can totally mess up the whole pathfinding.

How can I solve this problem quicker? Maybe different algorithms or... I really have no idea.

EDIT: Well, I'm not going to have different speeds on different terrain, so basically I can go with a simple BFS (still not sure if A* is better than BFS, both have worst case O(|E|), so is it worth to implement A*? BFS is much quicker to write). So right now the complexity is about 200k per second for one unit.

EDIT 2: I'd like to avoid using any pathfinding libraries. I'm doing that game only for learning purposes, so I'd love to do all the stuff by myself.

Improve this question
\$\endgroup\$
2
  • 1
    \$\begingroup\$ For a single unit there's a quick workaround - you build a path and store it, then walk it and check every next step, if it is suddenly blocked - rebuild path. For multiple units it gets much more complicated. I have an algo too, but would like to see other ideas first. \$\endgroup\$
    – Kromster
    Jul 5, 2018 at 9:22
  • \$\begingroup\$ A* is industry standard path-finding, so build an implementation you can reuse. How, and when you use the A-Star, is what makes it clever, and useful, or terrible. \$\endgroup\$
    – Ian Young
    Jul 5, 2018 at 10:53

2 Answers 2

Reset to default
7
\$\begingroup\$

With RTS pathfinding, your requirements are:

  1. You have to compute paths for all selected units fast.
  2. The pathfinding must take into account that a path may not be found (blocked)
  3. The pathfinding must take into account, units of varying size.
  4. The pathfinding must take into account that the path may become blocked by other allied units/buildings before the path has been completely walked.

So lets address each point in order, using starcraft as an example:

  1. Starcraft uses subdivision of cells to reduce top level path finding, and then performs a lower level of pathfinding to trace a path from one cell to the next. This makes it very cheap and thus, fast, to perform.
  2. A-Star (used by 90+% of games) is ideal for this, as the algorithm handles blocked paths fine.
  3. By using the aforementioned sub-division of cells, you can have units which occupy N subcells. by updating subcell maps frequently, you can allow the algorithm to path small fast units around large slow units.
  4. As with 3: You will want to periodically recompute each moving units' path, as a path that was previously open, may become blocked over time. Update the sub-cell maps and recompute, as in 1.

So, to summarise:

Use A-Star, subdivide subcells for performance and accuracy. Maintain a temporary subcell map of obstacles and units for pathing around blockages, or waiting for blocks to clear, and, as I have discovered through experience:

Do not recompute paths for every unit, every frame. Instead, do some sort of queuing system, and do a portion of it each frame, or every other frame, which leaves computational time for other game tasks.

Improve this answer
\$\endgroup\$
9
  • 1
    \$\begingroup\$ This covers well pathfinding for single units. How about "multiple-unit in a group" pathfinding? \$\endgroup\$
    – Kromster
    Jul 5, 2018 at 10:26
  • \$\begingroup\$ Starcraft (1) is infamous for how bad it handles multi-unit pathfinding. When you send a large number of units through a narrow gap, some of them will keep walking back and forth until all passed through. Well, par for the course 20 years ago, but that's not what players expect today. Or do you actually mean Starcraft 2? They improved on that aspect. \$\endgroup\$
    – Philipp
    Jul 5, 2018 at 10:27
  • 1
    \$\begingroup\$ But treating moving units like temporary static blockers is still a suboptimal solution which was "good enough" for 1998 but would not be what players expect from a game in 2018. I know that there are far better algorithms by now which allow a large number of agents to pass through a bottleneck in an orderly queue. Unfortunately that's not my area of expertise. \$\endgroup\$
    – Philipp
    Jul 5, 2018 at 10:35
  • 1
    \$\begingroup\$ OK: quick version: Your map is a grid of 256x256 (call this M)cells. Each cell is also a grid of 128x128 cells(Call this N). The general path is for M, and for inside the M cell, you compute a path for N. Think of M as a region, and N as the local area, which needs computed with greater accuracy. \$\endgroup\$
    – Ian Young
    Jul 6, 2018 at 8:50
  • 1
    \$\begingroup\$ @Executor1909 It should be fast enough, but it really depends on how responsive you want it to be (I assume you want real time responsiveness). Generally you want the entire army to have it's path calculated in under half a second, so that gives you maybe, 30 frames to divide all the work in. \$\endgroup\$
    – Ian Young
    Jul 6, 2018 at 12:33
1
\$\begingroup\$

Whole thing could be split into 3 big chunks:

  1. Pathfinding - where you build paths from point A to point B for each unit individually, or for a group together. Usually this is some modification of A* or HPA* (hierarchical variant of A*, when path gets build over large chunks of terrain)

  2. Path following - where units follow the path with some slack, walking around small static obstacles (e.g. trees) and check for larger changes in passability that they can not handle (then path gets rebuilt)

  3. Collision avoidance - where units resolve local collision problems with other walking units.

    3.1. E.g. in tile-based RTS if units path is blocked by another walking unit, it can wait some. If another unit is locked, we can sidestep around it. If unit is idle we can push it out of the way, and etc.

    3.2. Alternatively you can look into Reciprocal Velocity Obstacles (RVO) algorithms, that allow units to walk freely and resolve collisions in a more natural (and error prone) ways.

    3.3. There are also Flow-field algorithms.

Improve this answer
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .