• entries
9
9
• views
8592

673 views

# 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.

• 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.

• 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.

Brilliant! Certainly sounds like a useful technique.

The algorithm is nice, but I just want to point out it looses effectiveness the more dynamic the scene is.

This algorithm assumes A & B are the only dynamic objects in the scene. If you add C, D & E which can get in the way of A & B, it gets complicated.

This is simply because, over time, C, D & E moving around can break assumption 2.
It may not just be units, but also even moving obstacles or interactive objects.

Cheers
Dark Sylinc

@ Matias Goldberg:
Absolutely, this path-finding algorithm is easy and soft but could be quickly limited. However, I think it can apply in many games... For example, it would not surprise me that World of Warcraft uses this kind of algo...

## Create an account

Register a new account