Intro

There are many different algorithms for finding paths, for avoiding collision and for smoothly following a path.  A normal approach in game would be the following:

• Use a path finding algorithm like A* to construct a path.
  • (see my tutorial here: http://roy-t.nl/index.php/2009/07/07/new-version-a-pathfinding-in-3d/ )

• Construct an algorithm that follows the path exact enough not to collide with the predetermined ‘not empty tiles’ but loose enough so that it looks natural.
  • (In XNA you could use the curve class to help: http://msdn.microsoft.com/en-us/library/microsoft.xna.framework.curve.aspx )

• Construct an algorithm that detects objects that are on our path and calculates new routes around them.
  • (Maybe some ‘look ahead’ and A* again, question: do you calculate from the
    obstruction to the finish, or to the next free tile, or both?)

Although this looks like a lot of work, most of these algorithms are freely available, how to implement them is well know, and most of these algorithms are reasonably fast.  So for a little bit of work we get a solid, well known, always working, pretty fast algorithm that in a pretty constant world finds nice paths.

Problem

For my current project I’m trying to emulate a galaxy (no small taskJ) ships move from planet to planet, but these planets are not static, they are moving in ellipses around a sun. Calculating the paths ships have to take would be troublesome, because paths close the planets would constantly change, and even more important, once we get to the finish line the planet already moved a bit further. We could update our path every x-amount of time, but this would give our pour CPU too much to do, and would give us a strange and jerky path.

Solution

After a bit of whining on #XNA (see the links section) someone (I wish I remembered who, so I could give credit where it’s due) suggested taking a look at swarming algorithms. (Here computer models try to simulate how swarms of birds or fish interact with each other so that they don’t collide and keep following their leaders). Although I didn’t directly see a connection, I was interested in how these models kept birds from colliding with each other. Apparently when a bird ‘senses’ that another bird comes too close it tries to move in a direction so that the minimum space between them is restored, however it also tries to keep follow his targets, the result is a new direction vector  where the evasion and the following are calculated and weighted in. When a collision is imminent the weight of the evasion grows and when there is no danger at all the weight of evasion drops.

Another way to look at it is like a set of magnets. The bird is a little iron ball, the obstacles are negatively charged and try to push the ball away, while the finish is positively charged and tries to reel the ball in. Can you see it in your head now?

After I realized this it was pretty simple to create some code that produced the following video:

And now with moving obstacles:

As you can see the path is fairly smooth, nothing is hit, and we reach our end goal. All I had to do was write these 50 lines of code (including comments and white space)

 //Simple class that represents 2D objects
public class Object2D
{
    public Vector2 Position;
    public float Radius;
    public Color Color;
    public float MetersPerSecond;
}

        //All we need is this static method, here generically called update.
        public static void Update(GameTime gameTime, Object2D ship, Object2D[] obstacles, Object2D target)
        {
            float pullDistance = Vector2.Distance(target.Position, ship.Position);

            //Only do something if we are not already there
            if (pullDistance > 1)
            {
                Vector2 pull = (target.Position - ship.Position) * (1 /  pullDistance); //the target tries to 'pull us in'
                Vector2 totalPush = Vector2.Zero;

                int contenders = 0;
                for (int i = 0; i < obstacles.Length; ++i)
                {

                    //draw a vector from the obstacle to the ship, that 'pushes the ship away'
                    Vector2 push = ship.Position - obstacles[i].Position;

                    //calculate how much we are pushed away from this obstacle, the closer, the more push
                    float distance = (Vector2.Distance(ship.Position, obstacles[i].Position) - obstacles[i].Radius) - ship.Radius ;
                    //only use push force if this object is close enough such that an effect is needed
                    if (distance < ship.Radius * 3)
                    {
                        ++contenders; //note that this object is actively pushing

                        if (distance < 0.0001f) //prevent division by zero errors and extreme pushes
                        {
                            distance = 0.0001f;
                        }
                        float weight = 1 / distance;

                        totalPush += push * weight;
                    }
                }

                pull *= Math.Max(1, 4 * contenders); //4 * contenders gives the pull enough force to pull stuff trough (tweak this setting for your game!)
                pull += totalPush;

                //Normalize the vector so that we get a vector that points in a certain direction, which we van multiply by our desired speed
                pull.Normalize();
                //Set the ships new position;
                ship.Position += (pull * ship.MetersPerSecond) * (float)gameTime.ElapsedGameTime.TotalSeconds;
            }
        }

As you can see that is very little and simple code for path finding, collision avoidance and smooth following. However there are some drawbacks.

Take a note

Of course there is a good reason why not everyone is using this. The path finding is not optimal (with many objects the path is not always the shortest), there is a chance to get stuck if the finish is hard to reach and this code would fail horribly in mazes. However in space there are not many objects to avoid, it’s hard to get stuck and the paths might not be optimal, but after dodging a planet or two we can go to our target in a pretty much straight line. Other scenarios where it might be interesting to try this out is in racing game AI’s (where the target is for example a dot moving across the ideal line, a meter ahead of the car) where I think this would make a very interesting algorithm. (Of course you need a braking algorithm as well, maybe adjust throttle/braking on the change in direction compared to the current speed?)  Another genre might be surfing games, strategy games with little obstacles, or other ‘stupid’ AIs, like a pet AI for cute pets like in world of warcraft.

Conclusion

We made a simple and fun algorithm with much potential, when used wisely this algorithm can make your games code a lot easier. Take note of the drawbacks though, A* is not perfect in all situations (else we would’ve used A*) and this algorithm should only be used when it is appropriate. (If you have trouble deciding this please post a comment, I’ll try to help out, however sometimes it’s just a matter of experimenting).

Oh btw, after some browsing I found some fun alikeness  with steering behavior, although that does work a bit differently the same concept lays at the basics. You can find out more about steering behavior here: http://www.red3d.com/cwr/steer/

(Since this has become quite a long article, I would like to point out that the link and free e-book are found at the bottom of this article).

Algorithms and data structures are one of the most important (and sometimes hard) things in computer science. As I’ve recently came to see just how important having an efficient algorithm. Take for example my A* example, the first iteration of version 2 was incredibly slow because the .Net list data structure is geared toward iterating and adding items and less toward finding items.

First I did not see this problem. I benchmarked the A* code and came to the conclusion that it was too slow to be usable. Finding a path took about 3000ms. Without looking at the data structures and algorithms I began micro-optimizing the code. A tedious task which often makes the code less readable, however I was ‘successful’ finding a path now only took about 1000ms, making the algorithm 3 times as fast. A remarkable improvement, but still not enough to make A* usable in games. And I knew from previous experience and literature that A* is often used in games and rather fast.

After a while I asked for help on a couple of forums and people started to point out the slowness was caused because I had to look up if a tile was contained in a list or not. This happened a couple of times every iteration. The .Net list data type requires to look through the entire list from a till z (until it finds the item) to determine if it’s in there. This way every iteration became quite complex although not much needed to be done in each iteration I still had to check the entire list multiple times.

The solution was simple. Use a Boolean flag on the tile to put it in a list. This way I can just ask the tile if it is ‘in a list’ or not. This proved to make the code several orders of magnitude larger, now I could find a path in 10ms. Which made the code 100x faster, al because of using a different data structure.

Big O

To explain why this is possible I will first have to tell you something about “Big O”.  The .Net data structure for lists is not at all a poor or slow type. Adding something to the list is very fast (Usualy O(1) which means that no matter how much items are in the list, inserting another item will always be ‘constant time’ fast. No matter how much items are already in there).  Searching for an item however is a bit less fast.  To show how fast I will give a small code example:

for(int i = 0; i < list.Count; ++i)
{
        if(list[i] == searched){returen true;}
}

return false;

This is roughly how the contains method is implemented. As you can see we have to traverse the entire list until we find that list[i] == searched is true. If the item is not in the list we have to wait till the last item and then we can tell that it was not there.  This type of solution is considered O(n)  here n means that the time it takes to execute this algorithm is dependent on n, the number of items.

There are multiple ways for an algorithm to be dependent on n. Here I list the most common dependencies (with examples where to find them).

Usualy O(n^x) is considered inefficient but for some very specific problems involving primes it’s the fastest we can go. There are also problems that we can’t do efficiently yet, these involve all the problems in the class P ( http://en.wikipedia.org/wiki/Sharp-P )

Of course some problems are not exactly O(n). For example in the sample we could say we would have to do multiple things for each n. We have to check if ‘i’ is not bigger than the count, we have to check if we found our item, etc.. So let’s say that this problem is O(3n). This would be correct however we never write it down like that because constants don’t affect the complexity. Something that is O(n) depentend on n, will always be faster then something that is O(n^2) dependent on n.

Academically versus real world

Well academically it’s simple. No matter how inefficient your O(n) code. If another piece of code takes O(n^2) times (or anything else dependent on n) there is an n big enough which makes the algorithm dependent on n slower than the not dependent algorithm. Given this example O(1000n) versus O(n^2) we can see that for a number as small as 32 the ‘slow’ O(n) is slower than the ‘quick’ O(n^2). Since 32^2 = 1024 < 32000.

However what if we have a container with 1000 items. We now see that 1000^2 = 1000*1000. And what for an n even greater than 1000, say 1002? We now see that 1002^2 = 1004004 > 1002000. As we see 1000 is the breakeven point for O(1000n) and O(n^2). For an n greater than 1000 our O(n) algorithm is faster, as it should be.

Academically we are done, but in the real world we have to make a consideration? What is the chance that there will be more than 1000 items in our data structure? If the question is very unlikely it might be smart to go with the O(n^2) algorithm although for large numbers this is always slower. (And remember that for every n bigger than 1000 this functions takes ^2 more time, not a n-constant factor).

Always analyze what functions are used most on your data structures. (Is your data structure insert, find, or delete heavy? And does it ‘indexing’ access?) There is no data structure that can do everything fast, so be sure to search for a data structure that is as close to O(1) as possible for you.

For example a linked list has faster deletion (O(1) once the item is found) , and equally fast insertion as a normal list, however using linkedlist[550] is slow O(n) on a linked list while this is O(1) on a normal list. If you want to delete a lot you want to use a linked list, but if you want to index a lot you want to use a normal list.

Sometimes you can use two data structures in conjunction as to make all algorithms fast. Or cheat by doing a trick. Need to check if something is contained in a list? Try instead of using a list using a hash table which can do a ‘contains’ check in O(log n) or faster.  Or try using Boolean flags on the object it’s self.

Helpful link and an e-book

After randomly browsing the web I came along an interesting link on Sgt. Conker’s website.

Without further delay I present you: the link.

It’s a relatively old page on MSDN about Algorithms and Data structures for .Net, however I still think this is a must read for every .Net developer.

For a more general approach to efficient algorithms and data structures I can recommend this free e-book: http://www.jjj.de/fxt/#fxtbook (for most people the .pdf file link is what you are looking for), which in no less than 1000 pages explains everything there is to know about algorithms and data structures.

As I’ve recently moved to my own domain and hoster, I can now do a few things that I couldn’t do at wordpress.com. One of those things is ads.

Oh no, did he said ads, I never come here again!

Don’t worry about it, all I intend to add is a small box in the left menu bar. So I won’t be randomly adding adds to articles, and all this shouldn’t interrupt your viewing pleasure.

I’ve started using google ads today, and you will see the small box shortly (probably just psa-s for now ). I would like people to give feedback if anything out of the ordinary might happen. So feel free to hit that comment button!

Oh I’m using the excellent advertising manager for wordpress to manage these ads and to add them as widgets to my menu bars, check it out.

Well, this is the first time I’ll be showing off some things of SpaceAce.

The first video shows my simulation of our solar system, each of the eight planets is recreated accurately by putting all the data from wikipedia about these planets in the constructors and working from there. The relative sizes, speeds and rotations, inclinations and ellipsiness of the orbits around the sun are all accurate. The simulation shows 1day as 1 minute (that’s why the earth rotates so hard, it has to rotate 365 times a minute, and in one minute orbit the sun). About that sun, I don’t have it visible yet .

Oh the position between the planets is relatively correct, but it uses a different metric than planet size, else it would be almost impossible to be able to show more planet than one. (Those other planets are really far far away).

When I zoom out, and planets become smaller than their assigned icon, the planets stop being drawn and an icon appears in their place.

I’d really like to show the constructor of my planet class with you to show the complexity:

public Planet(GraphicsDevice device, SpriteBatch spriteBatch, ICamera camera, Effect effect, string technique, Texture2D texture, Model model,
            float equatorialDiamater, float orbitalRadius, float eccentricity, Vector3 focalPoint, float inclination, float rotationsPerMinute, float orbitsPerMinute, string name, Texture2D icon)
            : base(device, camera, effect, technique, icon)

And the video (sorry about the silly textures, their for debugging, btw best to watch it fullscreen in hq because youtube really made it hard to see).

An other video I created is to show off planetary gravity, (not implemented in the first video). It’s kinda fake, but this will allow the player to construct space stations and satellites that realistically orbit the planet. Satellites keep facing the planet as they orbit it. And the further away, the slower the orbit around the planet.

Oh well I think this video speaks for its self:

If anyone is interested I will make an article to show how I’ve done it. However the basics are storing a relative position (vector3) and updating the rotation from 0,0,0. Then setting the actual position to planet.position + relative.position .

Edit: after watching the videos on youtube I see there is another old game called SpaceAce, although SpaceAce for me is a working title I just wanted to tell you and make sure that my game has nothing to do with that old Atari game .

I’ve said before that I’m working on a game for some time now. Actually me and a friend of mine came up with this togheter, and now for a month or two I’ve been testing and laying foundations for this game. However I came a bit stuck as to “what to do now” LostC1tY @ #xna (effnet server) asked me why I didn’t make some kind of feature list and then try to work my way trough there. This reminded me of practices in the book Object-Oriented Analysis and Design and Iterative Development by Craig Larman (what a long name for a book ). In which he describes how to do iterative development.

One of the first few artifacts in iterative development are a small story “Vision” some uses cases and some features that are essential. Then you work your way down from there and keep refining the requirements while at the same time implementing them step by step.  I can really recommend this book!

Anyway, I’ve made a bit of a beginning  that I wanted to share, now you know what I’ve been working on. (Oh the working title is “SpaceAce” and I will post further related blog items under that tag, but the game will definitely not be called like that in the end, I’m just not good in thinking up names .

Design Document:

“Space Ace”

Vision:

My vision is to create a back-to-basics strategy game in space.  The setting is a small solar system with moving planets. The player starts on one planet and their opposition on another planet. Both players don’t know where the other player is located. Players start building ships and space stations. As long as these objects stay within the gravity well of the planet they will ‘follow’ the planet.  Planets got multiple ‘gravity well rings’. Depending on the planet there will be 2 to 6 rings. The inner most ring is the smallest and is very close to the planet. Objects in the innermost ring swiftly rotate around the planet this might be used tactically (say a space station with guns that can cover all approaches to the planet).  The inner most ring is only suitable for small objects (research stations, sentries, satellites etc…).  More outer rings cover a larger area and objects in that area orbit less swiftly. The most outer ring is very large; objects in this ring don’t orbit around the planet.  The outer rings are more suitable for factories and other large structures “that can’t handle the stress of rotating so fast.”

Once a player has a bit of an army they might decide to explorer. They can select a couple of units to form a fleet. Once they’ve cleared the gravity well of their home planet they can try to stay ahead of their planet (the slowest normal ships must be faster than the fastest planet, however comets and the like might be faster) or decide to go the other way in which case it’s much faster to find other planets.  It might be wise to have some ships in the gravity wells of planets that orbit the sun at different velocities as to always have a presence in different parts of the solar system.

The planets must move as fast around the sun as to not make this game boring but as slow such that the tactics of planets movement and gravity wells is still intact.

In the end players encounter other players. Fighting is pretty regular, different types of weapons do different types of damage (Kinetic, EM, Heat, and Electric). Each ship’s armor and shield are affected differently by these types of damage.  Players select their ships and then select enemy ships to attack these ships. Ships might also auto attack enemy ships when they are within the same gravity well.

Planets can be captured by sending troop ships, filled with troopers. Each planet has a “ground defense force” when you send sufficient amounts of troopers down to the planet the planet should be yours.

Economy is based on the number of captured planets, each planet has a different ‘economics’ and ‘resources’ value, per tick is calculated how much money and resources are gained. There is an ‘organization tax’ which slightly increases with each captured planet, to keep the game balanced when one player quickly acquires a few planets while others haven’t. Some special units might require rare materials; these can only be acquired by capturing special comets.

Preliminary feature list
As in proper iterative development this is not a complete feature list, but this will be grained out and refined during development.

(Starting with the most critical/difficult to implement features, which will be developed/tested first).

-Moving planets (complete)
-Gravity rings
-Build-able objects
-Ships
-Path finding
-Fighting
-AI
-Resources
-LAN
-Player control
-Menus
-Different difficulties
-Advanced editor
-Missions/storyline.