[Help] Help with RTS pathfinding

[Rifleman]

Hi guys

i tried to create a small RTS Like game in unity just for learning purpose, but i cant create pathfinding just like Pathfinding in RTS games like Warcraft , Starcraft , and any other rts like them
i just wondering what Algorithm is warcraft using? its a*?
i watched lot of youtube videos about pathfinding searched a lot in google but i still cant understand how pathfinding actually works, i created a simple a* pathfinding and its working but how to make unit get block by other units like warcraft , or how to even smooth the path you get from a* there is a lot of tutorial out there teaching how to create A* pathfinding but none of them acutally tell how to create pathsmothing or make unit avoid each other

Any help?

 

[Daffa]

@Retera might have an idea.

I personally think it seems to be A*. The core idea, in my view, is to add value in tiles with units (and appropriate removal of said value when unit left), effectively rendering unit position not suitable for other units. Should also be possible by utilizing the Collision component in separation, but that might mess with pathing.

 

[Retera]

So, the extent to which I can help, is maybe best shown by watching the code I wrote related to this, in action.

The link above is a video of a game I created on LibGDX game engine. So that's similar to Unity as you mentioned, but different because I was using Java instead of C#.

At a first glance, maybe that video looks like I was playing a game of Blizzard's Warcraft III, but it is not. In particular, it is a LibGDX game written in Java and I uploaded all of the code in my project to the internet and anybody in the War3 modding community can use it (MIT License): GitHub - Retera/WarsmashModEngine: An emulation engine to improve Warcraft III modding

So, inside this code repo is included the entire path-finding system that is making units walk around other units in the video linked above. Unlike original Warcraft III it is totally open source, so we can read how it works and take its code. As you can see in the video, peons who are actively harvesting wood or gold disable collision with other peons, but other units will "bump" into each other.

Unfortunately, when I was making this game on LibGDX to simulate Warcraft 3, in general I did not record the process of how my path-finding algorithm was created. Understanding is probably more valuable than code for you in this case. For example, I lack the understanding of what Blizzard did on Warcraft 3. I did not go try to look at their code; unlike my "Warsmash" project linked above, Warcraft 3 is proprietary so we don't even have their code to look at. All I did was assume based on rumors that Warcraft 3 was written in 3 months by a bunch of smart people in a hurry, so I tried to write code in a hurry and assume that if I think smart but have fun then what I create might come out looking roughly the same.

And so, if you glance at the video that I linked above, we have sometimes one Farseer and four or five units moving as a group. But we don't have 20 or 100 units moving. It turns out, my path-finding is better when it is used just for show like this. It makes good YouTube video demos to boldly declare that I can simulate Warcraft 3 without the original and be my own boss now. But when we get to the nitty gritty, it turns out my code is quite inferior to the 2002 Reign of Chaos. I mean this in a very objective sense; the running time complexity of the code that team put together is better than what I created on my own for fun as a single guy project.

If you ever played big games of Warcraft 3 customs, you might have experienced a problem where after about 100 units you lose the ability to move your units. You can tell them to move to a location, but they stand and stare at the location or sometimes wander a little in that direction and then stop and pause for great lengths of time. The purpose for that throttle is to avoid frame-dropping with bad lag. Rather than to fix my path-finder to be as good as Warcraft 3, at some point I implemented a similar throttle into my code. And because my algorithm has a worse running time complexity, the throttle kicks in much sooner on my rewrite than on the original Blizzard game.

And I guess that's why I get recommended to help you, because I was this rebellious that I wanted to publish a simulator of Warcraft 3 that runs on open source code to kind of prove to anybody on Hive that it's probably easier to make your game externally these days than to use World Editor. But in reality, I am just some guy and my creation is inferior to the original and was created partly just to prove a point.

So, we could break down the steps how my path-finder was created into two lists: what I did back then, and what I think I should have done now when I look back in hindsight.

What I did back then:

1. Given a system of "abilities" and "orders"/"behaviors," establish a concept of frictionless movement. For example, when a unit is told to move to a location, they turn and travel to that location with no path-find and no collision. This demonstrates that your system is already configured to support a concept of "unit" where each "unit" can be performing one "behavior" at a time.
2. Create your "collision test" function for some {X,Y} that says if the location is blocked or not. Upgrade the movement system from step #1 so that units are obstructed by a failed collision test, but still do not path-find
3. Copy the A* source code from wikipedia and paste it into a file that can be called up from the "move behavior" or whatever you want to call it that defines how a unit moved. So, previously the unit would probably do somthing like this.position += this.velocity to move to target where velocity was probably the normalized vector between the unit and target scaled by a move speed, but now instead that velocity updates whenever the unit reaches the next search node returned by the A*, and points to the node after, so that the unit moves along sort of a chained path of where to go.
4. Tweak the above so that it fits visually more to your liking. One of the things that really helped me was when a Hive contributor named Ghostwolf suggested that I could change the heuristic function used by the A* to incorporate an additional travel cost for turning (changing direction). It made the results look a lot better

What I think I should have done, now when I look back in hindsight:

1. Same setup of "collision test" from steps 1 and 2 above
2. Instead of copying the A* algorithm from wikipedia like I did back then, get a better search algorithm. I spoke with someone wise that I know in real life, and their Google-kung-fu was better than mine. They suggested this article if I recall, which covers HAA/HPA and is more insightful and will run faster than anything currently in Warsmash. Similarly, @bear_369 and others brainstormed on this topic here because of how it was so evident to users that something is "wrong" about Warsmash. Based on the recommendation in that topic, I tried porting the "l1 path finder" that was included in the link from @bear_369 and I was able to get a first iteration of my Java port of that pathfinder running on a Warsmash branch, but as far as I could tell that algorithm is not optimized for unit-on-unit collision so I didn't finish that part and began to think that next time I approach the topic I should use HAA/HPA instead.

