First off I think this topic deserves a bit of a briefing. The physical world is continuous. This is hard to represent in a computer because a computer is a discrete machine. So what we have to do to model the world is break it up into N by N chunks and call each chunk a tile. This is only one solution to the problem, there are many more sophisticated solutions. If you ever look at old Nintendo games you can actually point out where one tile begins and another ends.

If you are simply using 2 dimensions, this tiling is fairly straightfoward and easy to accomplish. However, I decided to create a video game from a pseudo-isometric perspective. Isometric is simply 2D only rotated a bit to create a 3D look that ignores perspective. So now I have the added dimension of height. What this essentially means is that each Tile can have one or more “levels” associated with it. Take a 10 story building for example. A Length by Width chunk with Length = Width = 2 feet could potentially have 10 levels. So if my character wants to walk on that Tile, I first need to see if there is a Level he can walk on, ie he can’t walk from a height of 2 feet to a height of 15 feet( that would be a wall ). I originally said my game would have up to height 5. This originally meant that I could have 9 possible Tile-heights( or Y Intercepts ) going from 1 to 1.5( stairs ) to 2 to 2.5 etc.

Now the big problem. This meant that if the user hit up on the keyboard, I would have to get the position after the move, and check to see if where he was standing was a legal spot to stand. A legal spot can be defined as: a Tile that is walkable( grass or dirt is able to be walked on, but water or a Tile with a tree would not be ) and a Tile with a level close enough to allow realistic height-movement( I can walk up a slope or stairs from height 1 foot to height 10 feet, but I can’t just teleport from 1 foot to 10 feet in one step ).

My original solution to this problem was absolutely terrible and still took me several sleepness nights in a row to come up with. It went like this:

You have the tile you are standing on. That tile has a level property associated with it. For every level property there is a list of allowed levels you can go to. So a level 2 tile can go to a [ level 1.5 tile or a level 2.5 tile ]. This got a bit more complicated when I added sloping in all 4 directions. That is if you are moving left on this tile and it is sloping up leftwards, your height value will increase but if you are moving right it will decrease. This also changed a few things when it came to the possible tiles you could move to as well. So when you tried to move, it got the tile you were on and compared it to the tile you will be on. If the tile you will be on has a property that is in the list of allowed properties, you can move, else you can’t. This worked all fine and dandy but it had several cases depending on which direction you were moving in and each case had almost identical code save a few variable values. It was horrid. Add to this this problem that since you now have a length, height, and width and your movement speed most likely isn’t equal to one tile at a time, and you now have to worry about checking against two tiles instead of one. IE if you are walking in the real world and the left-half of you is going to bump into a wall, you can’t just keep moving, you have to move right a little more first.

My second algorithm was a little cleaner, but still had the problem that each direction had its own case since walking on an up leftward sloping tile could have one of three results: y increase, y decrease, y stays the same. This algorithm just got the tile you are standing on now and got the tile(s) you would be standing on if you moved, took the absolute value of the difference in their y intercepts and if it was less than one, you could move to it. In the case of different y intercepts for each tile you would be moving to, the higher one was given precidence. So this was a bit cleaner to read and to type as well, but still had the problem of one case for each direction, with only a few things changing.

Now my current algorithm that I use. I have overhauled this code( all of it ) a grand total of 3 times. This last one was the biggest change since I A) Moved from Actionscript to C++ with OpenGL and B) Know a helluva lot more about vector-math and coding in general. The vector math really kicks in for this algorithm because instead of storing the direction the character is moving in a string, ie dir = “Right”, I instead store the direction as a vector, ie dir = { 0, 0, 1 }. Given that any tile will have two slopes, ( change of y ) / ( change of x ) and ( change of y ) / ( change of z ) and the direction, I can now ignore direction-dependent code. Instead of saying:

if ( dir = “right” and slope = “right” ) y = y + character.speed * 0.5 - assuming( like I did ) all tiles have a slope of 0.5

else if ( dir = “right” and slope = “left” ) y = y - character.speed * 0.5

else if ( dir = “right” and slope “left” and slope “right” ) y = y

I can say:

y = character.direction.x * tile.level.slopeXY * character.speed + character.direction.z * tile.level.slopeZY * character.speed + tile.y_intercept

It might be a little hard to read, but all it is saying is y = (mx)x + (mz)z + b. Where x = character.speed * character.direction.x( where the character will be after the move ) and z = character.speed * character.direction.z. With this solution I never have to specify which direction because if I am moving up or down, my direction.z will be 0. Also if the tile does not slope in either direction, the equation will just be y = tile.y_intercept. This makes for a much shorter piece of code. I know there are still better ways to do this, but I was pretty happy with this solution. The ironic thing is that with my first two ideas, I spent hours upon hours coding them until they worked. With this solution that I use now, the concept just fell into place because of how I set up my movement structure and tile structure. Good planning definately helps in the long run.

~Zach

* Thou shall not kurr-steal. *