Roy Triesscheijn’s Weblog

My programming world

Hollandia progress report #1

Posted by Roy Triesscheijn on 27th August 2010

So, it’s again time to show off a bit more Hollandia here. Today I was working on the dialogue system, very basic functionality really. A dialogue consist of a series of frames. Some frames have special actions like activating a generic trigger or by showing a couple of options, instead of just text. Of course the character talked too can respond to different suggestions (this is done by associating each of the options with an index to a next frame).

As I said pretty basic and I still need to think out a smart way to highlight a couple of words without this interfering too much with all the draw code.

I thought it would be very cool if the dialogue screen doesn’t just appears and disappears instantly so using our prepared effect system (some nice abstraction around the actual effect files) I quickly cooked up a new shader added a few lines and yay, there it is.

I’ll get more into the technicalities later (make a comment if you’re interested in any specific subsystem). For now I’ll just show you this (very much in development) sneak peak of Hollandia that I uploaded today:

Tags: , , ,
Posted in Blog, General Gamedesign, Hollandia, XNA | No Comments »

More A* improvements

Posted by Roy Triesscheijn on 27th June 2010

As you might know I’ve written quite a lot of articles on the A* algorithm.

This week I was contacted by Roman Kazakov (fourfor[AT]hotmail.com). He had a look at my previous A* articles and came up with a number of ways to speed up my latest version even more! Unfortunately he doesn’t have a blog, so he asked me to publish his enhancements here, so that everyone can use them. So I’ll forego the rest of this introduction and let the man speak.

(Note: the following quote is the last unedited part of an e-mail of Roman Kazakov).

Hi Roy, my name is Roman Kazakov and I am Russian guy, but live in Latin America. My Spanish is perfect, but my English is “so so”, I hope you understand me. :) I am not a professional programmer. This is just my hobby from university. And as “free lancer” I work with VS 2008 C# + DevXpress + SQL Server 2008.
I would like to present you my optimization for you program AStar. Oh, by the way, my game is 2D, and this example is in 2D dimension, but this version will by work and 3D too and more faster.
Here is code of FindPathReversed:

 private static BreadCrumb3 FindPathReversed5Final(bool[,] worldBlocked, Point2D start, Point2D end)
        {
            // Here we dont use the class Poin2D. It is bad idea use Class just for two int values (X Y)
            List<BreadCrumb3> openList2 = new List<BreadCrumb3>(256);
            BreadCrumb3[,] brWorld = new BreadCrumb3[worldBlocked.GetLength(0), worldBlocked.GetLength(1)];
            BreadCrumb3 node;
            int t1, t2;
            int tmpX, tmpY;
            int cost;
            int diff;
            t1 = worldBlocked.GetLength(0);
            t2 = worldBlocked.GetLength(1);
            BreadCrumb3 current = new BreadCrumb3(start.X, start.Y);
            current.cost = 0;

            BreadCrumb3 finish = new BreadCrumb3(end.X, end.Y);
            brWorld[current.X, current.Y] = current;
            openList2.Add(current);

            while (openList2.Count > 0)
            {
                //Find best item and switch it to the 'closedList'
                current = openList2[0];
                openList2.RemoveAt(0);
                int position = 0;
                cost = openList2.Count;
                do
                {
                    int left = ((position << 1) + 1);
                    int right = left + 1;
                    int minPosition;

                    if (left < cost && openList2[left].cost < openList2[position].cost)
                    {
                        minPosition = left;
                    }
                    else
                    {
                        minPosition = position;
                    }

                    if (right < cost && openList2[right].cost < openList2[minPosition].cost)
                    {
                        minPosition = right;
                    }

                    if (minPosition != position)
                    {
                        node = openList2[position];
                        openList2[position] = openList2[minPosition];
                        openList2[minPosition] = node;
                        position = minPosition;
                    }
                    else
                    {
                        break;
                    }

                } while (true);

                current.onClosedList = true;

                //Find neighbours
                for (int i = 0; i < 8; i++)
                {
                    tmpX = current.X + surrounding2[i, 0];
                    tmpY = current.Y + surrounding2[i, 1];
                 //   tmp = current.position + surrounding[i]; //This is is a really slow!!!
                    /*if (tmp.X >= 0 && tmp.X < t1 &&
                tmp.Y >= 0 && tmp.Y < t2 &&
                !worldBlocked[tmp.X, tmp.Y])*/
                    if (tmpX >= 0 && tmpX < t1 &&
             tmpY >= 0 && tmpY < t2 &&
             !worldBlocked[tmpX, tmpY])
                    {
                        //Check if we've already examined a neighbour, if not create a new node for it.
                        if (brWorld[tmpX, tmpY] == null)
                        {
                          //  node = new BreadCrumb3(tmpX,tmpY);
                           // brWorld[tmpX, tmpY] = node;
                            brWorld[tmpX, tmpY] = node = new BreadCrumb3(tmpX, tmpY); // This is more fast!
                        }
                        else
                        {
                            node = brWorld[tmpX, tmpY];
                        }

                        //If the node is not on the 'closedList' check it's new score, keep the best
                        if (!node.onClosedList)
                        {
                            diff = 0;
                            if (current.X != node.X)
                            {
                                diff += 1;
                            }
                            if (current.Y != node.Y)
                            {
                                diff += 1;
                            }
                            cost = current.cost + diff + ((node.X - end.X) * (node.X - end.X)) + ((node.Y - end.Y) * (node.Y - end.Y));//node.position.GetDistanceSquared(end);

                            if (cost < node.cost)
                            {
                                node.cost = cost;
                                node.next = current;
                            }

                            //If the node wasn't on the openList yet, add it
                            if (!node.onOpenList)
                            {
                                //Check to see if we're done
                               // if (node.Equals(finish)) // This is slow too!!!
                                if (node.X == finish.X && node.Y == finish.Y)
                                {
                                    node.next = current;
                                    return node;
                                }
                                node.onOpenList = true;
                                openList2.Add(node);

                                int position2 = openList2.Count - 1;

                                int parentPosition = ((position2 - 1) >> 1);

                                while (position2 > 0 && openList2[parentPosition].cost > openList2[position2].cost)
                                {
                                    node = openList2[position2];
                                    openList2[position2] = openList2[parentPosition];
                                    openList2[parentPosition] = node;
                                    position2 = parentPosition;
                                    parentPosition = ((position2 - 1) >> 1);
                                }

                            }
                        }
                    }
                }
            }
            return null; //no path found
        }