Other links:

WarsmashModEngine/core/src/com/etheller/warsmash/viewer5/handlers/w3x/simulation/pathing/CPathfindingProcessor.java at main · Retera/WarsmashModEngine

An emulation engine to improve Warcraft III modding - Retera/WarsmashModEngine

github.com

Spoiler: The Warsmash path finding at time of posting

package com.etheller.warsmash.viewer5.handlers.w3x.simulation.pathing;

import java.awt.geom.Point2D;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;

import com.badlogic.gdx.math.Rectangle;
import com.etheller.warsmash.viewer5.handlers.w3x.environment.PathingGrid;
import com.etheller.warsmash.viewer5.handlers.w3x.environment.PathingGrid.MovementType;
import com.etheller.warsmash.viewer5.handlers.w3x.simulation.CSimulation;
import com.etheller.warsmash.viewer5.handlers.w3x.simulation.CUnit;
import com.etheller.warsmash.viewer5.handlers.w3x.simulation.CWorldCollision;
import com.etheller.warsmash.viewer5.handlers.w3x.simulation.behaviors.CBehaviorMove;

public class CPathfindingProcessor {
    private static final Rectangle tempRect = new Rectangle();
    private final PathingGrid pathingGrid;
    private final CWorldCollision worldCollision;
    private final LinkedList<PathfindingJob> moveQueue = new LinkedList<>();
    // things with modified state per current job:
    private final Node[][] nodes;
    private final Node[][] cornerNodes;
    private final Node[] goalSet = new Node[4];
    private int goals = 0;
    private int pathfindJobId = 0;
    private int totalIterations = 0;
    private int totalJobLoops = 0;
    private final int pathingGridCellCount;

    public CPathfindingProcessor(final PathingGrid pathingGrid, final CWorldCollision worldCollision) {
        this.pathingGrid = pathingGrid;
        this.worldCollision = worldCollision;
        this.nodes = new Node[pathingGrid.getHeight()][pathingGrid.getWidth()];
        this.cornerNodes = new Node[pathingGrid.getHeight() + 1][pathingGrid.getWidth() + 1];
        for (int i = 0; i < this.nodes.length; i++) {
            for (int j = 0; j < this.nodes[i].length; j++) {
                this.nodes[i][j] = new Node(new Point2D.Float(pathingGrid.getWorldX(j), pathingGrid.getWorldY(i)));
            }
        }
        for (int i = 0; i < this.cornerNodes.length; i++) {
            for (int j = 0; j < this.cornerNodes[i].length; j++) {
                this.cornerNodes[i][j] = new Node(
                        new Point2D.Float(pathingGrid.getWorldXFromCorner(j), pathingGrid.getWorldYFromCorner(i)));
            }
        }
        this.pathingGridCellCount = pathingGrid.getWidth() * pathingGrid.getHeight();
    }

    /**
     * Finds the path to a point using a naive, slow, and unoptimized algorithm.
     * Does not have optimizations yet, do this for a bunch of units and it will
     * probably lag like a walrus. The implementation here was created by reading
     * the wikipedia article on A* to jog my memory from data structures class back
     * in college, and is meant only as a first draft to get things working.
     *
     * @param collisionSize
     *
     *
     * @param start
     * @param goal
     * @param playerIndex
     * @param queueItem
     * @return
     */
    public void findNaiveSlowPath(final CUnit ignoreIntersectionsWithThisUnit,
            final CUnit ignoreIntersectionsWithThisSecondUnit, final float startX, final float startY,
            final Point2D.Float goal, final PathingGrid.MovementType movementType, final float collisionSize,
            final boolean allowSmoothing, final CBehaviorMove queueItem) {
        this.moveQueue.offer(new PathfindingJob(ignoreIntersectionsWithThisUnit, ignoreIntersectionsWithThisSecondUnit,
                startX, startY, goal, movementType, collisionSize, allowSmoothing, queueItem));
    }

    public void removeFromPathfindingQueue(final CBehaviorMove behaviorMove) {
        // TODO because of silly java things, this remove is O(N) for now,
        // we could do some refactors to make it O(1) but do we care?
        final Iterator<PathfindingJob> iterator = this.moveQueue.iterator();
        while (iterator.hasNext()) {
            final PathfindingJob job = iterator.next();
            if (job.queueItem == behaviorMove) {
                iterator.remove();
            }
        }

    }

    private boolean pathableBetween(final CUnit ignoreIntersectionsWithThisUnit,
            final CUnit ignoreIntersectionsWithThisSecondUnit, final float startX, final float startY,
            final PathingGrid.MovementType movementType, final float collisionSize, final float x, final float y) {
        return this.pathingGrid.isPathable(x, y, movementType, collisionSize)
                && this.pathingGrid.isPathable(startX, y, movementType, collisionSize)
                && this.pathingGrid.isPathable(x, startY, movementType, collisionSize)
                && isPathableDynamically(x, y, ignoreIntersectionsWithThisUnit, ignoreIntersectionsWithThisSecondUnit,
                        movementType)
                && isPathableDynamically(x, startY, ignoreIntersectionsWithThisUnit,
                        ignoreIntersectionsWithThisSecondUnit, movementType)
                && isPathableDynamically(startX, y, ignoreIntersectionsWithThisUnit,
                        ignoreIntersectionsWithThisSecondUnit, movementType);
    }

