Thursday, October 11, 2012

Platformer AI: Swarmmers

This past week has been very busy for me. I could get a chance to enjoy my Fall break and play some video games that are sitting on my shelf all alone, but instead I get to spend the week with Game Maker. I'm still developing a tech demo to show off to my professor that must be done by this upcoming Monday, so procrastination isn't an option. All I have up to this point is an angel that can move around and shoot fireballs (just one of many abilities) and the lowest enemy that a player can fight.

I actually did quite enjoy developing this enemy since it required me to do some actual thinking (not just looking at documentation online to make sure I did it right). This enemy is a lot more complicated than your average Goomba who walks back and forth all day. For this enemy, I had to implement basic physics and calculation to estimate trajectory and get from platform to platform. I will be using some advanced physics equations (what you would learn in an intro college physics class that required Calculus).

For clarification, this specific enemy is called an Imp.

The Imp is a not powerful and very weak. It works well in large numbers where it swarms their enemy by strength in numbers. What I needed to do was to create an enemy, that when the angel got into range it would swarm straight towards it. This is not as straight forward in a platformer with multiple platforms at different levels.

The Imps default mode is just to walk back and forth on its platform until the imp spots the angel.

When the Imp spots the angel it determine if the angel is above, below, or on the same level as the angel. The same level argument is easy enough as the Imp just charges by setting the x velocity towards the angel.

When the Imp is above the angel:


The image above shows what should happen in this situation (red denotes Imp, blue denotes Angel). The Imp needs to get from the top platform to the bottom, So either he can run off the edge or jump off. Running off might seem simpler but that does collide with the code that makes the Imp stay on the platform in his default mode. Jumping not only makes it easier for the Imp to get to the target, but it adds a more fluid and natural looks of a demon trying to get to its target in the fastest way possible. 

To find the initial velocity needed to clear the platform, it needs the distance (d) from it to the edge. From there the equation is: 


vi is the initial velocity that is needed, g is gravity and theta is 45 degrees (pi/4) because its the easiest to calculate and x velocity and y velocity are the same. Everything else besides vi is known so we just rearrange the formula to get: 


using vi, just plug in that number into x and y velocity and the imp will jump off the platform and land below where it can swarm the angel.

There are some things to be aware of and it is the negation of the values that are put into x and y. For example, vi can be a positive number but the y velocity needs to be negative because of how the Cartesian coordinate system is arranged by the language. 

When the Imp is below the angel:



This requires some more insight than the previous one. When the Imp was jumping off a platform, it could jump at 45 degree angel making the calculation easier. In this case, X and Y are independent of each each other except time (t). The vector at which the Imp jumps can range from 1 to 89 degrees. The angel at which the imp jumps is irrelevant if the x and y velocities are known. In order to figure out the velocity in which the imp must jump, we must find the minimum velocity to reach the height of the platform (h). 


 Since the y velocity when the Imp reaches its height will be zero, the equation can be rearranged to:


Knowing the initial y velocity, we can now find the initial x velocity. The only thing that x and y velocities share is that it will take the same amount of time to reach their destination. We can use that knowledge to get the x velocity so that the Imp can reach its distance (d). We can start with the most basic of physics equations, the kinematic equation to find position. Since x does not have an outside force on it, acceleration is zero and we get the equation: 


xf and xi subtracted is the difference (delta) x which in turn is distance:


Again using the kinematic equation for the y axis for velocity, we can represent the initial y velocity as:


Again knowing that final y velocity is zero, we can rearrange that equation as:


We can rearrange the x axis formula two above as:


Plugging t into the x axis formula, we get:

Using basic Algebra, we can rearrange this to be:

Now that we have an initial velocity, the Imp can now jump to the next platform. 

There are some problems with this implementation, and that is it does not take into account where the imp is and the dimensions of the platform. The imp can be below the platform and jump straight into it. The other problem is that the imp will always be one step behind. The hero can be jumping up several platforms and the imp will only know when it lands on the previous platforms. There are ways for the imp to follow the angel up the platform and anticipate where the angel will be using more advanced algorithms. For the moment, this algorithm is sufficient for a basic low level enemy and does provide some basic challenge above the walking back and forth goombas. At least the imp is trying. 

That is all while I finish to complete my tech demo and get the first level finished. Game Maker doesn't make it easy as well as I have to forget everything I learned as a CS major to get some things to work also a debugger that doesn't let you step through your code.

Wednesday, October 3, 2012

Game Maker: Physics Engine and Globals

Physics Engines are one of the greatest things that a developer needs when making a game (especially a platformer game). It makes collision detection vastly easier and creates smoother transition and motion that looks more normal. But there are so many engines out there and half of them defunct. Finding a right one, then hooking it up to your project, and making sure it works correctly is no small task.

