Pathfinding

Overview

This page delves into the methodology behind the implementation of pathfinding for NPC entities in our game. We've adopted the A* algorithm, as detailed here, to generate the shortest path to a target. This path is subsequently managed by a ChaseTask within the PriorityTask, enabling the entity to navigate the shortest path to its target, taking into account the obstacles scattered across the map.

Implementation

Previously, ChaseTask guided the entities by sketching a vector line from the entity to the target entity, directing the entity's movement. With the new pathfinder introduction, the ChaseTask now prompts the entity to move towards a specific grid coordinate. This target grid is relayed to the PathFinder, which then yields a list of GridPoint2. The ChaseTask subsequently pinpoints the next optimal grid recommended by the pathfinder. This becomes the entity's target location. To achieve this, the ChaseTask utilizes the movementTask to transport the entity to the next optimal grid. This process persists until the entity lands on the grid occupied by the target entity.

Example:

ChaseTask(**enemy**, **target**, priority, maxdistance, mindistance)
- Starting grid for enemy: (0,0)
- Target grid for enemy: (2,2)

Pathfinder.findPath(starting_grid, target_grid)
- Returns: [(1, 1), (2, 2)]  // Pathfinder opts for the diagonal route being the shortest.

ChaseTask Operations:
- Targets grid (1, 1) 
- Shifts enemy to this grid using a new movementTask.
- Assesses if the target entity has moved:
  - If it relocates, a fresh path is identified using the pathfinder, and the procedure restarts.
  - If stationary, the pathfinder identifies the next best tile, (2, 2), and a movementTask update is initiated.

The procedure continues until the enemy occupies the same grid as the target entity.

Potential Bugs and Limitations:

1. Diagonal Grid Collision with Obstacle Hitboxes

   • Issue: Occurs when the entity is directed to a diagonal grid. If an obstacle is adjacent, the corners of the entity and the obstacle might clash due to their rectangular hitboxes, rendering the entity immobile.
   • Solutions: Direct entities to travel an additional grid away to bypass the obstacle hitbox or modify all entity hitboxes to be circular or curved to minimize corner collisions.

2. Failure to Update the Obstacle Map

   • Issue: The "RED" tiles, representing untraversable grid coordinates, remain static throughout gameplay. This restricts enemy pathfinding to the initial "RED" tiles, causing pathfinding issues when new obstacles are introduced during gameplay.
   • Solution: Introduce an update function within the pathfinder class, enabling real-time updates of the "RED" grids whenever a new obstacle is positioned on the map.

Testing

To assess the efficiency and reliability of the PathFinder class, refer to the comprehensive test plan provided here.