    private boolean isPathableDynamically(final float x, final float y, final CUnit ignoreIntersectionsWithThisUnit,
            final CUnit ignoreIntersectionsWithThisSecondUnit, final PathingGrid.MovementType movementType) {
        return !this.worldCollision.intersectsAnythingOtherThan(tempRect.setCenter(x, y),
                ignoreIntersectionsWithThisUnit, ignoreIntersectionsWithThisSecondUnit, movementType);
    }

    public static boolean isCollisionSizeBetterSuitedForCorners(final float collisionSize) {
        return (((2 * (int) collisionSize) / 32) % 2) == 1;
    }

    public double f(final Node n) {
        return n.g + h(n);
    }

    public double g(final Node n) {
        return n.g;
    }

    private boolean isGoal(final Node n) {
        for (int i = 0; i < this.goals; i++) {
            if (n == this.goalSet[i]) {
                return true;
            }
        }
        return false;
    }

    public float h(final Node n) {
        float bestDistance = 0;
        for (int i = 0; i < this.goals; i++) {
            final float possibleDistance = (float) n.point.distance(this.goalSet[i].point);
            if (possibleDistance > bestDistance) {
                bestDistance = possibleDistance; // always overestimate
            }
        }
        return bestDistance;
    }

    public static final class Node {
        public Direction cameFromDirection;
        private final Point2D.Float point;
        private double f;
        private double g;
        private Node cameFrom;
        private int pathfindJobId;

        private Node(final Point2D.Float point) {
            this.point = point;
        }

        private void touch(final int pathfindJobId) {
            if (pathfindJobId != this.pathfindJobId) {
                this.g = Float.POSITIVE_INFINITY;
                this.f = Float.POSITIVE_INFINITY;
                this.cameFrom = null;
                this.cameFromDirection = null;
                this.pathfindJobId = pathfindJobId;
            }
        }
    }

    private static enum Direction {
        NORTH_WEST(-1, 1), NORTH(0, 1), NORTH_EAST(1, 1), EAST(1, 0), SOUTH_EAST(1, -1), SOUTH(0, -1),
        SOUTH_WEST(-1, -1), WEST(-1, 0);

        public static final Direction[] VALUES = values();

        private final int xOffset;
        private final int yOffset;
        private final double length;

        private Direction(final int xOffset, final int yOffset) {
            this.xOffset = xOffset;
            this.yOffset = yOffset;
            final double sqrt = Math.sqrt((xOffset * xOffset) + (yOffset * yOffset));
            this.length = sqrt;
        }
    }

    public static interface GridMapping {
        int getX(PathingGrid grid, float worldX);

        int getY(PathingGrid grid, float worldY);

        public static final GridMapping CELLS = new GridMapping() {
            @Override
            public int getX(final PathingGrid grid, final float worldX) {
                return grid.getCellX(worldX);
            }

            @Override
            public int getY(final PathingGrid grid, final float worldY) {
                return grid.getCellY(worldY);
            }

        };

        public static final GridMapping CORNERS = new GridMapping() {
            @Override
            public int getX(final PathingGrid grid, final float worldX) {
                return grid.getCornerX(worldX);
            }

            @Override
            public int getY(final PathingGrid grid, final float worldY) {
                return grid.getCornerY(worldY);
            }

        };
    }