Comments:
Look in my screenshots which i made it for you. For looking performance I used ANTS Performance Profiler 5.2. This is a great “stuff”!
Also you can use your benchmark. Check the file zip attached. There is all source and information for compiled.
Comments about code:
The general “thing” in programming in C# is do not use Obj Class and etc. where really dont need to use that! The best performance is just “Value type” and List<>
Array, maybe Struct.
In my optimized code I deleting class MinHeap where T : IComparable. Why?! Because is really slow, and I dont know why. Also use class Point2D just for 2(3) types X and Y( and Z), it was a bad idea. And many thing more. Looked my code and you understand which changes I made it. I hope this is help you. And please put this optimization on you wonderful web page http://roy-t.nl, as New Optimized Version A*.
When we made the games, we looking for more faster algorithm and code. This article will be help a many people as us.
We made the games of our dreams…

Roman also included a couple of pictures to show the speed gain of his code
Original code (by me)

New implementations (by Roman)

Tags: , , , , , ,
Posted in Blog, General Gamedesign, XNA | 3 Comments »

Immediate GUIs in XNA: Setup and a button

Posted by Roy Triesscheijn on 10th March 2010

Introduction

Part 2 (Scrollbars) is located here

Immediate GUI’s are a pretty new concept to creating and drawing GUIs. One of the big differences between an Immediate (IM) GUI and a normal GUI is that an IMGUI is non persistent. Every frame a manager determines which screens/buttons/widgets have to be drawn and only these are drawn. There are no Button objects, Form objects or objects at all. GUI items are immediately drawn by calling a method. Most of these methods are prefixed by ‘Do’ to show the immediate nature of the button. Because of this, IMGUIs have a very low memory profile. However some objects are created every frame for drawing purposes and these might go havoc with the garbage collector if you don’t watch them properly (especially on the Xbox).

Because no objects are used, we have to use a special trick to keep track of ‘events’. To accompany this, every GUI item that can have a certain state, or can return something (for example a button, for which we want to know if it was clicked) is given a unique id (usually an integer).  The IMGUI manager holds a couple of variables to determine what item was clicked, what item the mouse was over and what item is receiving keyboard input. So the state literally consists of 3 integers, instead of a great series of objects.

Let’s create a framework for our own IMGUI in XNA.

Setup

Fire up a new XNA Windows Game project and create a new class called IMGUI. Add the following using statements:

using Microsoft.Xna.Framework.Input;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;

After that add the following fields:

private SpriteBatch spriteBatch;
private MouseState mouse;
private int hotItem = -1;
private int activeItem = -1;

We need a SpriteBatch to draw our GUI. The hotItem will store the ID of the item where the mouse is over. The activeItem will store the item being clicked. We will also store the mouse state so we don’t have to get the mouse state in every GUI item.

Let’s add an update method to automatically update our mouse.

