Mixing
How to layer objects - geometry?
$begingroup$
I'm developing a kind of perspective based 2d/3d game.
I've got an X- and an Y-axis like I've displayed in the image below.
To my question: I've got a bunch of objects (marked with "1" and "2") on my map with properties like:
- positionX / positionY
- sizeX / sizeY
In the image Object "1" does get the coordinates x:3, y:2, and the Object "2" does get the coordinates x:5, y:4. SizeX and sizeY is w:1, h:1 for both objects.
What I'd like to do with this info is to sort all of the objects in ascending order (based on the objects position and size) to know in 3d which objects comes for another object.
Note: The Camera has to fixed position - lets say the camera has the identical X and Y value so that the camera position must not be used while calculation CameraX = CameraY.
What I've tried so far:
define objects = [
{
name: "objectA",
x: 8,
y: 12,
w: 2,
h: 2
},
{
name: "objectB",
x: 3,
y: 5,
w: 2,
h: 2
},
{
name: "objectC",
x: 6,
y: 2,
w: 1,
h: 3
}
]
method sort (a, b)
define distanceA = sqrt(a.x**2 + a.y**2)
define distanceB = sqrt(a.x**2 + a.y**2)
return distanceA - distanceB;
I've tried to sort the objects based on their x/y coordinate but it seems like the width and height parameter must be used also while calculation to avoid errors.
How do I have to make use of width/height?
Tbh I've got no clue so any help would be really appreciated.
geometry euclidean-geometry 3d
asked Jan 19 at 10:55
jonas00jonas00
1185
$endgroup$
add a comment |
$begingroup$
I'm developing a kind of perspective based 2d/3d game.
I've got an X- and an Y-axis like I've displayed in the image below.
To my question: I've got a bunch of objects (marked with "1" and "2") on my map with properties like:
- positionX / positionY
- sizeX / sizeY
In the image Object "1" does get the coordinates x:3, y:2, and the Object "2" does get the coordinates x:5, y:4. SizeX and sizeY is w:1, h:1 for both objects.
What I'd like to do with this info is to sort all of the objects in ascending order (based on the objects position and size) to know in 3d which objects comes for another object.
Note: The Camera has to fixed position - lets say the camera has the identical X and Y value so that the camera position must not be used while calculation CameraX = CameraY.
What I've tried so far:
define objects = [
{
name: "objectA",
x: 8,
y: 12,
w: 2,
h: 2
},
{
name: "objectB",
x: 3,
y: 5,
w: 2,
h: 2
},
{
name: "objectC",
x: 6,
y: 2,
w: 1,
h: 3
}
]
method sort (a, b)
define distanceA = sqrt(a.x**2 + a.y**2)
define distanceB = sqrt(a.x**2 + a.y**2)
return distanceA - distanceB;
I've tried to sort the objects based on their x/y coordinate but it seems like the width and height parameter must be used also while calculation to avoid errors.
How do I have to make use of width/height?
Tbh I've got no clue so any help would be really appreciated.
geometry euclidean-geometry 3d
asked Jan 19 at 10:55
jonas00jonas00
1185
$endgroup$
$begingroup$
Game theory here is not about games devolloping, i think you can be answered but also would try stack overflow (if not mistaken about which site is for programming questions)
$endgroup$
– Daniel Moraes
Jan 19 at 10:57
$begingroup$
Oh this is a meaner one than I expected now that I think about it. I know it's not: location of front corner, location of back corner, location of center (consider a 1x1 in front of the backmost tile of a 1x4). You might get good results getting partial orderings by sweeping down diagonals and using a topological sort.
$endgroup$
– Dan Uznanski
Jan 19 at 11:17
$begingroup$
Thanks for your answer. To be honest, I don't really know how to install a topological sort. Would you be kind enough to post some kind of pseudo code or at least a formula? Many thanks in advance :) @DanUznanski
$endgroup$
– jonas00
Jan 19 at 11:19
$begingroup$
Oh, important question: are your objects densely packed? It occurs to me that the answer is usually yes (as it is in, say, ottd or SimCity or old xcom or civ2) but your data isn't. This is important because for densely packed objects, the generic method is very inefficient but there are greater efficiencies we can get from knowledge of the structure)
$endgroup$
– Dan Uznanski
Jan 19 at 11:55
$begingroup$
Oh ok. Hmhm yeah I would say there is a densely packed object-structure on my map. But we talk about maybe 100 objects not more. So efficieny is no important point in my case - I just need a working method :) @DanUznanski
$endgroup$
– jonas00
Jan 19 at 11:58
add a comment |
$begingroup$
I'm developing a kind of perspective based 2d/3d game.
I've got an X- and an Y-axis like I've displayed in the image below.
To my question: I've got a bunch of objects (marked with "1" and "2") on my map with properties like:
- positionX / positionY
- sizeX / sizeY
In the image Object "1" does get the coordinates x:3, y:2, and the Object "2" does get the coordinates x:5, y:4. SizeX and sizeY is w:1, h:1 for both objects.
What I'd like to do with this info is to sort all of the objects in ascending order (based on the objects position and size) to know in 3d which objects comes for another object.
Note: The Camera has to fixed position - lets say the camera has the identical X and Y value so that the camera position must not be used while calculation CameraX = CameraY.
What I've tried so far:
define objects = [
{
name: "objectA",
x: 8,
y: 12,
w: 2,
h: 2
},
{
name: "objectB",
x: 3,
y: 5,
w: 2,
h: 2
},
{
name: "objectC",
x: 6,
y: 2,
w: 1,
h: 3
}
]
method sort (a, b)
define distanceA = sqrt(a.x**2 + a.y**2)
define distanceB = sqrt(a.x**2 + a.y**2)
return distanceA - distanceB;
I've tried to sort the objects based on their x/y coordinate but it seems like the width and height parameter must be used also while calculation to avoid errors.
How do I have to make use of width/height?
Tbh I've got no clue so any help would be really appreciated.
geometry euclidean-geometry 3d
asked Jan 19 at 10:55
jonas00jonas00
1185
$endgroup$
I'm developing a kind of perspective based 2d/3d game.
I've got an X- and an Y-axis like I've displayed in the image below.
To my question: I've got a bunch of objects (marked with "1" and "2") on my map with properties like:
- positionX / positionY
- sizeX / sizeY
In the image Object "1" does get the coordinates x:3, y:2, and the Object "2" does get the coordinates x:5, y:4. SizeX and sizeY is w:1, h:1 for both objects.
What I'd like to do with this info is to sort all of the objects in ascending order (based on the objects position and size) to know in 3d which objects comes for another object.
Note: The Camera has to fixed position - lets say the camera has the identical X and Y value so that the camera position must not be used while calculation CameraX = CameraY.
What I've tried so far:
define objects = [
{
name: "objectA",
x: 8,
y: 12,
w: 2,
h: 2
},
{
name: "objectB",
x: 3,
y: 5,
w: 2,
h: 2
},
{
name: "objectC",
x: 6,
y: 2,
w: 1,
h: 3
}
]
method sort (a, b)
define distanceA = sqrt(a.x**2 + a.y**2)
define distanceB = sqrt(a.x**2 + a.y**2)
return distanceA - distanceB;
I've tried to sort the objects based on their x/y coordinate but it seems like the width and height parameter must be used also while calculation to avoid errors.
How do I have to make use of width/height?
Tbh I've got no clue so any help would be really appreciated.
geometry euclidean-geometry 3d
geometry euclidean-geometry 3d
asked Jan 19 at 10:55
jonas00jonas00
1185
asked Jan 19 at 10:55
jonas00jonas00
1185
edited Jan 19 at 10:58
jonas00
asked Jan 19 at 10:55
jonas00jonas00
1185
asked Jan 19 at 10:55
jonas00jonas00
1185
asked Jan 19 at 10:55
jonas00jonas00
1185
1185
$begingroup$
Game theory here is not about games devolloping, i think you can be answered but also would try stack overflow (if not mistaken about which site is for programming questions)
$endgroup$
– Daniel Moraes
Jan 19 at 10:57
$begingroup$
Oh this is a meaner one than I expected now that I think about it. I know it's not: location of front corner, location of back corner, location of center (consider a 1x1 in front of the backmost tile of a 1x4). You might get good results getting partial orderings by sweeping down diagonals and using a topological sort.
$endgroup$
– Dan Uznanski
Jan 19 at 11:17
$begingroup$
Thanks for your answer. To be honest, I don't really know how to install a topological sort. Would you be kind enough to post some kind of pseudo code or at least a formula? Many thanks in advance :) @DanUznanski
$endgroup$
– jonas00
Jan 19 at 11:19
$begingroup$
Oh, important question: are your objects densely packed? It occurs to me that the answer is usually yes (as it is in, say, ottd or SimCity or old xcom or civ2) but your data isn't. This is important because for densely packed objects, the generic method is very inefficient but there are greater efficiencies we can get from knowledge of the structure)
$endgroup$
– Dan Uznanski
Jan 19 at 11:55
$begingroup$
Oh ok. Hmhm yeah I would say there is a densely packed object-structure on my map. But we talk about maybe 100 objects not more. So efficieny is no important point in my case - I just need a working method :) @DanUznanski
$endgroup$
– jonas00
Jan 19 at 11:58
add a comment |
$begingroup$
Game theory here is not about games devolloping, i think you can be answered but also would try stack overflow (if not mistaken about which site is for programming questions)
$endgroup$
– Daniel Moraes
Jan 19 at 10:57
$begingroup$
Oh this is a meaner one than I expected now that I think about it. I know it's not: location of front corner, location of back corner, location of center (consider a 1x1 in front of the backmost tile of a 1x4). You might get good results getting partial orderings by sweeping down diagonals and using a topological sort.
$endgroup$
– Dan Uznanski
Jan 19 at 11:17
$begingroup$
Thanks for your answer. To be honest, I don't really know how to install a topological sort. Would you be kind enough to post some kind of pseudo code or at least a formula? Many thanks in advance :) @DanUznanski
$endgroup$
– jonas00
Jan 19 at 11:19
$begingroup$
Oh, important question: are your objects densely packed? It occurs to me that the answer is usually yes (as it is in, say, ottd or SimCity or old xcom or civ2) but your data isn't. This is important because for densely packed objects, the generic method is very inefficient but there are greater efficiencies we can get from knowledge of the structure)
$endgroup$
– Dan Uznanski
Jan 19 at 11:55
$begingroup$
Oh ok. Hmhm yeah I would say there is a densely packed object-structure on my map. But we talk about maybe 100 objects not more. So efficieny is no important point in my case - I just need a working method :) @DanUznanski
$endgroup$
– jonas00
Jan 19 at 11:58
$begingroup$
Game theory here is not about games devolloping, i think you can be answered but also would try stack overflow (if not mistaken about which site is for programming questions)
$endgroup$
– Daniel Moraes
Jan 19 at 10:57
$begingroup$
Game theory here is not about games devolloping, i think you can be answered but also would try stack overflow (if not mistaken about which site is for programming questions)
$endgroup$
– Daniel Moraes
Jan 19 at 10:57
$begingroup$
Oh this is a meaner one than I expected now that I think about it. I know it's not: location of front corner, location of back corner, location of center (consider a 1x1 in front of the backmost tile of a 1x4). You might get good results getting partial orderings by sweeping down diagonals and using a topological sort.
$endgroup$
– Dan Uznanski
Jan 19 at 11:17
$begingroup$
Oh this is a meaner one than I expected now that I think about it. I know it's not: location of front corner, location of back corner, location of center (consider a 1x1 in front of the backmost tile of a 1x4). You might get good results getting partial orderings by sweeping down diagonals and using a topological sort.
$endgroup$
– Dan Uznanski
Jan 19 at 11:17
$begingroup$
Thanks for your answer. To be honest, I don't really know how to install a topological sort. Would you be kind enough to post some kind of pseudo code or at least a formula? Many thanks in advance :) @DanUznanski
$endgroup$
– jonas00
Jan 19 at 11:19
$begingroup$
Thanks for your answer. To be honest, I don't really know how to install a topological sort. Would you be kind enough to post some kind of pseudo code or at least a formula? Many thanks in advance :) @DanUznanski
$endgroup$
– jonas00
Jan 19 at 11:19
$begingroup$
Oh, important question: are your objects densely packed? It occurs to me that the answer is usually yes (as it is in, say, ottd or SimCity or old xcom or civ2) but your data isn't. This is important because for densely packed objects, the generic method is very inefficient but there are greater efficiencies we can get from knowledge of the structure)
$endgroup$
– Dan Uznanski
Jan 19 at 11:55
$begingroup$
Oh, important question: are your objects densely packed? It occurs to me that the answer is usually yes (as it is in, say, ottd or SimCity or old xcom or civ2) but your data isn't. This is important because for densely packed objects, the generic method is very inefficient but there are greater efficiencies we can get from knowledge of the structure)
$endgroup$
– Dan Uznanski
Jan 19 at 11:55
$begingroup$
Oh ok. Hmhm yeah I would say there is a densely packed object-structure on my map. But we talk about maybe 100 objects not more. So efficieny is no important point in my case - I just need a working method :) @DanUznanski
$endgroup$
– jonas00
Jan 19 at 11:58
$begingroup$
Oh ok. Hmhm yeah I would say there is a densely packed object-structure on my map. But we talk about maybe 100 objects not more. So efficieny is no important point in my case - I just need a working method :) @DanUznanski
$endgroup$
– jonas00
Jan 19 at 11:58
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The strategy is simple: we will figure out what things are in front of what other things, and then set the order based on that. The latter is called topological sorting, and it's a powerful tool, and a simple one too.
I present two methods, each suitable for a different set of assumptions about the set of entities we are sorting.
Sparse entities
In this method, the entities do not fill the map; it is in general not true that we can travel "upward" through adjacent entities to find all entities that any particular entity is in front of.
First, for each object, we must find the left and right extents of the entity. These are, using the layout in your image, $(x-y-h, x+w-y)$. We will store these two extents, and the corresponding object, in a list.
(this code is in Python; I don't recognize your programming language so I couldn't code in it)
entity_extents =
for e in tile_entities:
entity_extents.append(((e.x-e.y-e.h, e.x+e.w-e.y), e))
We'll sort these by the left end.
entity_extents.sort(key=lambda x: x[0][0])
Now, we must examine each entity in turn: we have to find things that it's actually in front of or behind. Since they're already sorted by the left end, we'll check it against things further to the left that we haven't gotten past. To do this, we'll keep a list of things that are to the left of whereever we hare, sorted by the right end. As we do this we'll drop things out of the list that are no longer useful, because their right end doesn't extend past the left end of the thing we're looking at.
digraph = {}
leftward_entities =
for e in entity_extents:
left_h = e[0][0]
for n,le in enumerate(leftward_entities):
if le[0][1] > left_h: # we've found one to the right of what we have, so that one and everything further gets to live.
del(leftward_entities[:n])
break
else:
leftward_entities.clear() # everything's to the left. Nothing remains.
Now we figure out, for each remaining leftward entity, whether it's in front of or behind our current entity. For this, we'll find the vertical location of the left end of our current entity, and the vertical location of the topmost portion of each leftward entity at the same horizontal location as the left end of the current entity.
e_node = (set(), set())
digraph[e[1]] = e_node
left_v = e[1].x + e[1].y + e[1].h
for le in leftward_entities:
l_node = digraph[le]
target_top_h = le[1].x - le[1].y
target_left_v = le[1].x + le[1].y + abs(left_h - target_top_h)
if target_left_v < left_v:
l_node[1].add(e[1])
e_node[0].add(l[1])
else:
l_node[0].add(e[1])
e_node[1].add(l[1])
And finally we need to insert the current entity into the leftwards, based on the right end:
right_h = e[0][1]
for n,le in enumerate(leftward_entities):
if le[0][1] > right_h:
leftward_entities.insert(n,e)
break
else:
leftward_entities.append(e)
From here, we proceed to topological sorting.
Dense objects
The more common setup, the grid is filled with entities. if an entity can be considered behind another, they are connected by a whole path of entities behind one another that are also adjacent.
The strategy is vastly different: we'll just fill in the grid with entities...
entity_grid = {}
for e in tile_entities:
for u in range(e.x, e.x + e.w): # not all the way though. we don't care about the middles of buildings.
entity_grid[(u, e.y)] = e
entity_grid[(u, e.y + e.h - 1)] = e
for v in range(e.y, e.y + e.h):
entity_grid[(e.x, v)] = e
entity_grid[(e.x + e.w - 1)] = e
...and then look around the outside of each entity for other entities.
digraph[e] = {}
for e in tile_entities:
e_node = (set(), set())
for u in range(e.x, e.x + e.w):
if (u, e.y-1) in entity_grid:
e_node[0].add(entity_grid[(u, e.y-1)])
if (u, e.y+e.h) in entity_grid:
e_node[1].add(entity_grid[(u, e.y+e.h)])
for v in range(e.y, e.y + e.h):
if (e.x-1, v) in entity_grid:
e_node[0].add(entity_grid[(e.x-1, v)])
if (e.x+e.w, v) in entity_grid:
e_node[1].add(entity_grid[(e.x+e.w, v)])
And now proceed with topological sorting.
Topological sorting
Having built our digraph, we can actually sort things.
Each node in the digraph has to know two things: which things precede it, and which things follow it. In this, I've arranged so that the predecessors of an element e are in the set digraph[e][0], and its successors are in digraph[e][1].
First things first, we need to find all the entries in the digraph that have no predecessors: these are the ones that are near the very back.
itinerary = set()
for entity, (predecessors, _) in digraph.items():
if not predecessors:
itinerary.add(entity)
Now, we add these to our final sequence one at a time, while cutting its connections with its successors. Every time we end up with a former successor that has no still-connected predecessors, we add it to the pile to examine.
sorted_pile =
while itinerary:
entity = itinerary.pop()
sorted_pile.append(entity)
successors = digraph[entity][1]
for succ in successors:
digraph[succ][0].remove(entity)
if not digraph[succ][0]:
itinerary.add(succ)
return sorted_pile
And ... that's it! sorted_pile now obeys the back-to-front ordering you need to draw things correctly.
answered Jan 19 at 20:29
Dan UznanskiDan Uznanski
6,90021528
$endgroup$
$begingroup$
Would you mind to share your full source code? I'm absolutely clueless how to proceed tbh - you're approach is still not working for me. Thanks in advance :)
$endgroup$
– jonas00
Jan 27 at 20:34
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3079224%2fhow-to-layer-objects-geometry%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The strategy is simple: we will figure out what things are in front of what other things, and then set the order based on that. The latter is called topological sorting, and it's a powerful tool, and a simple one too.
I present two methods, each suitable for a different set of assumptions about the set of entities we are sorting.
Sparse entities
In this method, the entities do not fill the map; it is in general not true that we can travel "upward" through adjacent entities to find all entities that any particular entity is in front of.
First, for each object, we must find the left and right extents of the entity. These are, using the layout in your image, $(x-y-h, x+w-y)$. We will store these two extents, and the corresponding object, in a list.
(this code is in Python; I don't recognize your programming language so I couldn't code in it)
entity_extents =
for e in tile_entities:
entity_extents.append(((e.x-e.y-e.h, e.x+e.w-e.y), e))
We'll sort these by the left end.
entity_extents.sort(key=lambda x: x[0][0])
Now, we must examine each entity in turn: we have to find things that it's actually in front of or behind. Since they're already sorted by the left end, we'll check it against things further to the left that we haven't gotten past. To do this, we'll keep a list of things that are to the left of whereever we hare, sorted by the right end. As we do this we'll drop things out of the list that are no longer useful, because their right end doesn't extend past the left end of the thing we're looking at.
digraph = {}
leftward_entities =
for e in entity_extents:
left_h = e[0][0]
for n,le in enumerate(leftward_entities):
if le[0][1] > left_h: # we've found one to the right of what we have, so that one and everything further gets to live.
del(leftward_entities[:n])
break
else:
leftward_entities.clear() # everything's to the left. Nothing remains.
Now we figure out, for each remaining leftward entity, whether it's in front of or behind our current entity. For this, we'll find the vertical location of the left end of our current entity, and the vertical location of the topmost portion of each leftward entity at the same horizontal location as the left end of the current entity.
e_node = (set(), set())
digraph[e[1]] = e_node
left_v = e[1].x + e[1].y + e[1].h
for le in leftward_entities:
l_node = digraph[le]
target_top_h = le[1].x - le[1].y
target_left_v = le[1].x + le[1].y + abs(left_h - target_top_h)
if target_left_v < left_v:
l_node[1].add(e[1])
e_node[0].add(l[1])
else:
l_node[0].add(e[1])
e_node[1].add(l[1])
And finally we need to insert the current entity into the leftwards, based on the right end:
right_h = e[0][1]
for n,le in enumerate(leftward_entities):
if le[0][1] > right_h:
leftward_entities.insert(n,e)
break
else:
leftward_entities.append(e)
From here, we proceed to topological sorting.
Dense objects
The more common setup, the grid is filled with entities. if an entity can be considered behind another, they are connected by a whole path of entities behind one another that are also adjacent.
The strategy is vastly different: we'll just fill in the grid with entities...
entity_grid = {}
for e in tile_entities:
for u in range(e.x, e.x + e.w): # not all the way though. we don't care about the middles of buildings.
entity_grid[(u, e.y)] = e
entity_grid[(u, e.y + e.h - 1)] = e
for v in range(e.y, e.y + e.h):
entity_grid[(e.x, v)] = e
entity_grid[(e.x + e.w - 1)] = e
...and then look around the outside of each entity for other entities.
digraph[e] = {}
for e in tile_entities:
e_node = (set(), set())
for u in range(e.x, e.x + e.w):
if (u, e.y-1) in entity_grid:
e_node[0].add(entity_grid[(u, e.y-1)])
if (u, e.y+e.h) in entity_grid:
e_node[1].add(entity_grid[(u, e.y+e.h)])
for v in range(e.y, e.y + e.h):
if (e.x-1, v) in entity_grid:
e_node[0].add(entity_grid[(e.x-1, v)])
if (e.x+e.w, v) in entity_grid:
e_node[1].add(entity_grid[(e.x+e.w, v)])
And now proceed with topological sorting.
Topological sorting
Having built our digraph, we can actually sort things.
Each node in the digraph has to know two things: which things precede it, and which things follow it. In this, I've arranged so that the predecessors of an element e are in the set digraph[e][0], and its successors are in digraph[e][1].
First things first, we need to find all the entries in the digraph that have no predecessors: these are the ones that are near the very back.
itinerary = set()
for entity, (predecessors, _) in digraph.items():
if not predecessors:
itinerary.add(entity)
Now, we add these to our final sequence one at a time, while cutting its connections with its successors. Every time we end up with a former successor that has no still-connected predecessors, we add it to the pile to examine.
sorted_pile =
while itinerary:
entity = itinerary.pop()
sorted_pile.append(entity)
successors = digraph[entity][1]
for succ in successors:
digraph[succ][0].remove(entity)
if not digraph[succ][0]:
itinerary.add(succ)
return sorted_pile
And ... that's it! sorted_pile now obeys the back-to-front ordering you need to draw things correctly.
answered Jan 19 at 20:29
Dan UznanskiDan Uznanski
6,90021528
$endgroup$
$begingroup$
Would you mind to share your full source code? I'm absolutely clueless how to proceed tbh - you're approach is still not working for me. Thanks in advance :)
$endgroup$
– jonas00
Jan 27 at 20:34
add a comment |
$begingroup$
The strategy is simple: we will figure out what things are in front of what other things, and then set the order based on that. The latter is called topological sorting, and it's a powerful tool, and a simple one too.
I present two methods, each suitable for a different set of assumptions about the set of entities we are sorting.
Sparse entities
In this method, the entities do not fill the map; it is in general not true that we can travel "upward" through adjacent entities to find all entities that any particular entity is in front of.
First, for each object, we must find the left and right extents of the entity. These are, using the layout in your image, $(x-y-h, x+w-y)$. We will store these two extents, and the corresponding object, in a list.
(this code is in Python; I don't recognize your programming language so I couldn't code in it)
entity_extents =
for e in tile_entities:
entity_extents.append(((e.x-e.y-e.h, e.x+e.w-e.y), e))
We'll sort these by the left end.
entity_extents.sort(key=lambda x: x[0][0])
Now, we must examine each entity in turn: we have to find things that it's actually in front of or behind. Since they're already sorted by the left end, we'll check it against things further to the left that we haven't gotten past. To do this, we'll keep a list of things that are to the left of whereever we hare, sorted by the right end. As we do this we'll drop things out of the list that are no longer useful, because their right end doesn't extend past the left end of the thing we're looking at.
digraph = {}
leftward_entities =
for e in entity_extents:
left_h = e[0][0]
for n,le in enumerate(leftward_entities):
if le[0][1] > left_h: # we've found one to the right of what we have, so that one and everything further gets to live.
del(leftward_entities[:n])
break
else:
leftward_entities.clear() # everything's to the left. Nothing remains.
Now we figure out, for each remaining leftward entity, whether it's in front of or behind our current entity. For this, we'll find the vertical location of the left end of our current entity, and the vertical location of the topmost portion of each leftward entity at the same horizontal location as the left end of the current entity.
e_node = (set(), set())
digraph[e[1]] = e_node
left_v = e[1].x + e[1].y + e[1].h
for le in leftward_entities:
l_node = digraph[le]
target_top_h = le[1].x - le[1].y
target_left_v = le[1].x + le[1].y + abs(left_h - target_top_h)
if target_left_v < left_v:
l_node[1].add(e[1])
e_node[0].add(l[1])
else:
l_node[0].add(e[1])
e_node[1].add(l[1])
And finally we need to insert the current entity into the leftwards, based on the right end:
right_h = e[0][1]
for n,le in enumerate(leftward_entities):
if le[0][1] > right_h:
leftward_entities.insert(n,e)
break
else:
leftward_entities.append(e)
From here, we proceed to topological sorting.
Dense objects
The more common setup, the grid is filled with entities. if an entity can be considered behind another, they are connected by a whole path of entities behind one another that are also adjacent.
The strategy is vastly different: we'll just fill in the grid with entities...
entity_grid = {}
for e in tile_entities:
for u in range(e.x, e.x + e.w): # not all the way though. we don't care about the middles of buildings.
entity_grid[(u, e.y)] = e
entity_grid[(u, e.y + e.h - 1)] = e
for v in range(e.y, e.y + e.h):
entity_grid[(e.x, v)] = e
entity_grid[(e.x + e.w - 1)] = e
...and then look around the outside of each entity for other entities.
digraph[e] = {}
for e in tile_entities:
e_node = (set(), set())
for u in range(e.x, e.x + e.w):
if (u, e.y-1) in entity_grid:
e_node[0].add(entity_grid[(u, e.y-1)])
if (u, e.y+e.h) in entity_grid:
e_node[1].add(entity_grid[(u, e.y+e.h)])
for v in range(e.y, e.y + e.h):
if (e.x-1, v) in entity_grid:
e_node[0].add(entity_grid[(e.x-1, v)])
if (e.x+e.w, v) in entity_grid:
e_node[1].add(entity_grid[(e.x+e.w, v)])
And now proceed with topological sorting.
Topological sorting
Having built our digraph, we can actually sort things.
Each node in the digraph has to know two things: which things precede it, and which things follow it. In this, I've arranged so that the predecessors of an element e are in the set digraph[e][0], and its successors are in digraph[e][1].
First things first, we need to find all the entries in the digraph that have no predecessors: these are the ones that are near the very back.
itinerary = set()
for entity, (predecessors, _) in digraph.items():
if not predecessors:
itinerary.add(entity)
Now, we add these to our final sequence one at a time, while cutting its connections with its successors. Every time we end up with a former successor that has no still-connected predecessors, we add it to the pile to examine.
sorted_pile =
while itinerary:
entity = itinerary.pop()
sorted_pile.append(entity)
successors = digraph[entity][1]
for succ in successors:
digraph[succ][0].remove(entity)
if not digraph[succ][0]:
itinerary.add(succ)
return sorted_pile
And ... that's it! sorted_pile now obeys the back-to-front ordering you need to draw things correctly.
answered Jan 19 at 20:29
Dan UznanskiDan Uznanski
6,90021528
$endgroup$
$begingroup$
Would you mind to share your full source code? I'm absolutely clueless how to proceed tbh - you're approach is still not working for me. Thanks in advance :)
$endgroup$
– jonas00
Jan 27 at 20:34
add a comment |
$begingroup$
The strategy is simple: we will figure out what things are in front of what other things, and then set the order based on that. The latter is called topological sorting, and it's a powerful tool, and a simple one too.
I present two methods, each suitable for a different set of assumptions about the set of entities we are sorting.
Sparse entities
In this method, the entities do not fill the map; it is in general not true that we can travel "upward" through adjacent entities to find all entities that any particular entity is in front of.
First, for each object, we must find the left and right extents of the entity. These are, using the layout in your image, $(x-y-h, x+w-y)$. We will store these two extents, and the corresponding object, in a list.
(this code is in Python; I don't recognize your programming language so I couldn't code in it)
entity_extents =
for e in tile_entities:
entity_extents.append(((e.x-e.y-e.h, e.x+e.w-e.y), e))
We'll sort these by the left end.
entity_extents.sort(key=lambda x: x[0][0])
Now, we must examine each entity in turn: we have to find things that it's actually in front of or behind. Since they're already sorted by the left end, we'll check it against things further to the left that we haven't gotten past. To do this, we'll keep a list of things that are to the left of whereever we hare, sorted by the right end. As we do this we'll drop things out of the list that are no longer useful, because their right end doesn't extend past the left end of the thing we're looking at.
digraph = {}
leftward_entities =
for e in entity_extents:
left_h = e[0][0]
for n,le in enumerate(leftward_entities):
if le[0][1] > left_h: # we've found one to the right of what we have, so that one and everything further gets to live.
del(leftward_entities[:n])
break
else:
leftward_entities.clear() # everything's to the left. Nothing remains.
Now we figure out, for each remaining leftward entity, whether it's in front of or behind our current entity. For this, we'll find the vertical location of the left end of our current entity, and the vertical location of the topmost portion of each leftward entity at the same horizontal location as the left end of the current entity.
e_node = (set(), set())
digraph[e[1]] = e_node
left_v = e[1].x + e[1].y + e[1].h
for le in leftward_entities:
l_node = digraph[le]
target_top_h = le[1].x - le[1].y
target_left_v = le[1].x + le[1].y + abs(left_h - target_top_h)
if target_left_v < left_v:
l_node[1].add(e[1])
e_node[0].add(l[1])
else:
l_node[0].add(e[1])
e_node[1].add(l[1])
And finally we need to insert the current entity into the leftwards, based on the right end:
right_h = e[0][1]
for n,le in enumerate(leftward_entities):
if le[0][1] > right_h:
leftward_entities.insert(n,e)
break
else:
leftward_entities.append(e)
From here, we proceed to topological sorting.
Dense objects
The more common setup, the grid is filled with entities. if an entity can be considered behind another, they are connected by a whole path of entities behind one another that are also adjacent.
The strategy is vastly different: we'll just fill in the grid with entities...
entity_grid = {}
for e in tile_entities:
for u in range(e.x, e.x + e.w): # not all the way though. we don't care about the middles of buildings.
entity_grid[(u, e.y)] = e
entity_grid[(u, e.y + e.h - 1)] = e
for v in range(e.y, e.y + e.h):
entity_grid[(e.x, v)] = e
entity_grid[(e.x + e.w - 1)] = e
...and then look around the outside of each entity for other entities.
digraph[e] = {}
for e in tile_entities:
e_node = (set(), set())
for u in range(e.x, e.x + e.w):
if (u, e.y-1) in entity_grid:
e_node[0].add(entity_grid[(u, e.y-1)])
if (u, e.y+e.h) in entity_grid:
e_node[1].add(entity_grid[(u, e.y+e.h)])
for v in range(e.y, e.y + e.h):
if (e.x-1, v) in entity_grid:
e_node[0].add(entity_grid[(e.x-1, v)])
if (e.x+e.w, v) in entity_grid:
e_node[1].add(entity_grid[(e.x+e.w, v)])
And now proceed with topological sorting.
Topological sorting
Having built our digraph, we can actually sort things.
Each node in the digraph has to know two things: which things precede it, and which things follow it. In this, I've arranged so that the predecessors of an element e are in the set digraph[e][0], and its successors are in digraph[e][1].
First things first, we need to find all the entries in the digraph that have no predecessors: these are the ones that are near the very back.
itinerary = set()
for entity, (predecessors, _) in digraph.items():
if not predecessors:
itinerary.add(entity)
Now, we add these to our final sequence one at a time, while cutting its connections with its successors. Every time we end up with a former successor that has no still-connected predecessors, we add it to the pile to examine.
sorted_pile =
while itinerary:
entity = itinerary.pop()
sorted_pile.append(entity)
successors = digraph[entity][1]
for succ in successors:
digraph[succ][0].remove(entity)
if not digraph[succ][0]:
itinerary.add(succ)
return sorted_pile
And ... that's it! sorted_pile now obeys the back-to-front ordering you need to draw things correctly.
answered Jan 19 at 20:29
Dan UznanskiDan Uznanski
6,90021528
$endgroup$
The strategy is simple: we will figure out what things are in front of what other things, and then set the order based on that. The latter is called topological sorting, and it's a powerful tool, and a simple one too.
I present two methods, each suitable for a different set of assumptions about the set of entities we are sorting.
Sparse entities
In this method, the entities do not fill the map; it is in general not true that we can travel "upward" through adjacent entities to find all entities that any particular entity is in front of.
First, for each object, we must find the left and right extents of the entity. These are, using the layout in your image, $(x-y-h, x+w-y)$. We will store these two extents, and the corresponding object, in a list.
(this code is in Python; I don't recognize your programming language so I couldn't code in it)
entity_extents =
for e in tile_entities:
entity_extents.append(((e.x-e.y-e.h, e.x+e.w-e.y), e))
We'll sort these by the left end.
entity_extents.sort(key=lambda x: x[0][0])
Now, we must examine each entity in turn: we have to find things that it's actually in front of or behind. Since they're already sorted by the left end, we'll check it against things further to the left that we haven't gotten past. To do this, we'll keep a list of things that are to the left of whereever we hare, sorted by the right end. As we do this we'll drop things out of the list that are no longer useful, because their right end doesn't extend past the left end of the thing we're looking at.
digraph = {}
leftward_entities =
for e in entity_extents:
left_h = e[0][0]
for n,le in enumerate(leftward_entities):
if le[0][1] > left_h: # we've found one to the right of what we have, so that one and everything further gets to live.
del(leftward_entities[:n])
break
else:
leftward_entities.clear() # everything's to the left. Nothing remains.
Now we figure out, for each remaining leftward entity, whether it's in front of or behind our current entity. For this, we'll find the vertical location of the left end of our current entity, and the vertical location of the topmost portion of each leftward entity at the same horizontal location as the left end of the current entity.
e_node = (set(), set())
digraph[e[1]] = e_node
left_v = e[1].x + e[1].y + e[1].h
for le in leftward_entities:
l_node = digraph[le]
target_top_h = le[1].x - le[1].y
target_left_v = le[1].x + le[1].y + abs(left_h - target_top_h)
if target_left_v < left_v:
l_node[1].add(e[1])
e_node[0].add(l[1])
else:
l_node[0].add(e[1])
e_node[1].add(l[1])
And finally we need to insert the current entity into the leftwards, based on the right end:
right_h = e[0][1]
for n,le in enumerate(leftward_entities):
if le[0][1] > right_h:
leftward_entities.insert(n,e)
break
else:
leftward_entities.append(e)
From here, we proceed to topological sorting.
Dense objects
The more common setup, the grid is filled with entities. if an entity can be considered behind another, they are connected by a whole path of entities behind one another that are also adjacent.
The strategy is vastly different: we'll just fill in the grid with entities...
entity_grid = {}
for e in tile_entities:
for u in range(e.x, e.x + e.w): # not all the way though. we don't care about the middles of buildings.
entity_grid[(u, e.y)] = e
entity_grid[(u, e.y + e.h - 1)] = e
for v in range(e.y, e.y + e.h):
entity_grid[(e.x, v)] = e
entity_grid[(e.x + e.w - 1)] = e
...and then look around the outside of each entity for other entities.
digraph[e] = {}
for e in tile_entities:
e_node = (set(), set())
for u in range(e.x, e.x + e.w):
if (u, e.y-1) in entity_grid:
e_node[0].add(entity_grid[(u, e.y-1)])
if (u, e.y+e.h) in entity_grid:
e_node[1].add(entity_grid[(u, e.y+e.h)])
for v in range(e.y, e.y + e.h):
if (e.x-1, v) in entity_grid:
e_node[0].add(entity_grid[(e.x-1, v)])
if (e.x+e.w, v) in entity_grid:
e_node[1].add(entity_grid[(e.x+e.w, v)])
And now proceed with topological sorting.
Topological sorting
Having built our digraph, we can actually sort things.
Each node in the digraph has to know two things: which things precede it, and which things follow it. In this, I've arranged so that the predecessors of an element e are in the set digraph[e][0], and its successors are in digraph[e][1].
First things first, we need to find all the entries in the digraph that have no predecessors: these are the ones that are near the very back.
itinerary = set()
for entity, (predecessors, _) in digraph.items():
if not predecessors:
itinerary.add(entity)
Now, we add these to our final sequence one at a time, while cutting its connections with its successors. Every time we end up with a former successor that has no still-connected predecessors, we add it to the pile to examine.
sorted_pile =
while itinerary:
entity = itinerary.pop()
sorted_pile.append(entity)
successors = digraph[entity][1]
for succ in successors:
digraph[succ][0].remove(entity)
if not digraph[succ][0]:
itinerary.add(succ)
return sorted_pile
And ... that's it! sorted_pile now obeys the back-to-front ordering you need to draw things correctly.
answered Jan 19 at 20:29
Dan UznanskiDan Uznanski
6,90021528
answered Jan 19 at 20:29
Dan UznanskiDan Uznanski
6,90021528
answered Jan 19 at 20:29
Dan UznanskiDan Uznanski
6,90021528
answered Jan 19 at 20:29
Dan UznanskiDan Uznanski
6,90021528
6,90021528
$begingroup$
Would you mind to share your full source code? I'm absolutely clueless how to proceed tbh - you're approach is still not working for me. Thanks in advance :)
$endgroup$
– jonas00
Jan 27 at 20:34
add a comment |
$begingroup$
Would you mind to share your full source code? I'm absolutely clueless how to proceed tbh - you're approach is still not working for me. Thanks in advance :)
$endgroup$
– jonas00
Jan 27 at 20:34
$begingroup$
Would you mind to share your full source code? I'm absolutely clueless how to proceed tbh - you're approach is still not working for me. Thanks in advance :)
$endgroup$
– jonas00
Jan 27 at 20:34
$begingroup$
Would you mind to share your full source code? I'm absolutely clueless how to proceed tbh - you're approach is still not working for me. Thanks in advance :)
$endgroup$
– jonas00
Jan 27 at 20:34
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3079224%2fhow-to-layer-objects-geometry%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Game theory here is not about games devolloping, i think you can be answered but also would try stack overflow (if not mistaken about which site is for programming questions)
$endgroup$
– Daniel Moraes
Jan 19 at 10:57
$begingroup$
Oh this is a meaner one than I expected now that I think about it. I know it's not: location of front corner, location of back corner, location of center (consider a 1x1 in front of the backmost tile of a 1x4). You might get good results getting partial orderings by sweeping down diagonals and using a topological sort.
$endgroup$
– Dan Uznanski
Jan 19 at 11:17
$begingroup$
Thanks for your answer. To be honest, I don't really know how to install a topological sort. Would you be kind enough to post some kind of pseudo code or at least a formula? Many thanks in advance :) @DanUznanski
$endgroup$
– jonas00
Jan 19 at 11:19
$begingroup$
Oh, important question: are your objects densely packed? It occurs to me that the answer is usually yes (as it is in, say, ottd or SimCity or old xcom or civ2) but your data isn't. This is important because for densely packed objects, the generic method is very inefficient but there are greater efficiencies we can get from knowledge of the structure)
$endgroup$
– Dan Uznanski
Jan 19 at 11:55
$begingroup$
Oh ok. Hmhm yeah I would say there is a densely packed object-structure on my map. But we talk about maybe 100 objects not more. So efficieny is no important point in my case - I just need a working method :) @DanUznanski
$endgroup$
– jonas00
Jan 19 at 11:58