    public void update(final CSimulation simulation) {
        int workIterations = 0;
        JobsLoop: while (!this.moveQueue.isEmpty()) {
            this.totalJobLoops++;
            final PathfindingJob job = this.moveQueue.peek();
            if (!job.jobStarted) {
                this.pathfindJobId++;
                this.totalIterations = 0;
                this.totalJobLoops = 0;
                job.jobStarted = true;
                System.out.println("starting job with smoothing=" + job.allowSmoothing);
                workIterations += 5; // setup of job predicted cost
                job.goalX = job.goal.x;
                job.goalY = job.goal.y;
                job.weightForHittingWalls = 1E9f;
                if (!this.pathingGrid.isPathable(job.goalX, job.goalY, job.movementType, job.collisionSize)
                        || !isPathableDynamically(job.goalX, job.goalY, job.ignoreIntersectionsWithThisUnit,
                                job.ignoreIntersectionsWithThisSecondUnit, job.movementType)) {
                    job.weightForHittingWalls = 5E2f;
                }
                System.out.println("beginning findNaiveSlowPath for  " + job.startX + "," + job.startY + "," + job.goalX
                        + "," + job.goalY);
                if ((job.startX == job.goalX) && (job.startY == job.goalY)) {
                    job.queueItem.pathFound(Collections.emptyList(), simulation);
                    this.moveQueue.poll();
                    continue JobsLoop;
                }
                tempRect.set(0, 0, job.collisionSize * 2, job.collisionSize * 2);
                if (isCollisionSizeBetterSuitedForCorners(job.collisionSize)) {
                    job.searchGraph = this.cornerNodes;
                    job.gridMapping = GridMapping.CORNERS;
                    System.out.println("using corners");
                }
                else {
                    job.searchGraph = this.nodes;
                    job.gridMapping = GridMapping.CELLS;
                    System.out.println("using cells");
                }
                final int goalCellY = job.gridMapping.getY(this.pathingGrid, job.goalY);
                final int goalCellX = job.gridMapping.getX(this.pathingGrid, job.goalX);
                final Node mostLikelyGoal = job.searchGraph[goalCellY][goalCellX];
                mostLikelyGoal.touch(this.pathfindJobId);
                final double bestGoalDistance = mostLikelyGoal.point.distance(job.goalX, job.goalY);
                Arrays.fill(this.goalSet, null);
                this.goals = 0;
                for (int i = goalCellX - 1; i <= (goalCellX + 1); i++) {
                    for (int j = goalCellY - 1; j <= (goalCellY + 1); j++) {
                        if ((j >= 0) && (j <= job.searchGraph.length)) {
                            if ((i >= 0) && (i < job.searchGraph[j].length)) {
                                final Node possibleGoal = job.searchGraph[j][i];
                                possibleGoal.touch(this.pathfindJobId);
                                if (possibleGoal.point.distance(job.goalX, job.goalY) <= bestGoalDistance) {
                                    this.goalSet[this.goals++] = possibleGoal;
                                }
                            }
                        }
                    }
                }
                final int startGridY = job.gridMapping.getY(this.pathingGrid, job.startY);
                final int startGridX = job.gridMapping.getX(this.pathingGrid, job.startX);
                job.openSet = new PriorityQueue<>(new Comparator<Node>() {
                    @Override
                    public int compare(final Node a, final Node b) {
                        return Double.compare(f(a), f(b));
                    }
                });

                job.start = job.searchGraph[startGridY][startGridX];
                job.start.touch(this.pathfindJobId);
                if (job.startX > job.start.point.x) {
                    job.startGridMinX = startGridX;
                    job.startGridMaxX = startGridX + 1;
                }
                else if (job.startX < job.start.point.x) {
                    job.startGridMinX = startGridX - 1;
                    job.startGridMaxX = startGridX;
                }
                else {
                    job.startGridMinX = startGridX;
                    job.startGridMaxX = startGridX;
                }
                if (job.startY > job.start.point.y) {
                    job.startGridMinY = startGridY;
                    job.startGridMaxY = startGridY + 1;
                }
                else if (job.startY < job.start.point.y) {
                    job.startGridMinY = startGridY - 1;
                    job.startGridMaxY = startGridY;
                }
                else {
                    job.startGridMinY = startGridY;
                    job.startGridMaxY = startGridY;
                }
                for (int cellX = job.startGridMinX; cellX <= job.startGridMaxX; cellX++) {
                    for (int cellY = job.startGridMinY; cellY <= job.startGridMaxY; cellY++) {
                        if ((cellX >= 0) && (cellX < this.pathingGrid.getWidth()) && (cellY >= 0)
                                && (cellY < this.pathingGrid.getHeight())) {
                            final Node possibleNode = job.searchGraph[cellY][cellX];
                            possibleNode.touch(this.pathfindJobId);
                            final float x = possibleNode.point.x;
                            final float y = possibleNode.point.y;
                            if (pathableBetween(job.ignoreIntersectionsWithThisUnit,
                                    job.ignoreIntersectionsWithThisSecondUnit, job.startX, job.startY, job.movementType,
                                    job.collisionSize, x, y)) {

                                final double tentativeScore = possibleNode.point.distance(job.startX, job.startY);
                                possibleNode.g = tentativeScore;
                                possibleNode.f = tentativeScore + h(possibleNode);
                                job.openSet.add(possibleNode);

                            }
                            else {
                                final double tentativeScore = job.weightForHittingWalls;
                                possibleNode.g = tentativeScore;
                                possibleNode.f = tentativeScore + h(possibleNode);
                                job.openSet.add(possibleNode);

                            }
                        }
                    }
                }
            }

            while (!job.openSet.isEmpty()) {
                Node current = job.openSet.poll();
                current.touch(this.pathfindJobId);
                if (isGoal(current)) {
                    final LinkedList<Point2D.Float> totalPath = new LinkedList<>();
                    Direction lastCameFromDirection = null;

                    if ((current.cameFrom != null)
                            && pathableBetween(job.ignoreIntersectionsWithThisUnit,
                                    job.ignoreIntersectionsWithThisSecondUnit, current.point.x, current.point.y,
                                    job.movementType, job.collisionSize, job.goalX, job.goalY)
                            && pathableBetween(job.ignoreIntersectionsWithThisUnit,
                                    job.ignoreIntersectionsWithThisSecondUnit, current.cameFrom.point.x,
                                    current.cameFrom.point.y, job.movementType, job.collisionSize, current.point.x,
                                    current.point.y)
                            && pathableBetween(job.ignoreIntersectionsWithThisUnit,
                                    job.ignoreIntersectionsWithThisSecondUnit, current.cameFrom.point.x,
                                    current.cameFrom.point.y, job.movementType, job.collisionSize, job.goalX, job.goalY)
                            && job.allowSmoothing) {
                        // do some basic smoothing to walk straight to the goal if it is not obstructed,
                        // skipping the last grid location
                        totalPath.addFirst(job.goal);
                        current = current.cameFrom;
                    }
                    else {
                        totalPath.addFirst(job.goal);
                        totalPath.addFirst(current.point);
                    }
                    lastCameFromDirection = current.cameFromDirection;
                    Node lastNode = null;
                    int stepsBackward = 0;
                    while (current.cameFrom != null) {
                        lastNode = current;
                        current = current.cameFrom;
                        if ((lastCameFromDirection == null) || (current.cameFromDirection != lastCameFromDirection)
                                || (current.cameFromDirection == null)) {
                            if ((current.cameFromDirection != null) || (lastNode == null)
                                    || !pathableBetween(job.ignoreIntersectionsWithThisUnit,
                                            job.ignoreIntersectionsWithThisSecondUnit, job.startX, job.startY,
                                            job.movementType, job.collisionSize, current.point.x, current.point.y)
                                    || !pathableBetween(job.ignoreIntersectionsWithThisUnit,
                                            job.ignoreIntersectionsWithThisSecondUnit, current.point.x, current.point.y,
                                            job.movementType, job.collisionSize, lastNode.point.x, lastNode.point.y)
                                    || !pathableBetween(job.ignoreIntersectionsWithThisUnit,
                                            job.ignoreIntersectionsWithThisSecondUnit, job.startX, job.startY,
                                            job.movementType, job.collisionSize, lastNode.point.x, lastNode.point.y)
                                    || !job.allowSmoothing) {
                                // Add the point if it's not the first one, or if we can only complete
                                // the journey by specifically walking to the first one
                                totalPath.addFirst(current.point);
                                lastCameFromDirection = current.cameFromDirection;
                            }
                        }
                        if (stepsBackward > this.pathingGridCellCount) {
                            new IllegalStateException(
                                    "PATHING SYSTEM ERROR: The path finding algorithm hit an infinite cycle at or near pt: "
                                            + current.cameFrom.point
                                            + ".\nThis means the A* search algorithm heuristic 'admissable' constraint was probably violated.\n\nUnit1:"
                                            + CUnit.maybeMeaningfulName(job.ignoreIntersectionsWithThisUnit)
                                            + "\nUnit2:"
                                            + CUnit.maybeMeaningfulName(job.ignoreIntersectionsWithThisSecondUnit))
                                    .printStackTrace();
                            totalPath.clear();
                            break;
                        }
                        stepsBackward++;
                    }
                    job.queueItem.pathFound(totalPath, simulation);
                    this.moveQueue.poll();
                    System.out.println("Task " + this.pathfindJobId + " took " + this.totalIterations
                            + " iterations and " + this.totalJobLoops + " job loops!");
                    continue JobsLoop;
                }

                for (final Direction direction : Direction.VALUES) {
                    final float x = current.point.x + (direction.xOffset * 32);
                    final float y = current.point.y + (direction.yOffset * 32);
                    if (this.pathingGrid.contains(x, y)) {
                        double turnCost;
                        if ((current.cameFromDirection != null) && (direction != current.cameFromDirection)) {
                            turnCost = 0.25;
                        }
                        else {
                            turnCost = 0;
                        }
                        double tentativeScore = current.g + ((direction.length + turnCost) * 32);
                        if (!pathableBetween(job.ignoreIntersectionsWithThisUnit,
                                job.ignoreIntersectionsWithThisSecondUnit, current.point.x, current.point.y,
                                job.movementType, job.collisionSize, x, y)) {
                            tentativeScore += (direction.length) * job.weightForHittingWalls;
                        }
                        final Node neighbor = job.searchGraph[job.gridMapping.getY(this.pathingGrid, y)][job.gridMapping
                                .getX(this.pathingGrid, x)];
                        neighbor.touch(this.pathfindJobId);
                        if (tentativeScore < neighbor.g) {
                            neighbor.cameFrom = current;
                            neighbor.cameFromDirection = direction;
                            neighbor.g = tentativeScore;
                            neighbor.f = tentativeScore + h(neighbor);
                            if (!job.openSet.contains(neighbor)) {
                                job.openSet.add(neighbor);
                            }
                        }
                    }
                }
                workIterations++;
                this.totalIterations++;
                if (this.totalIterations > 20000) {
                    break;
                }
                if (workIterations >= 1500) {
                    // breaking jobs loop will implicitly exit without calling pathFound() below
                    break JobsLoop;
                }
            }
            job.queueItem.pathFound(Collections.emptyList(), simulation);
            this.moveQueue.poll();
            System.out.println("Task " + this.pathfindJobId + " took " + this.totalIterations + " iterations and "
                    + this.totalJobLoops + " job loops!");
        }
    }

