A* Algorithm => path finding

[a_bertrand]

My previous post was about generating a maze, now we should be able to automatically solve it. There is many ways to solve a maze or generally to go from a start point to a reach point, however the most versatile and usually the best solution is given by the so called A* (a star) algorithm. We should then dig into it. Let's start with a simple maze (I generated via my previous code) and a small code to render the maze, the start point and end point:

https://jsfiddle.net/L4xd1xct

This is basically nothing else than a static maze, and a "render" function which will show the result.

To solve this kind of issue, we use something which:
Store the start point in a "todo" list
Store the same point in the "visited" list
Pick a point in the todo
If this point is at a distance of 0 of the goal we reached the goal and we return the solution
Check all the 4 cells around this point and add all the empty cell, which we didn't visited yet
Add those in the todo / visited lists
Repeat going back to number 3 as long as there is something to do
The code could be:

https://jsfiddle.net/9udp2rpj

To see how this works and try different optimizations / algorithms you can use that:
https://qiao.github.io/PathFinding.js/visual/

Even if A* could scare you at first, it's actually is a pretty stupid code, it just tries all what's possible and pick the best solution (the one which has less steps). Actually it doesn't try ALL, it stops when it finds a solution and due to the fact we sort all the time the things to do based on the number of step we did, it should find the shorted possible way to go.

What is interesting is that by changing the sorting code with something a bit more complex you could actually change the behavior of the code. Think for example that some steps are slower (by walking in a swap for example) then you could have a "cost" for this step, and then by sorting by smaller cost you will find faster roads even if it requires more steps.

As always I'm here if you need more information

[Jackolantern]

I have played around with pathfinding a bit with A*. I did try both pathfinding.js and EasyStar and did tend to like the latter a bit better, at least for my uses.

One thing I have wondered, is that most A* libraries tend to rely on some kind of a tilemap/collision map with a set size of tile. But many games don't have perfect tile movements. For example, a game that will move the character to any exact point they click with a mouse. How would you make A* work in that case? Of course you can keep increasing the resolution of the "tilemap" that the player moves around on until you are virtually moving on a per-pixel basis or close enough. But of course this seems horribly wasteful and is likely not an optimal solution.

Would the best solution just be to get the character into the area using a standard tile-like approach and then figure the final move to the pixel-perfect destination using another method once the character moves into that final "tile"?

[a_bertrand]

Fun that you ask Jackolantern as I have exactly this issue with my current engine. While the map in my case is certainly based on a tilemap, objects and characters can freely move around. My solution is that I have a start offset and an end offset, move then using a pure tile, and finish with the offset. Not a perfect solution but it somewhat work.

A* is not based by itself on a grid movement but on "possible moves". So if you want to have a pixel perfect movement you should go down to the pixel but it will be way too much and cost too much. Depending on your goal there is other techniques which could do the trick.

[Jackolantern]

That is what I was thinking to do. I could definitely imagine if each move was a pixel that this would likely be horribly inefficient (you could probably get into thousands or tens of thousands of possible paths in even a moderately-sized area) and imagined that moving them according to tiles and then doing something for that final "nudge" to the correct pixel would work best.

Have you ever done any pathfinding in a 3D game? I have pretty much sworn off 3D game development, at least for a good while, but have wondered if it was any different or if you just run A* on the ground. It seems like it would work provided you calculated obstacles in the Y direction to be impassable on the ground matrix (such as a low-hanging pipe that the player cannot get by).

[a_bertrand]

I used A* in Cubicverse which is actually a 3D world, and it works without problems.

[Jackolantern]

Do you just flatten the ground mesh into a "grid" to run it into the A* algorithm?

[a_bertrand]

No, you can easily make it work on the 3D grid (it was a 3D grid anyhow )
Think that A* would work perfectly in a node graph it doesn't matter if the nodes are on the same level or not, it matter if you can reach one node from another or not.

[Jackolantern]

Ahhh, okay I gotcha. That makes sense, thanks!