OpenRA / OpenRA/OpenRA

PathFinding, mutli BlockedByActor check aware

Open
#19,221 8 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Idea/Wishlist Performance
Dominant language
C#
Stars
17.4k
Forks
3k
Avg merge
1d 12h
Merged PRs (30d)
14

Description

More of a question then a feature request.

Reading the path finding and Move.OnFirstRun activity code it seems that path finding is executed multiple times for multiple BlockedByActor states. If no path for the first state is found, the path finding is repeated.

While BlockedByActor.All is searched first - it seems it only results in a path in 7% of cases while None results in 93% of the cases in a path with a length greater that zero.

BlockedByActor.None 29231
BlockedByActor.Immovable 144
BlockedByActor.All 2221
Total OnFirstrun 31596.

Wouldn't it be potentially be a good optimization to let the path finder be able to search all states at once. This will likely will be slower and would require a cell layer per state. But wouldn't it at least be possible for the the second path search to at least reuse all found partial paths - the cell layer - (bidirectionally both ends) and use that a a starting point?

I.e. assuming a long path from a to b is blocked in the mid by an Stationary x. The BlockedByActor.All would fail. Couldn't the 'BlockedByActor.None' reuse most found path cells?

Why is the path BlockedByActor.None still tried to be found after All? Can the actor use the blocked by None path? Wouldn't it get blocked trying to use/walk it?

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reading the path-finding code and the Move.OnFirstRun activity mentioned in the issue, then trace how BlockedByActor.All, Immovable, and None are searched and consumed. A useful outcome would establish whether the None path can be used safely, whether partial search results can be reused, and what optimization scope is appropriate.

Written by the indexing model from the issue text.

Assessment

Tech stack
csharp
Domain
game-dev, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
20/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.