Pathfinding

edited in Tutorials
As promised, an explanation of how I do path finding.

The important thing to me is not where my character is coming from, but where he wants to go. As such, I apply my path finding in reverse and then I re-use it for various things in my game. I can make my character flee to the safest possible area, I can alter his course in-flight without having to recalculate and I can use the same path finding route for each and every character on my map, so I only need to calculate it once per Update() call or if nothing has changed I don't have to update it at all. I can pre-optimize certain paths and I could also apply preferential treatment or benefits to some paths and penalise others.

For this example the basic rules for movement limit you to horizontal and vertical moves. So no diagonal moves allowed.

It is pretty simple. Imagine this game map, which has land with a few water obstacles.
image

Next add your hero (represented by a red square) and 4 NPC's trying to get to him (represented in green squares)
image

You need them to each have a unique path to reach him, right?

So I go back a step at the point, and I remove my NPC's from the equation. After all, I don't care where my NPC's are, I simply want them to be able to reach my hero. What is important to my NPC's is the terrain they have to cross, nothing more. So I go to the destination and I mark each passable tile based on it's distance to the hero.
image

Next, I go to each tile next to the marked tiles and mark them based on their distance to the hero.
image

Again. repeat the process
image

Until you have marked the entire range of tiles that are of interest to your or covers your entire map
image

Now it's easy. Wherever your NPC is, he has to move to the next tile that has a smaller distance to the tile that he is currently standing on to move closer to the hero, or he has to do the opposite to move away from the hero.

The following figure shows how each of the NPC's can derive a unique path to the hero
image

Based on this, I am able to do lots of small little 'world awareness' things in my game without actually having to do anything, it's embedded in my map. Calculating paths had just become blisteringly fast and as a result, I can now make my surroundings and tiles behave based on distance to the Hero which makes the world feel a little more alive. At least that is the possibility. I am still working on it, but hey, who knows :)

So the bottom line is, the world plays a vital part in path finding and using this kind of mechanism you can have your world give your character feedback on what to do when. Imagine him ducking instinctively when he walks by a tree with a low hanging branch for example. Or the wind howling become more evident as you approach the edge of a cliff.

I hope this wasn't a complete waste of your times, but how does this compare to what you guys use?
Thanked by 1Bensonance

Comments

  • edited
    It seems like you are just using a Manhattan distance heuristic to get the shortest path to me, which A* uses too. I can't really see how you are calculating the actual shortest path according to your heuristic so I can't really compare it to A*? My path-finding knowledge is pretty rusty so maybe someone else will be more helpful :P
  • That's a pretty straightforward implementation of Dijkstra's algorithm (http://en.wikipedia.org/wiki/Dijkstra's_algorithm) - it's great for relatively static maps with no local avoidance and a single target point. It scales very well for large amounts of agents (again providing that you don't want/need local avoidance - although there are ways).
  • I've always found it fascinating how often an independently-discovered pathfinding technique uses what I once called "the recursive grid floodfill" method (actually, I still do. "Dijkstra" is a ridiculous word!). Is this evidence that we're all secretly wired into a sinister groupthink device which pulls the strings on us behind the scenes? :)

    It's a solid approach to 2D pathfinding, I think Desktop Dungeons uses something very similar.
    Thanked by 1LazyLizzard
  • In A*, at least in the way I've used it before, you start at your source and search outward until you find your destination. That means that each character that moves performs a pretty exhaustive search, which could be optimized in various ways. In my example I have admittedly a very simple method, but I don't have to apply path scoring, I don't have to apply retrace any steps I don't need to branch my search etc etc.

    So in A* if you have 10 characters moving, that's 10 searches. I have one path and each character that wants to move can move. He hardly has to think about it...

    Not sure if that explains it a little better?
  • I've always found it fascinating how often an independently-discovered pathfinding technique uses what I once called "the recursive grid floodfill" method (actually, I still do. "Dijkstra" is a ridiculous word!). Is this evidence that we're all secretly wired into a sinister groupthink device which pulls the strings on us behind the scenes? :)

    It's a solid approach to 2D pathfinding, I think Desktop Dungeons uses something very similar.
    HAHAHA well, we're all human beings, we've all come through a similar schooling system and we're all working on strangely similar problems. The fun part for me is discovering it for yourself and having an AHA! moment I suppose :)

    For me 2D is it, I have no aspirations for 3D as it makes me motion sick (for days!). So while there might very well be fantastic techniques for 3D the chances of me actually using them are slim, I suppose, without implying that I'm limiting possibilities here. So that's a bit of a limit to my exposure there.
    That's a pretty straightforward implementation of Dijkstra's algorithm (http://en.wikipedia.org/wiki/Dijkstra's_algorithm) - it's great for relatively static maps with no local avoidance and a single target point. It scales very well for large amounts of agents (again providing that you don't want/need local avoidance - although there are ways).
    I haven't used it extensively yet, so I suppose that there are pitfalls around the corner at some point. What I like about it is that I can group things together in my mind and have some common logic for common things in Zombie Apocalypse. Like all things, I don't see it as the silver bullet, but as one of the tools that has a place for certain things at least in the way I do them currently :)

    In fact, I had to interfere a bit to make my Zombies make bad decisions as to NOT always follow you, so I don't even apply it as specified at the moment, hahahahahaha. Also, because I want my Zombies to "swarm" the Hero if they reach him, I break out of this algo and use something different altogether at very close range.
  • @Nandrew said:
    It's a solid approach to 2D pathfinding, I think Desktop Dungeons uses something very similar.
    Nah, DD's using a modified A* right now. We didn't need the entire grid to be iterated through when there was only 1 mobile actor. Plus the heuristic could be easily modified to make the movement more aware of stuff like trying not to uncover tiles at the end of a path, move through tunnels on the same grid, etc. It does end up doing something similar mathematically when it can't find an easy square that won't reveal tiles, but that's an edge-case of the heuristic's weighting and not something we had to build specially anymore :)
  • edited
    Oh cool. Thanks for the write-up. :)

    [edit] btw, I get pretty bad headaches in a lot of 3D games too. Usually the culprit for me is motion blur. I always turn that off now.
  • @LazyLizzard: How do you deal with zombies blocking each other when they want to move? Does that just not happen?
  • edited
    They use the next best path...I've not over clomplicated it because as Zombies they are fairly random moving creatures
  • I recently (last night) worked through 2 episodes of "cooking with Unity" that explained a bit of pathfinding. What was nice about it is that they actually translate wikipedia's pseudo-code of Dijkstra's alg in C# during the episode. Just putting this out there for any newbies like myself that do not have any pathfinding experience at all. Can anybody suggest any other nice tutorials on the subject. Also, what is A*?
  • edited
    @FanieG A* is essentially Dijkstra's algorithm but it takes into account a heuristic (an estimation of how good a given position is).

    This article provides a very good explanation of A* and seems to be linked in most places where I've seen people ask for A* tutorials
  • @D3zmodos - Thank you so much for the link. That will come in extremely handy over the weekend. You're a legend :)
  • A* is essentially Dijkstra's algorithm but it takes into account a heuristic (an estimation of how good a given position is).
    I'll throw in that the reason a heuristic is used is to minimise the number of nodes that need to be visited by always visiting nodes that are more likely to lead to the destination (according to some heuristic).

    These sweet gifs show the difference in node visitation:

    Dijkstra's

    image

    A*

    image
Sign In or Register to comment.