public void Update(GameTime gameTime)
{
    mouse = Mouse.GetState();
}

Nothing fancy here, but this will keep track of the mouse.

We want our IMGUI to be selfcontained but we still need to begin and end our spriteBatch. We also need to clear the hotItem (the item where the mouse is over) before beginning. And at the end we need to check if the mouse is still pressed, if not we need to store in activeItem that no item is being clicked. To accommodate this, we will make a Begin() and End() methods, not unlike those of the normal spriteBatch.

public void Begin()
{
        //Clear hot items before we begin.
        hotItem = -1;
        spriteBatch.Begin(SpriteBlendMode.AlphaBlend, SpriteSortMode.Immediate, SaveStateMode.SaveState);
}

public void End()
{
    spriteBatch.End();
    //If the user isn't clicking anything anymore, unset the active item.
    if (mouse.LeftButton == ButtonState.Released)
    {
        activeItem = -1;
    }
}

It might still seem a bit odd why we have to do this. But when we create our first GUI item, it will make a lot more sense. So let’s get right on it!

/// <summary>
/// Draws a standard button with specified texture at the location of the rectangle
/// and returns if the button was clicked.
/// </summary>
/// <param name="id">Unique ID</param>
/// <param name="rectangle">Rectangle specifying the position of the button</param>
/// <param name="texture">Texture for the button</param>
/// <returns>True if button was clicked, otherwise False</returns>
public bool DoButton(int id, Rectangle rectangle, Texture2D texture)
{
      //Determine if we're hot, and maybe even active
      if (MouseHit(rectangle))
      {
      	hotItem = id;
            if (activeItem == -1 && mouse.LeftButton == ButtonState.Pressed)
                    activeItem = id;
      }

      //Draw the button
      Color drawColor;
      if (hotItem == id)
      {
      	if (activeItem == id)
            {
            	drawColor = Color.White;
            }
            else
            {
                 drawColor = Color.LightGray;
            }
      }
      else
      {
            drawColor = Color.Gray;
      }
            spriteBatch.Draw(texture, rectangle, drawColor);

      //If we are hot and active but the mouse is no longer down, we where clicked
      //Line updated after comment by anonymous user, I feel so silly now!
      return mouse.LeftButton == ButtonState.Released && hotItem == id && activeItem == id
}
//Small helper function that checks if the mouse is contained in the rectangle
//Might even be unneeded but I like not having to manually write ‘new Point…’ every time.
private bool MouseHit(Rectangle rectangle)
{
      return rectangle.Contains(new Point(mouse.X, mouse.Y))
}

As you can see this is not much code for a button, because we got rid of all the state information and just bother ourselves with drawing a button, we don’t need to do much at all. Let’s look at what we have here.  First we determine if the mouse is over our button. If that is the case we are ‘hot’. We set the hotItem to our id, we also check if no item is active, and if the mouse’s left button is pressed. If so we set ourselves to be the activeItem as well.

We then start to draw our button (nothing fancy, we just change the tint we apply to our texture, and then draw the texture at the specified place).

At the end of our method we check if the mouse was released. If the mouse released and we where the hot and active item (the mouse is over our button and the mouse was pressed when over our button) then we return true to signal that we where clicked, else we return false. Because we store those nifty hot and active item integers this is all we need to determine if we were pressed.

Using the button and the IMGUI would look something like this:

        IMGUI imgui = new IMGUI(spriteBatch);
        private Texture2D buttonTexture;
        public void DrawImGui()
        {
            imgui.Update(gameTime); //normally you would do this in the Update method of your screen
                                              //but for code-compactness reasons in tutorials, I'll just add it here
            imgui.Begin();

            if (imgui.DoButton(1, new Rectangle(0, 0, 64, 64), buttonTexture))
            {
                Console.Out.WriteLine("The button with id: 1 was pressed");
            }

            //More GUI items

            imgui.End();
        }

Easy isnt it? Just make sure that you keep your ids unique, and that you give the same button the same id every frame. Of course after a button is no longer used, you can reuse the id (make sure though that you wait at least one frame, or to check that the hotItem and activeItem where not set to the id you are going to reuses, else some false clicks might occur, but generally this shouldn’t be a problem).

If there is more animo I’ll write a following part somewhere next week. Here we are going tot tackle scrollbars and textfields, which are slightly more interesting because they require their own output to be inputted next frame.

Oh btw, one of the biggest sources on immediate GUIs is the website mollyrocket.com IMGUI video I’ve directly linked the one hour long video. Skip the first few minutes about “why this is a video tutorial, because he doesn’t have much time etc..” and delve straight into the interesting part!

