Formation Movement

A formation is a structure for units to move within. This can be used in games to make the AI look more realistic.

 In the above example the first part is the movement of units that all act on their own to get to an end point. These units could have simple behaviors to avoid colliding with each other but don't have any knowledge of the group as a whole. The line formation on the other hand has to have an outside system with knowledge of where everything in the group can be. This system can be ran with one unit leading a group or an external formation manager, managing all of the positions and movement of the desired positions. This post will focus more on an external system managing units rather than a leader but many of the concepts can be applied to both.

Dave Pottinger in an article called "Implementing Coordinated Movement" discusses many strategies of how to create and move formations. Researching these ideas I gained a good understanding of how the basics of formation movements work. Formations have slots that units fill and follow. A formation should have multiple states such as currently forming, formed, and moving along a path. A formation that is currently forming has units in it that have not yet filled a slot. It is often important to plan out the order in which units join the formation and can be worth it to have the units join one at a time. This is especially notable when creating a box formation.

This problem can easily be avoided with some planning. One way of approaching this is having each slot get filled one at a time. The order for filling the slots would be based on their distance from a reference point. When a slot gets chosen it will then choose the best available unit based on a heuristic value. This heuristic value can be created by taking into account factors such as distance, and ease of travel based on obstacles in the way of the path. For this situation it would make sense to have the reference point be the center position because that is the most likely point to get blocked off. If however the formation was created in a corner the center may not be the best choice. In this case using the center point will often result in the part closest to the corner being blocked off as the last unit attempts to go into place. These sort of things depend on the environment of your particular game.

Now that we have formed our formation, according to the way our states work, we can move. In all formations the units will be simply following their assigned slots in the formation. The formation itself and the slots will move using its own logic. Depending on the shape of the formation depends how it should move and rotate. In some cases the rotation doesn't matter much because the formation will look good regardless of the direction it is moving.

However, as seen in this example, with a line formation it must rotate in order to look correct. This can be done rather simply by stopping the formation and reforming it based on the new desired rotation.

I made a tech demo in order to understand some of these ideas in action. In this demo you can see square formation with the center as a reference point when it is not made at the corner of the screen. It also shows movement with both box and line formations as previously described.

This is just a simple example of formation movement but in a full game there would be many more obstacles to deal with. If a unit within the group gets far away from a point it needs to act accordingly. The article "Realistic Behavioral Model for Hierarchical Coordinated Movement and Formation Conservation for Real-Time Strategy and War Games" discusses a movement strategy to help solve this issue. Each unit has three movement states, slow, normal, and fast. Based on various factors such as the units distance for its slot it may switch between states. But regardless it will stay within the constraints of the fastest and slowest states. I implemented this in my tech demo based on the distance but it is not very noticeable due to lack of obstacles and collisions.

In the book,  "Artificial Intelligence For Games" by Millington, Ian, and Jon Funge, there is a section on scale-able formations. This is a formation such as a defensive circle that can get larger based on the number of units. This can be done fairly simply by increasing the radius of the circle allowing for more slots to be added.

Formations are often used in RTS games. In this case there are many units that group and move together across a complex map. In this situation path finding algorithms would be necessary to figure out a path that the entire formation could go but we won't go into that here. Another game that formations can be used in is a battle ships like game. In this situation a player could be the captain of a fleet of ships and have a formation follow him in an intelligent manner. These are just a few examples of where formations can be used.

As discussed earlier in order for formations to work well a lot of planning is needed. Making these plans and acting on them takes a decent amount of CPU time. Because of this it is important to consider how complex you want to make your formations based on your platforms restraints. On PC it is entirely possible to utilize the CPU power of modern day machines to have really well working complicated algorithms that create intelligent formation movement. This is not to say it can't be done on platforms such as mobile because it most certainly has; it is just important to tone down the complexity of the AI for a platform such as mobile to allow it to run smoothly. This technique can be used on most platforms if the complexity and efficiency are considered with the platform in mind.

References:

Mamdouh, Abdulla M., Ahmed Kaboudan, and Ibrahim F. Imam. "Realistic Behavioral Model for

Hierarchical Coordinated Movement and Formation Conservation for Real-Time Strategy and

Games."IAENG International Journal of Computer Science (2012): n. pag. Web.

Millington, Ian, and John David Funge. Artificial Intelligence for Games. Boca Raton: CRC, 2009. Print. 

Pottinger, Dave. "Gamasutra - Coordinated Unit Movement." Gamasutra Article. N.p., 22 Jan. 1999. Web.

04 Dec. 2013. 

Pottinger, Dave. "Gamasutra - Implementing Coordinated Movement." Gamasutra Article. N.p., 29 Jan.

1999. Web. 04 Dec. 2013. 

Hierarchical Pathfinding Tech Demo

This is a tech demo I did with Evan Schipellite for my game AI course. We implemented hierarchical pathfinding and path smoothing. The purpose of hierarchical pathfinding is to make the movement path calculated much smaller and relative to the characters current area. For example if your in your room and you need to get to work, the only path that is immediately important is the one to get out of your room and into the next one. In order to know which room is the next one (going into the hallway instead of your bathroom) there needs to be a higher level plan. To create this plan the hierarchical pathfinder needs to group up sections and layers. The first layer being the node information that would be used for something like A*; In our tech demo we use a tile grid with connections to all adjacent tiles without collision. The next layer could be grouped as rooms like the bed room, upstairs hallway, bathroom, ect. The layer after that could be the buildings such as your house, your work building, ect. From here you can keep making as many layers as necessary to increase efficiency. I created a level editor using C# XNA with winforms to provide the data for our tech demo. Using this editor we were able to easily specify sections in as many layers as we wanted as shown in the pictures above.

