Pathfinding Update Imminent

Movement heuristic and weight formular has been updated to (hopefully) better handling towers cluster. Moreover, additional pathfinding calculation layer will be performed to ensure the best route would be the most likely one that would be used (rather than having it going back and forth because of silly things, like number of units at the junction cell keep changing):-

  1. Calculate path from spawn point toward HQ, for each unit type, and without CrowdWeight.
  2. This path is re-calculated only when the buildings are changed (ie; tower built or moved) and is shared among all units of the same type. (Use separate weight field for each unit type?)
  3. Cells along this part have ZERO(?) movement weight
  4. A* calculation performs on units as usual with both normal danger and crowd weights, but use movement weight from (3).

Additional idea:

  • Crowd weight to be calculated by distance from the origin? With its effect reduced the further the cells are from the origin point, and may double or quadrople when right in the next cell?

Hexagrid Ai Personalities

  • Added weight to the danger posed by the tower in a radius.
  • Added support for multi-channels pathfinding where calculated path of one unit type may not be the same as another’s; Big unit won’t be able to go through partially blocked cells, and slow units will be much more likely to avoid going through a tower’s attack radius than fast units (4 times more likely, in fact).

Hex Grid

Once the grid coordinate converter and data structures are in place, with just a small bit of code modification, the game is back running again. We lose the ability to automatically measure the coverage of multiple-cells obstacles due to the shape of the grid, but the new level design does not seem to need them anymore as most obstacles would likely be in form of the gap in the floor, which would be filled up by the Hex Grid tool.

Hex Grid Generator

Hex Grid

Collision Updates


The collision now process momentums more appropriately; Velocity after collision is now determined by both weight of the unit, direction of movement, as well as the speed the other unit hit it at. Impatient unit also keep trying to obtain new navigation path to get itself out of the situation.

There seem to be a bug involved division by zero when there are too many units colliding with each other. Have to chase that out later.

Should I try going for Hexgrid implementation, or other AI things first?

Getting impatient?


(A) Introduce patient and intimidation parameters; Units could now get ‘impatient’ by getting stuck in a single cell for longer than the specified period. An ‘impatient’ unit get its repulsion value multiplied by its intimidation parameter as well as reduction to other unit’s pushes, allowing it a greater chance of breaking through a blockade.

(B) Implement collisions list to keep track of which unit is colliding and with who, ensuring the Collision Breaker won’t be executed more than intended.

(C) Take into account the size of the unit when calculating obstacle repulsion force.

PS: Video to be shown in next post.

Critical Radius, Emergency Breaks and the Merging of Forces

(A) Implemented unit collision and break algorithm using critical distance calculation; If two unit’s critical radius collide with each other, the emergency velocity diversion function is performed. The function will remove all velocity from direct collision course between the two units. It does this by projects each unit’s velocity onto a vector drawn between the two units. This projected collision velocity will then be removed from the unit’s velocity itself. Which force the unit to either divert away (if original velocity is not in direct collision) or stop moving entirely.

(B) Refactoring forces result from the difference functions to work better together, by treating the force as the targeting velocity itself rather than just velocity’s direction. Obstacle repulsion and target attraction are now both clamped to the same size, so that the only way for there to be a “sinkhole” would be if there is an obstacle directly between the target and the unit. After which, the unit’s attraction and repulsion is layered on top of the balanced equation, ensuring the push from movable units take priority.

This equation however seem to result in another “sinkhole” at the entrance of a balanced “tunnel” with obstacles on both side. Perhaps the targeting force should get a booster to always be higher than obstacle avoidance?

(C) Obstacle repulsion calculation is now performed as part of the background loop function in GameNavigator rather than calculated individually every frame by all units. As obstacles are near constants, delay of a fraction of a second should have little to no impact.

Unit formation with Potential Function

Added cross-unit forces calculation loop to the Potential Function algorithm. There are still two serious bug that I know of, one of which result in infinite loop that froze the game.

Much like how I did with A* algorithm, the inter-unit force calculations are now performed in the background by GameNavigator class, which constantly looping through the entire grid and perform calculation for a specific number of cells per frame, every frame, ensuring that these calculations will not be hogging the resources by trying to do everything in a single frame. In addition, by using a single function running in the background rather than separately in each unit, the code could be optimized to reduce the number of calculations while requiring only a single temporary variable per unit to keep track what has been calculated.

Writing this at midnight, so the text could be confusing…

Potential Obstacles Avoidance

2nd attempt in Potential function implementation. I had to spent hours tweaking all the numbers to get this result, which still is not perfect, as evident from the video where in certain spots, the units would totally froze up. I still need to find a way to ensure Target Attraction will not lock up or overwhelming where it should not.

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.

Lenard-Jones Potential Functions

Lenard-Jones potential function is actually a formular used to calculate molecule’s attraction and repulsion forces, which are varied by distance between two objects. However, it could also be adepted to use as a calculation in many AI behaviors, namely; chasing, intercepting, obstacle avoidances, as well as swarming. Changing the 4 parameters of the function could also drastically change the behavior of the AI itself without having to change any other code.

The formular for Lenard-Jones Potential Function is;

F = -( Attraction / r^n ) + ( Repulsion / r^m )

Where r is distance and F is the force between two objects.

By applying Attraction, Repulsion, n and m depends on the each obstacle and calculate force F between the current unit and all other objects in the scene, a complex behavior pattern could be created.

For example, by leaving out Attraction factor, the function becomes an obstrucle avoidance which push the unit away from the object. While a higher Attraction and low Repulsion could draw the unit to the object but retain a minimum distance. This function, when apply to a lots of units, could imitate angry bees swarm behavior where all units attempt to remain close to the group, while remain in constant motions, as oppose to Flocking algorithm which result in a neat movement formation.

For Reference:
Bourg, D. and Seemann, G. (2004) AI for Game Developers, Sebastopol: O’Reilly Media.

[ Placeholder for Scanned Images ]