Drawing Order in 2D Tile Editor

I'm working on a tile editor for my game and ran into the problem of the order the images are drawn.

I want to allow the user to be able to draw to different layers (4 total) and to be able to move tiles forward or backwards in the order they are drawn, as in a graphics program like Photoshop.

Right now, the technique I'm working for is 4 different types, one with a pointer for each layer. The drawing order would be determined by the order that is contained in that type object. Therefore, I would have to use "Before" and "After" to re-sort the tiles everytime the position of one is changed. Has anybody encountered this sort of problem in a tile editor? In what way did you program it in order for it to be efficient and functional?

I'm doing this all in 2D. I know many people suggest using 3D sprites instead. Is the extra work to change from 2D to 3D worth it, or necessary, even? What advantages are there to each?

Type layers
	Field s.tiles
	Field e.tiles
End Type

Type tiles
	Field image
	Field x
	Field y
	
	Field layer.layers
End Type

Function CreateLayer.layers()
	Local layer.layers
	
	;create new layer
	layer = New layers
	
	Return layer
End Function

Function DeleteLayer(layer.layers)
	Local tile.tiles
	
	;clear tiles from layer
	If layer\s <> Null
		tile = layer\s
		Repeat
			If tile = layer\e
				Delete tile
				Exit
			Else
				tile = After tile
				Delete Before tile
			End If
		Forever
	End If
	
	;delete layer
	Delete layer
End Function

Function CreateTile.tiles(image,x,y,layer.layers)
	Local tile.tiles
	
	;create new tile
	tile       = New tiles
	tile\image = image
	tile\x     = x
	tile\y     = y
	tile\layer = layer
	
	;insert tile into layer
	If layer\s = Null
		;this is first tile in layer, set start pointer to tile
		layer\s = tile
	Else
		;there are other tiles in this layer, add tile to end of list
		Insert tile After layer\e
	End If
	;update the end pointer to this tile
	layer\e = tile
	
	Return tile
End Function

Function DeleteTile(tile.tiles)
	;update layers list of tiles
	If tile = tile\layer\s And tile = tile\layer\e
		;if this tile is the only tile in layer NULL start end pointers (clear the list)
		tile\layer\s = Null
		tile\layer\e = Null
	ElseIf tile = tile\layer\s
		;tile is first in list, update start pointer
		tile\layer\s = After tile
	ElseIf tile = tile\layer\e
		;tile is last in list, update end pointer
		tile\layer\e = Before tile
	End If
	
	;delete tile
	Delete tile
End Function

Function MoveLayerUp(layer.layers)
	;if the layer before this layer exists, then move this layer, before it
	If Before layer <> Null Insert layer Before (Before layer)
End Function

Function MoveLayerDown(layer.layers)
	;if the layer after this layer exists, then move this layer, after it
	If After layer <> Null Insert layer After (After layer)
End Function

Graphics 640,480,32,2

;frame timer
Global timer = CreateTimer(50)

;create 3 layers
Global layer1.layers = CreateLayer()
Global layer2.layers = CreateLayer()
Global layer3.layers = CreateLayer()

;create some tile images
Global image1 = CreateImage(32,32)
Global image2 = CreateImage(32,32)
Global image3 = CreateImage(32,32)
SetBuffer ImageBuffer(image1)
ClsColor 255,0,0
Cls
SetBuffer ImageBuffer(image2)
ClsColor 0,255,0
Cls
SetBuffer ImageBuffer(image3)
ClsColor 0,0,255
Cls

;set active layer and image
Global currentlayer.layers = layer1.layers
Global currentimage        = image1

SetBuffer BackBuffer()
ClsColor 255,255,255
Repeat
	Cls	
		;render layers
		If Last layers <> Null
			layer.layers = Last layers
			Repeat
				;render this layers tiles
				If layer\s <> Null
					tile.tiles = layer\s
					Repeat
						DrawImage tile\image,tile\x,tile\y
						
						If tile = layer\e Exit
						tile = After tile
					Forever
				End If
				
				If layer = First layers Exit
				layer = Before layer
			Forever
		End If
		
		;user interface
		x = MouseX()
		y = MouseY()
		If x > 160
			DrawImage currentimage,x,y
			If MouseHit(1)
				CreateTile(currentimage,x,y,currentlayer)
			End If
		End If
		
		If KeyHit(2) currentlayer = layer1
		If KeyHit(3) currentlayer = layer2
		If KeyHit(4) currentlayer = layer3
			
		If KeyHit(200) MoveLayerUp(currentlayer)
		If KeyHit(208) MoveLayerDown(currentlayer)
			
		If KeyHit(57)
			Select currentimage
				Case image1
					currentimage = image2
				Case image2
					currentimage = image3
				Case image3
					currentimage = image1
			End Select
		End If
		
		Color 0,0,0
		Rect 0,0,160,480,1
		Color 255,255,255
		Text 2,2,"left click to place"
		Text 2,16,"a tile."
		Text 2,40,"up to move layer up"
		Text 2,64,"down to move layer"
		Text 2,78,"down"
		Text 2,102,"1,2,3 to change"
		Text 2,116,"the current layer"
		Text 2,140,"space to change"
		Text 2,154,"tile image"
		
		Text 10,178,"current tile"
		DrawImage currentimage,40,192
		
		y = 244
		For layer.layers = Each layers
			If layer = layer1
				If layer = currentlayer
					Color 0,128,0
					Rect 2,y,156,20,1
					Color 0,55,0
					Rect 2,y,156,20,0
					Color 255,255,255
					Text 4,y,"layer 1"
				Else
					Color 128,128,128
					Rect 2,y,156,20,1
					Color 55,55,55
					Rect 2,y,156,20,0
					Color 0,0,0
					Text 4,y,"layer 1"
				End If
			ElseIf layer = layer2
				If layer = currentlayer
					Color 0,128,0
					Rect 2,y,156,20,1
					Color 0,55,0
					Rect 2,y,156,20,0
					Color 255,255,255
					Text 4,y,"layer 2"
				Else
					Color 128,128,128
					Rect 2,y,156,20,1
					Color 55,55,55
					Rect 2,y,156,20,0
					Color 0,0,0
					Text 4,y,"layer 2"
				End If
			ElseIf layer = layer3
				If layer = currentlayer
					Color 0,128,0
					Rect 2,y,156,20,1
					Color 0,55,0
					Rect 2,y,156,20,0
					Color 255,255,255
					Text 4,y,"layer 3"
				Else
					Color 128,128,128
					Rect 2,y,156,20,1
					Color 55,55,55
					Rect 2,y,156,20,0
					Color 0,0,0
					Text 4,y,"layer 3"
				End If
			End If
			y = y + 20
		Next
	Flip
	WaitTimer(timer)