Update 30-03-2010 added a call to imgui.Update(..) which I forgot and only saw in the next installment in this series.

kick it on GameDevKicks.com

Tags: , , , , , ,
Posted in Blog, General Gamedesign, XNA | 12 Comments »

Code snippet: converting keyboard input to text in XNA

Posted by Roy Triesscheijn on 11th February 2010

In the standard XNA libraries, there is no method that deals with converting keyboard input to text. There are several methods on the Internet, but most of them are pretty incomplete or extremely slow. I found one solution, which was pretty complete, but it used a gigantic “if-then-else if…” to check every key to see if it was pressed. This makes for an extremely slow process (Still O(c) where c is constant), but having the computer look trough 60 if-statements every frame is a bit of a waste.

After I couldn’t find anything else to my liking I decided to create my own method. I used GetPressedKeys() to get the pressed keys. If keys are pressed I take the first one (if a users presses multiple keys at once, except modifier keys like shift, it’s rubbish anyway). And throw that one in a switch, which branches to the correct character immediately (in contrast to an if-then-else-if construction). I’ve tried modeled the code the same as TryParse, so a bool is returned to show that we either converted a character, or not. And via the out keyword, we pass the found character.

(Note: some of the ‘oem’-keys might not register when pressing shift, see here for a bit more in depth info about this known bug in XNA’s Keyboard api).

 /// <summary>
        /// Tries to convert keyboard input to characters and prevents repeatedly returning the
        /// same character if a key was pressed last frame, but not yet unpressed this frame.
        /// </summary>
        /// <param name="keyboard">The current KeyboardState</param>
        /// <param name="oldKeyboard">The KeyboardState of the previous frame</param>
        /// <param name="key">When this method returns, contains the correct character if conversion succeeded.
        /// Else contains the null, (000), character.</param>
        /// <returns>True if conversion was successful</returns>
        public static bool TryConvertKeyboardInput(KeyboardState keyboard, KeyboardState oldKeyboard, out char key)
        {
            Keys[] keys = keyboard.GetPressedKeys();
            bool shift = keyboard.IsKeyDown(Keys.LeftShift) || keyboard.IsKeyDown(Keys.RightShift);            

            if(keys.Length > 0 && !oldKeyboard.IsKeyDown(keys[0]))
            {
                switch (keys[0])
                {
                    //Alphabet keys
                    case Keys.A: if (shift) { key = 'A'; } else { key = 'a'; } return true;
                    case Keys.B: if (shift) { key = 'B'; } else { key = 'b'; } return true;
                    case Keys.C: if (shift) { key = 'C'; } else { key = 'c'; } return true;
                    case Keys.D: if (shift) { key = 'D'; } else { key = 'd'; } return true;
                    case Keys.E: if (shift) { key = 'E'; } else { key = 'e'; } return true;
                    case Keys.F: if (shift) { key = 'F'; } else { key = 'f'; } return true;
                    case Keys.G: if (shift) { key = 'G'; } else { key = 'g'; } return true;
                    case Keys.H: if (shift) { key = 'H'; } else { key = 'h'; } return true;
                    case Keys.I: if (shift) { key = 'I'; } else { key = 'i'; } return true;
                    case Keys.J: if (shift) { key = 'J'; } else { key = 'j'; } return true;
                    case Keys.K: if (shift) { key = 'K'; } else { key = 'k'; } return true;
                    case Keys.L: if (shift) { key = 'L'; } else { key = 'l'; } return true;
                    case Keys.M: if (shift) { key = 'M'; } else { key = 'm'; } return true;
                    case Keys.N: if (shift) { key = 'N'; } else { key = 'n'; } return true;
                    case Keys.O: if (shift) { key = 'O'; } else { key = 'o'; } return true;
                    case Keys.P: if (shift) { key = 'P'; } else { key = 'p'; } return true;
                    case Keys.Q: if (shift) { key = 'Q'; } else { key = 'q'; } return true;
                    case Keys.R: if (shift) { key = 'R'; } else { key = 'r'; } return true;
                    case Keys.S: if (shift) { key = 'S'; } else { key = 's'; } return true;
                    case Keys.T: if (shift) { key = 'T'; } else { key = 't'; } return true;
                    case Keys.U: if (shift) { key = 'U'; } else { key = 'u'; } return true;
                    case Keys.V: if (shift) { key = 'V'; } else { key = 'v'; } return true;
                    case Keys.W: if (shift) { key = 'W'; } else { key = 'w'; } return true;
                    case Keys.X: if (shift) { key = 'X'; } else { key = 'x'; } return true;
                    case Keys.Y: if (shift) { key = 'Y'; } else { key = 'y'; } return true;
                    case Keys.Z: if (shift) { key = 'Z'; } else { key = 'z'; } return true;

                    //Decimal keys
                    case Keys.D0: if (shift) { key = ')'; } else { key = '0'; } return true;
                    case Keys.D1: if (shift) { key = '!'; } else { key = '1'; } return true;
                    case Keys.D2: if (shift) { key = '@'; } else { key = '2'; } return true;
                    case Keys.D3: if (shift) { key = '#'; } else { key = '3'; } return true;
                    case Keys.D4: if (shift) { key = '$'; } else { key = '4'; } return true;
                    case Keys.D5: if (shift) { key = '%'; } else { key = '5'; } return true;
                    case Keys.D6: if (shift) { key = '^'; } else { key = '6'; } return true;
                    case Keys.D7: if (shift) { key = '&'; } else { key = '7'; } return true;
                    case Keys.D8: if (shift) { key = '*'; } else { key = '8'; } return true;
                    case Keys.D9: if (shift) { key = '('; } else { key = '9'; } return true;

                    //Decimal numpad keys
                    case Keys.NumPad0: key = '0'; return true;
                    case Keys.NumPad1: key = '1'; return true;
                    case Keys.NumPad2: key = '2'; return true;
                    case Keys.NumPad3: key = '3'; return true;
                    case Keys.NumPad4: key = '4'; return true;
                    case Keys.NumPad5: key = '5'; return true;
                    case Keys.NumPad6: key = '6'; return true;
                    case Keys.NumPad7: key = '7'; return true;
                    case Keys.NumPad8: key = '8'; return true;
                    case Keys.NumPad9: key = '9'; return true;

                    //Special keys
                    case Keys.OemTilde: if (shift) { key = '~'; } else { key = '`'; } return true;
                    case Keys.OemSemicolon: if (shift) { key = ':'; } else { key = ';'; } return true;
                    case Keys.OemQuotes: if (shift) { key = '"'; } else { key = '\''; } return true;
                    case Keys.OemQuestion: if (shift) { key = '?'; } else { key = '/'; } return true;
                    case Keys.OemPlus: if (shift) { key = '+'; } else { key = '='; } return true;
                    case Keys.OemPipe: if (shift) { key = '|'; } else { key = '\\'; } return true;
                    case Keys.OemPeriod: if (shift) { key = '>'; } else { key = '.'; } return true;
                    case Keys.OemOpenBrackets: if (shift) { key = '{'; } else { key = '['; } return true;
                    case Keys.OemCloseBrackets: if (shift) { key = '}'; } else { key = ']'; } return true;
                    case Keys.OemMinus: if (shift) { key = '_'; } else { key = '-'; } return true;
                    case Keys.OemComma: if (shift) { key = '<'; } else { key = ','; } return true;
                    case Keys.Space: key = ' '; return true;
                }
            }

            key = (char)0;
            return false;
        }

