PlatformerPathfinding2D
Edit: Just a note, any transition away from the open-source state state for this asset is unlikely at best. On reflection, any further improvements to the code would need to be really good to be worth money, IMO, and if there’s enough people contributing to it, I’d just keep it open-source. Better programmers could easily make better solutions that would actually be worth money. If the change does happen, it’ll probably occur after a considerable amount of thought, feedback, and will probably just end up being a ‘pro’ version like the A* project. Again, unlikely to happen.
A currently open-sourced platformer pathfinding system using a basic A* implementation, written for my own game project (which will get its own thread eventually). May become a paid asset eventually, but its currently buggy state, it’s not nearly worth any real asking price.
Since the amount of actual platformer pathfinding solutions that are available and readily usable are nearly nearly nil (I know someone is making their own implementation for the asset store, but I don’t know when it’s gonna be published), I had decided to try and implement a solution myself, based off princples from an article from Yoann Pignole on 2D platformer pathfinding and Sebastian Lague’s wonderful A* tutorials. Pathfinding agent requires Prime31’s CharacterController2D asset to work. However, since I’m running into bugs with the implementation (so close yet so far!), I felt perhaps open-sourcing this thing would be good for myself and the community, mainly to help make this properly functional and to give the community more material on this specific type of pathfinding.
In short, I’m not so subtly looking for help on making this thing work properly and a lot better, but because I believe in giving back to the community, everyone benefits, not just myself. Platformer pathfinding is a sorely neglected, and I hope to try and help change that, despite my relatively crappy programming.
Demo Project Download (includes an editor interface and an example grid and tileset, uses Unity 5.2, press ‘P’ on the keyboard to place a path destination)
Obviously, STILL MAJOR ISSUES PRESENT. THE BASIC FUNCTIONALITY STILL NEEDS SOME FIXES. It’s not ready for general use yet.
Why?
2D platformers aren’t known for complex AI, or AI that requires proper navigation of their environment. However, there are exceptions to these, and I feel that there simply isn’t any pathfinding solutions that are remotely suited to the unique requirements of platforming games. Thus, designers have to implement their own solutions, or compromise on what their NPCs can do. For such a popular genre, the fact that AI pathfinding for platformers is so neglected by asset devs is puzzling.
Other programmers could probably implement much better implementations in their sleep, but you gotta start somewhere.
Structure and Features
The pathfinding functionality uses a ScriptableObject-based saving system (along with a large dose of serialization). This allows the pathfinding grid to not only be editable in-editor in both edit and play modes, but also re-usable across multiple scenes if required. The grid, upon generation, performs automatic assignment of nodes of different types, and the grid can automatically generate links between those nodes.
However, due to the way the grid is structured, it is heavily unsuited for dynamic generation of pathfinding nodes. This could be worked around in time, but at the moment, it’s best used for environments that are static in nature.
On the plus side, however, this allows more fine-grained control for the designer, especially assigning links that the generation scripts overlook.
The pathfinding itself is fairly basic, and doesn’t have a complex heuristic. An attempt to implement a heap went awry due to a bug in the heap that couldn’t be properly identified.
Best Practices
Currently, the recommended size of grid spaces should be about half the size of the tiles in your grid, or the average environmental object if you’re not using tilesets, but the grid is designed and tested for use with tilesets, currently. Nodes should have a radius of half the grid space. The smaller size ensures increased pathfinding accuracy for certain link types and allows slope nodes to be closer together to prevent inaccuracies during generation.
It’s best to avoid using the jump link generator, as it will take time, and will likely produce an excessive number of redundant links, currently.
Current Issues
The pathfinding often has issues with some nodes’ link lists.
The jump link generation is still somewhat inaccurate.
The AI agent has problems with jump nodes.
The AI agent has indexing problems when reaching the end node.
The To-Do List
Fix the major bugs preventing basic functionality
Improve the editor interface and functionality
Implement dynamic links (for things such as locked doors and other obstacles)
Implement wall nodes
Implement wall-scaling nodes (for wall-climbing/jumping and ledge climbing)
!