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.

4 comments:

navself said...

Hi,

Thanks for the code snippet.
Well i was working on the same line to layout elements in a grid and i came out with few more mathematical expressions
If you have to find certain elements in the grid. for eg.

in a 3x3 grid(the elements being arranged as shown)
1st row 0, 1, 2
2nd row 3, 4, 5
3rd row 6, 7, 8

If you want to select say more than one element in the grid, then i would do something like this

first case
(2, 4, 6)//diagnol-right to left top to bottom
for (m = 0; m < 3; m++) {
System.out.println(2*(m + 1)));
}

Second case
(0, 4, 8)//diagnol-left to right top to bottom
for (m = 0; m < 3; m++) {
System.out.println((m * 4));
}

third case
(3, 4, 5)//horizontal
for (m = 0; m < 3; m++) {
System.out.println((m + 3));
}

fourth case
(1, 4, 7)//vertical
for (m = 0; m < 3; m++) {
System.out.println((m + 1) + (m * 2));
}

keep up the good work.

Thanks,
navself

Anonymous said...

Very nice blog. Keep up the good work!

MorbidMorvick said...

Thanks for the replies, their much appreciated.

@navself Interesting insight. It is nice to see other people have experimented with this method as well.

I have definitely found many different usages for representing the grid in this way as I will show with layering and smooth scrolling.

Keep reading and I will be sure to keep writing.

MorbidMorvick

DavidX said...

instead of

x = i - y * cols;

use

x = i % cols;

Post a Comment