Pathfinding For Workers

Introduction

A breadth-first search algorithm was used to implement pathfinding movement for the workers. Implementing a full pathfinding algorithm like A* is a challenging undertaking since the game uses physics and is not grid-based. There is also a challenge of finding a reasonable heuristic considering there is little predictability to map generation/layout. WorkerMovementTask was updated to use a Breadth-First Search pathfinding algorithm so that workers can go to locations and avoid obstacles so that they won't get stuck. A Breadth-First Search Algorithm was used to find the optimal path for workers.

Finding all occupied positions to determine a path

The map service provides this BFS algorithm and determines the occupied positions by taking all entities with map components and calculating the GridPoint2 positions that they occupy. The logic for doing this is shown below:

	/**
	 * Retrieves all current positions occupied by an entity.
	 * 
	 * @param comp the entity
	 * @return list of occupied positions.
	 */
	private List<GridPoint2> getAllOccupiedPositions(MapComponent comp) {
		List<GridPoint2> positions = new ArrayList<>();
		Vector2 position = comp.getEntity().getPosition();
		float width = comp.getEntity().getScale().x;
		float height = comp.getEntity().getScale().y;
		for (float x = position.x; x < position.x + width; x += tileSize) {
			for (float y = position.y; y < position.y + height; y += tileSize) {
				positions.add(new GridPoint2((int) (x / tileSize), (int) (y / tileSize)));
			}
		}
		return positions;		
	}

BFS Algorithm

The algorithm for finding a path from the current position of the worker to the desired destination is shown below:

	/**
	 * Finds a path between two points using BFS search.
	 * 
	 * @param start the starting position
	 * @param goal the end position
	 * @return a list of positions indicating the shortest path
	 */
	public List<GridPoint2> getPath(GridPoint2 start, GridPoint2 goal) {
		List<Node> fringe = new ArrayList<>();
		List<Node> visited = new ArrayList<>();
		if (goal.equals(start)) {
			return new ArrayList<>();
		}
		fringe.add(new Node(start, null));
		
		int tempCounter = 0;

		while (fringe.size() > 0) {
			tempCounter++;
			Node node = fringe.get(0);
			fringe.remove(0);
			if (goal.equals(node.position)) {
				return node.backtrack();
			}
			List<Node> children = node.getChildren();
			for (Node child : children) {
				if (!visited.contains(child)) {
					if (!isOccupied(child.position)) {
						fringe.add(child);
						visited.add(child);
				}
			}
		}
		// no solution
		logger.debug("No path found after " + tempCounter + " iterations");
		return new ArrayList<>();
	}

How this is applied in the WorkerMovementTask

This will return a path of grid points on the map for the worker to traverse in order to arrive at the final destination. When a task is created for the worker to move to a location on the map in WorkerMovementTask, the agent's (worker) MapComponent is unregistered in the list of occupied positions in MapService. Not doing so will result in the Breadth First Search algorithm returning an empty path list. A path is then found using the functions above. In rare cases, they will return an empty path so alternatively, the worker will keep moving toward the final target, and if there are any obstacles in the way, knockback force will be applied to the worker so that there is a chance for the worker to move until there is free space to get unstuck. The logic for starting and completing a movement task for the worker with the pathfinding algorithm is shown below:

    @Override
    public void start() {
        super.start();
        this.movementComponent = owner.getEntity().getComponent(PhysicsMovementComponent.class);
        this.mapService = ServiceLocator.getMapService();
        this.mapService.unregister(owner.getEntity().getComponent(MapComponent.class));
        this.path = mapService.getPath(MapService.worldToTile(owner.getEntity().getCenterPosition()), MapService.worldToTile(target));
        this.finalTarget = target;
        logger.debug("Path from {} to {}: {}", MapService.worldToTile(owner.getEntity().getCenterPosition()), MapService.worldToTile(target), path);
        if (!path.isEmpty()) {
            this.setTarget(MapService.tileToWorldPosition(path.get(0)));
            path.remove(0);
            movementComponent.setMoving(true);
            logger.info("Starting movement towards {}", MapService.worldToTile(target));
            lastTimeMoved = gameTime.getTime();
            lastPos = owner.getEntity().getPosition();
            owner.getEntity().getEvents().addListener("changeWeather", this::changeSpeed);
        } else {
            this.setTarget(target);
            movementComponent.setMoving(true);
            logger.info("NO PATH FOUND USING DEFAULT MOVEMENT Starting movement towards {}", MapService.worldToTile(target));
        }    
    }

    @Override
    public void update() {
        if (isAtTarget()) {
            if (path.isEmpty()) {
                movementComponent.setMoving(false);
                status = Status.FINISHED;
                logger.info("Finished path");
            } else {
                setTarget(MapService.tileToWorldPosition(path.get(0)));
                path.remove(0);
                movementComponent.setMoving(true);
                logger.debug("Moving to the next target: {}", MapService.worldToTile(target));
                lastTimeMoved = gameTime.getTime();
                lastPos = owner.getEntity().getPosition();
            }
        } else {
            // checks if the worker is stuck and applies knockback if it is
            if (gameTime.getTime() - lastTimeMoved > 1000) {
                if (lastPos.epsilonEquals(owner.getEntity().getPosition(), 0.01f)) {
                    logger.info("Stuck, moving to final target");
                    PhysicsComponent physicsComponent = owner.getEntity().getComponent(PhysicsComponent.class);
                    if (physicsComponent != null) {
                        Body entityBody = physicsComponent.getBody();
                        Vector2 direction = owner.getEntity().getCenterPosition().sub(owner.getEntity().getCenterPosition());
                        Vector2 impulse = direction.setLength(0.2f);
                        entityBody.applyLinearImpulse(impulse, entityBody.getWorldCenter(), true);
                    }
                    setTarget(finalTarget);
                    movementComponent.setMoving(true);
                    path.clear();
                }
                lastTimeMoved = gameTime.getTime();
                lastPos = owner.getEntity().getPosition();
            }
        }
    }

    public void setTarget(Vector2 target) {
        this.target = target;
        movementComponent.setTarget(target);
    }

Creating a movement task with pathfinding

To create a task for an entity to move to a location with the search algorithm:

startPos = owner.getEntity().getPosition();
movementTask = new WorkerMovementTask(startPos);
movementTask.create(owner);
movementTask.start();