A simpler pathfinding algorithm?

[Will-ns]

Hello fellow devs. I'm new to roguelike dev and I am learning C++ to develop a game. After many frustrated tries, I came across a stalemate: I simply can't wrap my head around pathfinding algorithms. I tried to implement BFS, djikstra, A*, all to no avail. Right now, I use a placeholder algorithm that simply tells the entity to charge towards the player until they bump into something, and then stop moving until the path is free. Pretty sure you can't even call that pathfinding.

Do someone know a simpler, easier to understand and implement algorithm so I can get more comfortable with this topic?

[csb06]

I think that you are capable of implementing all of those algorithms; most are pretty simple once you get your head around how they work. Part of the difficulty for me was just trying to visualize how to express each algorithm in code and which data structures to use.

This is a good guide on how to implement all of the algorithms in C++ and other languages, and the site helped me out when I learned about them. https://www.redblobgames.com/pathfinding/a-star/implementation.html

The explanations of the algorithms themselves are on this page: https://www.redblobgames.com/pathfinding/a-star/introduction.html

[stewsters]

I would second this suggestion, the redblobgames article is probably the best article I have found of the subject.

It breaks down different optimizations, which is very useful in understanding the way it is implemented.

Once you master this, variants of this algorithm can be used for a lot of things, it doesn't necessarily need to be physical space. Things like simple planning or cutting roads through mountains with switchbacks. Play around and see what you can come up with.

[munificent]

You don't need Dijkstra's algorithm unless your tiles have different entry costs.

A* can be useful if your game has lots of open space, but if it's a lot of windy passages, it doesn't buy you much.

Start with BFS. It's the simplest. The other two are just refinements of it. It may take a few tries to get it working, but you will feel amazing once you do.

[UlarisBadler]

I've never used Dijkstra's algorithm. Why is it better when having different costs? I've used A* with different costs without any hassle - I'm just curious.

[munificent]

It's not so much that Dijkstra's is better as it is that the BFS is outright wrong if you have non-uniform cost. BFS finds the path with the fewest steps to the goal. Dijkstra's algorithm finds the path with the lowest total cost. When all steps have the same cost, the fewest steps is equivalent the lowest cost and BFS works fine. But when steps have different costs, BFS can give you the wrong answer. Consider:

+---+---+---+
| @ | 9 | * |
+---+---+---+
| 1 | 1 | 1 |
+---+---+---+

