Very soft pathfinding algorithm

by Richard Geslot, algorithm used in Theolith

Introduction

When we hear "pathfinding", we often directly think "expensive algorithm". My aim is to present you a very soft pathfinding algorithm.

• The algorithm must start with these hypotheses:
  
  
  
  • Point B wants to go to Point A (1)
    
  • Between A and B, there is no obstacle (2)
    
  
  
• After the start of the algorithm, just (1) is needed.
  

The hypothesis (2) may seem restrictive. But imagine any RPG: You are the hero (Point A) and there is an enemy NPC (Point B). B is aggressive: when he knows that you are here, he goes to you.
But to know that you are here, (2) must be true. Why? Because to know that you are here, it's because he saw you, so there is no wall between you and your target, so (2) is check. Another case is that you cast it a spell, but if (2) isn't true, you can't cast your spell because there is a wall between you and your target.
To conclude, if in your game, a fight can only begin if (2) is true: Don't use expensive A*, look at this algorithm, it's certainly sufficient for your game.

The algorithm

I called it "little thumb" because it's exactly the same idea. When it is at x meters of the old "stone", Point A drops a new "stone". All stone's positions are in an array.
Let's see the algorithm with images:

1)At the beginning, B doesn't know that A is here. A approaches B. B knows that A is here because he saw him or because A casts a spell on B. (1) and (2) are check, the algorithm start.


2)Is the segment [AB] free (no collision)? Yes. B follows the BA vector


3)A is very fast and B very slow. While B was walking along BA vector, A moves behind the wall and stops. So the segment [AB] is not free


4)The segment [AB] isn't free, so B needs a new vector to follow. No problem, B tests [B,Stone1]: no there is obstacle, the same with Stone2... Until Stone6. [B,Stone6] is free so B,Stone6 is the new vector followed by B. When B is on Stone6, B try again [BA], [B,Stone1]... It's ok with Stone2. And when B is on Stone2, it's now ok to go directly to A.

Discussion about the algorithm

• The "little thumb" drops "stone" at each X meters. The more X is small, the more the array that contains stone's positions is large. About this Array, it's certain that it will not save all stones since the beginning of the game. Make sure that it saves the last Y. If B has traversed the entire stone's array without finding any stone that can be reached without hindrance: there is no possible way to reach A. But you could considerer that as an error, because as we seen upper, (2) must always be check at the start, to use this algorithm.
  
• Be careful, in this example, when A is behind the wall, A stops. If A continues to walk, the StoneX become the Stone(X+1).
  
• It's not obliged that B reaches a stone to re-compute its following vector. We could compute at each update of B.
  
• The difficulty is to know if a segment has a collision or not. Anyway, if you use this algorithm you should have implement that before, because you needed to know if the enemy "sees" (there is no wall between them) the target. Or because you needed to know if the character can cast his spell to his target (again, that means that there is nothing between them). The collision between a shape and a segment isn't the subject of this article. Briefly, about me, I wrap my shapes in simple cubes composed of 12 triangles (in 3 dimensions) and I use the D3DXIntersectTri function with DirectX.