Tuesday, November 23, 2010

Game Engine Design: Game Contexts

I have been working on game engine design for the past... um... hmm I can't remember when I started... well lets just say it's been years. Typically I have entity objects, and a Game State Machine implementation. The entity objects became the base class for all other game objects. Entity objects would have been able to be updated and rendered. This allowed me to do everything I needed specific to each entity.

For rendering I would pass only the graphics object to each entities render method. Something that looks like public void render(Graphics2D g). For updating I would pass the time passed since the last call which looked something like public void update(double dt). Each entity would have their render/update methods called at least one per frame.

How it used to be!
As I was working on a few games using my work-in-progress engine code, I came across situations where it would be easier for the entities to already have all the information they need and have spawn and kill functions. A game entity needs to know information about the world, other objects, screen sizes, etc. Also I needed the ability for an entity to change states of the game system. But that is only because the entities were checking input and doing game logic.

The system worked fine the way it was, it was just very painful modifying constructors and adding parameters to methods, I had even modified the render methods sometimes to be passed the time and dimensions of the screen. I constructed a Spawner interface which essentially was implemented by my world container class and allowed objects to have a spawner and to spawn other objects. The spawner was really really nice because it allowed any entity to create new ones on the fly the creating entity could hold on to them and then kill them if need be. The problem with this approach is that each object contains a reference to a spawner, which had to be set and could potentially not have been set causing errors or lots of additional null checks.

Enter Game Contexts
I am a big fan of Design Patterns and after experimenting with different design patterns in games such as the Composite, Observer, Visitor and Mediator. I found that what my entity objects needed was a mediator between them and the rest of the game system. So I figured I could put all the methods and information needed by the game objects into an interface to be implemented by the main game class. It turned out to look something like this
public interface GameContext {

    // the width of the screen
    public int getWidth();

    // the height of the screen
    public int getHeight();

    // the input manager
    public InputManager getInput();

    // the time passed in seconds between frames
    public double getTimePassed();

    // spawn a new entity
    public void spawn(Entity e);

    // kill the entity
    public void kill(Entity e);

    // switch game states
    public void changeState(State next);

    // return the graphics object used for rendering
    public Graphics2D getGraphics();

    // set fullscreen mode
    public void setFullscreen(boolean fullscreen);

    // return whether the game is fullscreen or not
    public boolean isFullscreen();

}
This interface gave each game object the methods it needed to do a lot more than they could before. The render/update methods now changed to
public void render(GameContext gc);

public void update(GameContext gc);
It really does make a lot of difference when creating new entities and you can add lots more to the GameContext. For instance you could have a method for collision detection or initiating certain effects etc... It is also just as efficient as the previous method since only one parameter is being passed to the game objects.

I hope to show a full runnable snippet using this idea sometime in the future. This should be enough to get you started if you already have something in place. If you have an alternative method to share it would be much appreciated, or if you've already used something like this it would be nice to know as well.

That's all for now, getting ready for Turkey day.

Tuesday, November 16, 2010

Rendering Multi-layered Map

Similar to the previous snippet only now the
green squares and diamonds represent some foliage.
Note: That the map generation algorithm still needs
a bit of work to make decent looking terrain.
When using a map in a game you always are going to want to draw items equipment and perhaps buildings and structures on top of terrain. This is known as layering, you may be familiar with it if you have done used photoshop or perhaps in making your own games. It is even used in GUI programming although it is usually referred to as z-ordering. You want to use it anytime you have a rendering order in which something you are drawing will appear on top of a part of something else but doesn't fully cover it. In 3D graphics many times you don't have to worry about the order in which you draw objects since the graphics card will automatically determine per pixel drawn if it is covered by something else, that entails using a depth buffer.

If we wanted to we could implement our own depth buffering system on the CPU side, however it would take a lot of processing power and be inefficient. So we will draw in top left to bottom right order drawing the bottom layer and then each layer above that separately.

Ordering

So how do we determine this order and make it flexible for pretty much any game we want to create. Ones first instinct is usually to make a list or map of layers each layer containing all the objects to be rendered on that layer, and traverse these nested lists in order. This results in some nested for loops which I try to avoid at all costs. So my solution is to order each rendered element when you insert it into the collection of all elements to draw. This makes the rendering loop a single continuous loop we can't get much more efficient than that. The only other optimization we can do is to make sure we only draw what is visible on the screen, and nothing we draw is unnecessary, sometimes the cost of removing those unnecessary loop cycles is to expensive so it's best to just try and determine them beforehand or not at all.


Code Snippet

This snippet is based off of the previous snippet Rendering Basic Tiled Maps. Not much has changed between the two except the tile class, map generation function, and tileset generation function have added support for layers demonstrated by some placeholder images. The map generation algorithm I'm afraid is a little bit confusing.

How Layers Work

This implementation sets each tile with a layer integer that is used in the TreeSet red-black tree sorting. Which makes it efficient because you are going to order the tiles and layers when creating the map and you don't need to touch it after that. Another way of doing this would be to use an ArrayList or any other sortable collection in the Java Collections package and sort when you need to, especially if you need constant time access into the collection. Alternatively you can create another collection of the tiles or containers of subsets of the map in order to do whatever you need. I choose to use TreeSet as it is simple enough for this example, and I won't be needing to do anything but draw the list of objects on the map.

