Archived

This topic is now archived and is closed to further replies.

EDI

My unsolvable problem

Recommended Posts

Greetings all, I have been working on a 2D Isometric game engine for quite some time now *2 years I guess* and I have been able to overcome every problem it''s development has thrown at me, except this one. I''ve looked in the history of this forum to find an answer to my problem but all the methods I saw didint seem to work for me. The problem is Large Sprites, a sprite that takes up 2x4 tiles or perhaps 5x3 tiles something large. when I place this sprite *i call it a structure* I must place it on a single tile, this is it''s anchor tile, and it''s the tile that draws the sprite, now i can set an anchor on the sprite itself to that it''s offset from this anchor tile any way i want, but i discoverd that no matter where i set this anchor to it always caused me overdraw issues, i though about this for a while and found this is due to the fact that only a single tile is drawing this large multi-tile sprite. i''m sure most of you know what im talking about, so here are a few solutions i found but didint work for me. Split the object into multiple structures: this didnt work since it would add alot of overhead to designing and making graphics for the game, plus it would mean for an interactive sprite (clickable) i would need multiple objects that all are technicly the same sprite, it would require a sizable re-work of my engine to make it work, this method is just too complex and thus i cant use it. Sort the objects so that they draw back to front: I tried this, i sorted them by Y then by X and it still didint work, it would work of the sprites occupied a square region of tiles, but not certain rectangles. so, ive been racking my brain for a while now and i cant come up with a solution, im about at the point to just leave the 2D engine as is and start a 3D one, but this would mean 50% of my work was a waste and the game ive been working to create will be delayed and the work ive done on it was a waste too. so please if anyone can help me i would be extreamly greatful, if there is anything you need me to provide you with just let me know. thank you all in advance Raymond Jacobs, www.EDIGames.com www.EtherealDarkness.com

Share this post


Link to post
Share on other sites
If it is a large "structure" and not an item,npc,pc etc, when you sort by the y value, couldn''t you just place "structures" at the end of the y sort?
like A,B,C,D,E and F all have the same y value, but C is a "structure", so sort it ABDEFC. Is that possible with your current setup?


Evillive2
E-Mail

Share this post


Link to post
Share on other sites
um, i dont think i understand what you mean.

this is an example of where sorting by Y fails





the grey area is the ''foot print'' of a structure

and the red dot within it marks it''s anchor tile

the yellow area is a sprite and the red dot is it''s anchor tile

if it is sorted by Y the sprite is drawn first then the structure is drawn over the sprite later =/

Raymond Jacobs,

www.EDIGames.com

www.EtherealDarkness.com

Share this post


Link to post
Share on other sites
This is one of those issues that i believe will unfortunately never be solved for solutions that use 2D APIs to render. In a solution that renders with a 3D API, this issue disappears, as the structure would be represented with a 3D model.

Share this post


Link to post
Share on other sites
Wouldn''t this work better if you used the point in the structure thats is the farthest back as the point that your drawing it from? ie. the highest point on the grey rect in your diagram, that would put it behind the sprite and anything else that is in front of it.. but I haven''t done this before so I''m probably missing something

Please visit Turt99 Productions

Share this post


Link to post
Share on other sites
Turt99:

thank you for your reply,
while in the above example that might fix things it''s not a flexable solution, since:





still wouldnt work =/


TANSTAAFL:

thanks for your reply,
yes that is what i feared, i guess i had better start learning to make 3DGames then eh?

it seems like this would be more common of a problem though, i wonder what other people do to get around this *other than what i have mentioned, since they dont sound like ''good'' solutions*



Raymond Jacobs,

www.EDIGames.com

www.EtherealDarkness.com

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:

This is one of those issues that i believe will unfortunately never be solved for solutions that use 2D APIs to render.



Unless the objects actually intersect, there is nothing to stop you from rendering them in the correct order.
The only restriction is that the objects must be convex, or at least "close to" convex... (if they are not, split them into parts that are)

The problem cannot be solved by sorting along any axis, instead you must compare each axis separately.

the rules are quite simple to figure out if you think about bounding boxes (pen and paper are your friends).

The exact rules depend on what your coordinate system looks like.

Share this post


Link to post
Share on other sites
Ah, dont switch to 3d because you cant solve a 2d layering problem without lots of work. Bah.

Now, I am not sure if I understand the problem correctly, but if I do:

This is a bit of a tricky problem you have on your hands though. I can think of a few more elegant solutions, but all of them would really cause a performance hit, and your drawing code for a 2d game like this is probobly already a bottleneck.

One possible solution might be to 'mark' all the tiles which a large multi-tile structure obscures. (using something like a linked list on every tile, the list would consist of links to structures that are obscuring that tile)

