PDA

View Full Version : My solution to the overlapping issue in isometric worlds.



Solstice Project
01-11-2013, 12:47 AM
Hi.

I wanted to write an isometric level editor and i'm almost done actually,
but i'm switching over to topdown 3d now, because it suits better.

So i thought i'll share how i did it.

Somewhere on this forum i read about sorting through the tiles,
every frame, which i believe is a horrible idea.

Sorry for that, unnamed internet stranger. ^_^

Solstice Project
01-11-2013, 12:48 AM
Type
tItem =
Record
Item,X : Word;
End;

pItem = ^tItem;

tOrder = Array[0..300] of tItem;


Const
ItemSize = SizeOf(tItem);


Var
// OrderHeap : Array[0..GroundSizeY] of ^tOrder;//tHeapArray;
OrderHeap : Array[0..GroundSizeY] of ^tOrder;
pHeap : Pointer;

// DrawOrder : Array[0..GroundSizeY] of PWordArray;// absolute OrderHeap;//Array[0..GroundSizeY] of Pointer;
Items : Array[0..GroundSizeY] of LongInt;
Dummy : pItem;




Procedure InitHeap;
Var
y : longword;


Begin
For y := 0 to GroundSizeY do
Begin
GetMem(OrderHeap[y],SizeOf(tOrder));
FillChar(OrderHeap[y]^[0],SizeOf(tOrder),00);
Items[y] := 0;
End;
End;

Procedure AddItem(y : LongWord; Data : tItem);
Var
b : longword;

Begin
OrderHeap[y]^[Items[y]] := data;
// writeln(y);
Inc(Items[y]);
End;


Function ReadItem(y,x : LongWord) : tItem;
Begin
ReadItem := OrderHeap[y]^[x];
End;


Procedure MoveItem(y : LongWord; Src,Dest : Word);
Var
Dummy2 : pItem;

Begin

OrderHeap[y]^[Dest] := OrderHeap[y]^[Src];
OrderHeap[y]^[Src] := OrderHeap[y]^[Items[y]-1];
Dec(Items[y]);
End;

Procedure MoveItemToY(y1 : word; Src : byte; y2 : word);
Var
xxx : LongWord;

Begin
OrderHeap[y2]^[Items[y2]] := OrderHeap[y1]^[Src];
OrderHeap[y1]^[Src] := OrderHeap[y1]^[Items[y1]-1];
Dec(Items[y1]);
Inc(Items[y2]);
End;There are a few things to mind here.

"OrderHeap" is actually just one long chain of bytes. Memory allocation is silly,
but i want to switch this to actual pointers each pointing to the beginning of their
line in one huge chunk of heap. ^_^

GroundSizeY currently is ... 8192*2 = 16384, times 4 Bytes, times 300 items per Y ...
making OrderHeap 19 MByte big ... which isn't even a lot.

Please note that OrderHeap's height equals the depth of the drawn, visual city. (aka top to bottom of whole rendered map)
I have "Blocks" of 512x512, which i plot at 256x256 to have more details when zoomed in.

Now how does it work ?

First, I'm scanning through a 128x128 bitmap.
If a pixel is set, i calculate the y-position of the tile on the image
and add an item to it's corresponding y-line in DrawOrder.



For y := 0 to 127 do
For x := 0 to 127 do
Begin
If (CityMap[x,y] <> 0) then
Begin
m := x;
v := (y*64); // v is the line we have our tile set at.

// writeln(m,' : ',v);

xxx.Item := MaxHumans;
xxx.X := m;

AddItem(v,xxx);
End;
End;

MaxHumans. That's a constant limiting the amount of NPC humans walking around on the map.
With MaxHumans, the first building-tile starts. It's not relevant to this thread.


After this went through, i had my OrderHeap filled.

f = Y of the top most visible line on screen
g = Y of the bottom most ...



for y := f to g do
begin
if (Items[y] > 0) then
for x := 0 to Items[y] - 1 do
begin
xxx := ReadItem(y, x);
m := xxx.X * (BlockSize div 2);
v := y;
DropSprite(0, m, v - (BlockSize div 2), BlockSize, BlockSize);
end;
end;

Now this is a bit tricky. Obviously i have no idea how you made your tiles
and how you plan on dropping them onto screen.

All this basically does is go through a whole line and draw everything onto the backbuffer.
Sorting on X is completely unnecessary, so we can just weeze through it all at once,
enjoying the fact that we're making the cache happy too.

This way ... buildings stay behind people ... or in front of them.

There's something else i have to add, although i'm not sure if it will affect you.

(v - (BlockSize div 2)) shows that i am dropping the Sprite actually ABOVE the current OrderHeap[y].
This makes sense to me, because it pushes the tiles center line to y. Isometric tiles are basically blocks,
starting with a tight top, extending into center and tightening again towards the bottom.

Having it's center line at y will prevent sprites from wrongly overlapping with it.

Solstice Project
01-11-2013, 12:49 AM
Procedure AddItem(y : LongWord; Data : tItem);
Var
b : longword;

