Jump to content
  • Advertisement
  • entries
    9
  • comments
    9
  • views
    8483

Very soft pathfinding algorithm

Sign in to follow this  
RichardGe

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

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

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

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
03

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

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.
Sign in to follow this  


3 Comments


Recommended Comments

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

Share this comment


Link to comment
@ 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...

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!