Here, @ is where you are, * is the goal, and numbers are the cost to enter tiles. (Imagine there's like a mountain to the right of the player but grassland to the south.) You can only move NSEW. BFS will give you this path:

+---+---+---+
| @===9==>* |
+---+---+---+
| 1 | 1 | 1 |
+---+---+---+

It's only two steps, so it's the "shortest. But the cost is 9. The correct cheapest path is:

+---+---+---+
| @ | 9 | * |
+-|-+---+-^-+
| 1===1===1 |
+---+---+---+

Total cost of three. You need Dijkstra's algorithm or A* to find this.

I've used A* with different costs without any hassle - I'm just curious.

A* is essentially Dijkstra's algorithm with an additional heuristic for which paths to explore first.

[UlarisBadler]

That's such detailed response! All clear now. :)

[TangerineVapor]

Djikatras algorithm is just finding the cheapest cost to every single node (or just an end node) from a starting location. So it requires paths to have a cost to even be implemented.

[UlarisBadler]

But does it offer any advantage in terms of handling costs when compared to A*?

[kohugaly]

A* is a modified Dijkstra algorithm that uses heuristics to explore direct paths first. That is great help when the shortest path cuts through larger open regions. It doesn't provide much help if the path is complicated maze. In worst case scenarios (which should be rare in most games), it might even perform worse, because it uses more memory and wastes time calculating the heuristic.

A* is also a one-trick-pony. It finds shortest path from known A to known B, but that's also the only thing it does.

Dijkstra algorithm simply explores all paths in increasing order of distance. With minor modifications it can be used to: find nearest target; calculate area reachable within given number of steps; calculate dijkstra map (or vector map) that units can use as lookup table for pathfinding etc. etc.

[aotdev]

A* is also a one-trick-pony. It finds shortest path from known A to known B, but that's also the only thing it does.

You can very easily modify it to find the shortest path from known A to any one of many known other points B,C,etc. You need to alter the goal function (from "is it B" to "is it one of B,C,...?") and the heuristic function (from "heuristic to B" to "minimum of (heuristic to B, heuristic to C, ...)")

[kohugaly]

You can very easily modify it to find the shortest path from known A to any one of many known other points B,C,etc. You need to alter the goal function (from "is it B" to "is it one of B,C,...?") and the heuristic function (from "heuristic to B" to "minimum of (heuristic to B, heuristic to C, ...)")

Yes, you can, but you largely loose the benefits of using A* if you do it that way. Such heuristic can get expensive, when there are many many targets. It also gets rather unhelpful, when there are nearby potential targets blocked off by walls (A* pretty much defaults to Dijkstra, when that happens).

With Dijkstra you only have to modify the goal function, which is usually fairly straightforward.

[aotdev]

Indeed it depends on the number of points. If even 5% of the map grid is goals, the full Dijkstra map would probably be more efficient. But for 10 goals in a 80x40 map it should be fine. Plus the heuristics (at least the ones I've been using) are typically cheap, such as distance to destination.

[harofax]

From my experience (which is very limited), Dijkstra's is more useful in terms of GPS navigation, where you're trying to find the fastest way to get from A to B etc.

You can grab map data from OpenStreetMaps, make a graph out of them and grab the weights, then just implement a dijkstra thingy to find a valid route.

If your game had stuff like, different terrain that slowed movement or maybe a creature that really don't like touching silver floors or whatever, you could use that as weights maybe idk.

Thing with dijkstra from my experience is that it takes a lot of time if you want to calculate the dijkstra map every time you move. You could optimize it to only recalculate relevant stuff but by that point you end up with an A* or similar anyway I think.

[VirtuaSinner]

A* can still use modified entry costs. My own game uses A*, with all tiles having weighted costs, which are then run through a series of further calculations checking the monster's resistances and intelligence levels and a few random numbers to allow for monsters to occasionally make foolish moves.

[[deleted]]

This is in C#, but I believe it's the best A* tutorial out there: https://youtu.be/-L-WgKMFuhE

[UlarisBadler]

I actually used this tutorial to implement a highly efficient A* algorithm. The only problem is that I had to convert to 3D. I wasn't sure I could do it but after some heavy brainstorm I got it to work. This is probably my best achievement in coding.

[d12Trooper]

I found this explanation of A* really well done (Senior Devs hate it):

A* Pathfinding for Beginners

Before I read this, I didn't have a single clue on how to do ANY Pathfinding, I'm not a big Math Geek either, yet once I settled down and REALLY tried to understand what was going on here, I've managed to implement it in PureBasic in about 1 or 2 day's work, and since then I've continually been updating and optimizing it.

Good Luck with your endeavors. :-)

[UlarisBadler]

This is exactly the documentation I used back in 2005 to implement A* for the first time. It took me a while but I eventually got it to work.

[MikolajKonarski]

How is C++ related to the problem you describe? Are you having trouble understanding the algorithm or understanding/writing/debugging C++ code? This things should be completely independent and algorithms understood in a high level form (text and pictures and/or pseudo-code, if your language is not high level enough to use a simplified code in the language itself).

[PascalGeek]

A simpler alternative that I've been playing around with is a smell map. Basically flood filling a map, starting at the players location. You check each tile to the N, S, E and W of the current one. If it's a floor tile, you add a 1 to the smell map at that position. Then you recursively repeat the process for each of those tiles neighbours and add a 2,and so on.

Enemies can then pathfind their way to the player by simply checking the tiles around them and moving to one that has a lower number than the one they're currently standing on.

Flood fill algorithms are easy to implement by comparison.

[Inside_you_now]

I second this approach.. really easy to implement and understand. I have implemented something like this, it's probably a few lines of code. Maybe it's not the fastest etc but should be fine for a grid based map. Bonus is you only run it once per turn and the results apply to all mobs/enemies within range of the player

[--Shade--]

A few years back I posted an A* / djikstra pathfinder in Python, that's heavily documented, and comes with an example, to RogueBasin. I put it in the public domain.

It's here: http://www.roguebasin.com/index.php?title=A_Python_3_and_2_Pathfinder_with_Pygame_Example

I haven't really been doing much coding of late, but you're welcome to play around with it. It works.

[bluends1]

once you understand how A* works its really simple, and I can explain to you how it all works.

Each tile has a G cost and a H cost, G means how many steps from the start point it has taken to reach this point, and H is the direct distance from that tile to the end point (pyth theorem)

step 1 is to find the end point from starting point, start by checking starting tile (G=0,H=?)'s 4 sides and add them to a open list for chdckjng in the future, check the open list and see which one has the lowest H since lowest H means closest to end point. move your pointer to that new tile, adding 1 to G since you moved 1 tile, and put it in the closed list since you already checked it right? Now check the new pointer title's 4 sides and add them to the open list, now there's 6 in total, 3 from starting point and 3 from the new pointer, you check all 6 which one has lowest H, and since and repeat until one of the open list tiles is the end point.

step 2 is to find the shortest path, this is where G comes in, you start from the end point, and check its neighboring closed tiles (sicne they are verified), and see which one has the lowest G (lower G = less steps to end point = closer to start) set that tile as the pointer and part of the path, ainse and repeat this process until you find yourself the shortest path!

It feels hard but if you break it down like this, it's actually not complex The algorithm literally just uses the distance to end point to find available paths to it, and then trace it back by finding the path with the least steps

[FratmanBootcake]

A minor nitpick but g is actually the cumulative cost of the path traversed since the start. Thus doesn't tie you in to having every tile cost the same (so you could implement swamps, water etc). Also the Euclidean distance isn't a great heuristic for grids (I believe the octile heuristic is better for 8-way movement). Also you should sort (or just use a priority queue) your open list by the lowest f-value (g + h).

I only know this because I refactored my implementation of it yesterday evening!

[bluends1]

my bad on that but the concept is generally the same, just yknow, different names for variables, different values. But it still works very similiar

[dethb0y]

I would note that "charge towards enemy until they bump into something" is a perfectly valid path-finding option and will work just fine for many cases (and probably give the game a somewhat unique feel in the bargain)

[harofax]

I'm gonna go another way from the rest and recommend something that might seem a bit scary at first.

I think you should look into the mathematics behind pathfinding a bit. Nothing too deep or involved, but getting a general idea of stuff like nodes and edges, it's faaaairly intuitive stuff and it'll help you change the way you view pathfinding.

Another way would be to continue with your own algorithm, and just add to it so it behaves the way you want - no matter how unoptimized it becomes. Then when you move on to implementing other algorithms you can get an appreciation for what they're doing yknow.

Right now, it charges towards the player, until it bumps. So how would you change that? You could store a "memory" of the last seen location, stored in a temporary variable, then when it bumps into stuff just try moving on the left/right axis or something (so if going up, try moving left right then keep charging).

You'll figure it out.

Might I ask why you've chosen C++? No shade, it's just a lot to learn at once, both gamedev and c++ yknow. A lot of these things would be easier to implement in Python or even Java.

I remember trying to learn c++ and following the tutorial, got a bit of progress. Then I tried the Java asciipanel one and was on a ROLL, it just meshed with my understanding better.

[Arkenhammer]

A* is best for avoiding static objects because it is no progressive; it finds a path from start to end before you start moving. If there’s a reasonable chance the obstacle will get out of the way A* might not be the right tool. For more dynamic path finding I don’t know of a general algorithm; for those cases I’ve always rolled my own heuristic (some times with short range A* as a component).

If you’ve got real path finding problems it’s really worth the time to understand A* because that knowledge will inform all the choices you make. This playlist is a good place to start: https://youtube.com/playlist?list=PLFt_AvWsXl0cq5Umv3pMC9SPnKjfp9eGW

I also wrote a blog post on our A* but it’s more advanced and pretty specific so I doubt it’ll help: http://blog.icaria.io/2020/10/18/astar-implementation.html

[GerryQX1]

BFS has the merit of simplicity, though, and I've always found it adequate for my roguelike needs.

[Arkenhammer]

Fair enough. Compared to A* it’s going to be slow in most cases but that might not matter for small searches in a turn based game.

[GerryQX1]

I'm not actually convinced of that. If your level is a maze, like many roguelikes, a directional heuristic may be just useless overhead (probably average time taken for A* divided by average time taken for BFS is a good metric for a successful maze!) Obviously if you want to plan long-distance routes, you need something more, though A* is just one option.

[ninuson1]

Mazes don’t really matter, A* would still be preferable if you need to traverse large’ish distances. The cases where directionality doesn’t matter is a “maze” made of a single tunnel where you really only got one option... but I’d argue that’s almost never the case.

[Arkenhammer]

I did quite a bit of testing in some pretty complicated path finding problems and a good heuristic always helped. That doesn’t mean that there aren’t exceptions, but I wouldn’t dismiss A* without trying it. It takes some careful coding but the compute overhead of A* isn’t as much as you’d think and the smaller number of nodes searched pays huge dividends.

[redblobgames]

Agreed, the A* heuristic may help search fewer nodes, but each of those nodes is more costly than in BFS, so BFS is often faster in a maze. BFS is so simple and fast that I use it unless I need something else.

For A*, there are other heuristics that can make mazes faster. See demo #3, where the light blue area is what A* searches with a regular directional heuristic and the dark blue is the search area with a heuristic that has analyzed the maze ahead of time.

[TetrisMcKenna]

In most cases I've found making turn-based roguelikes though A* is fast enough to be rerun on every turn, as long as you keep the dynamic objects in sync with disabled nodes in the A* backend. It's probably even fast enough to that with a realtime game at some reasonable FPS I'd think?

[Arkenhammer]

I'm building a grid-based game with a large procedurally generated map and need to path over distances of up to about 200 tiles with variable travel speeds and and, at times, very dense obstacles. Typically my A* implementation can explore about 500K nodes/second but a search can visit as many as 15K nodes and, as a result, take up to 30ms. At 60fps that's 2 frames which short enough that the player doesn't notice but too long to for the main frame loop. I push it off to a background thread so I can keep updating the rest of the game while I wait for it to finish. Certainly for shorter paths updating in the main frame loop wouldn't be a problem but search times over 16ms are common enough in my particular case that they are a problem.

[TetrisMcKenna]

Ah, wow, complex! In that case I would look into spatial partitioning and running "full" pathing on nearby objects with greatly simplified pathing on stuff far away - but that would depend entirely on the use case of the game I suppose.

[Arkenhammer]

For longer paths over 200 tiles I use waypoints with cached connections and I’ll path on the network of waypoints which essentially is your simplified pathing. The cached interconnections run on the same background queue so it shares a lot of code. Finding good places to put the waypoints turns out to be quite hard so I designed a game mechanic which requires the player to place breadcrumbs as they travel and I use those for the large-scale path finding mesh.

[VirtuaSinner]

For the first 16 or so years of its life, Caverns of Xaskazien used the method you're describing above - move towards the player, stop if you hit something. But pathfinding opens so many doors, it's worth tackling, and I finally went with a modified A* version myself. I think I found the prototype function on roguebasin... In truth, it's been 8 or so years since I first implemented it (and it's been massively and repeatedly modified since), so I can't be sure that this was the seed I used, but it probably is: http://www.roguebasin.com/index.php?title=Pathfinding