The rendering loop remains the same, just as simple as we can possibly make it.
protected void render(Graphics2D g) {
  // keeping it simple, and fast
  for (Tile tile : world) {
   tile.render(g);
  }
 }
Any simpler and it'd just be a completed list drawing each tile individually in the order we wanted.

The real meat of this snippet is in the compareTo function of the Tile. Because the TreeSet either requires a comparator to order the elements or requires the element type to implement the Comparable interface we need to provide one of the two. For simplicity I choose the later of the two, even though making a Comparator would be advantageous because then it would be easier to add different types of objects to our map other than just Tile objects.
/* (non-Javadoc)
   * @see java.lang.Comparable#compareTo(java.lang.Object)
   */
  @Override
  public int compareTo(Tile o) {
   if (layer > o.layer) {
    // this object should be displayed after o because it is
    // on a higher layer than o
    return 1;
   } else if (layer < o.layer) {
    // o should be displayed before this object because it is
    // on a lower layer than o
    return -1;
   } else {
    // if there are on the same layer sort them top,left to bottom
    // right order
    if (y < o.y) {
     return -1;
    } else if (y > o.y) {
     return 1;
    } else if (x < o.x) {
     return -1;
    } else if (x > o.x) {
     return 1;
    } else {
     // their in the same position same layer, this is probably
     // not intentional, but could happen
     return 0;
    }
   }
  }
 }
A bit messy but it gets the job done efficiently. So we compare the layers, if the two objects are not on the same layer there is no need to go any further we return 1 meaning that the tile compareTo was called on should come after the tile o because its on a higher layer, and -1 if it should come before the tile o.

If they are on the same layer we are going to order the objects from top-left to bottom-right order. So we compare the coordinates of each tile. This is actually something that can be handled by the indexing method I explained in the previous post.

So here is the snippet for you to play around with comments are welcome as always.



Tuesday, November 9, 2010

Rendering Basic Tiled Maps

Auto generated map and tiles it's a
bit rough though.
O.k! So this snippet is a little lengthy, I could not find an acceptable way of showing the map without either using a random map generator or including code for loading a map from a file. I choose the former but the algorithm didn't quite turn out the way I had hoped. It's a bit messy as I tried to avoid recursion and also the generated maps don't really look spectacular. Although it should get the point across and provide a basis for much more work to be done with it.

Tiles
The tiles are a bit complex and I hope to show much easier and cleaner ways of both representing and rendering. While there is nothing wrong with a loop through all tiles drawing each in it's own known position. It doesn't provide the flexibility we need to add features such as layers, smooth scrolling, at least not in an efficient way. We later we will want to limit our drawing to only show the part of the map that is actually visible, and maps can get large.

Inevitably these limitations will force us to make trade-offs for game performance. If we draw more we will have less time to devout to updating enemies and objects that aren't even on screen yet. And the levels can get larger and larger. Which is why there are concepts like check points and areas where the level is split up. It's not so much keeping that in memory as it is updating those objects every frame. Unfortunately for most game concepts you can't remove unneeded updates to those objects easily unless your game is designed for it. This is most true in strategy games and simulations where the drawing only accounts for a small fraction of the total number of updated objects. But more on these later.

Oddities in Snippet
A couple things you might find odd about the way I coded the rendering algorithm or my coding style in general. First of all I dislike large procedures so I will try my best to keep every method simple, though there have been a few lengthy ones but they have almost always been cohesive. I avoid nested loops like the plague, so for the creation of the map I use a little mathematical trick I conjured up myself.

I take the x, and y coordinates and transform them into an index into a grid. The index counts left to right from the top, left tile to the bottom right. All you need to know is the width of the grid and you can calculate what the index is for a given x and y value. You can do the same with the index but it's definitely odd to see in the code.

For instance in a 3x3 grid the index of the last element or position (2, 2) in the grid is given by
i = y * cols + x

i = 2 * 3 + 2

i = 8 (qed)

Meaning that you count up starting from 0, 1, 2, ..., 7, 8, and for a 3x3 grid you get 9 indexes as you should.

So now to reverse this craziness. This is where we have the i value say for a 3x3 grid the i value is 4. Where on the grid x,y might i fall if we were to count starting with 0 from the first box on the grid and go left to right till we got to 4. We need to calculate y first as it will be used to calculate x.

y = i / cols

y = 4 / 3

The trick here is that the result is truncated. So

y = 1

More mathematically correct is the following formula for y.

y = floor(4/3)

In code if we use integers the result of the division will automatically be truncated. Now to the confusing part finding x.

x = i - y * cols;

x = 4 - 1 * 3

x = 1

So in a 3x3 grid where x and y start go from 0 to 2 each, index 4 is the point 1,1 or the second row second column.

+-x 0   1   2
y .---.---.---.
0 | 0 | 1 | 2 |
  |---|---|---|
1 | 3 | 4 | 5 |
  |---|---|---|
2 | 6 | 7 | 8 |
  '---^---^---'

As you can see the math does work out, provided we use the floor function in our calculations, in code we just have to use integers. This can be useful for representing a grid using a Map of integers to tiles where the integer key is the index in the grid.

There are quite a few different ways to use this for our drawing purposes as well as converting between coordinate systems, i.e. mouse position to grid position.

O.K! So now that I've managed to completely confuse you here is the code.