Today let's talk about a classic in all devlogs: pathfinding! I wanted to tackle it in Wanderer quite quickly as pathfinding for a platformer was totally new for me and I didn't wanted to realize in 6 months that all my level structure would need to be redone to fit with pathfinding. It's also an important aspect of the game as one key feature is having companions following you most of the time and interacting with you and the environment, so we wanted to be sure that technically it was not a dead end.
From this point, 2 options were possible:
1) Trying to create a "smart" pathfinding system, automatically retrieving the colliders from a level and trying to navigate between them.
2) Manually help the pathfinding system by creating "by hand" a navigation graph in each level.
And without any suspense, We went for solution 2! The first one was too risky, pathfinding bugs with entities committing suicide of being stuck by a wall is a total immersion killer, we decided that having more control on where an entity can navigate was worth the work we'll need to do on each scene to create the navigation graph.
After deciding this, I made some researches and I based my work on this paper:
http://joostdevblog.blogspot.fr/2014/06/solving-path-finding-and-movement-in-2d.htmlThe main idea is to solve the pathfindind problem from 2 levels, a global and a local one.
The global solver is actually just a classic AStar, on each scene we have nodes and links, and we apply the AStar to find a path between 2 positions.
The local solver was a bit more tricky, it's used to determine how we navigate between 2 nodes, so its job is to tell me that when I want to take this link between 2 nodes, I'll need to walk for 200 pixels, then jump above a hole, then climb and finally reach my destination. Actually it's not "smart", it won't determine a path (it's the global solver job), it will just start from a position, and then try to reach another position by going in its direction, and he knows he can jump, crouch and climb, if at any point there's an intersection, he will just take the first route and maybe fail to reach it's destination, but it's not a big deal as in this case I can help him by adding new nodes and delegating work to the global solver.
Here is what a navigation graph looks like:
Orange dots are nodes, yellow lines are links, and as you can see these links are cut into multiple segments. It's the local solver job to create each segment and telling me than in this segment I'll need to jump, in this one I'll need to climb and in this one I'll just need to walk for instance.
Here is my first attempt to navigate through the graph:
And then I replaced the blue dot by an animated character following each segments and applying the correct animations:
And finally I added some tricks to be able to move from one scene to another using the same portals used by the player, and I was able to create my first companion, Rook's twin brother:
So I'm quite happy with this system, even if there are limitations, for instance it won't work when timing is involved (for instance to jump on a moving platform). But it's not a problem as actually, when we'll want to make an area with a bit more of challenging platforming, our companions won't follow us and we'll "retrieve" them at the end, but I'll let Kaiser talk about it if he wants as it's tide to the scenario and I don't want to spoil!
So now, what's the next step? Well we'll continue to refine the platforming part and then we'll enter in "production mode" to actually create the first areas of the game, and I must admit that it's quite exciting, Kaiser is doing a fantastic work on designing, storyboarding and creating assets for these areas!
Community
