Pathfinding for a tile-based game

Archived Forums Questions & Answers
1

I have defined the map for a tile based game as a 2D array in js. I would like to use this array as the main input to a pathfinding library.

I’ve looked through all of the asset store tools for pathfinding, and they all seem to work on the premise that you give them a pre-made world and they will ‘search’ for traversable spaces, and calculate paths on that. This seems to be the case even for libraries which use a grid search, in that they want to calculate their own grids based on the terrain height maps rather than simply taking an existing grid. These options will not work for me, as the contents of my map array will change continuously over the course of the game. Paths which were available when the game started may not be available after a change in the map.

I did find a raw js algorithm which seems close to what I want, API wise, here:

However I’m not really sure how to adapt that to work for Unity.

For now I have written something for this myself, but I would prefer to use something that was a bit more sturdy and optimized than my little ‘based on wikipedia’ unityscript implementation.

Can anyone give me any recommendations? They don’t have to be free, but preferably not be massive or all-encompassing AI libraries which happen to contain a bit of pathfinding.

Thanks in advance.

2 Answers

2
2

Well information about pathfinding algorithms is a lot.

For most programmers the case is that they prefer to create their own algorithm so it fits the project.

Dijkstra will give you a 100% shortest path result.

A* is considered to give very accurate and fast results.

The pseudocode here really shows how it should work.

Considering the fact you talk about a changing and thus dynamic map the D* algorithm might be useful as well.
D - Wikipedia*

So basically you have to figure out what you want to use in your program.

Then search how to program it.

3

I know this question is old but it appears to be still open and I was struggling with this myself until I found this useful tutorial:


And here’s the code ready to be imported into unity:

Hope that helps.

Thanks a lot!! that was super useful!

 –

I'm at a loss for words how useful and simple that code is;

 –