I hope you enjoy this code, feel free to use it, but if you do please post a thank you message here or something like that. As usual tips, tricks, comments and improvements are welcome!

Tags: , , , , , ,
Posted in Blog, XNA | 5 Comments »

Mouse position in 3D, snippet

Posted by Roy Triesscheijn on 13th January 2010

And another snippet for today. I wanted to test some more path finding code so I wanted to move a collidable object with the mouse. To do so you have to ‘unproject’ your mouse coordinates (x and y) to a position in 3D space (x,y,z). I first tried to use the unproject method directly. But after reading the msdn article I figured out that the z-values can be either 0 (near clip plane) or something else (far clip plane). So this didn’t give me good results if I just plugged in the z level I wanted.

After reading on about rays and intersect methods, user ConkerJo on #XNA pointed out that intersect returns a point of intersection instead of true or false. So with that knowledge, and a little help from him and msdn, I quickly produced the following code.

This code will convert your mouse position to a point laying on the ground plane.

Remember that the definition of your ground plane is a normal. So if you want the x-z space to be the floor (eg. y is up), assign it like this:

private Plane GroundPlane = new Plane(0, 1, 0, 0);  //creates a plane on the x-z axises.

And if you use another common approach, where z is up and the ground is on x-y use this:

private Plane GroundPlane = new Plane(0, 0, 1, 0); //creates a plane on the x-y axises.

And now here’s the actual snippet:

