Isometric coordinate systems – the modern way

Figure 6
Submit to StumbleUpon

Hello and welcome back to my blog!

This time i’m going to cover a subject aimed at beginners setting out trying to make a simple isometric 2d, grid based game. The reason i thought this would be of use is because i’ve not seen isometric coordinate systems described this way before, and i thought it was a nice simple way to approach the subject.

Isometric grid

An isometric tile based grid looks something like this usually:

Figure 1

Diamond shaped tiles (in this case half as high as they are wide) butted up to each other over the course of the map.

Each tile represents a different logical location in the game world.

Storage vs rendering

Ok, so the obvious way to store this map in memory is a simple 2d array, which works great until you try to render the tiles (which must be done back to front) and then you discover that the array needs to be traversed in a bizarre order.

Figure 2

Figure 2 shows one possible array mapping for the tiles, however the render order is quite different as shown in Figure 3.

Figure 3

So, we need a way to traverse through the array in the order shown in Figure 3. I developed the following piece of code for the job:

///
/// This function is the code to traverse an isometric grid in sorted order from back to front
///
private function TraverseGrid(sortedAction:Function, reverse:Boolean):void
{
	// isometric grid traversal
	var limit:int = m_dimension-1;
	var i:int = 0;
	var j:int = limit;
	var iStart:int = i;
	var jStart:int = limit;
	var jTerm:int = limit;
 
	for (;;)
	{
		// call out to the delegate to perform logic at this sorted grid location
		if (reverse)
		{
			sortedAction(j, i);
		}
		else
		{
			sortedAction(i, j);
		}
		i++;
		j++;
 
		if (j > jTerm)
		{
			// new line
			jStart--;
			if (jStart < 0)
			{
				// clamp at 0
				jStart = 0;
				jTerm--;
				iStart++;
				if (iStart > m_dimension - 1)
				{
					break;
				}
			}
 
			i = iStart;
			j = jStart;
		}
	}
}

It will call out to the delegate function sortedAction with the grid coordinate that its currently on.

Coordinate Systems

Ok, so now we can draw everything back to front ok, we still need to have a think about coordinate systems. Specifically we’d like to be able to go from screen-space (pixel coordinates) to grid space (array coordinates) and back again, for things like mouse clicks and so forth.

Figure 4

So in Figure 4, we’ve chosen an origin point (labelled 0,0) and two axis vectors (right and up) which define the two possible directions of motion in the game.

Now, if we pick our axis vectors carefully, any location in the game can be described as a combination of the origin and axis vectors. This lets us keep all of our object coordinates in grid-space (which is very handy for collision detection and so forth) but have a simple mapping into screen-space where everything is actually positioned on screen.

Figure 5

In Figure 5, the axis vectors have been shortened so that each one is half the width/height of a tile. This makes sense because the entire width of the 8×8 map is then 8 times the length of the right vector, and similarly with the height.

This lets us describe the location of the blue ball in screen-space quite easily given the grid-space coordinates (i, j):

BallPosScreen = orgin + right*BallGridPos.i + up*BallGridPos.j

This means that for any point on the grid we can immediately look up the screen space position. Technically what we’ve done is form a coordinate basis for our map.

Ok, so what about the reverse mapping? Given any point on the screen, find the location in grid space.

Figure 6

This is a little bit more tricky, but Figure 6 shows what needs to be done. Candidate screen-space location P can be found in grid-space by intersecting the two blue ‘rays’ emanating from the candidate point against the right and up vectors we defined earlier.

The ‘time’ of intersections along the right and up vectors, Tr and Tu are actually the grid-space coordinate that we’re looking for. And the blue ‘rays’ can be found easily by just subtracting the right and up vectors from the candidate point.

/**
* Intersect two line segments defined by A->B and C->D
*
* Returns the time of intersection along A->B
*/
public function RayIntersect(A : Vector2, B : Vector2, C : Vector2, D : Vector2) : Number
{
	// turn C->D into a plane...
	const n : Vector2 = D.Sub(C).m_Perp;
 
	// ...and do the regular plane vs ray maths
	const numerator : Number = C.Sub(A).Dot(n);
	const denom : Number = B.Sub(A).Dot(n);
 
	return numerator / denom;
}

Above is an appropriate ray intersection routine. What we could do instead to get the grid-space coordinates, is to form a matrix from our right, up and origin, and then invert it and transform our screen-space point by that matrix. But this isn’t nearly as easy to visualise and comes down to the same maths anyway.

