Posts
Not great looking, but you get the idea.
In the process of looking for ways to form good representations, I've come to see a lot of different ways that people suggest to express these "maps" of the ground. Usually I'm put-off by the suggestion, because it's one or more of the following:
- Difficult to understand.
- Tricky for no good reason.
- Too wasteful for my purposes.
- Lacking a specification for iteration that is back-to-front rendering ordered.
As such, I've come up with a sort of solution of my own, to the above, and I thought that I might share it with the world. In my travels, I haven't seen anything similar, so perhaps it will be of some use to someone, despite it's as-forseen-by-me limited applications.
The Way We Might Express a Map
Some people have suggested (long long ago) that a good way to express a map of ground in a 2D tile-based game would be to simply stagger a 2D array, or any expression of a 2D table of accessible data, such that odd rows are offset by the radius of the tile's width. Indeed, most of the material I've seen that covers the subject of tile-based games' maps are variations to this theme.
There is something that I feel will be detrimental to memory and execution speed with this method, in the context of the maps that I will be creating.
- There will be too many empty places.
For instance, take the following, this is a stylized and simplified example of what I hope to end up with. My maps will all be variations of a rhombus shape, most likely of an equal ratio on all the sides (Read, a diamond shape, most likely a square shape tilted over.) For lack of space, I've only begun to show one corner here, the uppermost one, but you will be able to imagine the shape in it's entirety easily enough.
Now, though, what would happen if we were to try to express this using the standard "stagger every other row" solution? We'd end up wasting lots of space! Consider the transluscent tiles below to be the places in whichever data structure that we choose to express this map, and how useless they would be.
If we were to finish this to completion, we would see that half of the data structure would be used to contain purely empty space! This is not good.
Another Thing We Don't Want
Other possible ways to express this map in data structures lack a well defined way to properly iterate through, in order to obtain back-to-front rendering. Let's look at why we want this real quickly. Consider the example below, where a simple order for iteration has been established, and the way this might affect our rendering.
You might be able to tell from this that all we've done here is set the leftmost corner of our map as the top left of a 2D tabular data structure expressing our map. So, simply, we're going from left to right, top to bottom. In actuality, this was what I did for my first attempt, and how I discovered the problem that lead to the solution of this post! What sort of result does this beget, though?
Let's see.
Hey! So far so good, we've got the leftmost tile up there, and soon the rest will follow.
Hey, what the heck? What happened? Well, since we wrote the next tile after the first, we've just overwritten part of the first tile, and since the first tile is supposed to be in front, and not behind, that spells trouble. If we continue on, let's see what happens.
Well, at least some of the mess-up is overwritten by the next row's first tile. But then, it's still clearly visible that something is not right.
Unfortunately, all illusions of realism, however frail, are lost when you don't render from back to front, as you see here. What's the moral of the story? Badly iterated data structures representing these maps are a bad thing!
What We Do Want
So, knowing that, what do we really want? Well, why not just change the order of the numbers on the previous example?
If you were to run through this, and imagine it rendering, you can see that anything of the previous tiles will be overwritten, and that we end up with this nice realistic looking set of tiles.
A simple and wasteless way to do this is exactly what I'm attempting to achieve.
In order to do this, I took a step back, and looked at not only what I wanted in the previous picture above, but at how I was currently ordering my ground tiles. It looked abstractly like this.
Each coordinate pair in that table is representative of a single tile. As it was, 0,0 was the leftmost tile, and as you saw above, this will not work the way that we want it to. So what are we to do? Well, all you have to do is tilt your head! Observe.
Doesn't that look an awful lot like the shape we're seeing in the previous examples? That's because it is! By simply changing our viewpoint on the data, we've just solved the problem. By looking at it this way, we're able to trim excess waste, and, provided we can iterate through it properly, render from back-to-front.
"Great!" you say, "But, how do we iterate through it properly?"
You're in luck, because that was the next logical progression in the series of steps that led to (I think) a great solution of mine.
Firstly, let's expand on our simple grid, to make a more representative demonstration. A 5 by 5 table should suffice.
First and foremost, we need to set our beginning point. 0,0 is the only logical place, in this context, due to not only it's easily accessible spot, but also by our back-to-front iteration requirements. Remember that when displaying the tiles visually, the result is tilted from our usual view of the tabular data.
Now we need to define rules for moving to the next diagonal row. Check out the numbers in Y's 0 row, and X's N column (in this case, 5), notice any similarities that we can depend on?
Indeed, The Y values are all 0, and the X values are all N, where N is the width. Knowing this, we can craft a pretty good conditional statement to figure out whether we need to go to the next diagonal row or not.
(Y == 0 or X == Width)
So, what do we do when we see that we need to go to the next diagonal row?
If you look at the correlation between the X value of any diagonal row's last position, and the Y value of the next diagonal row's start position, you will usually see that it is greater by 1, unless the X value happens to be the Height, in which case it will be that instead. Also note that the X value will always be 0. Using this, we can just set the coordinate pair as follows. (Current X + 1) Modulo Height, 0
However, next we face a new dilemma. How do we move to the next item on a diagonal row if it's not the end, or final item in the table alltogether? Can you spot any consistant similarities between the values from any given position to the next?
Indeed, it seems that the Y value is always one less than the previous, and the X value is always one more than the previous. Knowing that, we can decrement Y, increment X, and then we're at the next given position along the same diagonal row.
And we're done...
but not quite! You see, we need a final case, one which determines when we're done looking through this thing altogether. You may be able to see right away what this will be, or at least where it is, but for the sake of completeness, consider the following.
Yup, that's all there is to it, we're always going to find that the last position has the values of X = Width, and Y = Height. So all we have to do is test for that, and when we find it, we're completely done.
A little tip for those who did indeed bother to look at the last example (You avid readers are appreciated, after all!) Note that since this will only ever occur at the end of a diagonal row, that there's an added benefit of only ever having to test for this when you note that we're at the end of a diagonal row. This makes me a happy panda.
Some Concerns
Of course, every solution is not without it's problems and constraints. One such constraint that I've forseen (as alluded to at the beginning of this post) is that this solution will absolutely, I guarantee it, only work for maps that take a diamond shape. It might even only work for those which have equal ratios on all sides. (More on this in a later post.)
This means that if you're considering having dynamically shaped maps, either now or the possibility of such in the future (Like one that may be shaped like an L, or such like that.) then this will not work for you in it's current form.
Another concern is that this may not be the absolute speediest way to do things, in this particular area, where I'm sure that my knowledge is by no means complete.
Given all of that, however, I think the strength of this lies in:
- It's simplicity of expression, compared to other solutions.
- It's accurate space usage.
- It's natural iteration resulting in back-to-front rendering order.
And Finally
I'd like to thank the following people:
- the #gamedev community on irc.afternet.org for their ongoing support, and, perhaps disproportionately greater, their ongoing distraction of my attention from things like this blog, and other projects mentioned therein.
- Gamedev.net (the website with which #gamedev is associated) with it's copious articles, forum posts, and journals related to not only this subject, but game development in general.
- The authors of Dia, because it's a kickass data/organization/etc. visualization expression tool.
- The authors of Adobe Photoshop, because, while not as kickass at what Dia does, it's still a kickass painting program.
Thanks for reading, and as always, discussion is welcome. :-)
