It has been a long time since I posted anything or really worked on this project.  I finally got some motivation and decided to tackle a couple of the hard issues that I was facing and wasn’t sure the best way how to handle.

First up, clicking outside of walk boxes.  What should happen? Where should the player move? I went through lots of experimentation to find the best results.  Finally I made an algorithm to expand a + out from the click point to see if it hit any walk boxes.  If it does, then that is the spot the player walks to.  If not, then it means it is in a diagonal and I need to find the closest walk box vertices to the click point, and have the player walk to that position.

That was difficult but I was able to handle it with relative ease.  The second issue was that I had the player walking the path to a click point, but he would move to the center point of each walk box as he walked through them. This lead to a very unnatural look.

When I originally made the code for walk box path finding, I remembered that Julian Ceipek wrote about something called the Simple Stupid Funnel Algorithm. http://jceipek.com/Olin-Coding-Tutorials/pathing.html#funnel-algorithm This algorithm finds a more direct route for the player to walk, and it looks a lot better.  I followed this article that he linked to by Digesting Duck which gives a very excellent explanation of how it works. http://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html

However, much of his code was hard to follow and in psuedo code.  Luckily in the comments I found someone used his code in a javascript example and posted it on pastebin.  http://pastebin.com/7jwrmw1i

It actually probably only took me a couple hours to port the code to c++.  The hard part was to figure out all the “portal points” along the walking path.  This means basically finding all the vertices of the edges the player walks through. Also not a horribly difficult task.

What was hard, is that I needed to keep track of the point orientation as the player walked the path.  This was crazy hard for me to figure out the best way to do it.  You could not just say, if the player goes left, the left vertices is the bottom one and the right is the top.  That might work for some shaped walk boxes, but others it wouldn’t, especially if the angle you were walking into it was a diagonal.

The solution I finally came up with was to find the orientation of the segment. If it was mostly vertical, or mostly horizontal. Then I got the direction the player was moving in. Based on that I made the following conclusions which seem to work.

If the segment was vertical and player moving right, then left = upper vertices, right = lower.

If the segment was vertical and player moving left, then left = lower vertices, right = upper.

If the segment was horizontal and player moving up, then left = left vertices, right = right.

If the segment was horizontal and player moving down, then left = right vertices, right = left.

So now after tweaking my code to move the player along the path via the center points of each walk box, the player walks a smooth line to the click point!

The final step in the process is Steering.  I’m unsure if I’m going to do this or not.  I don’t think my walk box paths are going to be that big and it looks pretty good as is.  For example, if a player is walking around a turn, he will make a 0-point turn.  You could use steering to tell the character to generally stay within a range of the path I made with the Simple Stupid Funnel and steer back to it if they get off track. If I implement this, I’ll have to do some more research into the best way to implement it.

Now for a demo!