1
\$\begingroup\$

I have been tweaking my path-finding in my game for a while now, and it's mostly functional, but there are some major issues that are holding me up.

I have a flocking algorithm implemented to help enemies avoid colliding with each other so they'll form crowds, rather than stacking on top of each other, and on its own, it works perfectly.

However, ever since implementing flow field path-finding, they are mostly able to find their way to me with the exception of a couple edge cases. Basically, any time the enemies try to move towards the same grid position, the flocking algorithm prevents them from getting within range of the center of the grid space, which is what triggers their movement logic to get the next movement node, leaving them to spaz out trying to move around each other to get to the movement node. This is the biggest issue.

Right now, my method of having the enemies travel to nodes in their path is as follows:

protected void calculatePath(TMap map) {
        Player player = Player.getPlayer();
        boolean playerSighted = playerInSights(map);
        Pair<Integer> gridCoords = map.worldToGridCoords(position);

        if(playerSighted) {
            // Follow flow field.
            Pair<Integer> pPos = map.worldToGridCoords(player.getPosition());
            if(pPos != lastKnownPlayerPosition) currentNode = player.getFlowField().cheapestNeighbor(gridCoords.x, gridCoords.y);
            lastKnownPlayerPosition = pPos;
            if(currentNode == null) currentNode = player.getFlowField().cheapestNeighbor(gridCoords.x, gridCoords.y);
            if(!sawPlayerLastStep) {
                // TODO: Make zombie noises?
            }
        } else {
            if(sawPlayerLastStep) {
                // Just lost sight of player. Calculate A* path to last known player position.
                path = new Path(map, gridCoords, lastKnownPlayerPosition);
                if((path != null) && path.pathPossible()) currentNode = path.getNextNode();
            } else {
                // TODO: Wander aimlessly. Choose random neighbor and set currentNode to that neighbor.
            }
        }

        if(currentNode != null) {
            // Travel towards node.
            Pair<Float> target = new Pair<Float>((float)((currentNode.x * map.getTileWidth()) + (map.getTileWidth() / 2)), (float)((currentNode.y * map.getTileHeight()) + (map.getTileHeight() / 2)));
            int ret = Calculate.FastDistanceCompare(position, target, (bounds.getWidth() / 2));
            if(ret <= 0) {
                currentNode = player.getFlowField().cheapestNeighbor(gridCoords.x, gridCoords.y);
                if(currentNode != null) {
                    target = new Pair<Float>((float)((currentNode.x * map.getTileWidth()) + (map.getTileWidth() / 2)), (float)((currentNode.y * map.getTileHeight()) + (map.getTileHeight() / 2)));
                    theta = Calculate.Hypotenuse(position, target);
                }
            }

            if(currentNode != null) theta = Calculate.Hypotenuse(position, target);
        }

        sawPlayerLastStep = playerSighted;
}

Essentially, if they can currently see the player, they follow the flow field. If they lose sight of the player, they calculate an A* path to the player's last known position until they re-establish contact, or if they lose track of the player entirely, they just stand there.

When the enemy has a valid node to travel to, a theta value is calculated pointing them to the center of the grid position of the next node in the flow field / A* path, and then I transform their position along this theta value, adjusting via the flocking algorithm, until they reach the center of that node's grid tile.

My flocking algorithm works as follows:

