Proposed Final Pathfinding Algorithm

Proposed final pathfinding algorithm which I am to implement; The algorithm will be a a combination of A* Pathfinding, Bezier curve function, Lenard-Jones Potential functions, Flocking algorithm. While Follow-the-Leader algorithm will be used to determine which unit is the leader of the current units group, which would potentially be used for optimization and movement cohesion. The result of each algorithm will be combined as force vector (F) and then used to apply actual movement (flowchart below).

Steering option may be added to help imitate units such as tanks, which could only move forward and backward.

Function of each algorithm is as such:

  • Follow-the-Leader function is used to determine which algorithm need to be used; A Follower unit may not need A* or Target Attraction for example, while the leader may not need Flocking.
  • A* Pathfinding search for the optimal path toward target waypoint on a grid-level, ensuring the unit will have mostly clear path to follow.
  • Target Attraction(Potential Function) ensures a constant force which drag object toward current target provided by Bezier curve.
  • Obstacle Repulsion (Potential Function) applys to all grid-level obstacle to force the unit away from its range.
  • Neighbour Attraction/Repulsion (Potential Function) keep the units in a minimum distance away from each other and, depends on the unit type, attract to each other in a swarming pattern.
  • Cohesive and Alignment (Flocking), when activated, keep the unit in a formation marching toward the target.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s