Key Events
• New pathfinding
• Added steering behaviors
• Tools to create navmesh

At the beginning of August I challenged myself to get pathfinding under control. In truth, if I couldn’t figure it out I would be forced to consider making the game turn based instead. So, I set out with a giant todo list containing many edge cases to solve. Fortunately, the main branch was merged in yesterday, so I’m in an infinitely better position than I was. It’s been an exhausting month, so I’m ready to move on. Let’s have a look at what’s been completed, and what issues still remain.

A Sampling of Pathfinding Issues

How hard can walking be, right? Well, finding the best path is only one of the many issues. But there are many more like managing state, performance and user input. Here is a list of the main issues tackled:

• Port navmesh to use iOS9’s new GKObstacleGraph
• Port code to use iOS9’s entity component system with steering agents
• Write tool to import data from PhysicsEditor
• Manage multiple GKObstacleGraphs so that wider formations take a larger turn radius
• If destination is more than 2 radians of a turn, reform squad instead of wheeling
• When Idle, check every so often to see if a unit has been bumped, and attempt to move back into position
• If destination is invalid (off of a cliff), stop as close to destination as possible
• If leader is still moving but destination is invalid, leave formation and just attempt to stay nearby other followers
• If stuck on a physics object, leave formation and use pathfinding to figure a way back to the squad.
• Multiple performance issues with units overlapping, updating their direction, etc
• Figure out a way to preview a move
• Figure out a way to allow the user to rotate a squad
• Decouple UI actions from squad commands
• Define a completed move so that sound, state and other callbacks / listeners are always accurate

The list continues on with each item getting more specific. The point is that this has been a ton of work. During the first year of game development, I learned a lot about movement so I chalk that time up to education. Now that I know what to look for, I’m still amazed at how complex everything becomes. According to RescueTime, I’ve put in 116 programming hours this month, which resulted in ~2,500 lines of code.

For those of you interested, let’s break down a few of the issues.

Stuck on an Object

This is something that should rarely happen because the navmesh should have a proper turn radius set for each unit. That said, there will be edge cases. For example, catapult knocks one unit aside but doesn’t kill it. The unit will have to figure out how to catch up to his friends. I hard coded walking into a corner, and how it would be solved. Check out the gif.

As you can see, their pathfinding eventually kicks in and they round the corner.

Invalid Positions

There are multiple types of invalid positions. First, we can have the user tapping on water or a cliff. That should be detected, and provide visual feedback. Second, we have a leader who has stopped in a valid position, but tells some of his followers that their desired position is off of a cliff. Third, we have a leader who is moving, and is temporarily telling is followers to walk off of a cliff. The gif below shows how the third case was solved.

The blue dots represent the leaders orders. Whenever the dot is in an invalid position, each follower is instructed to stay close by, but favor moving towards the dot. If the follower hits a physics edge, ignore the dot, and just try to stay close by while avoiding obstacles. That’s easy enough to type out in english, but you can imagine the math and constant checks per frame to make sure they’re doing the right thing.

Previewing and Rotating a Move

I was trying to think of an elegant way to allow previewing rotating. I didn’t want a separate button for rotate, and I still wanted moving to be easy. So, the solution is: Tap to move, hold your finger down to preview, and move your finger while holding to rotate. Surprisingly, it feels quite natural, so I’m happy with the outcome.

The code isn’t quite perfect yet as you can see. Units don’t face the proper direction at the end, for example. But the idea and code is there. Speaking of the code, this took quite a refactor. Tap and hold should only be registered  when a move command is active. So basically, each icon is now a full component that updates each frame. Each icon is responsible for registering its own events, updating UI with icons like the move marker, disabling itself, etc. This was a necessary refactor that feels good to have finished as well.

Problems with the Actual Mesh

Getting the GKObstacleGraph to work took up quite a bit of time. First, I need a tool to help make the outline of the map. Adding each coordinate by hand wouldn’t cut it. So, I wrote an importer from PhysicsEditor. That was super cool until I noticed random imperfections. To investigate, I wrote a tool that tries to move to every 20 pixels on the map, and placed a red X if it was in the buffer region and inaccessible.

As you can see, there are pockets that look like they are in a valid position but can’t be walked to. It turns out that the triangles exported by Physics Editor (remember, no concave objects allowed) are sometimes sharp angles. When you stroke the path of a sharp angle, the resulting path points out quite a bit further. So, as a temporary fix, I had to manually adjust the individual triangles to try to have 30 degrees or larger angles.

Bumped out of Position

Contact with a physics object could cause some followers of an idle squad to be bumped out of position. When that happens, they should attempt to move back into position. See the problem in the yellow squad:

There are two ways to solve this. First, on physics contact, change state to find a way back to the desired position. Second, check if you are out of position during certain intervals. The first is more accurate, but requires more CPU. The second has a noticeable delay, but works and is not intensive. Currently, I’ve implemented the second, but I do plan to experiment with quad trees at some point. If I can get the performance where it needs to be, I can switch to more accurate options.

Where Does This Leave Us?

We’re now in a cautiously optimistic spot. Most importantly, everything is flexible now. I can easily scale up and down the accuracy. What you see now is balanced for performance, so I may even do different things for different platforms. Additionally, my state machine now makes sense and does not have a ton of redundant code. So, the logic for certain conditions is clean and easy to modify. All of this is good, and it will make the next steps easier.

What are the next steps? Combat and avoidance. Building on this foundation, make combat look more natural. While the combat code is ready to go, the pathfinding for it is horrible. I need to work on charging, surrounding units, and fleeing with everything appearing believable. As for avoidance, I’m putting it on the future list for now. Ideally, units would try to avoid each other instead of walking through one another.