Rollercoaster's depth sorting: how?
Author
Hello,
for an isometric game which looks quite similar to typical isometric games ala Rollercoaster Tycoon et al, I've got problems with the depth sort.
Each fream I put all objects of the visible world into a display list. Ground tiles as well as fix items (trees, bushes) and mobile items (people etc). Currently the objects can be larger than a map tile. Additional to their 3d position in x, y and z, they've got a bounding box in x, y and z, which represents their width, depth and hight.
A simple heap sort on the display list doesn't work very good, because especially overlaping tiles are wrong (althought the speed of the sorting would be fine). A "Newell-Newell-Sancha" algorithm (or "Full Depth Sorting") doesn't bring too good results, too, but especially it's way too slow.
How does Chris Sawyer's game does the trick? Or any other isometric games of that kind?
Unfortunately I don't find any good information on that topic in the Internet. It's always just basic stuff which I've already tested and it never really does the job.
I know that if I would cut all objects to the map's tile size, quite some problems would dissappear, but not all I'm afraid.
There must be a better way and Chris did obviously know it. :-)
Any hints please? Resources on the web? Thanks in advance.
Edited by - Faramir on August 2, 2001 5:36:15 AM
You have a couple of choices. I assume you are not using
a 3D api but it would help a great deal if you could as
a hardware zbuffer would fly and be just about perfect.
If your screen does not scroll then a precomputed Z buffer
will do the trick. Your moving entities will simply check
this buffer. It will not be slow because you are dealing
with a small number of entities.
Failing all of that you could try using span buffers. Span
buffers solve this type of VSD problem. There are a few
caveats. If you end up with far too many spans then you
might as well just use a zbuffer because the sort will
hurt you.
Each span is compared with other spans that it overlaps. When
one or more horizontal spans intersect the Z coordinate is
determined and a new split is put on the list.
At the end of this process you have a list of horizontal
spans for each scanline sorted in Z.
So for Y you will have a set of spans going from left to
right (Depending on how you want to do it). For each span
store starting X,starting Z,ending X,ending Z and a pointer
to the graphic.
Note there are a lot of optimisations to be had because all
your tiles are regular so you can precompute span coordinates
and cache them.
I will say that again. Imagine that your iso tiles are actually
just polygons that have been pre transformed. You can easily
build a list of horizontal spans from these tiles in a pre
process.
EG. (Imagine this is one of your tiles Diamond shaped,whatever)
TILE (A)
--*****
---*****
----*****
-----*****
Store a list of local offsets.
X1=2,X2=6,Z1=6,Z2=0
And so on for each tile scan line.
When you come to render you will have to add the world X,Y,Z
to these local values. You could do a rough back to front
sort of all your tiles and do it this way to get your world X,
Y and Z offsets and it might help the sorting phase.
Let''s say your screen res is 800x600. Create an indexed array
of 600 elements for each scan line.
Loop through your tiles scan lines and put them in the appropriate Y bucket. Now there may or may not be other
spans on this Y. You can either allocate on the fly or
build a cache bucket for the X spans which you can use up
to avoid having to allocate and deallocate each render
pass.
Now for this Y bucket you may have other spans in X. This
is the tricky bit. Sort the span (x1) on minimum X. Now
compare this span with other spans on this Y scan line for
X overlaps. If you don''t sort then you cannot "early out"
because every span you put on that Y line will have to
be compared with every other span. If they are sorted then
as soon as you get no intersecction with X1,X2 you can come out of the loop.
So you are looping through your tiles spans. You have tile
(A) and it starts on scan line 10. Tile (B) has also hit
gone into scan line 10 at X1=0.
(A) starts at 0 as well. Sort your span into the bucket. Now
do the compares.
AAAAAAAA
BBBBBBBBBBBB
On the screen they might end up like this....
AAAAAAABBBBBBB
For this example I will assume Z decreases as it gets closer
to the camera (If not just flip the assumption)
(A) has z (left to right) between 10-17
(B) has z between 15-26
There are several different cases of overlap to consider but
here is an example.
(A) overlaps (B) (or vice versa it doesn''t matter) at X=0
through to X=7.
For (A) Z=10 at X=0 and Z=17 at X=7
For (B) Z=15 at X=0 and Z=22 at X=7
Z1 and Z2 of A are both less than B so we clip B to X=8
recompute Z at X=8 for B then carry on.
At the end of this pass you will have no overdraw and a list
of sorted spans. The tricky part of the algorithm is the
bucket sort on X for overlap and trying to optimise it.
A side product of this algo is that it will perfectly handle
sprites larger than one tile. Just plug them into the scan
test.
There are variations on this algorithm. I suggest reading
up on S-buffers (But they only solve overdraw as they
expect perfectly sorted polygons,so not much use to you but
worthwhile reading).
a 3D api but it would help a great deal if you could as
a hardware zbuffer would fly and be just about perfect.
If your screen does not scroll then a precomputed Z buffer
will do the trick. Your moving entities will simply check
this buffer. It will not be slow because you are dealing
with a small number of entities.
Failing all of that you could try using span buffers. Span
buffers solve this type of VSD problem. There are a few
caveats. If you end up with far too many spans then you
might as well just use a zbuffer because the sort will
hurt you.
Each span is compared with other spans that it overlaps. When
one or more horizontal spans intersect the Z coordinate is
determined and a new split is put on the list.
At the end of this process you have a list of horizontal
spans for each scanline sorted in Z.
So for Y you will have a set of spans going from left to
right (Depending on how you want to do it). For each span
store starting X,starting Z,ending X,ending Z and a pointer
to the graphic.
Note there are a lot of optimisations to be had because all
your tiles are regular so you can precompute span coordinates
and cache them.
I will say that again. Imagine that your iso tiles are actually
just polygons that have been pre transformed. You can easily
build a list of horizontal spans from these tiles in a pre
process.
EG. (Imagine this is one of your tiles Diamond shaped,whatever)
TILE (A)
--*****
---*****
----*****
-----*****
Store a list of local offsets.
X1=2,X2=6,Z1=6,Z2=0
And so on for each tile scan line.
When you come to render you will have to add the world X,Y,Z
to these local values. You could do a rough back to front
sort of all your tiles and do it this way to get your world X,
Y and Z offsets and it might help the sorting phase.
Let''s say your screen res is 800x600. Create an indexed array
of 600 elements for each scan line.
Loop through your tiles scan lines and put them in the appropriate Y bucket. Now there may or may not be other
spans on this Y. You can either allocate on the fly or
build a cache bucket for the X spans which you can use up
to avoid having to allocate and deallocate each render
pass.
Now for this Y bucket you may have other spans in X. This
is the tricky bit. Sort the span (x1) on minimum X. Now
compare this span with other spans on this Y scan line for
X overlaps. If you don''t sort then you cannot "early out"
because every span you put on that Y line will have to
be compared with every other span. If they are sorted then
as soon as you get no intersecction with X1,X2 you can come out of the loop.
So you are looping through your tiles spans. You have tile
(A) and it starts on scan line 10. Tile (B) has also hit
gone into scan line 10 at X1=0.
(A) starts at 0 as well. Sort your span into the bucket. Now
do the compares.
AAAAAAAA
BBBBBBBBBBBB
On the screen they might end up like this....
AAAAAAABBBBBBB
For this example I will assume Z decreases as it gets closer
to the camera (If not just flip the assumption)
(A) has z (left to right) between 10-17
(B) has z between 15-26
There are several different cases of overlap to consider but
here is an example.
(A) overlaps (B) (or vice versa it doesn''t matter) at X=0
through to X=7.
For (A) Z=10 at X=0 and Z=17 at X=7
For (B) Z=15 at X=0 and Z=22 at X=7
Z1 and Z2 of A are both less than B so we clip B to X=8
recompute Z at X=8 for B then carry on.
At the end of this pass you will have no overdraw and a list
of sorted spans. The tricky part of the algorithm is the
bucket sort on X for overlap and trying to optimise it.
A side product of this algo is that it will perfectly handle
sprites larger than one tile. Just plug them into the scan
test.
There are variations on this algorithm. I suggest reading
up on S-buffers (But they only solve overdraw as they
expect perfectly sorted polygons,so not much use to you but
worthwhile reading).
I have an isometric engine which can have tiles bigure than the tile shape but doesn''t require ordering because I blit the tiles back to front. Here is a simple loop that goes through each tile from back to front, assuming that MAPSIZE is the size of the map in both length and width:
Of course, this only works if you have a grid with layers to put everything (I put my characters in their own layers into the grid.) I wouldn''t know how to do it with a large list.
for (int i=0; i<=MAPSIZE*2-1; i++){ if (i<MAPSIZE) { int minj=0; int maxj=i; } else { int minj=i; int maxj=i-MAPSIZE; } for (int j=minj; j<=maxj; j++) { paint(j, i-j); }} Of course, this only works if you have a grid with layers to put everything (I put my characters in their own layers into the grid.) I wouldn''t know how to do it with a large list.
Author
Hello,
To paint from back to front is OK and works for my ground tiles, however I''ve got even more tiles which are dynamically moving and so I need a kind of sorting, because all tiles end in one display list which has to be sorted.
Greetings.
To paint from back to front is OK and works for my ground tiles, however I''ve got even more tiles which are dynamically moving and so I need a kind of sorting, because all tiles end in one display list which has to be sorted.
Greetings.
Author
Hello,
thanks to your reply, and the reply of the other poster, too.
Probably I can''t use you line raster methode however, because I''ve got very many objects, many of them dynamically moving, so that the time needed to insert them into a line raster would be very high... Unfortunately I''ve to use a software solution, so O can''t use a real Z-Buffer.
Do you know David Braben''s game Zarch/Virus on the Amiga/Atari ST/Acorn Archimedes/PC ? He used a fixed 3d landscape which constisted of same sized tiles, and also moving objects. He must have had the same "problems" to sort them, like today Rollercoaster or that like has got.
Unfortunately I don''t know this solution yet. :-)
Greetings.
thanks to your reply, and the reply of the other poster, too.
Probably I can''t use you line raster methode however, because I''ve got very many objects, many of them dynamically moving, so that the time needed to insert them into a line raster would be very high... Unfortunately I''ve to use a software solution, so O can''t use a real Z-Buffer.
Do you know David Braben''s game Zarch/Virus on the Amiga/Atari ST/Acorn Archimedes/PC ? He used a fixed 3d landscape which constisted of same sized tiles, and also moving objects. He must have had the same "problems" to sort them, like today Rollercoaster or that like has got.
Unfortunately I don''t know this solution yet. :-)
Greetings.
Well, I''ve been able to sort _lots_ of objects at a time very quickly.
1) You sort all objects on screen as soon as you start, so you are starting with a pre-sorted doubly linked list. Each object points to the last thing behind it and the next thing in front of it.
class DrawObject
{
DrawObject *pLastDraw;
DrawOhject *pNextDraw;
}
2) Within each object, only when it changes location, you compare to the one behind it and the one in front and rearrange as necessary. Because most objects move small amounts at a time, you won''t actually be changing the order all the time.
3) You can also maintain a list of 10-20 pointers to get you to the approximately correct location when insertting new objects or when an object moves longe distances.
Rather than update these from within objects, just update 1 of them every frame, so the entire list gets updated every 10-20 frame. You don''t care that these are perfectly accurrate, just close.
DrawObject *pdoInsertionHelpers[20]; (0 is front of screen, 19 is rear)
The key is that you really shouldn''t need to re-sort the list every frame, just move a few things around in it. You can even sort only a portion of the list every frame, so that the whole list gets updated every 10-30 frames. This will lead to occassional artifacts, but very few.
hope this helps,
cheers,
mat williams
Lead Programmer, Designer
Zero Sum Software
www.zero-sum.com
1) You sort all objects on screen as soon as you start, so you are starting with a pre-sorted doubly linked list. Each object points to the last thing behind it and the next thing in front of it.
class DrawObject
{
DrawObject *pLastDraw;
DrawOhject *pNextDraw;
}
2) Within each object, only when it changes location, you compare to the one behind it and the one in front and rearrange as necessary. Because most objects move small amounts at a time, you won''t actually be changing the order all the time.
3) You can also maintain a list of 10-20 pointers to get you to the approximately correct location when insertting new objects or when an object moves longe distances.
Rather than update these from within objects, just update 1 of them every frame, so the entire list gets updated every 10-20 frame. You don''t care that these are perfectly accurrate, just close.
DrawObject *pdoInsertionHelpers[20]; (0 is front of screen, 19 is rear)
The key is that you really shouldn''t need to re-sort the list every frame, just move a few things around in it. You can even sort only a portion of the list every frame, so that the whole list gets updated every 10-30 frames. This will lead to occassional artifacts, but very few.
hope this helps,
cheers,
mat williams
Lead Programmer, Designer
Zero Sum Software
www.zero-sum.com
Author
Hello Mat,
thanks for the reply. Your suggestion could help, I'll have to check it.
Greetings.
Edited by - Faramir on August 6, 2001 11:49:44 AM
thanks for the reply. Your suggestion could help, I'll have to check it.
Greetings.
quote:Original post by Thathmew
Well, I've been able to sort _lots_ of objects at a time very quickly.
...
Edited by - Faramir on August 6, 2001 11:49:44 AM
Is the problem finding a good comparison function for sorting?
If you''re working in isometric 2D, here''s how I did it and it is fairly effective. It assumes the following fixed axis:
+z
|
|
/ \
/ \
+y +x
You need the screen bounding rect of each object and it''s depth.
The depth is the simply the sum of the world x,y,z coordinates.
Greater depth is closer to you. So you just check for overlap, then compare depths. Or just sort everything by depth.
You can, of course, do a lot more sophisticated sorting using bounding boxes, but I found this to work 99% of the time. You may have to weight the z a bit. Can be a bit of a problem with large flat objects, but solvable bye using their fartherest corner for comparision rather than their center.
cheers,
mat williams
Lead Programmer, Designer
Zero Sum Software
www.zero-sum.com
If you''re working in isometric 2D, here''s how I did it and it is fairly effective. It assumes the following fixed axis:
+z
|
|
/ \
/ \
+y +x
You need the screen bounding rect of each object and it''s depth.
The depth is the simply the sum of the world x,y,z coordinates.
Greater depth is closer to you. So you just check for overlap, then compare depths. Or just sort everything by depth.
You can, of course, do a lot more sophisticated sorting using bounding boxes, but I found this to work 99% of the time. You may have to weight the z a bit. Can be a bit of a problem with large flat objects, but solvable bye using their fartherest corner for comparision rather than their center.
cheers,
mat williams
Lead Programmer, Designer
Zero Sum Software
www.zero-sum.com
Author
Hallo,
Yes, the problem is to find a good comparison function, and then a quick way to sort.
My fixed axis are exactly like you printed it, and I''ve got quite some very large objects which seem to confuse the sorting order.
Your idea to "just" sort the overlaping ones I''ll have a look at. But mabye the large objects won''t allow this way. All the objects have got a bounding box and I think I''ll have to use this information (too).
The objects have got real 3d position internally and I didn''t get good results so far with no weighting sorting formula like x+y+z. For a nice quick heapsort I need such an unique value however, but something like z*1000+y*100+x doesn''t help much, either.
Furthermore typically I got between 4000-8000 objects on the screen, which means quite some stuff to sort. But because the screen''s scrolling and there are many movable objects on screen I tend to say that sorting every frame would be good.
It''s a bit of a dilemma.... :-)
Cheers.
Yes, the problem is to find a good comparison function, and then a quick way to sort.
My fixed axis are exactly like you printed it, and I''ve got quite some very large objects which seem to confuse the sorting order.
Your idea to "just" sort the overlaping ones I''ll have a look at. But mabye the large objects won''t allow this way. All the objects have got a bounding box and I think I''ll have to use this information (too).
The objects have got real 3d position internally and I didn''t get good results so far with no weighting sorting formula like x+y+z. For a nice quick heapsort I need such an unique value however, but something like z*1000+y*100+x doesn''t help much, either.
Furthermore typically I got between 4000-8000 objects on the screen, which means quite some stuff to sort. But because the screen''s scrolling and there are many movable objects on screen I tend to say that sorting every frame would be good.
It''s a bit of a dilemma.... :-)
Cheers.
quote:Original post by Thathmew
Is the problem finding a good comparison function for sorting?
Like I said earlier I don'' think you''ll really need to re-sort the entire screen every time. It shouldn''t be necessary if objects are grouped properly. Maybe using rows, so you have on screen a list of rows = screenheight / tileheight + some number to account for overdraw (objects that are high in the air, but who''s x,y is off screen).
Objects are placed into rows based on where their lowest pixel is.
Within a row objects are sorted left to right. The trick is that each row can encompass only a set range of z values. If an object''s Z is greater than the row it is in it gets pushed forward to the next row and so on. You do overlap detection only within rows as moving something between rows takes care of most occlusion problems.
You could probably start with you static objects pre sorted into these rows.
When moving up or down you can discard and add an entire row, left or right adds objects to the front or back of a row.
If you''re having problems with the x + y + z, rather than using x+y+z, use the converted screeny + z*constant to get depth, again greater depth = closer to camera. The more closely related your world x,y,z to pixels the easy this is. I assume you have a good routine to convert from world x,y,z to screen x,y.
When comparing to objects for depth sort if the objects don''t fit well within cubes, then they''re going to cause some issures regardless. But that being said:
If object A''s top bound (center + height/2) < B''s bottom bound(center- height-2) B is in front of A.
If object B''s top bound (center + height/2) < A''s bottom bound(center- height-2) A is in front of B.
Takes care of a surprising number of cases.
If neither of these is true the two object''s overlap.
Rather than look at their 3-D positions, look at their 2D,
i.e.
if A''s left pixel is left of B''s then if A''s front bound (center + depth/2) is greater then B''s front bound it is in front, if not in back.
Not too many checks.
blah, blah, blah,
-m
mat williams
Lead Programmer, Designer
Zero Sum Software
www.zero-sum.com
Objects are placed into rows based on where their lowest pixel is.
Within a row objects are sorted left to right. The trick is that each row can encompass only a set range of z values. If an object''s Z is greater than the row it is in it gets pushed forward to the next row and so on. You do overlap detection only within rows as moving something between rows takes care of most occlusion problems.
You could probably start with you static objects pre sorted into these rows.
When moving up or down you can discard and add an entire row, left or right adds objects to the front or back of a row.
If you''re having problems with the x + y + z, rather than using x+y+z, use the converted screeny + z*constant to get depth, again greater depth = closer to camera. The more closely related your world x,y,z to pixels the easy this is. I assume you have a good routine to convert from world x,y,z to screen x,y.
When comparing to objects for depth sort if the objects don''t fit well within cubes, then they''re going to cause some issures regardless. But that being said:
If object A''s top bound (center + height/2) < B''s bottom bound(center- height-2) B is in front of A.
If object B''s top bound (center + height/2) < A''s bottom bound(center- height-2) A is in front of B.
Takes care of a surprising number of cases.
If neither of these is true the two object''s overlap.
Rather than look at their 3-D positions, look at their 2D,
i.e.
if A''s left pixel is left of B''s then if A''s front bound (center + depth/2) is greater then B''s front bound it is in front, if not in back.
Not too many checks.
blah, blah, blah,
-m
mat williams
Lead Programmer, Designer
Zero Sum Software
www.zero-sum.com
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