Then, you could go through and treat large multi-tile structures in a more sane way, and handle all the odd layering cases.
(as it would be possible to tell at a glance, what structures are drawn at any given tile)

Hope that helps somewhat.

[EDIT]
Note: I don't quite understand whats wrong with Turt99's solution. Your diagram doesnt seem to explain.

If the anchor is well choosen (as in your illustration), and structures stay fairly small (as in not dozens of tiles) then there should be no reason that what he is suggesting wouldnt work in all reasonable cases.
Maby i'm missing something?
[/EDIT]
- Jacob

[edited by - Kevlar-X on October 10, 2003 5:52:06 PM]

Share this post


Link to post
Share on other sites
No need to split the object. (Re-read my post to see what I mean).

What I am suggesting is, to simply indicate on every tile, what structures are obscuring it.
The structure would still be one image, and only exactly one structure would exist. The difference is, instead of only the anchor tile linking to the structure (or containing it) ... all obscured tiles would have a pointer to it.

Yea dig?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
What i ment is that if you have e.g a house, that is T-shaped, you need to split it, there is no way around it, im sure you''re aware of that already.

But say you have two objects A and B, with bounding boxes, you can determin the draw order by something like:

if(A.min.x>B.max.x || A.min.y>B.max.y || A.min.z>B.max.z){
render A, then B;
}else if(A.max.x<B.min.x || A.max.y<B.min.y || A.max.z<B.min.z){
render B, then A;
}else{
// objects overlap
// handle some other way
}

But like i said, this depends on how your coordinate system id defined.

Oh, and if the 2D bounding boxes of the two objects don''t overlapp, the order is irrelevant...

Share this post


Link to post
Share on other sites
As seen in this picture:




Why not simply sort based on which row(the ones defined by the lines going down the right side) they are on? Since the farther down the rows, the closer to the screen? This would put the sprite in front of the building, and I''m pretty sure you already have rows/columns support built into your engine(hopefully).

Jesus is Lord!!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
This page has some helpful hints.

http://www-cs-students.stanford.edu/~amitp/gameprog.html

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Rather than sorting by your Y screen coordinate, you should look at the both the X and Y map coordinates of the objects. You could draw ground tiles using an array, then create a list of structure and sprite overlays. Then sort that according to both the X and Y coordinates on the map - not the screen. For example, if an object is northeast of a structure on the map, it will be drawn before the structure.

I think that would work...

Share this post


Link to post
Share on other sites
Just one question. Instead of sorting by just X or just Y, have you tried sorting by X+Y? This results in a truer back-to-front ordering than X or Y alone.


X 0 1 2 3 4
Y
0 0 1 2 3 4
1 1 2 3 4 5
2 2 3 4 5 6 Comparison values for sorting back to front
3 3 4 5 6 7
4 4 5 6 7 8



In an isometric environment, this sorts values like this:


0
1 1
2 2 2
3 3 3 3
4 4 4 4 4
5 5 5 5
6 6 6
7 7
8



It might help you a little bit, anyway.



Josh
vertexnormal AT linuxmail DOT org


Check out Golem: Lands of Shadow, an isometrically rendered hack-and-slash inspired equally by Nethack and Diablo.

Share this post


Link to post
Share on other sites
thank you all for your replies,

vertexnormal:

just tried X+Y in my comparator

ac=ax+ay;
bc=bx+by;
if ( ac < bc )
{
return -1;
}
else if ( bc < ac )
{
return 1;
}
return 0;

didint work, actualy seemed to cause more harm then help

CD579:

i dont think that would work, especialy since your idea would favor row aligned drawing, would have to work the other way too.

Kevlar-X:

good idea, but I alredy thought of that, runtime spliting of the object isnt an option either since it would require to much rework to the engine.


I know it sounds like im just being stubborn, but the goal is to have a minimaly invasive solution, that doesnt complicate things.




Raymond Jacobs,

www.EDIGames.com

www.EtherealDarkness.com

Share this post


Link to post
Share on other sites
quote:
Original post by EDI
I know it sounds like im just being stubborn, but the goal is to have a minimaly invasive solution, that doesnt complicate things.



Then you should have spotted this during your requirments and/or design stage. If you''ve worked on this for 2 years and only just noticed this problem then thats just a total lack of foresight.

Its pretty unsolvable - by forcing yourself to a single anchor point for a large structure you''ve thrown away information. Your engine has no idea if its something vertical like a character or a tree (which would span lots of tiles, but not hide objects behind it) or something with depth which needs to obstruct other objects behind it (your building example).

Two ideas:
- Software depth map for each sprite. Could be tricky to create if your structures are hand drawn though.
- Split the structures into thin strips, each one tile wide and having a unique anchor point.

Share this post