For Fallen, I have to link up a physics engine to make collision detection easier when the sprite moves and jumps on platforms and slopes. The built in functions to do this are too jagged and sloppy and are just simply horrible and convoluted to do anything useful. Thus I had to hook up a physics engine to my game. That is where the problems started.

When I first started looking I came across an engine called GM Physics. It seemed promising and the initial reviews for it were favorable. I hooked it up and looked at the demos to see what to do with it. The demos has no comments explaining what each function did and when I looked online to find out, there was no documentation of any kind. This proved problematic as I had no idea what to do with a library that didn't tell me what it could and could not do. I spent a good 2 hours trying to find something to help me with the engine, but to no avail. It was when I came upon a forum when I found out that the developer had stopped development some 2 years ago and had many internal bugs that were not going to be fixed any time soon. I had to give up my search with GM Physics and try again.

I started my search again and came upon an engine called Extreme Physics (http://www.maartenbaert.be/extremephysics/). I found out that the developer has not given up on it and is still coming out with updates for bug fixes. This was my first good sign. There were some good reviews on it too, and the fact that there was a page of documentation explaining what the functions were called and what they did. The explanation and the documentation is poor in my opinion, but it was better than nothing and what I've seen from Game Maker, it is the best I'm going to do.

I hooked it up and followed the demo on how it did collision detection for hitting into boxes. I was initially stuck since when I hooked up the bounding boxes to the player and the platform box, the player always started out knee deep into the floor. Upon inspection and a few hours of agony, I was able to figure out that the way I set up the bounding boxes, was wrong. When I made the box, I set the width and height as the right numbers, but the x and y coordinate was wrong. I set is as 0,0 which should make sense if the way it sets it up is like any other language sets up a box. However, this apparently offset the box down and to the right since my player would get stuck down in the ground and get stuck to a wall if he jumped to the right, but not to the left. The way I had to fix it was to set my x and y as half the width and height. This fixed my problem and my player can jump on platforms very smoothly. I really hate when developer don't explain details like this and assume that you should know. Its okay for developers to stray from convention and what other languages do in a similar situation. But you have to explain why you strayed and how the new way works to avoid people spending hours figuring you weird convention out.

Starting to feel that I have this collision detection down, I started to work on the player walking up and down ramps. This requires the use of a bounding triangle. The way that I did it was by creating a polygon and attaching it to the ramp. I created the polygon as the documentation and the demo instructed. I even attached it as the demo showed. However, that was not enough as a error showed that said the polygon was not convex. I thought this impossible, because a triangle only having three sides would only be convex and never have a vertex that defiled the meaning of a convex polygon. Instead of fixing it, I decided to take a break already spending several hours just that day figuring out two different engines and running into many brick walls.

When I had finally came back to the problem, my initial guess was not that it was or was not convex, but that I just built it in the wrong order. Past experience has showed me that when you build a polygon, that if you construct the vertices in a counter-clockwise way, then the side that would be culled would be facing towards the camera and that in order to get the right way showing was to construct the vertices in a clockwise way. I thought that this may be the same reason too, but for some reason didn't pursue it. About 30 minutes passed of playing around with values with no result was when I decided to construct the vertices in a clockwise manner. To my thrill it worked, my player could walk up and down ramps now. However, the motion up the ramp is still jittery and I believe I can fix it, I just need to play with the values a bit.

Hooking up the collision detection took a vast majority of my time, but when I wanted to take a break from it (after I got the platform and ground working), I decided to add two different rooms that were part of the level. In order to do this I needed to keep track of what the previous room was so that the player could end up in the right spot in the next room and facing the right direction.

I created an exit trigger (just a square), that would start the event to transport the player to the next room. If this was regular code,then each instance of the object I created would have a global variable that showed what room it was currently in so it would be easy to set up the player. At this point, my interpretation of how variables worked was based on how other languages did it. There are three ways to set up variables  in Game Maker:

  1. global.varName
  2. var varName
  3. varName
My initial misreading of the documentation was that to var and global.varName was the same way to set up a global variable while varName was a local variable that would only exist for that function (script). I also initially thought that a global variable was only global for the object. Then when I did obj_name.global_var did I figure that that didn't work. So I decided to create a getter method that would return global.varName. Game Maker didn't like that either and would always throw a bug when I did it like that. I spend a good hour online trying to figure out what to do when I came across a youtube video explaining variables in Game Maker. It was the moment that he said that global.varName would create the variable that was global to all objects in a game did I realize that I had it all wrong. 

I went back to the documentation on variables to see what else I got wrong, when I figured out that varName was global to the object and could be called like obj_name.varName and that var varName was only local to the script it was in. After this realization, using variables and being able to pass them around became significantly easier. I will have to go back in my code sometime and change around variables that were initialized under my false presumptions to something that actually fits convention and good programming style. 

I have now figured out that Game Maker has changed the game on many things with programming from what they normally are in more C based languages. I now just wonder how many more surprises I will face.