The most challenging part of this project was understanding and implementing hierarchical pathfinding. We used Artificial Intelligence For Games by Ian Millington and John Funge for the explanation of how hierarchical pathfinding works and algorithm for implementing the pathfinding. It took us a few hours to completely understand how hierarchical pathfinding should work and how we should approach doing it. I was able to create an infrastructure that would read in the data from my level editor and create multiple layers that we could use in our pathfinding algorithm. We were then able to take that infrastructure and apply it to the algorithm in the book to get a working hierarchical pathfinder.

To show off the smaller subsections of hierarchical pathfinding working we added the ability to turn on and off continuous pathfinding. When continuous pathfinding is off the characters only move to the next room on the higher path. This demonstrates how small of a path is created at one time.

In order for hierarchical pathfinding to really be worth it the map would need to be much larger than it is in this tech demo. In this situation it would not be impossible to A* across the whole map but if the map was much larger it would take far too much time to A* to any position. In that case this technique would be very useful to allow for pathfinding over a smaller area.

Spacewars Game Jam

In my networking class last Friday our professor John Pile surprised us with a Spacewar themed game jam. The goal was to group with one other person and make a networked game similar to the 1985 version of Spacewar. I choose to group with my friend Evan Schipellite. We decided to use his game for the last assignment as a starting point. From here we both just looked at the requirements and started to code. I started to work on game-play features such as the player class while he converted the architecture to work better with our new game. After I finished creating a few classes I needed to merge them with his architecture in order to test if they worked. Evan at this point had already setup some classes to make it relatively easy to merge our work. With just a little help I was able to get everything linked up and ready to go. The player class started to work with little need for fixes. The speed and some other values weren't the best but it worked and that was good. At this point there was still much to be done and with only very little time left. I was able to squeeze in bullets and the display of health within the last few minutes but there was not time for perfection. I had initially set it up so each player would be authoritative over when they took damage from a bullet but when I looked at the clock and saw less than five minutes left I realized that sending health data over the network was not going to happen in time. So I decided to comment out the line making it authoritative and just had everyone decided the score for everyone else. At the end we had working ships that could move around in a way fairly similar to space wars, bullets that hurt enemies, a awesome star field background made by Evan and a win state. To be able to create all of these things in a somewhat working fashion in such a short period of time was a success that I could feel good about. In retrospect though it would have been good to have a little bit more planning as to what we each were going to get done and what we wanted to accomplish during the time period. While we were doing the game jam both of us had very little idea what we were going to do let alone what the other person was doing. We just looked at the list and started programming things that needed to be done.

After the game jam we decided to improve upon the game and take our own spin on Spacewar rather then trying to make an exact copy. I came up with the idea that instead of in space we could be in quick sand because this would still work for the idea of gravity in the game. We evolved the idea from there and decided to make it a group of tourist that got stuck in quicksand and the tour guide only being able to save the last one. From here I went into polishing the old game features and adding on new ones. One of the requirements for the game was to have the bullets limited to 10 per player but last forever (with screen wrap). This caused a lot more difficulties than originally intended. Having this happen wasn't to difficult but as we watched the game go on the bullets would lag behind on different player screens. If a bullet was only alive for a second than the difference was so minor that it couldn't be noticed but if it were on the screen for 10 seconds a bullet on one screen would be maybe 3 seconds behind another. This was a pretty major problem so we tried our best to fix it. First we attempted to have all the computers sync up without sending bullet information over the network. We used methods such as having a physics timer so the bullets would only update every 50 milliseconds, multiplying the elapsed time by the speed and reducing the frame rate. All of this went to no avail so in the end we made the host authoritative over bullets sending their positions with a byte ID over the network. In the end I am happy with how both versions of the game worked out.

Bounce

Developers: Jacob Ellenberg, Devon Case, Robert Bethune, Noah Drayton, Eric Teall and Stephen Baptiste.

This is a project I did for my production class. We were grouped into teams of 5 or 6 and given 6 weeks to create a mobile game. My group consisted of 2 programmers, 2 artist, and 2 designers. We decided to make our game for the Nexus 7 because it was the most commonly owned device among are group so it would be the easiest for testing.

Bounce is a physics based game so to make our lives easier we decided to use a physics engine. The other programmers, Robert Bethune, and I decided to use Box 2D as our physics engine. This worked out really well except for the fact that comers of objects sometimes did unpredictable things.

Most of the programming in this game went smoothly. Rob and I worked really well together. For the most part we met up in the labs and programmed there. We would divide up what we needed to do at the start and help each other out if one of us got stuck on anything. This worked out well for the most part but towards the end of the project when we added some extra levels the game wouldn't work on mobile. This is likely due to the amount of memory we were requiring it to hold when loading all of the levels at the beginning of the game. We did not notice that this was happening until it was too late to fix because we were testing primarily on the PC when doing finishing touches. I learned from this that it is very important to test on mobile even after making what may seam like minor changes.