    public static final class PathfindingJob {
        private final CUnit ignoreIntersectionsWithThisUnit;
        private final CUnit ignoreIntersectionsWithThisSecondUnit;
        private final float startX;
        private final float startY;
        private final Point2D.Float goal;
        private final MovementType movementType;
        private final float collisionSize;
        private final boolean allowSmoothing;
        private final CBehaviorMove queueItem;
        private boolean jobStarted;
        public float goalY;
        public float goalX;
        public float weightForHittingWalls;
        Node[][] searchGraph;
        GridMapping gridMapping;
        PriorityQueue<Node> openSet;
        Node start;
        int startGridMinX;
        int startGridMinY;
        int startGridMaxX;
        int startGridMaxY;

        public PathfindingJob(final CUnit ignoreIntersectionsWithThisUnit,
                final CUnit ignoreIntersectionsWithThisSecondUnit, final float startX, final float startY,
                final Point2D.Float goal, final PathingGrid.MovementType movementType, final float collisionSize,
                final boolean allowSmoothing, final CBehaviorMove queueItem) {
            this.ignoreIntersectionsWithThisUnit = ignoreIntersectionsWithThisUnit;
            this.ignoreIntersectionsWithThisSecondUnit = ignoreIntersectionsWithThisSecondUnit;
            this.startX = startX;
            this.startY = startY;
            this.goal = goal;
            this.movementType = movementType;
            this.collisionSize = collisionSize;
            this.allowSmoothing = allowSmoothing;
            this.queueItem = queueItem;
            this.jobStarted = false;
        }
    }
}

 