Until KeyDown(1)

Erm...how about a double linked list?

type tile

field image
field x
field y

field next.tile
field previous.tile

end type

Then your layers only need to function as "pointers" into individual groupings of tiles...and each tile "points" to both the next and previous tile with in the group.

sorta like this (trying to sorta diagram it out):


first these are the layers:

Layer.tile(1) -> tile 707
Layer.tile(2) -> tile 53


now for the tiles:

tile 707.previous -> Null
tile 707.next -> tile 811



tile 811.previous -> tile 707
tile 811.next -> tile 12



tile 12.previous -> tile 811
tile 12.next -> Null


tile 53.previous -> Null
tile 53.Next -> Null



(the numbers 707,811,12 are just there it identify specific tiles in the diagram, showing that the tile order is specificly controlled by the next/previous links)...notice that the first tile...the one that the layer points to...the 'previous' link value is null...and the last tile in the grouping, the 'next' link value is null...in this way you can easily check if you have reached the top or bottom of a layer grouping (and if both 'previous' and 'next' links are Null...then there it only one tile in grouping)

So useing the above...say you wanted to move tile 811 from the first to the second layer grouping...a function like this could work (assumeing that layer() is a global array )

Function movetile( me.tile, laynumber%)

;temp variables used to store the previous/next pointers
tempprevious.tile = me.previous
tempnext.tile = me.next

;swap out the previous/next pointers with the linked tiles
;effectively this removes the "me" tile from the layer group

if tempprevious then tempprevious.next = tempnext

if tempnext then tempnext.previous = tempprevious


;now set "me" previous to null (indicateing it is the first tile in a layer grouping)

me.previous = null

;then set "me" next to the first tile in the layer grouping

me.next = layer(laynumber)

;then set that tile (the first tile in the laynumber grouping)
;'previous' value to "me"

if layer(layernumber) then layer(laynumber).previous = me

;and finaly set "me" at the top of the leyer grouping

layer(laynumber) = me

end function


It's kinda hard to explain linked lists (and I likely screwed up the blitz programing syntax for types up there..which won't help)...but I hope that helps

Thanks for the replies!

So, when drawing the tiles, should I use

For t.tile = each tile
DrawImage t\image
Next

Or would something like this be necessary for it to draw correctly?

me.tile = First tile
While me <> Null
DrawImage me\image
me = me.next
Wend

The second option would be the way to go for the linked list method I outlined above.

The problem with conditional level checking as shown by Skn[ac] in the code above is that you end up checking all the tiles multiple times...this isn't bad when you have a small over all number of them...but say you have 10,000 (a 100 by 100 array)...and 17 of them are on the first layer, 45 are on the second, 9,000 on the third, and 54 on the fourth...you end up checking all 10,000 tiles 4 times per update...and thus in the first layer alone with only 17 tiles to draw, means you are wasteing time checking the remaining 9983 tiles...sure this is pretty fast, but you are wasteing time on checking instead of processing other things (like AI, etc..)

However there are simple ways to speed even that up...bounds checking...for each layer you would record the minimum and maximum array locations that include the specific layer in question...

for example if the map is 100 tiles wide by 100 tiles tall you could have something like this for each layer at map load:

Layer1_min_X = 100
Layer1_min_Y = 100
Layer1_max_X = 0
Layer1_max_y = 0

then run through the tiles in the array...if the tile is on the particular layer then check if the array X/Y location is within those bounds:

For X = 0 to 100
For Y = 0 to 100

;obviously do this for each layer
If map.tile(x,y)\layer = 1 then
If X < level1_min_X then level1_min_x = x
If y < level1_min_y then level1_min_y = y
If X > level1_max_X then level1_max_x = x
If y > level1_max_y then level1_max_y = y
end if

next
next


then when you draw, you can do it as Skn[ac] showed except for each layer you set up the for/next loops to start at minX/Y to maxX/Y...something like:

For X = Level1_min_X to Level1_max_X
For Y = Level1)min_Y to Level1_max_Y

if map.tile(x,y)\layer = 1 then draw tile

next
next

this will only have you checking for the correct layer in an area of the map that is certain to have tiles in it...meaning you arn't wasteing time checking for the correct layer in potentialy larger areas of the map that won't have tiles to draw right now...

However the linked list method is more efficent in that it directly points to the tiles that need to be drawn.