/// <summary>
        /// Calculates where the mouse would be if it would float around at the level of the ground plane.
        /// Based on http://msdn.microsoft.com/en-us/library/bb203905.aspx and user conkerjo who
        /// pointed out that Ray.Intereset returns a vector3 and not a boolean (true/false) *DOH*.
        /// </summary>
        /// <returns></returns>
        private Vector3 CalculateMouse3DPosition()
        {
            int mouseX = Mouse.GetState().X;
            int mouseY = Mouse.GetState().Y;

            Vector3 nearsource = new Vector3((float)mouseX, (float)mouseY, 0f);
            Vector3 farsource = new Vector3((float)mouseX, (float)mouseY, 1f);

            Matrix world = Matrix.CreateTranslation(0, 0, 0);

            Vector3 nearPoint = device.Viewport.Unproject(nearsource,
                camera.ProjectionMatrix, camera.ViewMatrix , Matrix.Identity);

            Vector3 farPoint = device.Viewport.Unproject(farsource,
                camera.ProjectionMatrix, camera.ViewMatrix, Matrix.Identity);

            Vector3 direction = farPoint - nearPoint;
            direction.Normalize();
            Ray pickRay = new Ray(nearPoint, direction);
            float? position = pickRay.Intersects(GroundPlane);

            if (position.HasValue)
            {
                return pickRay.Position + pickRay.Direction * position.Value;
            }
            else
            {
                return target.Position;
            }
        }

Tags: , , , , , , , ,
Posted in Blog, General Gamedesign, XNA | 1 Comment »

SpaceAce: planetary gravity and solar system simmulation

Posted by Roy Triesscheijn on 6th December 2009

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 :) .

Tags: , , , ,
Posted in Blog, General Gamedesign, XNA | No Comments »

Quick Tips: C# inline event handlers and Reordering method / constructor parameters

Posted by Roy Triesscheijn on 15th October 2009

I always hate having to write an extra method to deal with event handlers and today it irritated me more than ever. The extra event handlers all consisted of just one line of code, it’s also harder to read what is going on if you have to scroll down all the time to check what that event handler is doing.

So today I finally typed in “C# inline event handlers” in Google. And the first website I clicked already gave me what I was looking for. Apparently this was added in C# 2.0 and it basically boils down to this:

this.button1.Click +=
delegate(object sender, EventArgs e)
{    MessageBox.Show(&amp;quot;Test&amp;quot;);   };

Quick easy and very handy!
(note: crashovrd noted correctly that these are not ‘inline event handlers’ but are called anonymous methods, thanks crashovrd!)

Another thing that I found out recently is that you can easily reorder method and constructor parameters using Visual Studio 2008′s built in refactoring tools. All you have to do is right click the method/constructor and select Reorder parameters. Very easy and very handy. Just the kind of trick you have to know that is there to be able to use it.

Reorder context

You’ll get a nice form which allows you to reorder your parameters, Visual Studio will automatically update all callers.

Of course these are all tips that are simple and are well documented on the internet, if you look for them,  but maybe I’ll make a few of you guys happy with these.

Tags: , , , , , , , ,
Posted in Blog, General Coding, Tips | No Comments »

Computermanagement software

Posted by Roy Triesscheijn on 12th October 2009

Lately I’ve been bussy working at the Rijksuniversiteit Groningen as ‘one day a week’  systemadministrator/programmer.

One of the first jobs that was assigned to me was reorganizing a set of 14 computers. These computers run ‘exhibits’ so people interested in going to the university can see what we do. The old setup was kinda odd, all computers where attached to 4 remote controlled powerinterupters and each morning someone at the reception, or me turned on then powerinterupters and each computer turned on because “wake on power” was turned on in their bioses.

Each afternoon someone would again turn off the powerinterupters and each computer would just stop because the power ran out.

If there was something wrong with a computer, you’d just pick up your keys, keyboard and mouse and sat in front of the damn thing until it worked again.

I quickly started working on laying networkcables between all computers, setting up remote desktop configurations, configuring a sever to become a proxy/dhcp server/webserver and setting up all computers to “wake on lan.” After that the administration began, find each computers username, password and mac adress, and setting a helpful computername.

After these changes I could remote desktop to the server, and from there remote desktop to each connected computer, configure it, install new software, reboot it, etc… The proxy server blocked all websites except for the websites of the university so the computers could no longer be used for ‘bad browsing’.

There was still one thing that bothered me though, and that was not being able to see which computers where still working without logging in to each and every one of them. I also wasnt happy with still having to login in to the server to send the wake on lan packets in the morning, and shutting every computer down by login in again in the afternoon.

To overcome this problem I wrote two programs, creatively called ComputerManager and ComputerMonitor. ComputerMonitor is a small application that runs in the background and sends a “I’m alive” packet to ComputerMonitor every 2minutes, it also has a small listenserver running to listen to shutdown and reboot commands. I installed this on all 14 pc’s.

The ComputerManager program listens for those “I’m alive ” packets and keeps track of which computers have not send an “I’m alive” packet for 5 minutes and adds these to a “red list”. The computers that keep responding keep being updated in the “green list” with their last update time, computername and ip-adress.