Link to post
Share on other sites
I *think* I came up with a solution. Basically, place all anchors in the upper right hand corner of structures. Now render tiles row by row, always starting from the upper right. If you hit a anchor, don't render the structure and proceed to the next line. Whenever you hit an edge of a structure, skip to the next line. Once you skip to the line below the structure-stop. Render the structure and and start rendering from the top right side of the structure.

Here is the map I used:

  

upper right of isometric map


0 1 2 3 4 5 6 7 8 9 10 /
___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___
| | | | | | | | | | | |
0 | | | | | | S2| S2|S2A| | | |
|___|___|___|___|___|___|___|___|___|___|___|
| | | | | | | | | | | |
1 | | S0|S0A| | | S2| S2|S2 | | | |
|___|___|___|___|___|___|___|___|___|___|___|
| | | | | | | | | | | |
2 | | S0| S0| | | S2| S2| S2| | | |
|___|___|___|___|___|___|___|___|___|___|___|
| | | | | | | | | | | |
3 | | S0| S0| S1|S1A| | | | | | |
|___|___|___|___|___|___|___|___|___|___|___|
| | | | | | | | | | | |
4 | | | | S1| S1| | | | S3|S3A| |
|___|___|___|___|___|___|___|___|___|___|___|
| | | | | | | | | | | |
5 | | | | S1| S1| | | | S3| S3| |
|___|___|___|___|___|___|___|___|___|___|___|
| | | | | | | | | | | |
6 | | | | S1| S1| | | | | | |
|___|___|___|___|___|___|___|___|___|___|___|
| | | | | | | | | | | |
7 | | | | | | | | | | | |
|___|___|___|___|___|___|___|___|___|___|___|



Here is code illustrating this (using the map I just specified):
(Warning this is quick and dirty code - so its ugly in places)
(this code does compile if you want to try)


#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#include <conio.h>

#define WIDTH 11
#define HEIGHT 8

using namespace std;



struct Location
{
int Row;
int Col;
};



struct Structure
{
int Width;
int Height;
};


Structure Anchor[4] = { 2,3,
2,4,
3,3,
2,2 };

Structure *Map[HEIGHT][WIDTH] = {0};

int LastColRendered[HEIGHT+2] = {0};


int count = 0;
void RenderTile (int Row, int Col)
{

if (count == 10)
{
cout << endl;
count = 0;
}
cout << Row << "," << Col << " ";

++count;
}


void StructRender (Location Anchor, Structure Info,int Row)
{
int Col = LastColRendered[Row];

for (;;)
{
Col--;
while (Col < 0)
{
Row++;
if (Row >= HEIGHT)
{ break; }
Col = LastColRendered[Row] - 1;
}
if (Row >= HEIGHT)
{ break; }
if (Col <= Anchor.Col)
{
Col = 0;
continue;
}
if (Row >= Anchor.Row + Info.Height)
{ break; }
if (Map[Row][Col] == 0)
{
LastColRendered[Row] = Col;
RenderTile (Row, Col);
}
else
{
Location Anchor;
Anchor.Row = Row; Anchor.Col = Col;
StructRender (Anchor, *(Map[Row][Col]), Row + 1);
Col = LastColRendered[Row];
}
}

//Render the actual structure

cout << "\nRendering structure: " <<endl;
count = 0;
for (int i = 0; i < Info.Height; ++i)
{
for (int j = 0; j < Info.Width; ++j)
{
LastColRendered[Anchor.Row + i] = Anchor.Col - j;
RenderTile (Anchor.Row + i, Anchor.Col - j);
}
}
count = 0;

cout << "\nDone Rendering Structure: " <<endl;

}






int main()
{


memset (Map, 0, sizeof Map);
for (int i = 0; i < HEIGHT; ++i)
{ LastColRendered[i] = WIDTH; }

Map[1][2] = Anchor;
Map[3][4] = Anchor + 1;
Map[0][7] = Anchor + 2;
Map[4][9] = Anchor + 3;

int Row = 0;
int Col = LastColRendered[0];

for (;;)
{
--Col;
while (Col < 0 )
{
++Row;
if ( Row >= HEIGHT )
{
_getch();
return 0;
}
Col = LastColRendered[Row] - 1;
}
if ( Map[Row][Col] == 0)
{
RenderTile(Row,Col);
LastColRendered[Row] = Col;
}
else
{
Location Anchor;
Anchor.Row = Row; Anchor.Col = Col;
StructRender (Anchor, *(Map[Row][Col]), Row + 1);
Col = LastColRendered[Row];
}

}

_getch();
return 0;
}


This algorithms appears to work correctly. Here is how it renders the tiles:

0,10 0,9 0,8 1,10 1,9 1,8 2,10 2,9 2,8
Rendering structure:
0,7 0,6 0,5 1,7 1,6 1,5 2,7 2,6 2,5
Done Rendering Structure:
0,4 0,3 0,2 0,1 0,0 1,4 1,3 2,4 2,3 3,10
3,9 3,8 3,7 3,6 3,5 4,10 5,10
Rendering structure:
4,9 4,8 5,9 5,8
Done Rendering Structure:
4,7 4,6 4,5 5,7 5,6 5,5 6,10 6,9 6,8 6,7
6,6 6,5
Rendering structure:
3,4 3,3 4,4 4,3 5,4 5,3 6,4 6,3
Done Rendering Structure:

Rendering structure:
1,2 1,1 2,2 2,1 3,2 3,1
Done Rendering Structure:
1,0 2,0 3,0 4,2 4,1 4,0 5,2 5,1 5,0 6,2
6,1 6,0 7,10 7,9 7,8 7,7 7,6 7,5 7,4 7,3
7,2 7,1 7,0

The code can be condensed to be made smaller. I'm pretty sure the loop inside the main function can be eliminated and its functional ity put inside the StructureRender function with only a couple changes.
Like, I said, I *think* this works-maybe I'm missing something obvious about rendering in isometric. I had never done isometric tile rendering before. If I missed something, let me know, maybe I can still fix my algorithm.

edit: Trying to get the map to display correctly.

[edited by - CrazyMike on October 11, 2003 7:21:43 AM]

[edited by - CrazyMike on October 11, 2003 10:24:07 AM]

Share this post


Link to post
Share on other sites
hmm, maybe I'm missing something but it seems like a simple problem to me and so heres a simple solution.



You have you map:

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

0= empty tile

and your sturcture lets say it house:
! *
* *

! = the anchor point
* = the other squares


now when you try to place the house you simply check that tiles its going to be placed on are empty. Starting with the anchor point and then working your way out from its dimensions. If any of the tiles are occuiped you return a failure

placing the first house goes ok.
0 0 0 0 0
0 ! * 0 0
0 * * 0 0
0 0 0 0 0
0 0 0 0 0

but placing a second house causes a failure
! * 0 0 0
* X 1 0 0
0 1 1 0 0
0 0 0 0 0
0 0 0 0 0

X = unable to place
1 = occupied tile.



Does that solve your problem? Or did misunderstand what your looking for?

hmm if its just about drawing the sprite, then can't you simply draw all your structures last with their own rending loop?
-----------------------------------------------------
Writer, Programer, Cook, I'm a Jack of all Trades
Current Design project
Chaos Factor Design Document




[edited by - TechnoGoth on October 12, 2003 12:26:28 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by EDI
Thanks for your reply CrazyMike,

Ive yet to try and implement this, since your last edit seemed to imply that it doesnt work, is this true? or have you resloved the problem?

Raymond Jacobs,

www.EDIGames.com

www.EtherealDarkness.com




It works, I meant that that I was having trouble displaying the map
,that I ''drew'' in text, in message correctly because of spacing issues. Unless, I''m missing something I believe my solution will work.

Share this post


Link to post
Share on other sites
Instead of displaying the building when you display the ground tiles add the structure to the object list and display along with the objects.

This means you need two passes for the drawing (Pass 1 draw terrain, pass 2 draw objects). Objects are drawn from back to front (Ascending Y value).

In my solution each object has a placement X and Y as well as a map offset X and Y. The map offset is where it is drawn but the Placement X and Y are used for sorting (sort of represents the feet of an object). In your example the placement X and Y will be the top corner of the building, the map offset will be the top of the builiding. Sort by Placement Y and draw.

If you need an example I can create a quick Delphi program and send to you.

Share this post


Link to post
Share on other sites
Technogoth:
you missunderstood =)
the problem is not enforcing boundries but is having things larger than one tile drawing over things they shouldnt.

Crazymike:
i will work to implement it immediatly=)

cairnswm:
i already render in two passes, and have tried sorting,
so it''s really another problem all together.

Raymond Jacobs,

www.EDIGames.com

www.EtherealDarkness.com

Share this post


Link to post
Share on other sites
fortunatly for you, the problem is solvable.
the real problem is the comparison function,

first you must know if your sprite is single tile (ST) or multi-tile (MT).
next when comparing you have three situations:
1. MT (a) < MT (b) you compare anchor points
(a.y <= b.y || a.x < b.x)
2. MT < ST you compare world positions in reverse
!(ST world < MT world)
3. ST < MT this is the usual, (MT world < ST world)

ok, why do we do that:
I don''t remember all the details (I did it a long time ago),
but realize this; in isometric view an object is considered to be behind another object when its x,y positions in the tile map are smaller than the other (A.x < B.x && A.y < B.y).
however if you use only this comparison you may notice that you get the same result if you do A

Share this post


Link to post
Share on other sites