[ThompZon]

There are many questions to consider when it comes to Path Finding but I assume you are talking about something in the following context:

• There is terrain (or similar) that is "100% static".
• There are buildings/trees/destructables that are mostly static (I.E. "there" or "not there") that isn't updated too often.
• There are (many) units that block pathing for other units and many units position can be updated every frame and they can "suddenly" be blocked by each other (other units) and maybe need to recalculate path.

If there are many units close together they all don't really need one A* run each in order to find a good path. Some other methods can be used instead, commonly a "nav-mesh" or some kind of "binary space partitioning" to let some of the "rough" pathfinding be pre-calculated (because it's static or "almost static" anyways).

Then units comes into the picture and makes it all complicated because there are many decisions to be made imo.
I'm personally working on this issue kind of "right now" but "procrastinated" by implementing other features of the game I'm making that is needed while I think about how to do it.

How many units can exist at once? How many units in "average case"?
10-100? 100-1000? 1000-10000? 10000+? "As many as possible"?
The answers to these questions will guide towards a reasonable solution (performance at the cost of precision basically).

 

[bear_369]

i watched lot of youtube videos about pathfinding searched a lot in google but i still cant understand how pathfinding actually works, i created a simple a* pathfinding and its working but how to make unit get block by other units like warcraft , or how to even smooth the path you get from a* there is a lot of tutorial out there teaching how to create A* pathfinding but none of them acutally tell how to create pathsmothing or make unit avoid each other

Any help?

Perhaps you could try to check for unit/s in the path during the pathfinding? If the current search node contains an existing unit in the way, then you could treat them as if they are a wall.

Or if the next path node they're moving to suddenly has a unit in (which could be a case in any RTS/dynamic map), tell the moving unit to stop and perform another Pathfinding algorithm, updating its previous calculation into something recent.

This method is something similar to Warcraft 3, which I found out during some pathfinding test with a unit moving from one side to another before suddenly generating wall/s which where they often move to. When the unit's next node is suddenly blocked, the engine will iterate through unit's queued pathing nodes, removing those that are no longer traversible for them until it'll find the one that is still traversible which will perform another pathfinding to that node, appending the pathfinding's new nodes to the unit's queued pathing nodes.

i tried to create a small RTS Like game in unity just for learning purpose, but i cant create pathfinding just like Pathfinding in RTS games like Warcraft , Starcraft , and any other rts like them
i just wondering what Algorithm is warcraft using? its a*?

Warcraft and other older RTS games make use hybrids of A* considering how slow the processors back then. I personally believe Warcraft 3 make use of Hierarchial Path-Finding A* (HPA) to minimize the amount of searches while maintaining the suboptimality of A*. Here's basically the jist of it:

On Initialization:

1. Group the map's whole pathing nodes into regions of pathing nodes with fixed size. (16x16, 32x32, your call)
2. Determine the connections between regions by performing an pathfinding algorithm.

On Runtime (i.e unit moving to target position)

1. Perform an pathfinding algorithm between the unit's current position and its target position to get the queued regions (not the pathing nodes)
2. Perform an A* pathfinding between its current position and the connection to the next queued region (or directly to target position if its within the next queued region) to get the queued pathing nodes.
   • Make sure that the pathfinding algorithm only searches nodes within the current and target regions.
   • If the unit moved across into its target queued region, repeat Step 2 until there are no more queued regions to check.

When the map is updated (i.e construction of buildings, destroying destructibles), you could update the affected regions' connections the same as during the initialization phase. Do note that in Warcraft 3's pathfinding search at the region level only takes in account that affected the pathing types (Terrain, Structures, Destructibles) whereas the actual check for units happens in the pathfinding search at the pathing node level.

Reference: Clearance-based Pathfinding and Hierarchical Annotated A* Search | AiGameDev.com

Although even with this method, pathfinding through units is still an issue especially for Warcraft 3 as they'll rather attempt to move through a shortest path blocked by bunch of units rather than through a long path with open space.

 

[Uncle]

There's multiple pathfinding solutions on the Unity asset store which you could use as a frame of reference. But you'll need to modify them to mimic that exact Warcraft 3 feel, which will probably take a lot of trial and error. I personally use a system called Agents Navigation, which actually has a demonstration video made in the spirit of Warcraft 3. This system takes advantage of ECS/DOTS to get high performance and showcases some impressive results. It even has a hybrid mode if you're uncomfortable with the data oriented design and want to stick with OOP (Game Objects and standard Unity API). I use the hybrid approach and have 500+ units all navigating at once while hitting 200+ fps (and my pc is pretty average). Note that this asset is still a work in progress and seems to have a very dedicated developer, but you never know what could happen. So do your own research before making any decisions.

 

[Rifleman]

There's multiple pathfinding solutions on the Unity asset store which you could use as a frame of reference. But you'll need to modify them to mimic that exact Warcraft 3 feel, which will probably take a lot of trial and error. I personally use a system called Agents Navigation, which actually has a demonstration video made in the spirit of Warcraft 3. This system takes advantage of ECS/DOTS to get high performance and showcases some impressive results. It even has a hybrid mode if you're uncomfortable with the data oriented design and want to stick with OOP (Game Objects and standard Unity API). I use the hybrid approach and have 500+ units all navigating at once while hitting 200+ fps (and my pc is pretty average). Note that this asset is still a work in progress and seems to have a very dedicated developer, but you never know what could happen. So do your own research before making any decisions.