protected void avoidObstacles(GameState gs, int delta) {
        EnemyController ec = EnemyController.getInstance();
        List<Enemy> allies = ec.getAliveEnemies();

        if(!allies.isEmpty()) {
            Vector2f alignment = computeAlignment(allies);
            Vector2f cohesion = computeCohesion(allies);
            Vector2f separation = computeSeparation(gs, allies);

            velocity.x += (alignment.x + cohesion.x + (separation.x * 5));
            velocity.y += (alignment.y + cohesion.y + (separation.y * 5));

            // Compute the new vector based on alignment, cohesion and separation. Then calculate new theta value.
            velocity = Vector2f.normalize(velocity, (getSpeed() * delta));
            theta = Calculate.Hypotenuse(position, new Pair<Float>((position.x + velocity.x), (position.y + velocity.y)));
        }
    }

    private Vector2f computeAlignment(List<Enemy> allies) {
        Vector2f v = new Vector2f();
        int neighbors = 0;

        for(Enemy e : allies) {
            if((e != this) && (Calculate.Distance(position, e.getPosition()) < 300)) {
                v.x += e.getVelocity().x;
                v.y += e.getVelocity().y;
                neighbors++;
            }
        }

        if(neighbors == 0) return v;

        v.x /= neighbors;
        v.y /= neighbors;
        v = Vector2f.normalize(v, 1);
        return v;
    }

    private Vector2f computeCohesion(List<Enemy> allies) {
        Vector2f v = new Vector2f();
        int neighbors = 0;

        for(Enemy e : allies) {
            if((e != this) && (Calculate.Distance(position, e.getPosition()) < getCohesionDistance())) {
                v.x += e.getPosition().x;
                v.y += e.getPosition().y;
                neighbors++;
            }
        }

        if(neighbors == 0) return v;

        v.x /= neighbors;
        v.y /= neighbors;
        v = new Vector2f((v.x - position.x), (v.y - position.y));
        v = Vector2f.normalize(v, 1);
        return v;
    }

    private Vector2f computeSeparation(GameState gs, List<Enemy> allies) {
        Vector2f v = new Vector2f();
        int neighbors = 0;

        for(Enemy e : allies) {
            if((e != this) && (Calculate.Distance(position, e.getPosition()) < getSeparationDistance())) {
                v.x += e.getPosition().x - position.x;
                v.y += e.getPosition().y - position.y;
                neighbors++;
            }
        }

        // Calculate separation from non-walkable tiles.
        TMap map = gs.getLevel().getMap();
        int mw = map.getMapWidth();
        int mh = map.getMapHeight();
        int tw = map.getTileWidth();
        int th = map.getTileHeight();
        int etx = ((int)((position.x / (mw * tw)) * mw) - 1);
        int ety = ((int)((position.y / (mh * th)) * mh) - 1);

        // Check the surrounding tiles for walkability and calculate separation. This is to avoid checking the entire map.
        for(int x = (etx - 1); x <= (etx + 1); x++) {
            for(int y = (ety - 1); y <= (ety + 1); y++) {
                // If this coordinate is within the bounds of the map.
                if((x > 0) && (x < mw) && (y > 0) && (y < mh)) {
                    // ...and if the tile is not walkable.
                    if(!map.isWalkable(x, y)) {
                        // Use the center of the tile's bounds as the separation point.
                        v.x += (((x * tw) + (tw / 2)) - position.x);
                        v.y += (((y * th) + (th / 2)) - position.y);

                        neighbors++;
                    }
                }
            }
        }

        if(neighbors == 0) return v;

        v.x /= neighbors;
        v.y /= neighbors;
        v.x *= -1;
        v.y *= -1;
        v = Vector2f.normalize(v, 1);
        return v;
    }

The avoidObstacles() method is used to transform the enemy's velocity vector to move them away from obstacles. I know that the flocking algorithm is the root cause of the above issue because when I comment out the avoidObstacles() call, their path-finding works perfectly, except that they eventually end up stacking on top of each other and will partially clip through walls / obstacles.

Can anyone recommend a way to modify my algorithm to avoid the issue I mentioned? Or do I need to re-write or trash the flocking algorithm entirely?

\$\endgroup\$
  • \$\begingroup\$ "the flocking algorithm prevents them from getting within range of the center of the grid space, which is what triggers their movement logic to get the next movement node" - sounds like you should not wait until you reach the center of the grid space to look at the next node. \$\endgroup\$ – DMGregory Dec 3 at 1:11
  • \$\begingroup\$ @DMGregory But then how should I determine that they're in a position that targeting the next node won't cause some sort of collision? I know that targeting the center is arbitrary, but I didn't know what else I should trigger it on. \$\endgroup\$ – Darin Beaudreau Dec 3 at 1:13
  • \$\begingroup\$ You can target the edge you want to exit through. Any point inside a square can be joined by a line to any edge without going outside the square. And that goes for any convex polygon if your grid is non-square. \$\endgroup\$ – DMGregory Dec 3 at 1:21
  • \$\begingroup\$ @DMGregory But I only at any one time know the next node. I don't have a list of nodes to the player because the flow field is recalculated any time the player's position in the overall grid changes. The enemies only look one node ahead at a time. I suppose I could change that, but I don't know how to target the "exit edge". \$\endgroup\$ – Darin Beaudreau Dec 3 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.