Demo

Here is a simple demo of the techniques described in this article; all the blocks are positioned using a combination of the screen-space array traversal (to pick the correct block from the map array) and the grid-space to screen-space transform described (to pick the right position on screen to place the blocks).

If you drag the mouse, it uses the final technique to map the click-point from screen-space to grid space, finds the associated block and replaces it with a different block.

Conclusion

Using these simple, modern techniques it becomes much easier to code and understand isometric 2d games, leading to greater productivity.

Source code

If you found this article useful and would like to see more like this, please consider buying the source-code which i have made available on this page for a small cost – this will allow an indie developer like me to justify his existence for another month, and more importantly pay for things like food and rent!

After purchasing, you will be redirected to a page where you can download the source immediately.

USD 2.99

Subscribers can access the source here

Have fun,

Cheers, Paul.

Submit to StumbleUpon

About Paul Firth

A games industry veteran of ten years, seven of which spent at Sony Computer Entertainment Europe, he has had key technical roles on triple-A titles like the Bafta Award Winning Little Big Planet (PSP), 24: The Game (PS2), special effects work on Heavenly Sword (PS3), some in-show graphics on the BBC’s version of Robot Wars, the TV show, as well as a few more obscure projects.   Now joint CEO of Wildbunny, he is able to give himself hiccups simply by coughing.   1NobNQ88UoYePFi5QbibuRJP3TtLhh65Jp
This entry was posted in AS3, Geometry, Graphics, Technical. Bookmark the permalink.

11 Responses to Isometric coordinate systems – the modern way

  1. Daniel Hotop says:

    Hey Paul,
    You missed a trick with the render, you can render the tiles using normal 2D array traversal. Using you image above you render { a,c,f,j } , { b,e,i } , { d,h }, { g }

    If you put your origin at the Top point and not the the Left point it then just all comes out in the wash.

    This is how I did it on that Project which I can not name.

  2. Jameson says:

    The person above beat me to it, but I thought I’d add that you don’t need to move the origin, just the first tile you render from.

    To explain, the algorithm I thought of would:

    Locate ‘highest’ square, this is your starting square.
    the ‘line’ to render can be either direction, just pick one and stick to it, the other direction is the next line.

    This should be implementable in a quicker way than the way you have described, although the source code would probably be longer (big cases would probably be the most efficient way to program this, I think). It comes with two flaws I can see: objects existing in this grid should be restricted to the cube in which they reside; if they are bigger, overlaps may get ordered wrong.

    The other flaw is a very unlikely one, but if you want a non-rectangular game world, this won’t really work. Who’d use a non-rectangular world though, really?

    • Paul Firth says:

      Hi Jameson,

      Yes, indeed it does look like I was overcomplicating the render order algorithm here :) I will update the sample and article as soon as I get a chance….

      Thanks for the feedback!

      Cheers, Paul.

  3. craig says:

    Great article with one exception… the .m_Perp property of the Vector2 object… what is it? Presumably .m_Perp is an abbreviation of something?

    I’m looking for an equivalent in C#’s XNA or, if none exists, a wikipedia article explaining what it is / how it’s calculated. Am finding this a little hard without really knowing what “m_Perp” is!

  4. Jacob says:

    When rendering isometric tiles, the general rule is that all tiles in a V behind a tile must be rendered before a tile is rendered. Any algorithm that satisfies this will work.

  5. Steve says:

    Hi Paul,
    Instead of line intersections, couldn’t you just subtract the origin from the candidate position, and then dot this vector against the ‘right’ and ‘up’ vectors to get your co-ordinates?

    Cheers,
    Steve

  6. Michel says:

    I don’t understand the code, because I just programming in C++. And by the way, what programming language is it? I tried to understand what do vectors A, B, C and D mean, because the drawing show to us different vectors (Up, Right, Tr, Tu and P) and how functions like this D.Sub(C).m_Perp or this C.Sub(A).Dot(n) work.

    C.Sub(A).Dot(n) maybe means (C-A).n

    Michel,
    Thanks for attention.

    • Paul Firth says:

      Hi Michel,

      If you look at the comment to the function, you can see what A, B, C and D mean:

      /**
      * Intersect two line segments defined by A->B and C->D
      *
      * Returns the time of intersection along A->B
      */

      And yes, C.Sub(A) = (C-A).

      Dot() = dot product.
      m_Perp = perpendicular operator

      Cheers, Paul.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

WP-SpamFree by Pole Position Marketing