The program also allows for saving mac adresses of computers. These mac adresses are used to wake-up all computers on 8:55 am. The program also sends a shutdown message to every computer on 6:05pm. This way my job got allot easier. Ofcourse it was allot of work at first but it was worth my effort.

As a final touch I created one more little program that can be run by an exec command in a php script. This allowed me to make a secure webpage where people other than me can only press two buttons: “Turn all on” and “Turn all off”.

I’m releasing the sourcecode of ComputerManager and Monitor to everyone. Allot is still hardcoded, and there are probably some bad design descissons here and there but it might be useful to someone. The asynchronous listen server is solid and a good learning example. There’s also allot of code dealing with win32 calls like shutdown and reboot.

The most recent version can be downloaded here

I won’t be actively updating or supporting this program since it was just written for my personal use, but if you got any questions or comments, feel free to ask.

Tags: , , , , , , , , , , , , ,
Posted in Blog, General Coding | 2 Comments »

New Version A* pathfinding in 3D

Posted by Roy Triesscheijn on 7th July 2009

Intro and thanks.

Ok so let’s quickly forget the debacle around the first release of this code sample, I wan’t to delete the entire post about that one but I would’nt  have know that I made an error (until much later on) if it wasn’t for some people spotting it instantly! So I would first like to thank some of my visitors who spotted the errors:

-Oscar for spotting possible performance problems.

-Ryan for suggesting possible HashSet’s (altough I didn’t use them in the end, see below why).

I would also like to thank posters from www.tweakers.net  who helped me get this version of A* so fast, especially (on post order):

-Phyxion & Mammon for their one line version of Equals()

-Nick The Heazk for spotting that I totally forgot the Heuristic part for scoring (doh, I swear I had it in my draft)

-pedorus &  jip_86 for suggesting to use a Binary(Min)Heap

-Marcj & NotPingu for pointing out a 3D version of Pythagoras

-Soultaker for letting me think more about efficiency of containers (O(?) of add, extract and contains))

-.oisyn & pedorus for suggesting to combine a binary heap and a HashSet (altough I didn’t use it in the end, see why below)

-PrisonerOfPain for suggesting to use binary flags instead of extra HashSet’s (that’s why I didn’t use them).

Why is this version faster?

A lot was changed from the previous version, let’s start with the openList, checking if an item is in the openList costs O(n) iterations and checking which item has the lowest score costs O(n) and removing an item costs O(log(n)). So I’ve replaced the openList with a BinaryHeap for checking the lowest score and removing/adding. These operations cost O(1), O(log(n)). That’s allot faster already.

As for checking if an item is in an openList (or closedList) all I did was add a boolean flag to the BreadCrumb class (onOpenList and onClosedList).  Checking this flagg is O(1) so that really makes checks allot faster.

Also all I needed the closedList for was checking if items where already in there, so with the boolean flag I could completely remove the closedList.

Another new feature is that we immediatly return from the FindPath function when we find the finish, this also saves some operations.

I also made sure that I don’t  create to much new objects but re-use them after they where first indexed (this was  also the cause for a small ‘score’ bug) and I’ve re-aranged some ifs.