the package is 40 dollars that seems quiet expensive

Perhaps you could try to check for unit/s in the path during the pathfinding? If the current search node contains an existing unit in the way, then you could treat them as if they are a wall.

Or if the next path node they're moving to suddenly has a unit in (which could be a case in any RTS/dynamic map), tell the moving unit to stop and perform another Pathfinding algorithm, updating its previous calculation into something recent.

This method is something similar to Warcraft 3, which I found out during some pathfinding test with a unit moving from one side to another before suddenly generating wall/s which where they often move to. When the unit's next node is suddenly blocked, the engine will iterate through unit's queued pathing nodes, removing those that are no longer traversible for them until it'll find the one that is still traversible which will perform another pathfinding to that node, appending the pathfinding's new nodes to the unit's queued pathing nodes.


Warcraft and other older RTS games make use hybrids of A* considering how slow the processors back then. I personally believe Warcraft 3 make use of Hierarchial Path-Finding A* (HPA) to minimize the amount of searches while maintaining the suboptimality of A*. Here's basically the jist of it:

On Initialization:

1. Group the map's whole pathing nodes into regions of pathing nodes with fixed size. (16x16, 32x32, your call)
2. Determine the connections between regions by performing an pathfinding algorithm.

On Runtime (i.e unit moving to target position)

1. Perform an pathfinding algorithm between the unit's current position and its target position to get the queued regions (not the pathing nodes)
2. Perform an A* pathfinding between its current position and the connection to the next queued region (or directly to target position if its within the next queued region) to get the queued pathing nodes.
   • Make sure that the pathfinding algorithm only searches nodes within the current and target regions.
   • If the unit moved across into its target queued region, repeat Step 2 until there are no more queued regions to check.

When the map is updated (i.e construction of buildings, destroying destructibles), you could update the affected regions' connections the same as during the initialization phase. Do note that in Warcraft 3's pathfinding search at the region level only takes in account that affected the pathing types (Terrain, Structures, Destructibles) whereas the actual check for units happens in the pathfinding search at the pathing node level.

Reference: Clearance-based Pathfinding and Hierarchical Annotated A* Search | AiGameDev.com

Although even with this method, pathfinding through units is still an issue especially for Warcraft 3 as they'll rather attempt to move through a shortest path blocked by bunch of units rather than through a long path with open space.

the thing that confuse me is the collision shape in warcraft is circle ( or maybe im wrong? ) but the units pathfinding find the path in the grid of squares( am i right? ) so how its works?

So, the extent to which I can help, is maybe best shown by watching the code I wrote related to this, in action.

The link above is a video of a game I created on LibGDX game engine. So that's similar to Unity as you mentioned, but different because I was using Java instead of C#.

At a first glance, maybe that video looks like I was playing a game of Blizzard's Warcraft III, but it is not. In particular, it is a LibGDX game written in Java and I uploaded all of the code in my project to the internet and anybody in the War3 modding community can use it (MIT License): GitHub - Retera/WarsmashModEngine: An emulation engine to improve Warcraft III modding

So, inside this code repo is included the entire path-finding system that is making units walk around other units in the video linked above. Unlike original Warcraft III it is totally open source, so we can read how it works and take its code. As you can see in the video, peons who are actively harvesting wood or gold disable collision with other peons, but other units will "bump" into each other.

Unfortunately, when I was making this game on LibGDX to simulate Warcraft 3, in general I did not record the process of how my path-finding algorithm was created. Understanding is probably more valuable than code for you in this case. For example, I lack the understanding of what Blizzard did on Warcraft 3. I did not go try to look at their code; unlike my "Warsmash" project linked above, Warcraft 3 is proprietary so we don't even have their code to look at. All I did was assume based on rumors that Warcraft 3 was written in 3 months by a bunch of smart people in a hurry, so I tried to write code in a hurry and assume that if I think smart but have fun then what I create might come out looking roughly the same.

And so, if you glance at the video that I linked above, we have sometimes one Farseer and four or five units moving as a group. But we don't have 20 or 100 units moving. It turns out, my path-finding is better when it is used just for show like this. It makes good YouTube video demos to boldly declare that I can simulate Warcraft 3 without the original and be my own boss now. But when we get to the nitty gritty, it turns out my code is quite inferior to the 2002 Reign of Chaos. I mean this in a very objective sense; the running time complexity of the code that team put together is better than what I created on my own for fun as a single guy project.

If you ever played big games of Warcraft 3 customs, you might have experienced a problem where after about 100 units you lose the ability to move your units. You can tell them to move to a location, but they stand and stare at the location or sometimes wander a little in that direction and then stop and pause for great lengths of time. The purpose for that throttle is to avoid frame-dropping with bad lag. Rather than to fix my path-finder to be as good as Warcraft 3, at some point I implemented a similar throttle into my code. And because my algorithm has a worse running time complexity, the throttle kicks in much sooner on my rewrite than on the original Blizzard game.

And I guess that's why I get recommended to help you, because I was this rebellious that I wanted to publish a simulator of Warcraft 3 that runs on open source code to kind of prove to anybody on Hive that it's probably easier to make your game externally these days than to use World Editor. But in reality, I am just some guy and my creation is inferior to the original and was created partly just to prove a point.

