I didn’t post last week at all, but that’s not to say I wasn’t working on the game at all.  I spent a good amount of time making the room builder easier to use by adding a toolbar to the top.  Prior I had keyboard shortcuts.

I then started the task of adding perspective scale to walk boxes.  The higher up on the screen I want the player to look further away, smaller and move slower.  There are a couple ways to handle this.  You could just scale the player via it’s Y position, however I want a little more control than that.

I tried adding a scale value to each walk box, so as long as the player was in that box, he would be that size.  However that didn’t work to well because there wasn’t a good way to set a speed to uniformly scale the player when it crossed a border to the new box.

I changed methods and assigned a scale value to each corner of the walk boxes.  The closer to the corner it gets, the closer to that scale it gets.  It took me a lot of experimentation to get it working.  It still has some weirdness to it, but as long as I follow a few rules, it works.

Each walk box can only have at most 2 scale sizes in it. This means I am limited to using rectangles or triangles. If I add more points or scale sizes, it jumps up or down to different scale sizes too rapidly when it changes to a new closest point.  I’m sure there is a way to somehow average some values together of all the points or something to get a smoother transition to use more corners, but I’m bad at math and this seems to work so I’m going to move on to the next thing.

I actually did try averaging the scales between the closest corner and all the other corners but that had the effect of shrinking the player in the center of the box and growing him along the edges, which kind of makes sense.

The method I am using to determine the scale is the following:

• Get the closest point to the player and second closest point to the player with a different scale value
• Get the difference in scale between the two
• Get the distance between the two on the Y axis
• Divide the difference in scale by the distance
• Subtract that value from the larger scale size
• When the player walks, multiply the scale by the speed that I’m moving it so that it moves slower when “further away” from the camera

In the video below, the blue line drawn is the distance from player to the closest corner, and the red is to the second closest. I set the scale values pretty drastically different for testing purposes so you can really see the scale changes.  At the top of the screen the scale is .5, and bottom of the screen 1.0 – In the actual game, I don’t think they will be so drastic.

I’m going to hold off on tweaking the path finding and smoothing algorithms until later.  Instead, this week I decided to take what I learned from last week to create a new application that I’ll be developing along side the game.  It will have much of the same code as the game, but it’s main functionality will be a level editor. This will save me a lot of time in creating each room of the game.  I’ll be able to quickly layout the room and easily edit them visually instead of the long slow process of doing it in code.

I will be able to drop in a background, click and draw where I want the walk boxes to be and how they connect with each other.  I’ll be able to add portals/doors, game objects and other sprites into it.  Then when I’m done with the level, I can save the configuration to a json file so the game will be able to easily load it.

I have the file loading, exporting to json, and path finding working with a test mode, but I need to add the tools yet to add other objects, and images. I also need to add the ability to delete points of a polygon or whole polygons.

Here is a demo of it so far.

This week I spent a few days trying to figure out walk boxes and path finding algorithms, which led to a lot of frustration and wishing that I paid more attention in my freshman CS 367 class on data structures!

After doing a lot of research and finding very little code online to follow, I was finally able to stitch together a prototype that implements walk boxes and path finding!

Walk boxes are polygons that limit the areas that a player can walk in the world.  Path finding is finding the shortest path from a point in Polygon A to a point in polygon Z using those walk boxes to go around obstacles. If you have to walk through several polygons to get to a target, it will return a list of the polygons that has the shortest path.

Here is a really crude example.  Please excuse my horrible Photoshopping skills, but in this image the green arrow is what the algorithm, A* (pronounced A star), would calculate the path of the player should be if they were on A and wanted to get to H. It would then tell me the path should be through polygons A, B, C, D, E, F, G, H.

I found many good articles about the theory behind it, but I couldn’t find much code.  What I could find, wasn’t written in C++. The other issue was that a lot of the articles were written for a simplified version of A* using a grid system. This would be great if I was making a tile based game like Lumps of Clay or Super Mario Brothers, but it doesn’t really help much when it comes to polygons / nodes.

In the end I found a wonderful article written by Julian Ceipek. http://jceipek.com/Olin-Coding-Tutorials/pathing.html It describes path finding much better than I ever could.  It also describes in detail the  algorithm to find the shortest path between two nodes.  Perfect! That’s precisely what I wanted.  But the little code he had was written in another language.

It took a while but I was able to make my own node / graph class to store the node and edge data.  Then I was able to port his code over to C++ to analyze the graph data to find the shortest path between nodes. It seems to be working after some tweaks.

Now I need to find some time to implement the algorithm, “Simple Stupid Funnel”.  It is a smoothing algorithm which makes the path taken more direct instead of having the player walk to the center of each polygon before moving on to the next.

Without further ado, a short demo!