For the algorithm itself I now use DistanceSquared for the (forgotten) Heuristic part of the scoring which is allot better than ManHattan distance which is slightly biased. I’ve also changed the cost (G) to move from the current node to the next node to incorporate these squared cost  (so instead of 1,  1.4 and 1.7 I can now use 1,2,3 for these scores. I also don’t have to multiply all these numbers by 10 since 1, 2 and 3 are integers.

A final additon is the class Point3D which allows us to use only Integers instead of floats (which are slower for a cpu).

All in all this made this code about 200x faster (yes really!). But that is not completely fair since the first code was broken. If you count from after I fixed the heuristic part of the code the code is ‘only’ about 30x faster.

Benchmark results.

And before we get to the exciting part (the code!).  Let’s first show some benchmarks.

Situation:

World: 10x10x10

Start: 0,0,0

End: 9,5,8

Nodes blocked: 300

Time:

Total (100 iterations) : 134ms

Average:  1.34ms

Lowest:   < 1ms

Highest:  17ms

Note: as you can see because we did this test 100 times there is quite allot off difference between the lowest and highest time we needed to calculate this route, that’s because sometimes the cpu stops executing this program, and starts handleing an irq or doing something else, that’s why it’s important to always take a big number of benches to be representative. We can see from the average that this code is extremely fast.

Efficiency:

A* is an extremely efficient algorithm, consider we would’ve liked to brute-force this problem instead of using A*. That would’ve cost us 10^10^10 = 1,e+100 iterations. However with an (this) A* implementation we only needed 119 iterations (in which we checked 3094 nodes).

So, on to the code!

The code.

Well since I’ve divided every thing in much neater classes it’s a bit of a problem adding showing off all these as code-listings as I usually do. So I will only show the most important method here, the rest of the classes, and an example  you can download at the bottom of this article or by clicking here

        /// <summary>
        /// Method that switfly finds the best path from start to end. Doesn't reverse outcome
        /// </summary>
        /// <returns>The end breadcrump where each .next is a step back)</returns>
        private static BreadCrumb FindPathReversed(World world, Point3D start, Point3D end)
        {
            MinHeap<breadCrumb> openList = new MinHeap<breadCrumb>(256);
            BreadCrumb[, ,] brWorld = new BreadCrumb[world.Right, world.Top, world.Back];
            BreadCrumb node;
            Point3D tmp;
            int cost;
            int diff;

            BreadCrumb current = new BreadCrumb(start);
            current.cost = 0;

            BreadCrumb finish = new BreadCrumb(end);
            brWorld[current.position.X, current.position.Y, current.position.Z] = current;
            openList.Add(current);

            while (openList.Count > 0)
            {
                //Find best item and switch it to the 'closedList'
                current = openList.ExtractFirst();
                current.onClosedList = true;

                //Find neighbours
                for (int i = 0; i < surrounding.Length; i++)
                {
                    tmp = current.position + surrounding[i];
                    if (world.PositionIsFree(tmp))
                    {
                        //Check if we've already examined a neighbour, if not create a new node for it.
                        if (brWorld[tmp.X, tmp.Y, tmp.Z] == null)
                        {
                            node = new BreadCrumb(tmp);
                            brWorld[tmp.X, tmp.Y, tmp.Z] = node;
                        }
                        else
                        {
                            node = brWorld[tmp.X, tmp.Y, tmp.Z];
                        }

                        //If the node is not on the 'closedList' check it's new score, keep the best
                        if (!node.onClosedList)
                        {
                            diff = 0;
                            if (current.position.X != node.position.X)
                            {
                                diff += 1;
                            }
                            if (current.position.Y != node.position.Y)
                            {
                                diff += 1;
                            }
                            if (current.position.Z != node.position.Z)
                            {
                                diff += 1;
                            }
                            cost = current.cost + diff + node.position.GetDistanceSquared(end);

                            if (cost < node.cost)
                            {
                                node.cost = cost;
                                node.next = current;
                            }

                            //If the node wasn't on the openList yet, add it
                            if (!node.onOpenList)
                            {
                                //Check to see if we're done
                                if (node.Equals(finish))
                                {
                                    node.next = current;
                                    return node;
                                }
                                node.onOpenList = true;
                                openList.Add(node);
                            }
                        }
                    }
                }
            }
            return null; //no path found
        }

(note the class also has a normal FindPath() method that switches start and end for you).

Download.

In case you missed the download link in the middle of the text, download the entire example:  here

kick it on GameDevKicks.com

Tags: , , , , , , , , , ,
Posted in General Gamedesign, XNA | 26 Comments »

A* 3D update

Posted by Roy Triesscheijn on 7th July 2009

Just a small update so to keep you all who’ve been anxiously waiting for the updated version of A* happy :) .

I’ve been working on implementing A* more efficiently using a MinHeap for storage instead of Lists<> add this time I made sure that I didn’t forget the H (heuristic) part of the scoring (silly me). To give you a bit of an idea how much better the algorithm is now.

Situation 10x10x10 grid, 1/3 of the nodes blocked, find a path from 0,0,0 to 9,5,8

Old code: +-600ms (If I’d just have profiled it before I would’ve known something was wrong)

New code: 8.86ms 6.82ms 5.27ms averaged over 100 runs.

So yeah that is allot better, however when decreasing the number of blocked nodes the time goes up slightly (average 19ms for 0 nodes blocked). And I really want to get that lower, so I’ve asked some people at http://gathering.tweakers.net if they saw more room for optimalisation and there are still a few tips that I haven’t explored there. So I’ll be releasing the new (correct/fast) source code soon, but not untill I’ve made sure that I’ve cramped out all the speed that I can.

There is atleast one method that will speed everything up significantly. A player can now make a step over 3 axis at the same time (x,y,z) ofcourse that is more expensive but sometimes gives a better path, however this means that each node has to consider 26 neighbours instead of just 18. I’m playing with the idea to restrict motion a bit for a faster algorithm.

Maybe I’ll build in some different motion types for speed, best path, or some average.

Tags: , , ,
Posted in General Coding, General Gamedesign, XNA | No Comments »