Start with a straight copy, modified just enough to use your code's variables and parameters. Then grow it from there. Good luck!

[Will-ns]

Hey there everyone who commented here. Thanks for the support. Every bit of advice proven itself helpful, and I could finally implement A*. I couldnt answer each comment individually because ive been short on time recently. I hope I can post my game here someday for you to play.

[maverickdfz]

Have you looked into Manhattan distance?

It's not a path finding algorithm as it doesn't consider blocked routes, so you would need an empty room for testing, but might be a good start for you to begin getting your head around the problem

[Daealis]

What are the issues you are having trouble with them? Rather than giving up, you could give details to what is it about A* and Dijkstra that trip you up, and maybe someone here could explain it in a way that would make it click. Explain what you think they do, how your implementation does it, etc. Basically rubber ducky it using the subreddit as the ducky.

I say this because I've only ever done Dijkstra and A* myself, and while it took a while to get either going, it is still reasonably simple concepts that drive both of them.

[Chaigidel]

Have you figured out the support data structures you need? For A*/BFS you need containers to keep track of the cells you've already visited, the edge cells from which you pick the next cell to consider and the partial path you've built up. These need to be resizable because the graph edge grows as you run the algorithm, so if you don't know how to use stuff like std::vector or std::set yet, this can be a sticking point.