So, we could break down the steps how my path-finder was created into two lists: what I did back then, and what I think I should have done now when I look back in hindsight.

What I did back then:

1. Given a system of "abilities" and "orders"/"behaviors," establish a concept of frictionless movement. For example, when a unit is told to move to a location, they turn and travel to that location with no path-find and no collision. This demonstrates that your system is already configured to support a concept of "unit" where each "unit" can be performing one "behavior" at a time.
2. Create your "collision test" function for some {X,Y} that says if the location is blocked or not. Upgrade the movement system from step #1 so that units are obstructed by a failed collision test, but still do not path-find
3. Copy the A* source code from wikipedia and paste it into a file that can be called up from the "move behavior" or whatever you want to call it that defines how a unit moved. So, previously the unit would probably do somthing like this.position += this.velocity to move to target where velocity was probably the normalized vector between the unit and target scaled by a move speed, but now instead that velocity updates whenever the unit reaches the next search node returned by the A*, and points to the node after, so that the unit moves along sort of a chained path of where to go.
4. Tweak the above so that it fits visually more to your liking. One of the things that really helped me was when a Hive contributor named Ghostwolf suggested that I could change the heuristic function used by the A* to incorporate an additional travel cost for turning (changing direction). It made the results look a lot better

What I think I should have done, now when I look back in hindsight:

1. Same setup of "collision test" from steps 1 and 2 above
2. Instead of copying the A* algorithm from wikipedia like I did back then, get a better search algorithm. I spoke with someone wise that I know in real life, and their Google-kung-fu was better than mine. They suggested this article if I recall, which covers HAA/HPA and is more insightful and will run faster than anything currently in Warsmash. Similarly, @bear_369 and others brainstormed on this topic here because of how it was so evident to users that something is "wrong" about Warsmash. Based on the recommendation in that topic, I tried porting the "l1 path finder" that was included in the link from @bear_369 and I was able to get a first iteration of my Java port of that pathfinder running on a Warsmash branch, but as far as I could tell that algorithm is not optimized for unit-on-unit collision so I didn't finish that part and began to think that next time I approach the topic I should use HAA/HPA instead.

Cool i will start researching the code now !

 

[Uncle]

the package is 40 dollars that seems quiet expensive

the thing that confuse me is the collision shape in warcraft is circle ( or maybe im wrong? ) but the units pathfinding find the path in the grid of squares( am i right? ) so how its works?

Cool i will start researching the code now !

It's pretty inexpensive for what it offers, but there are other free pathfinding assets on there (just sort by free). Also, you can try to catch it on sale, I got it for $12 during a Flash Deal. You also get a 30% discount if you're a new customer I believe.

 

[bear_369]

the thing that confuse me is the collision shape in warcraft is circle ( or maybe im wrong? ) but the units pathfinding find the path in the grid of squares( am i right? ) so how its works?

During the pathfinding, when there's are nearby units, the pathfinding will perform a basic circle detection between the moving unit and the nearby unit to check whether the current search node is open for the moving unit to traverse through.

bool isOccupied = <Distance between the current search node and Nearby Unit> <= (Moving Unit's collision size + Nearby Unit's collision size)

Structures will not treated the same though, as they directly affected the pathing map.

I'm not sure how Warcraft 3 limits the amount of unit checking for their pathfinding. If I have to guess, it's either Spatial Hashing or Quadtrees.

Additionally, the unit's collision size (circle thing) are used as a clearance value for the pathfinding I believe; so I recommend reading the reference above.

 

[Dr Super Good]

You can check out the open source 0 A.D. RTS game to see how they implemented their path finder. It had issues when I tried it all those years ago, but it worked and hopefully has been improved since then.

More modern RTS games like StarCraft II ("modern") use a mesh based path finder. As the nodes can cover large areas where pathing is simple this can provide significant performance improvements over a tile based approach such as used by Warcraft III.

Games like factorio use a tiered path finder system. Over long distances navigation is done using 32x32 tile chunks. Individual tiles and even collideable objects are only considered when obstructions are encountered or the unit is trying to attack a target.

Unit on unit collisions are difficult and it is my understanding that the path finder usually does not handle them directly. For example in Warcraft III, if one occurs the engine simply makes both units stop and wait for a pathing update. The pathing updates then make the units move in a direction to try and avoid colliding with each other. StarCraft II on the other hand applies some sort of particle physics to the collision, trying to push/slide the units past each other while keeping moving in the direction the path finder told them to.

 

[maddeem]

This definitely is not a solved problem and it's one that I've spent years exploring. I think you should start by learning exactly how astar works. Then from there you should learn about spatial hashing. You can combine these two in multiple ways. One way is implementing soft body collisions so that units can push past each other, or block each other when they are enemies. If you spend time learning these fundamentals you can use them later for other parts of your project.

You would be surprised how much use you can get out of just these two algorithms... Then you can tweak them to your specific needs. Just take your time learning and enjoy the process. Make tons of small prototype projects before tackling the big rts project... They are hands down the hardest game to make

 

[ThompZon]

So: I've "finally" designed my pathfinding for a Tower Defence with masses of enemies. Basically I make a vector field pointing towards the goal that is re-run when building or selling. Each unit just indexes where the unit is in this vector field and goes in that direction.

I can add some local avoidance or other tweaks later to make them spread out slightly more, but this should work for my tower defence for now (I have some enemy spawning issues right now, so have not been able to test it at all yet).

While doing this, I saw that Supreme Commander 2 does something along those lines to handle masses of units moving together (with some local avoidance).