Begin
OrderHeap[y]^[Items[y]] := data;
// writeln(y);
Inc(Items[y]);
End;

This is pretty self explanatory. Items[y] always contains the next empty spot in the array.



Function ReadItem(y,x : LongWord) : tItem;
Begin
ReadItem := OrderHeap[y]^[x];
End;



Procedure MoveItem(y : LongWord; Src,Dest : Word);
Begin

OrderHeap[y]^[Dest] := OrderHeap[y]^[Src];
OrderHeap[y]^[Src] := OrderHeap[y]^[Items[y]-1];
Dec(Items[y]);
End;

Okay now what's the point of this ? ^_^
It's never used. There is none.
I just keep it as a reference.

The actually important one is the next one.


Procedure MoveItemToY(y1 : word; Src : byte; y2 : word);
Var
xxx : LongWord;

Begin
OrderHeap[y2]^[Items[y2]] := OrderHeap[y1]^[Src];
OrderHeap[y1]^[Src] := OrderHeap[y1]^[Items[y1]-1];
Dec(Items[y1]);
Inc(Items[y2]);
End;

This part deals with moving entities that change Y.

The part i like most about this approach is that whenever an item
needs to move to different Y, the empty spot it left can get filled instantly by the last in line.

No holes, no need for management.



I am fairly certain that i have missed something and owe you explanations.
Sadly, it's 0241, but i'll check back at it tomorrow and hopefully
there are questions you want to have answered ! :D

Or, you know, just flame me.

User137
02-11-2013, 11:52 PM
Is GroundSizeY the index of last item, or count of items in array? Your current code would suggest that it's index of last item.

OrderHeap : Array[0..GroundSizeY] of ^tOrder;

If you want it to represent array length, you need to change the array to

OrderHeap : Array[0..GroundSizeY-1] of ^tOrder;

And actually there is nothing wrong with sorting. We aren't sorting any drawn tiles, because they are linear anyway, and simple mathematics can tell the order in which to draw. But what remains is all the game objects, such as players and objects, which aren't tied to any tile. If they are, they are drawn right after the tile itself.

As for sorting, you have different algorithms to choose from. You don't need to go through all possible checks every frame, because there is very high propability that the whole object array is not going to be much different next frame. So for each unique object, you could only compare it to previous item, and push it back if it's higher/lower in Z order. Then stop with that item and do the same for next item, and so on. But even if it's "slowly" sorting the array the way it should be, it's faster than player can see, and trivially fast for the CPU.

edit: Oh, drawing a freely placed sorted object array in the mix of tiles... I think it should be done at the same time as the tiles are. Going through the list and comparing Z order to the currently drawn tile.

Solstice Project
10-11-2013, 06:59 PM
Yay, a response. :D

Well ... i don't really see what you mean. GroundSizeY ranges from top to bottom for every Y.
If it's one more or not doesn't really matter to me. Personally, in my arrays i like to have one additional one,
just to be safe. It's not exact, but it's not really relevant in most cases.

Well ... you think there's nothing wrong with sorting and that's okay, but i don't see a need for wasting time with it,
when there's a much faster way that's also really easy to set up.
I tend to trade pages for cycles ... and that's the outcome of it.

I don't really understand what you mean. It's not irrelevant if a person can or can not see a difference.
Small parts of a code can have a big impact on runtime performance and that's relevant. I understand that nowadays most people
don't care about their slow code, but that's not something i am happy with.


I understand that you think that you need to do that, but you don't. With my approach, no additional sorting at all is needed.

Why would you want to go through the list and compare Z order, when the Z order is obviously there already ?

You render back to front and go from the top to the bottom of the Order-List.

You don't need to stick to tiles, btw. You can add anything to the list.
My "humans" are in it too. I use it for everything on screen, obviously,
because it's so straight forward and easy.

User137
10-11-2013, 10:05 PM
I only gave solution which would work smooth 60+ fps even if your map is like 10000 x 10000 tiles, and 10000 dynamic game objects in it, with a low spec computer. All the while using very little memory. Can you say the list works as well? The point of new algorithms is often to improve on something that exists before. That said, i don't completely understand how your code works.

SilverWarior
10-11-2013, 10:48 PM
Small parts of a code can have a big impact on runtime performance and that's relevant. I understand that nowadays most people
don't care about their slow code, but that's not something i am happy with.

Most pepole nowadays don't care about their slow code becouse they don't have to. Why? Becouse nowadays computers are so powerfull.
But more and more game and aplication developers are starting to care about their slow code becouse the mobile devices doesn't offer so much processing power and therefore require more optimized code.

As for your example I'm afraid that like User137 I don't exactly understand how it works. That is why I havent posted any coments so far.


But as for general improvment of Isometric map drawing:
The best aproach on speeding it up is to split your map into mulltiple sections (chunks) and then processing only seperate chunks instead of whole map.
This gives you hte ability to have practically endess sized map without much of performance slowdowns.
So in the end you could still use slow tile sorting approach becouse it won't be such a big problem as you will use this approach only on smaller part of the map and not the whole map.