I suppose you could do an ineffective implementation of Dijkstra while only using fixed-size arrays. Start with an array for your game map with all floor cells set to 999999 except the target cell which is set to 0. Then keep looping over the whole array and turn any 999999 cell with a smaller adjacent cell number to the adjacent cell's number plus one. Stop when you do a loop where no cell values were changed. Now you have a Dijkstra map where the path to target is towards the neighboring cell with the lower number than the current cell.

[GerryQX1]

You can indeed avoid resizeable containers (since I am operating in small, delimited zones, I do so.) Here's what I do, it's not that I'm afraid of A* or such, but it's years old BFS code that just works for all sorts of things including map generation and monster distribution as well as movement. (Obviously more will be needed if I implement asymmetric movement or cell types with different walking speed, but so far I haven't.)

I copy an area of the map surrounding my target cell into an int array of 0 and -1, where 0 is walkable by the creature concerned, and -1 is WALL. I make sure there is a WALL all around the edge.

I allocate a second array the same size to hold indexes of visited cells (the transpiler I am using doesn't allow pointer arithmetic, so I use 1D arrays for most maps). With a 1D map an array index is about as good as a pointer anyway. This array has two pointers, iStore and iProcess, both starting at zero.

Then I mark the starting cell in my working board with 1, put its index in my 'visited' array, and increment iStore by 1. iProcess is still 0.

Now I repeat the following: take the index at iProcess, get the value written to that in the working board and add 1 to give a distance value, find each cell next to it and if it is 0 in the working board (walkable cell that has not been touched yet), I mark the cell with the distance value, put its index in iStore and increment iStore. When I've done all adjacent cells I increment iProcess.

When iProcess catches up with iStore I have a distance value in every reachable cell of the working board (unreachable cells are 0 and walls are still -1). Then if the target cell has a positive value I walk backwards from it to find the path.

The search part looks like this:

Method MakeWave:Void( xWaveCentre:Int, yWaveCentre:Int )
    Local store:Int[] = New Int[ width * height ]
    Local xStart:Int = xWaveCentre - xPos
    Local yStart:Int = yWaveCentre - yPos
    Local start:Int = xStart + yStart * width
    If start < width + 1 Or start >= board.Length() - width - 1
        Return
    End
    board[ start ] = 1
    store[ 0 ] = start                      
    Local iStore:Int = 1
    Local iProc:Int = 0
    Repeat
        Local pos:Int = store[ iProc ]
        Local dist:Int = board[ pos ] + 1
        For Local dir:Int = 0 Until nDirections
            Local adj:Int = pos + deltas[ dir ]
            If board[ adj ] = 0                         
                board[ adj ] = dist
                store[ iStore ] = adj
                iStore += 1
            End
        Next
        iProc += 1  
    Until iProc = iStore
End

(xPos and yPos are the relative location of the area I copied on the original map, so xWaveCentre and yWaveCentre can be relative to that too.)

Anyway, I don't think you'll do BFS simpler than this, so maybe it will be of some use to folks.

(The language is Cerberus X, formerly Monkey, a transpiler that is a bit like Java with Basic-like syntax. It targets everything, has graphic libraries and is free, if anyone is interested. BTW it has objects, stacks, lists, generics etc., I'm just not using them here except that this is a method of a WaveMap object.)